The effect of random restrictions on formula size

DOI10.1002/rsa.3240040202zbMath0771.68065OpenAlexW1991702990MaRDI QIDQ4696224

Noam Nisan, Russell Impagliazzo

Publication date: 29 June 1993

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240040202

zbMATH Keywords

lower boundformula size complexity of Boolean functions

Mathematics Subject Classification ID

Related Items (17)

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 ⋮ A satisfiability algorithm and average-case hardness for formulas over the full binary basis ⋮ Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases ⋮ How Do Read-Once Formulae Shrink? ⋮ 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 ⋮ 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

This page was built for publication: The effect of random restrictions on formula size