Lower bounds for the polynomial calculus
DOI10.1007/S000370050013zbMATH Open1026.03043DBLPjournals/cc/Razborov98OpenAlexW2093396771WikidataQ56701136 ScholiaQ56701136MaRDI QIDQ1293358FDOQ1293358
Authors: Alexander Razborov 
Publication date: 7 December 2003
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s000370050013
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
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)
Cited In (47)
- Reflections on Proof Complexity and Counting Principles
- A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
- Title not available (Why is that?)
- Perfect matching in random graphs is as hard as Tseitin
- Title not available (Why is that?)
- Semialgebraic proofs, IPS lower bounds, and the \(\tau\)-conjecture: can a natural number be negative?
- Towards NP-P via proof complexity and search
- The Complexity of Propositional Proofs
- Graphs with large girth and chromatic number are hard for Nullstellensatz
- The surprising power of constant depth algebraic proofs
- Degree complexity for a modified pigeonhole principle
- 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
- Towards an understanding of polynomial calculus: new separations and lower bounds (extended abstract)
- 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?)
- Resolution lower bounds for perfect matching principles
- On the automatizability of polynomial calculus
- Lower bounds for polynomials of many variables
- Extended Nullstellensatz proof systems
- A generalized method for proving polynomial calculus degree lower bounds
- Complexity of Null- and Positivstellensatz proofs
- Lower bounds for a polynomial in terms of its coefficients
- Space Complexity in Polynomial Calculus
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Polynomial calculus for optimization
- Homogenization and the polynomial calculus
- Algebraic proof systems over formulas.
- A framework for space complexity in algebraic proof systems
- On the degree of ideal membership proofs from uniform families of polynomials over a finite field
- Optimality of size-degree tradeoffs for polynomial calculus
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Complexity of Positivstellensatz proofs for the knapsack
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
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)
