Connections Between Hardness and Randomness in the Algebraic Setting
summary
Shows that derandomizing low-formal-degree PIT is essentially equivalent to proving algebraic circuit lower bounds: a polynomial-size, low-degree algebraic circuit lower bound gives a deterministic PIT algorithm, and conversely a deterministic PIT in P yields comparable lower bounds. Proof ingredients include Schwartz–Zippel randomness, multilinear extension of boolean functions, the permanent’s permanent self-reduction plus Valiant/Toda completeness, and reductions giving nontrivial deterministic or nondeterministic algorithms; recent work extends the connection to finite fields and to branching-program equivalence.
AI-written summary · about
chapters (4)
related talks
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
23mTowards General and Tight Hardness Results for Graph Problems
44mAlgorithmic Pirogov-Sinai Theory
24mVerifying Almost-Sure Termination for Randomized Distributed Algorithms
33mGeometry of Secure Computation
01h 03mBeyond Boolean Circuits in Garbled Circuits
31mParameterized Verification of Systems with Precise (0,1)-Counter Abstraction
10mQuery, Communication and Discrepancy