Consider you have two (possibly same) convex $1$-skeleton of a regular graph $A$ and $B$ in $m$-dimensions inscribed in a sphere with possibly exponential number of vertices in $n$-dimension with promise that either every vertex is same or every vertex is distinct (the polyhedra could still overlap). If $m<n$ we can assume they just live on a hyperplane with vertices on the sphere.
You have to decide with probability $>2/3$ whether $A$ and $B$ are same.
You do not have the polyhedron as explicit inputs since they could have exponentially large number of vertices.
You have an oracle access that you can use polynomially (in $n$) many number of times to get random samples of vertex coordinates and neighbor coordinates which are connected by a $1$-dimensional edge.
Would there be any way to decide at all with probability $>2/3$ that the two polyhedrons are distinct in polynomial in $n$ time?
Assume coordinates of polytopes have vertex coordinates from finitely many bounded integer values (say from $0$ to $c$).
I think the fact that I have convex $1$-skeleton of a regular graph seems to make that the only non-trivial configuration would be one is rotation of other.