scientific article; zbMATH DE number 1114017

zbMATH Open0890.03029MaRDI QIDQ4375786FDOQ4375786

Samuel R. Buss

Publication date: 24 June 1998

Title of this publication is not available (Why is that?)

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

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)

Cited In (12)

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