BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS
From MaRDI portal
Publication:5168421
DOI10.1142/S0129054113500378zbMath1360.68477OpenAlexW1974865967MaRDI QIDQ5168421
Publication date: 4 July 2014
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054113500378
Integer programming (90C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (1)
Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory
Cites Work
- A stronger LP bound for formula size lower bounds via clique constraints
- Improvements on Khrapchenko's theorem
- On convex complexity measures
- A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
- Tighter representations for set partitioning problems
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- The quantum adversary method and classical formula size power bounds
- Polynomial degree vs. quantum query complexity
- Complexity of the realization of a linear function in the class of \(\Pi\)-circuits
- Global Optimization with Polynomials and the Problem of Moments
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- A New Rank Technique for Formula Size Lower Bounds
- Cones of Matrices and Set-Functions and 0–1 Optimization
- The Shrinkage Exponent of de Morgan Formulas is 2
- Fractional Covers and Communication Complexity
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
This page was built for publication: BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS
