Semialgebraic proofs, IPS lower bounds, and the -conjecture: can a natural number be negative?

DOI10.1137/20M1374523MaRDI QIDQ6562829FDOQ6562829

Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret

Publication date: 27 June 2024

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

proof complexityalgebraic circuit complexitysemialgebraic proofs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Cites Work

• Title not available (Why is that?)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• The complexity of computing the permanent
• Stable sets and polynomials
• A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Title not available (Why is that?)
• Semidefinite Optimization and Convex Algebraic Geometry
• Mathematical problems for the next century
• Negation can be exponentially powerful
• Anneaux preordonnes
• The relative efficiency of propositional proof systems
• Arithmetic Circuits: A survey of recent results and open questions
• Title not available (Why is that?)
• The cost of computing integers
• Title not available (Why is that?)
• Lower bounds for the polynomial calculus
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• Lower bounds for the polynomial calculus and the Gröbner basis algorithm
• Title not available (Why is that?)
• Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
• Polynomial size proofs of the propositional pigeonhole principle
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
• On defining integers and proving arithmetic circuit lower bounds
• Title not available (Why is that?)
• Hypercontractivity, sum-of-squares proofs, and their applications
• Algebraic proof systems over formulas.
• Characterizing Propositional Proofs as Noncommutative Formulas
• Adventures in monotone complexity and TFNP
• On the ultimate complexity of factorials
• Title not available (Why is that?)
• Complexity of Null- and Positivstellensatz proofs
• Unsolvable systems of equations and proof complexity
• Semialgebraic Proofs and Efficient Algorithm Design
• A lower bound for polynomial calculus with extension rule
• Complexity of Positivstellensatz proofs for the knapsack
• Approximability and proof complexity
• SOS Is Not Obviously Automatizable, Even Approximately
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Bit Complexity of Sum-of-Squares Proofs
• Title not available (Why is that?)
• Resolution with counting: dag-like lower bounds and different moduli
• Circuit Complexity, Proof Complexity, and Polynomial Identity Testing
• Title not available (Why is that?)
• Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
• On the virtue of succinct proofs
• The Surprising Power of Constant Depth Algebraic Proofs
• Arithmetic and Logic in Computer Systems
• Iterated lower bound formulas: a diagonalization-based approach to proof complexity

This page was built for publication: Semialgebraic proofs, IPS lower bounds, and the \(\tau\)-conjecture: can a natural number be negative?

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