scientific article; zbMATH DE number 1114017

MaRDI QIDQ4375786zbMATH OpenFDO

Authors Samuel R. Buss

Publication date 24 June 1998

zbMATH Keywords

propositional logicdesignsNullstellensatz proof systemalgebraic identities in fieldshousesitting principleNullstellensatz lower bounds

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Classical propositional logic (03B05) Other designs, configurations (05B30) Complexity of proofs (03F20)

Recommendations

• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• Complexity of Null- and Positivstellensatz proofs
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting

Cited in

(12)

• Linear gaps between degrees for the polynomial calculus modulo distinct primes
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• Propositional proofs and reductions between NP search problems
• Limitations of algebraic approaches to graph isomorphism testing
• Nullstellensatz size-degree trade-offs from reversible pebbling
• Zero-One Designs Produce Small Hard SAT Instances
• Nullstellensatz size-degree trade-offs from reversible pebbling
• On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
• A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
• Design Strategies for ARX with Provable Bounds: Sparx and LAX
• Lov\'asz Meets Weisfeiler and Leman
• Extended Nullstellensatz proof systems

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 Q4375786)