Geometric Perspectives on Problems in Complexity Theory
summary
Shows that huge row/column pairings built from vectors of minors or sub‑Pfaffians reduce to a single M×M determinant/Pfaffian, with polynomial tests for membership; frames Valiant’s conjecture via determinantal complexity and orbit closures and gives DC(perm) > m^2/2 from an explicit vanishing polynomial; proves under a symmetry restriction that equivariant determinantal complexity of the permanent equals (2m choose m)−1, yielding an exponential lower bound; tools: algebraic geometry, representation theory, shifted partial derivatives and permutation‑group arguments.
AI-written summary · about