DIMACS Workshop on Feasible Arithmetics and Length of Proofs: Program

SUNDAY, APRIL 21, 1996 - Location: Holiday Inn, 
			 South Plainfield, NJ

09: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   Reception



MONDAY, APRIL 22, 1996 - DIMACS, CoRE Building, Rutgers Univ., 
           	         Piscataway, NJ

09: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 talk


TUESDAY, APRIL 23, 1996 - DIMACS, CoRE Building, Rutgers Univ., 
		          Piscataway, NJ

09: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