Lower Bound Results for Hard Problems Related to Finite Automata
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Shows ETH-based lower bounds for universality, inequivalence and intersection-nonemptiness on NFAs/DFAs by encoding SAT and 3-coloring into unary/bounded alphabets. Key tools are Chinese remainder theorem encodings and cycles of prime lengths so words a^z represent assignments; reductions produce NFAs with union/product constructions that mirror subset-construction blowup. Claims include NP-completeness already for unary alphabets and lower bounds that rule out algorithms significantly faster than the standard subset/product automaton constructions.
AI-written summary · about
chapters (20)
- 0:00Introduction
- 0:20Finite Automata
- 0:49Non universality
- 1:40Why
- 2:25Hardness
- 3:18Universality
- 4:15Lower Bounds
- 11:02Improving Lower Bounds
- 12:21Absalon
- 13:49Intersection
- 19:45Summary
- 20:33Sketch
- 20:50Periodicity
- 22:48Synchronization
- 24:10Jumping Fire
- 24:35Jumping Fire Automata
- 25:06Uniform Membership
- 25:56Universe Membership
- 27:02Conclusion
- 29:05Other examples
related talks
01h 32mInapproximability of Constraint Satisfaction Problems I
25mExponential separations using guarded extension variables
01h 01mComplexity and Algorithmic Game Theory I
20mTFNP Characterizations of Proof Systems and Monotone Circuits
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
19mA Formal Disproof of Hirsch Conjecture
01h 31mCircuits of Bounded Depth
34mTesting Intersectingness of Uniform Families or how Dana and I intersected