Pages that link to "Item:Q1293358"

The following pages link to Lower bounds for the polynomial calculus (Q1293358):

Displaying 40 items.

• Towards NP-P via proof complexity and search (Q408544) (← links)
• Lower bounds for a polynomial in terms of its coefficients (Q604214) (← links)
• Algebraic proofs over noncommutative formulas (Q642520) (← links)
• Lower bounds for polynomials of many variables (Q680071) (← links)
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting (Q1377580) (← links)
• Algebraic proof systems over formulas. (Q1401356) (← links)
• Degree complexity for a modified pigeonhole principle (Q1407601) (← links)
• Homogenization and the polynomial calculus (Q1430569) (← links)
• Resolution lower bounds for perfect matching principles (Q1881260) (← links)
• On the automatizability of polynomial calculus (Q1959382) (← links)
• Lower bounds for the polynomial calculus and the Gröbner basis algorithm (Q1961057) (← links)
• On the complexity of Hilbert refutations for partition (Q2252121) (← links)
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution (Q2255289) (← links)
• Another look at degree lower bounds for polynomial calculus (Q2333803) (← links)
• A framework for space complexity in algebraic proof systems (Q2796410) (← links)
• Space Complexity in Polynomial Calculus (Q2944568) (← links)
• A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems (Q2944868) (← links)
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs (Q2944908) (← links)
• On the correspondence between arithmetic theories and propositional proof systems – a survey (Q3619867) (← links)
• (Q4464663) (← links)
• Randomized feasible interpolation and monotone circuits with a local oracle (Q4562441) (← links)
• Lower bounds for discriminants of polynomials (Q4595094) (← links)
• A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds (Q4601843) (← links)
• Reflections on Proof Complexity and Counting Principles (Q5027248) (← links)
• (Q5028363) (← links)
• (Q5092479) (← links)
• Narrow Proofs May Be Maximally Long (Q5277920) (← links)
• The Complexity of Propositional Proofs (Q5444711) (← links)
• Proof Complexity of Non-classical Logics (Q5894972) (← links)
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity (Q5941296) (← links)
• Linear gaps between degrees for the polynomial calculus modulo distinct primes (Q5943090) (← links)
• Complexity of Positivstellensatz proofs for the knapsack (Q5957725) (← links)
• Complexity of Null- and Positivstellensatz proofs (Q5957910) (← links)
• Propositional proof complexity (Q6064569) (← links)
• Linear gaps between degrees for the polynomial calculus modulo distinct primes (Q6483597) (← links)
• Perfect matching in random graphs is as hard as Tseitin (Q6562700) (← links)
• Semialgebraic proofs, IPS lower bounds, and the \(\tau\)-conjecture: can a natural number be negative? (Q6562829) (← links)
• Graphs with large girth and chromatic number are hard for Nullstellensatz (Q6573006) (← links)
• Extended Nullstellensatz proof systems (Q6621298) (← links)
• Polynomial calculus for optimization (Q6665696) (← links)