Cubic Formula Size Lower Bounds Based on Compositions with Majority
From MaRDI portal
(Redirected from Publication:5090412)
Recommendations
- A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints
- A stronger LP bound for formula size lower bounds via clique constraints
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- Average-case lower bounds for formula size
Cites work
- A method for obtaining more than quadratic effective lower estimates of complexity of schemes
- Average-case lower bounds for formula size
- Complexity and depth of formulas for symmetric Boolean functions
- Complexity of the realization of a linear function in the class of -circuits
- Formula lower bounds via the quantum method
- scientific article; zbMATH DE number 3162894 (Why is no real title available?)
- Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound
- Mining circuit lower bound proofs for meta-algorithms
- Probability Inequalities for Sums of Bounded Random Variables
- Short monotone formulae for the majority function
- Shrinkage of de Morgan formulae under restriction
- Small bias requires large formulas
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- The critical complexity of all (monotone) boolean functions and monotone graph properties
- The effect of random restrictions on formula size
- The Shrinkage Exponent of de Morgan Formulas is 2
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
Cited in
(4)
This page was built for publication: Cubic Formula Size Lower Bounds Based on Compositions with Majority
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090412)
