On the contrary, in the field of Bounded Arithmetic it has become customary to show conditional independence results via a powerful "witnessing" technique which allows us to reduce the statement of interest to some well-studied hypothesis in pure Complexity Theory.
In this talk we survey recent research (work in progress) on developing an analogue of this witnessing technique for propositional proofs (which are about the same as proofs of $\Delta_1^b$-formulae in Bounded Arithmetic) and thus reduce questions about the complexity of propositional proofs to purely complexity-theoretic assumptions. We present both the general framework (interpolation theorems, complexity of disjoint NP-pairs) and concrete results already obtained in this way.
About the Speaker:
Alexander Alexandrovich Razborov is widely recognized as a leading figure in mathematics and computer science. His work presenting superpolynomial lower bounds on the size required to compute certain functions on monotone or constant-depth circuits has had a profound influence on recent progress in complexity theory; for this work he was awarded the Nevanlinna prize of the International Mathematical Union in 1990.
A. A. Razborov did his undergraduate work at Moscow University, in the Department of Mechanics and Mathematics. While there, he studied combinatorial group theory under S. I. Adian. He completed his undergraduate studies in 1985 and in the same year became a graduate student at the Steklov Mathematical Institute, Moscow. In 1987 he finished this course, defended his PhD thesis ("On systems of equations in free groups") and was hired to the Steklov Mathematical Institute. In 1991 he defended his doctoral thesis ("Lower Bounds in the Boolean Complexity").
In 1993 A. A. Razborov was elected to the Academia Europea. At present he is a leading researcher of the Steklov Institute. ----------------------------------------------------------------------------- The final speaker in the Distinguished Lecturer Series of the DIMACS Special Year on Logic and Algorithms is: Vaughn Pratt (Stanford University), Tuesday, July 23
For additional information about the DIMACS special year, please see the following web site:
http://dimacs.rutgers.edu/archive/SpecialYears/1995_1996/ ------------------------------------------------------------------------------ The speaker is being hosted by Ann Yasuhara (yasuhara@cs.rutgers.edu).
This talk is scheduled in conjunction with the Rutgers Department of Computer Science Special Colloquium Series. For more information about DCS colloquia, please see the following web site:
http://athos.rutgers.edu/pub/colloquia/
or contact Sven Dickinson (Colloquium Committee Chair) at x5-0021, x5-6154 or at sven@kiva.rutgers.edu.