Shrinkage of de Morgan formulae under restriction

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

zbMATH Keywords

lower boundshrinkage exponentformula size complexity of Boolean functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30)

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

• Unnamed Item

This page was built for publication: Shrinkage of de Morgan formulae under restriction