Complexity theory and efficient algorithms. Randomized, distributed, online and approximation algorithms. Formal languages, computational learning and mathematical machines. Cryptography. Semantics and verification of programs.
Symbolic computation. Quantum computing. Computational geometry, bioinformatics, computer vision.
INVITED SPEAKERS
Manindra Agrawal
Indian Institute of Technology Kanpur, Kanpur, India
Determinant versus permanent
Wednesday, August 30, 16:00-16:45
Jon M. Kleinberg
Cornell University, Ithaca, USA
Complex networks and decentralized search algorithms
Tuesday, August 29, 15:00-15:45
Omer Reingold
Weizmann Institute of Science, Rehovot, Israel
On expander graphs and connectivity in small space
Saturday, August 26, 16:00-16:45
Tim Roughgarden
Stanford University, Stanford, USA
Potential functions and the inefficiency of equilibria
Tuesday, August 29, 16:00-16:45
Ronitt Rubinfeld
Massachusetts Institute of Technology, Cambridge, USA
Sublinear time algorithms
Wednesday, August 30, 17:00-17:45
Alexander Semenovich Holevo
Steklov Mathematical Institute, Moscow, Russia
The additivity problem in quantum information theory
Tuesday, August 29, 17:00-17:45
Luca Trevisan
University of California, Berkeley, USA
Pseudorandomness and combinatorial constructions
Saturday, August 26, 15:00-15:45