Concepedia

Complexity of Positivstellensatz proofs for the knapsack

D. Grigoriev

Computational Complexity · 2001 · 105 citations · 8 references

DOIFull text

Open access

Concepts

References

8

Real algebraic geometry

Choice Reviews Online · 2014 · 1.3K citations

, , +12

Cones of Matrices and Set-Functions and 0–1 Optimization

László Lovász, Alexander Schrijver · SIAM Journal on Optimization · 1991 · 1K citations

, , +17

Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity

Dima Grigoriev · Theoretical Computer Science · 2001 · 210 citations

, , +4

Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs

Paul Beame, Russell Impagliazzo, Jan Krajı́ček et al. · Proceedings of the London Mathematical Society · 1996 · 165 citations

, , +10

Lower bounds for the polynomial calculus

Alexander Razborov · Computational Complexity · 1998 · 160 citations

, , +8