scientific article; zbMATH DE number 2174386
From MaRDI portal
Publication:4681889
Recommendations
- Lower bounds for the polynomial calculus
- Random CNF's are hard for the polynomial calculus
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Towards an understanding of polynomial calculus: new separations and lower bounds (extended abstract)
Cited in
(30)- Lower bounds for the polynomial calculus
- On the automatizability of polynomial calculus
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Another look at degree lower bounds for polynomial calculus
- A framework for space complexity in algebraic proof systems
- Space complexity in polynomial calculus
- Towards NP-P via proof complexity and search
- Satisfiability, branch-width and Tseitin tautologies
- Special issue in memory of Misha Alekhnovich. Foreword
- Lower bounds for k-DNF resolution on random 3-CNFs
- scientific article; zbMATH DE number 2068058 (Why is no real title available?)
- scientific article; zbMATH DE number 6829271 (Why is no real title available?)
- A generalized method for proving polynomial calculus degree lower bounds
- Proof Complexity Meets Algebra
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- scientific article; zbMATH DE number 7561756 (Why is no real title available?)
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Lower bounds for a polynomial in terms of its coefficients
- Sharp Effective Finite-Field Nullstellensatz
- Propositional proof complexity
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Perfect matching in random graphs is as hard as Tseitin
- Graphs with large girth and chromatic number are hard for Nullstellensatz
- Sufficient condition for polynomial solvability of random 3-CNF formulas
- Lower bounds for polynomials of many variables
- Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs
- A generalized method for proving polynomial calculus degree lower bounds
- Near-optimal lower bounds on quantifier depth and Weisfeiler-Leman refinement steps
- Searching for falsified clause in random ( n)-CNFs is hard for randomized communication
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4681889)
