skip to main content

Theory Group Meeting

Tuesday, April 3, 2018
4:00pm to 5:00pm
Add to Cal
Annenberg 322
Graph Rigidity and Polynomial Identity Testing
Rohit Gurjar,

ABSTRACT:  Given a graph, one can embed its vertices in space and view its edges as solid bars joined at vertices. If this obtained framework is rigid, i.e., its shape cannot be modified, then the graph is called rigid. The algorithmic questions here are to test if a given graph is rigid and if yes,  construct a rigid embedding. The answer depends on the dimension of the underlying space. The problem has a randomized polynomial time algorithm via the Polynomial Identity Testing (PIT) algorithm (for every dimension). For dimension 2, there is also a deterministic algorithm, which is combinatorial. We want to derandomize the algorithm based on PIT.

For more information, please contact Bonnie Leung by email at [email protected].