SUNDAY, APRIL 21, 1996 - Location: Holiday Inn, South Plainfield, NJ09:00-09:10 Welcome - Eric Allender, DIMACS Organizer for Special Year on Logic and Algorithms 09:10-10:10 Toniann Pitassi, University of Pittsburgh Simplified Lower Bounds for Resolution 10:10-10:30 Coffee break 10:30-11:30 Steven Rudich, Carnegie Mellon University "Natural Proofs - A Survey, Part I." 11:30-12:00 Peter Clote, Ludwig-Maximilians Universit\" at M\"unchen (joint with A. Setzer) "A note on Degen's principle and odd charged graphs" 12:00-1:00 Lunch, provided by the conference organizers. 01:30-02:30 Daniel Leivant, Indiana University "Functions and Functionals Provable in Ramified Theories" 02:30-03:00 Sam Buss, University of California, San Diego "Designing Lower Bounds" 03:00-03:45 Coffee break 03:45-04:15 Ken Regan, SUNY Buffalo "Descriptive Complexity and the W Hierarchy." 04:15-04:45 Jin-Yi Cai "Constant Depth Circuits and the Lutz Hypothesis" 04:45-05:15 Soren Riis, Aarhus University "Hashing on AC^0 RAMs" 07:00-09:00 ReceptionMONDAY, APRIL 22, 1996 - DIMACS, CoRE Building, Rutgers Univ., Piscataway, NJ09:00-10:00 Russell Impagliazzo, University of California, San Diego "Algebra, Proofs and Algorithms" 10:00-10:30 Coffee break 10:30-11:30 Alexander A. Razborov, Stekloc Mathematical Institute "Proof Complexity in Algebraic Systems and Constant Depth Frege Proofs." 11:30-12:00 Steven Rudich, Carnegie Mellon University "Natural Proofs - A Survey, Part II." 12:00-01:00 Lunch, provided by the conference organizers. 01:30-02:30 Pavel Pudlak, Academy of Sciences of the Czech Republic "Monotone Circuits and Propositional Calculus." 02:30-03:00 Xudong Fu, University of Toronto "Lower Bounds on the Size of Cutting Planes Proofs for Modular Coloring Principles." 03:00-03:45 Coffee break 03:45-04:15 Fernando Ferreira, Faculldade de Ci\^encias, Lisbon "A Proof that LogSpace is not equal to NLin." 04:15-04:45 Barbara Kauffman, Carnegie Mellon University "Bounded Arithmetic: Comparion of Herbrand Analysis and the Witnessing Method." 04:45-05:15 Open Problems Session/Short talkTUESDAY, APRIL 23, 1996 - DIMACS, CoRE Building, Rutgers Univ., Piscataway, NJ09:00-10:00 Jan Krajicek, Academy of Sciences of the Czech Republic "Model Theory Related to Lengths of Proofs." 10:00-10:30 Coffee break 10:30-11:30 Gaisi Takeuti, University of Illinois, Urbana-Champaign "Incompleteness Theorems, Forcing and P=/=NP." 11:30-12:00 Dan Willard, SUNY Albany "Self-Justifying Axiom Systems, Their Reflection Principles and Possible Connections to NP." 12:00-1:00 Lunch, provided by conference organizers 01:30-02:00 Jeremy Avigad, University of Michigan/DIMACS "Plausibly Hard Tautologies?" 02:00-02:30 Paul Beame, University of Washington, Seattle TBA 02:30-03:00 Coffee break 03:00-03:30 Steven Bellantoni "Ramification and Feasibility." 03:30-04:00 Jan Johannsen, Universit\"at Erlangen-N\"urnberg "A Model-Theoretic Property of Sharply Bounded Formulae, with Some Applications" 04:00-04:30 Alessandra Carbone, Technische Universit\"at Wien "Proofs, Groups and Combinatorics"

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on November 2, 1998.