A stronger LP bound for formula size lower bounds via clique constraints

DOI10.1016/j.tcs.2012.02.005zbMath1280.68103OpenAlexW2149120558MaRDI QIDQ428879

Kenya Ueno

Publication date: 25 June 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.02.005

zbMATH Keywords

linear programmingstable set polytopeformula size lower boundmonotone self-dual Boolean function

Mathematics Subject Classification ID

Integer programming (90C10) Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory ⋮ BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improvements on Khrapchenko's theorem
• Geometric algorithms and combinatorial optimization
• Almost integral polyhedra related to certain combinatorial optimization problems
• Better lower bounds for monotone threshold formulas
• Decompositions of positive self-dual Boolean functions
• Minimum self-dual decompositions of positive dual-minor Boolean functions
• The quantum adversary method and classical formula size power bounds
• Complexity of the realization of a linear function in the class of \(\Pi\)-circuits
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
• Short monotone formulae for the majority function
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Two applications of information complexity
• A New Rank Technique for Formula Size Lower Bounds
• The Shrinkage Exponent of de Morgan Formulas is 2
• On the noise sensitivity of monotone functions
• Fractional Covers and Communication Complexity
• Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
• On the facial structure of set packing polyhedra
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Quantum lower bounds by quantum arguments
• Hardness amplification within NP