ACM SIGLOG News · 2016 · 13 citations · 35 references
ComputingComputer ScienceMathematicsAlgebraCircuit TheoryTheory Of ComputationCircuit ComplexityComplexity TheoryComputational ComplexityProof ComplexityProof TheoryTheorem ProvingCircuit Lower BoundsDerandomizationIdentity TestingLower BoundsPolynomial Identity TestingProof Size Lower BoundsProof SystemsTautologies
We survey recent progress in the proof complexity of strong proof systems and its connection to algebraic circuit complexity, showing how the synergy between the two gives rise to new approaches to fundamental open questions, solutions to old problems, and new directions of research. In particular, we focus on tight connections between proof complexity lower bounds (namely, lower bounds on the size of proofs of certain tautologies), algebraic circuit lower bounds, and the Polynomial Identity Testing problem from derandomization theory.
35
The complexity of computing the permanent
Leslie G. Valiant · Theoretical Computer Science · 1979 · 2.8K citations
The intractability of resolution
Armin Haken · Theoretical Computer Science · 1985 · 829 citations
The relative efficiency of propositional proof systems
Stephen Cook, Robert A. Reckhow · Journal of Symbolic Logic · 1979 · 827 citations
Completeness classes in algebra
Leslie G. Valiant · 1979 · 487 citations · Full text