Section 14

Mathematical Aspects of Computer Science

In case of several authors, Invited Speakers are marked with a ^{∗}.

Miklós Ajtai: Worst-Case Complexity, Average-Case Complexity and Lattice Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III 421

Joan Feigenbaum: Games, Complexity Classes, and Approximation Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III 429

Johan Håstad: On Approximating NP-Hard Optimization Problems III 441

Toniann Pitassi: Unsolvable Systems of Equations and Proof Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III 451

Madhu Sudan: Probabilistic Verification of Proofs . . . . . . . . . . . . . . . . . . III 461
Artur Andrzejak and Emo Welzl^{∗}: Halving Point Sets . . . . . . . . . III 471

Documenta Mathematica · Extra Volume ICM 1998 · III ·

420

Documenta Mathematica · Extra Volume ICM 1998 · III ·