default search action
DIMACS Workshop: Proof Complexity and Feasible Arithmetics 1996
- Paul Beame, Samuel R. Buss:
Proof Complexity and Feasible Arithmetics, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, April 21-24, 1996. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 39, DIMACS/AMS 1998, ISBN 978-0-8218-0577-0 - Jeremy Avigad:
Plausibly hard combinatorial tautologies. 1-12 - Paul Beame, Søren Riis:
More on the relative strength of counting principles. 13-35 - Stephen J. Bellantoni:
Ranking arithmetic proofs by implicit ramification. 37-57 - Samuel R. Buss:
Lower bounds on Nullstellensatz proofs via designs. 59-71 - Stephen Cook:
Relating the provable collapse of P to NC1 and the power of logical theories. 73-91 - Peter Clote, Anton Setzer:
On PHP st-connectivity, and odd charged graphs. 93-117 - Rodney G. Downey, Michael R. Fellows, Kenneth W. Regan:
Descriptive complexity and the W hierarchy. 119-134 - Xudong Fu:
Lower bounds on sizes of cutting plane proofs for modular coloring principles. 135-148 - Jan Johannsen:
Equational calculi and constant depth propositional proofs. 149-162 - Stasys Jukna:
Exponential lower bounds for semantic resolution. 163-172 - Barbara Kauffmann:
Bounded arithmetic: Comparison of Buss' witnessing method and Sieg's Herbrand analysis. 173-193 - Alexis Maciel, Toniann Pitassi:
Towards lower bounds for bounded-depth Frege proofs with modular connectives. 195-227 - François Pitt:
A quantifier-free theory based on a string algebra for NC1. 229-252 - Chris Pollett:
A propositional proof system for Ri2. 253-277 - Pavel Pudlák, Jirí Sgall:
Algebraic models of computation and interpolation for algebraic proof systems. 279-295 - Dan E. Willard:
Self-reflection principles and NP-hardness. 297-320
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.