How to fool people to work on circuit lower bounds
I will present two families of mathematical problems that are very
simple to describe, that seem natural to study from geometric,
algebraic or combinatorial points of view, and are seemingly unrelated
to theoretical computer science, and whose solution would give
exceptionally strong results in theoretical computer science; namely,
super-polynomial lower bounds for the size of general arithmetic
circuits and formulas.
More specifically, I will discuss ‘elusive functions and lower bounds
for arithmetic circuits’ – an approach to prove exponential lower
bounds for circuit size; and ‘tensor-rank and lower bounds for
arithmetic formulas’ – an approach to prove super-polynomial lower
bounds for formula size.
Speaker Details
Ran Raz is a Professor of Mathematics and Computer Science at the Weizmann Institute of Science. He received his B.Sc in mathematics and physics and his PhD in mathematics from the Hebrew University, and after a short postdoc at Princeton University joint the Weizmann Institute.
His main research area is complexity theory, with emphasis on proving lower bounds for computational models. More specifically, he is interested in Boolean and arithmetic circuit complexity, communication complexity, propositional proof theory, probabilistically checkable proofs, quantum computation and communication, and randomness and derandomization.
He was a member at the Institute for Advanced Study (2000-2001, and fall 2002) and a visiting researcher at Microsoft Research Redmond (spring 2006). He is currently visiting Microsoft Research New England (July-December 2009).
- Date:
- Speakers:
- Ran Raz
- Affiliation:
- Weizmann Institute
-
-
Jeff Running
-
