Symmetric Formulas for Products of Permutations
summary
Proves that the permutation-matrix product decision problem PMM_{k,n} requires size n^{Ω(log k)} for formulas invariant under the shifted-diagonal Sn^{k-1}, matching the known divide-and-conquer upper bound up to constants. Argument builds a tight size–depth tradeoff, lifts symmetry to a left–right G-plus action, analyzes stabilizers using the orbit–stabilizer theorem and Goursat's lemma on An^k × An^k, and converts subgroup index lower bounds into formula-size lower bounds.
AI-written summary · about
chapters (6)
- 0:00Computational model
- 1:30Symmetry in functions
- 3:12Invariant formula complexity
- 6:15Permutation matrix problem
- 9:29Symmetry and lower bounds
- 12:49Proof strategy
related talks
01h 31mCircuits of Bounded Depth
01h 02mFine-Grained Counting Complexity I
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
01h 02mFine-Grained Counting Complexity II
30mParameterized Inapproximability of Max k-Subset Intersection under ETH
26mLower Bounds on the Running Time for Scheduling and Packing Problems
01h 00mCorrespondence Colouring of Random Graphs
31mConstructive Algorithm for Matroid Pathwidth