Semialgebraic proofs, IPS lower bounds, and the -conjecture: can a natural number be negative?
From MaRDI portal
Publication:6562829
Cites work
- scientific article; zbMATH DE number 5161489 (Why is no real title available?)
- scientific article; zbMATH DE number 3744549 (Why is no real title available?)
- scientific article; zbMATH DE number 3461412 (Why is no real title available?)
- scientific article; zbMATH DE number 3629255 (Why is no real title available?)
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 512977 (Why is no real title available?)
- scientific article; zbMATH DE number 527343 (Why is no real title available?)
- scientific article; zbMATH DE number 1916823 (Why is no real title available?)
- scientific article; zbMATH DE number 1390276 (Why is no real title available?)
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
- A lower bound for polynomial calculus with extension rule
- Adventures in monotone complexity and TFNP
- Algebraic proof systems over formulas.
- Anneaux preordonnes
- Approximability and proof complexity
- Arithmetic and Logic in Computer Systems
- Arithmetic circuits: a survey of recent results and open questions
- Characterizing propositional proofs as noncommutative formulas
- Circuit complexity, proof complexity, and polynomial identity testing. The ideal proof system
- Complexity of Null- and Positivstellensatz proofs
- Complexity of Positivstellensatz proofs for the knapsack
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Hypercontractivity, sum-of-squares proofs, and their applications
- Iterated lower bound formulas: a diagonalization-based approach to proof complexity
- Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Lower bounds for the polynomial calculus
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Mathematical problems for the next century
- Negation can be exponentially powerful
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- On defining integers and proving arithmetic circuit lower bounds
- On the bit complexity of sum-of-squares proofs
- On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
- On the ultimate complexity of factorials
- On the virtue of succinct proofs
- Polynomial size proofs of the propositional pigeonhole principle
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Resolution with counting: dag-like lower bounds and different moduli
- SOS is not obviously automatizable, even approximately
- Semialgebraic Proofs and Efficient Algorithm Design
- Semidefinite Optimization and Convex Algebraic Geometry
- Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
- Stable sets and polynomials
- The complexity of computing the permanent
- The cost of computing integers
- The relation between polynomial calculus, Sherali-Adams, and sum-of-squares proofs
- The relative efficiency of propositional proof systems
- The surprising power of constant depth algebraic proofs
- Unsolvable systems of equations and 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)
