Joint DIMACS-DIMATIA Workshop on Algebraic Methods and Arithmetic Circuits

June 2- 4, 1999
DIMACS Center, CoRE Building, Rutgers University, Piscataway, NJ

Principal Organizers:

• Eric Allender, Rutgers University, allender@cs.rutgers.edu
• Jan Krajicek, Czech Academy of Sciences, krajicek@math.cas.cz
• Pavel Pudlak, Czech Academy of Sciences, pudlak@matsrv.math.cas.cz
• Mike Saks, Rutgers University, saks@math.rutgers.edu

Workshop Program:

  
Wednesday, June 2, 1999       

 9:00 -  9:25	Registration/Breakfast

 9:25 -  9:30   Welcome and Greeting:
                Fred S. Roberts, DIMACS Director

 9:30 -  9:35	Welcoming Remarks (Allender, Krajicek, Pudlak, Saks)

 9:35 - 10:20	Amin Shokrollahi, Bell Labs (Lucent)
		How fast can we multiply matrices?

                Slide Presentation from Workshop

10:20 - 11:05	Amos Beimel, Harvard
		On Arithmetic Branching Programs

                Slide Presentation from Workshop

11:05 - 11:30	Coffee Break

11:30 - 12:15	Carsten Damm, Trier
		On the Complexity of Tensor Formulae

                Slide Presentation from Workshop


12:15 -  3:00	Lunch, informal discussions

 3:00 -  3:20	Eric Allender, Rutgers
		Counting classes and arithmetic circuits

 3:20 -  3:40	Samir Datta, Rutgers
		Closure Properties of #AC^0

 3:40 -  4:00	Andris Ambainis, Berkeley
		Non-closure Properties of #AC^0

 4:00 -  4:20	Coffee break

 4:20 -  4:50   Vince Grolmusz, Eotvos Univ. and Univ. of Chicago
		On circuits with modular gates


Thursday, June 3, 1999

 9:00 -  9:30	Breakfast

 9:30 - 10:15	Meera Sitharam, Univ. of Florida
		Algebraic proof degrees and permutation modules

10:15 - 11:00	Paul Beame, University of Washington
		Time-space tradeoffs 

11:00 - 11:30	Coffee Break

11:30 - 12:15	Pierre McKenzie, University of Montreal
		Algebraic circuits and polynomial replacement systems

                Slide Presentation from Workshop

12:15 -  3:00	Lunch, informal discussions

 3:00 -  3:30	Satyanarayana Lokam, Loyola (Chicago)
		On the Rigidity of Vandermonde Matrices

                Slide Presentation from Workshop

 3:30 -  4:00	Chrystopher Nehaniv, University of Hertfordshire
		Synthesis of Least-Depth Circuits for Aperiodic Computation

 3:00 -  4:20	Coffee break

 4:20 -  4:50	Pavel Pudlak, Czech Acedmy of Sciences
		On the Structure of Low-Rank Matrices


Friday, June 4, 1999

 8:30 -  9:00	Breakfast

 9:30 - 10:15	Amir Shpilka, Hebrew University
		Quadratic lower bounds for Depth-3 Arithmetic Formulae
                over Fields of Characteristic Zero.

10:15 - 11:00	Alan Woods, University of Western Australia
		The number of functions defined by formulas of a given size

11:00 - 11:30	Coffee Break

11:30 - 12:15	David Mix Barrington, University of Massachussetts
		Monotone Planar Circuits

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage