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

DOI10.1016/J.TCS.2012.02.005zbMATH Open1280.68103OpenAlexW2149120558MaRDI QIDQ428879FDOQ428879

Authors 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

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

Recommendations

• A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints
• Breaking the rectangle bound barrier against formula size lower bounds
• Breaking the rectangle bound barrier against formula size lower bounds
• A New Rank Technique for Formula Size Lower Bounds
• Higher lower bounds on monotone size

Cites work

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

Cited in

(7)

• Breaking the rectangle bound barrier against formula size lower bounds
• A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints
• A New Rank Technique for Formula Size Lower Bounds
• A note on the quasi-additive bound for Boolean functions
• Exploring the limits of subadditive approaches: parallels between optimization and complexity theory
• Lower Bounds for Width-Restricted Clause Learning on Small Width Formulas
• Breaking the rectangle bound barrier against formula size lower bounds

This page was built for publication: A stronger LP bound for formula size lower bounds via clique constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q428879)