Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus

DOI10.1007/s00493-002-0007-7zbMath1027.03043OpenAlexW2611922447WikidataQ101130844 ScholiaQ101130844MaRDI QIDQ1416118

Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao

Publication date: 14 December 2003

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-002-0007-7

zbMATH Keywords

combinatoricsmatrix

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (4)

Resolution lower bounds for perfect matching principles ⋮ An Introduction to Lower Bounds on Resolution Proof Systems ⋮ Parameterized Bounded-Depth Frege Is Not Optimal ⋮ Unnamed Item

This page was built for publication: Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus