| Title | : | Complexity of Geometric Constraint Systems |
| Speaker | : | Meera Sitharam (Professor of Computer Science and Affiliate Professor of Mathematics, University of Florida) |
| Details | : | Mon, Feb 6, 2023 4:00 PM, @ Aryabhatta Hall |
| Abstract | : | The talk will consist of two parts, both on graphs underlying geometric constraint systems over discrete sets of primitive geometries that underlie diverse application domains from soft matter modeling, kinematics, matrix completion and machine learning. PART I: We settle a decade-old conjecture and completely characterize graphs G and their non-edges f such that across all 3-dimensional Euclidean realizations of a given G-linkage, f attains lengths in a single interval. More precisely, given any assignment of (Euclidean) edge-lengths for G, f attains a single interval of length values across all 3-dimensional point configurations for which the pairwise distances agree with the given edge lengths. Although related to the minor-closed class of so-called 3-flattenable graphs, this class is not minor closed, has no obvious well quasi-ordering, and there are infinitely many minimal graphs-nonedge pairs - w.r.t. edge contractions - in the complement class. Our characterization overcomes these obstacles, is based on the 2 forbidden minors of the class of 3-flattenable graphs, and contributes to the theory of Cayley configurations used for analyzing distance-constrained configuration spaces in a range of application domains. Based on this result, generalizations to higher dimensions and efficient algorithmic characterizations will be discussed. PART II: We discuss 3 problems that connect the 150 year old Maxwellian quest to combinatorially characterize graph rigidity, to derandomization of determinantal identity testing, and parametrized complexity of (geometric constraint) graph decomposition. |