"NSF Science and Technology Center in Discrete Mathematics and Theoretical Computer Science, a consortium of Rutgers University, Princeton University, AT&T Labs, Bell Labs, and Bellcore".

Papers from the proceedings of the DIMACS Workshop on Feasible Arithmetics and Length of Proofs, held on April 21-24, 1996 at Rutgers, New Jersey.

Includes bibliographical references.

Plausibly hard combinatorial tautologies / Jeremy Avigad -- More on the relative strength of counting principles / Paul Beame and Soren Riis -- Ranking arithmetic proofs by implicit ramification / Stephen J. Bellantoni -- Lower bounds on Nullstellensatz proofs via designs / Samuel R. Buss -- Relating the provable collapse of P to NC1 and the power of logical theories / Stephen Cook -- On PHP st-connectivity, and odd charged graphs / Peter Clote and Anton Setzer -- Descriptive complexity and the W hierarchy / Rodney G. Downey, Michael R. Fellows, and Kenneth W. Regan -- Lower bounds on the sizes of cutting plane proofs for modular coloring principles / Xudong Fu -- Equational calculi and constant depth propositional proofs / Jan Johannsen -- Exponential lower bounds for semantic resolution / Stasys Jukna -- Bounded arithmetic : comparison of Buss' witnessing method and Sieg's Herbrand analysis / Barbara Kauffmann -- Towards lower bounds for bounded-depth Frege proofs with modular connectives / Alexis Maciel and Toniann Pitassi -- A quantifier-free theory based on a string algebra for NC1 / François Pitt -- A propositional proof system for Ri2 / Chris Pollett --Algebraic models of computation and interpolation for algebraic proof systems / Pavel Pudlák and JiŘí Sgall -- Self-reflection principles and NP-hardness / Dan E. Willard.