Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory

DOI10.4036/iis.2015.L.03zbMath1478.68102OpenAlexW2184055362MaRDI QIDQ5135262

Kenya Ueno

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

zbMATH Keywords

linear programminginteger programmingformula complexity

Mathematics Subject Classification ID

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

This page was built for publication: Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory