Ran Raz
My main research area is complexity
theory, with emphasize on proving lower bounds for computational models. More
specifically, I am interested in Boolean circuit complexity, arithmetic circuit
complexity, communication complexity, propositional proof theory, probabilistic
checkable proofs, quantum computation and communication, randomness and De-randomization.
Recent Publications
- Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size (Manuscript, 2003).
- On the Complexity of Matrix Product. SIAM Journal of Computing 32 (5) (2003) 1356-1369.
- Resolution Lower Bounds for the Weak Pigeonhole Principle. Journal of the Association for Computing Machinery (to appear).