Cubic Formula Size Lower Bounds Based on Compositions with Majority

DOI10.4230/LIPIcs.ITCS.2019.35OpenAlexW2913244533MaRDI QIDQ5090412

Nuñez Adrian Trejo, Avishay Tal, Anna Gál

Publication date: 18 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.35

zbMATH Keywords

compositionrandom restrictionsKRW conjectureformula lower bounds

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Quantified Derandomization: How to Find Water in the Ocean

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity and depth of formulas for symmetric Boolean functions
• A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• Mining circuit lower bound proofs for meta-algorithms
• Complexity of the realization of a linear function in the class of \(\Pi\)-circuits
• Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
• Short monotone formulae for the majority function
• The critical complexity of all (monotone) boolean functions and monotone graph properties
• The Shrinkage Exponent of de Morgan Formulas is 2
• The effect of random restrictions on formula size
• Shrinkage of de Morgan formulae under restriction
• Formula lower bounds via the quantum method
• Probability Inequalities for Sums of Bounded Random Variables
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• Average-case lower bounds for formula size

This page was built for publication: Cubic Formula Size Lower Bounds Based on Compositions with Majority