Theory Group Meeting

Tuesday April 3, 2018 4:00 PM

Graph Rigidity and Polynomial Identity Testing

Speaker: Rohit Gurjar
Location: Annenberg 322

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.

Contact: Bonnie Leung