On the Critical Point Method and Deciding Connectivity Queries in Real Algebraic Sets
summary
Algorithms use critical point method and polar varieties to reduce connectivity queries to solving explicit Lagrange/determinantal systems and building a roadmap via polar varieties that meets every connected component. Complexity is singly exponential in the number of variables with previous practical exponents near ~55 but new analyses and regularity hypotheses cut the hidden constants. An exact computation implementation based on FGb-style Gröbner tools and tailored algebraic routines is built and tested and solves typical instances up to about 6–8 variables much faster than worst case.
AI-written summary · about
chapters (6)
- 0:00Start
- 37:44Polar varieties and homotopy techniques
- 42:02Summary
- 42:56Example: torus
- 47:30Complexity results for roadmaps
- 56:57First implementation
related talks
30mDetermination Problems for Orbit Closures and Matrix Groups
18mOn the Verification of a Subgraph Construction Algorithm
01h 00mAverage-case Complexity for Polynomials, and All That
01h 04mFrontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems
31mAnswering FAQs in CSPs, PGMs, Databases, Logic and Matrix Operations
47mNatural Proofs in Algebraic Circuit Complexity
01h 07mWhere the Hard Things Are
01h 22mTutorial 5: The GCT Chasm II