15. Mathematical Aspects of Computer Science

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