Shrinkage of de Morgan formulae under restriction
From MaRDI portal
Publication:4696225
DOI10.1002/rsa.3240040203zbMath0771.68067OpenAlexW2129059686MaRDI QIDQ4696225
Uri Zwick, Michael S. Paterson
Publication date: 29 June 1993
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/60867/6/WRAP_cs-rr-171.pdf
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (19)
Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ An improved deterministic \#SAT algorithm for small De Morgan formulas ⋮ On the shrinkage exponent for read-once formulae ⋮ Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases ⋮ How Do Read-Once Formulae Shrink? ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation ⋮ Fourier concentration from shrinkage ⋮ Natural proofs ⋮ Negation-limited formulas ⋮ Cubic Formula Size Lower Bounds Based on Compositions with Majority ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Mining circuit lower bound proofs for meta-algorithms
Cites Work
This page was built for publication: Shrinkage of de Morgan formulae under restriction
