scientific article; zbMATH DE number 1559594

MaRDI QIDQ4527043zbMATH OpenFDO

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

Publication date 1 March 2001

zbMATH Keywords

read-once branching programs

Mathematics Subject Classification ID

Searching and sorting (68P10)

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)

• Space bounds for resolution
• 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

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)