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

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

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)

Cites Work

• Geometric algorithms and combinatorial optimization
• Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• On the facial structure of set packing polyhedra
• Applications of matrix methods to the theory of lower bounds in computational complexity
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Almost integral polyhedra related to certain combinatorial optimization problems
• Short monotone formulae for the majority function
• Two applications of information complexity
• Fractional Covers and Communication Complexity
• Title not available (Why is that?)
• The Shrinkage Exponent of de Morgan Formulas is 2
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum lower bounds by quantum arguments
• 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
• A New Rank Technique for Formula Size Lower Bounds
• On the noise sensitivity of monotone functions
• Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
• Hardness amplification within NP
• Improvements on Khrapchenko's theorem

Cited In (6)

• Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory
• BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS
• Breaking the rectangle bound barrier against formula size lower bounds
• Lower Bounds for Width-Restricted Clause Learning on Small Width Formulas
• A New Rank Technique for Formula Size Lower Bounds
• A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints

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)