lower boundBoolean functiondegreepigeonhole principle[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Gr%EF%BF%BD%EF%BF%BDbner+proofs&go=Go Gr��bner proofs]polynomial calculus proofs
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Mechanization of proofs and logical operations (03B35) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)
Recommendations
- scientific article; zbMATH DE number 2174386
- Lower bound functions for polynomials
- A lower bound for polynomial calculus with extension rule
- Another look at degree lower bounds for polynomial calculus
- Lower bounds for polynomials of many variables
- A generalized method for proving polynomial calculus degree lower bounds
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- scientific article; zbMATH DE number 3846868
- Lower bounds for a polynomial in terms of its coefficients
- Lower bounds for polynomial evaluation and interpolation problems
Cited in
(47)- Complexity of Positivstellensatz proofs for the knapsack
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
- Reflections on Proof Complexity and Counting Principles
- scientific article; zbMATH DE number 2174386 (Why is no real title available?)
- Perfect matching in random graphs is as hard as Tseitin
- scientific article; zbMATH DE number 7561756 (Why is no real title available?)
- Towards NP-P via proof complexity and search
- Semialgebraic proofs, IPS lower bounds, and the \(\tau\)-conjecture: can a natural number be negative?
- The Complexity of Propositional Proofs
- Graphs with large girth and chromatic number are hard for Nullstellensatz
- Degree complexity for a modified pigeonhole principle
- The surprising power of constant depth algebraic proofs
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- On the complexity of Hilbert refutations for partition
- Lower bounds for discriminants of polynomials
- Proof complexity of non-classical logics
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Towards an understanding of polynomial calculus: new separations and lower bounds (extended abstract)
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- scientific article; zbMATH DE number 2068058 (Why is no real title available?)
- Resolution lower bounds for perfect matching principles
- On the automatizability of polynomial calculus
- Lower bounds for polynomials of many variables
- Lower bounds for a polynomial in terms of its coefficients
- Extended Nullstellensatz proof systems
- A generalized method for proving polynomial calculus degree lower bounds
- Complexity of Null- and Positivstellensatz proofs
- Space Complexity in Polynomial Calculus
- scientific article; zbMATH DE number 1670882 (Why is no real title available?)
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Another look at degree lower bounds for polynomial calculus
- Propositional proof complexity
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- Randomized feasible interpolation and monotone circuits with a local oracle
- Algebraic proofs over noncommutative formulas
- Algebraic proofs over noncommutative formulas
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Narrow proofs may be maximally long
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- Polynomial calculus for optimization
- Homogenization and the polynomial calculus
- Algebraic proof systems over formulas.
- A framework for space complexity in algebraic proof systems
- Optimality of size-degree tradeoffs for polynomial calculus
- On the degree of ideal membership proofs from uniform families of polynomials over a finite field
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
This page was built for publication: Lower bounds for the polynomial calculus
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1293358)
