Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory
From MaRDI portal
Publication:5135262
DOI10.4036/iis.2015.L.03zbMath1478.68102OpenAlexW2184055362MaRDI QIDQ5135262
Publication date: 19 November 2020
Published in: Interdisciplinary Information Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4036/iis.2015.l.03
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A stronger LP bound for formula size lower bounds via clique constraints
- Boolean function complexity. Advances and frontiers.
- Improvements on Khrapchenko's theorem
- On convex complexity measures
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Geometric algorithms and combinatorial optimization
- A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
- Better lower bounds for monotone threshold formulas
- Tighter representations for set partitioning problems
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Subadditive approaches in integer programming
- 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
- Short monotone formulae for the majority function
- 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 Strong Dual for Conic Mixed-Integer Programs
- BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS
- Explicit lower bound of 4.5n - o(n) for boolena circuits
- Paths, Trees, and Flowers
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- Natural proofs
