DOCUMENTA MATHEMATICA

Extra Volume ICM 1998

Invited Forty-Five Minute Lectures


Section: 14. Mathematical Aspects of Computer Science

Contents: dvi.gz, dvi, ps.gz.


Miklós Ajtai
Worst-Case Complexity, 
Average-Case Complexity and Lattice Problems
Doc.Math.J.DMV Extra Volume ICM III (1998) 421-428
Abstract 2 k, dvi.gz 16 k, dvi 37 k, ps.gz 57 k. 

Joan Feigenbaum
Games, Complexity Classes, 
and Approximation Algorithms
Doc.Math.J.DMV Extra Volume ICM III (1998) 429-439
Abstract 2 k, dvi.gz 21 k, dvi 49 k, ps.gz 61 k. 

Johan Håstad
On Approximating NP-Hard Optimization Problems
Doc.Math.J.DMV Extra Volume ICM III (1998) 441-450
Abstract 2 k, dvi.gz 21 k, dvi 47 k, ps.gz 75 k. 

Toniann Pitassi
Unsolvable Systems of Equations and Proof Complexity
Doc.Math.J.DMV Extra Volume ICM III (1998) 451-460
Abstract 2 k, dvi.gz 20 k, dvi 46 k, ps.gz 74 k. 

Madhu Sudan
Probabilistic Verification of Proofs
Doc.Math.J.DMV Extra Volume ICM III (1998) 461-470
Abstract 2 k, dvi.gz 23 k, dvi 52 k, ps.gz 79 k. 

Artur Andrzejak and Emo Welzl
Halving Point Sets
Doc.Math.J.DMV Extra Volume ICM III (1998) 471-478
Abstract 2 k, dvi.gz 16 k, dvi 34 k, ps.gz 65 k. 
This manuscript may contain graphics, 
 therefore the dvi files may be incomplete.