scientific article; zbMATH DE number 1559594
From MaRDI portal
Publication:4527043
zbMATH Open0963.68048MaRDI QIDQ4527043FDOQ4527043
Authors: A. Wigderson, Andrew Chi-Chih Yao, Alexander Razborov 
Publication date: 1 March 2001
Title of this publication is not available (Why is that?)
Recommendations
- Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
- Resolution lower bounds for the weak pigeonhole principle
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Resolution lower bounds for the weak functional pigeonhole principle.
- scientific article; zbMATH DE number 1223618
Cited In (7)
- Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
- Resolution lower bounds for the weak functional pigeonhole principle.
- On the read-once property of branching programs and CNFs of bounded treewidth
- Width versus size in resolution proofs
- A new proof of the weak pigeonhole principle
- No small nondeterministic read-once branching programs for CNFs of bounded treewidth
- Space bounds for resolution
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4527043)
