Ernest Schimmerling

Mathematical logic seminar - February 5, 2003

Speaker: Clifford Smyth
Zeev Nehari Visiting Assistant Professor
Department of Mathematical Sciences
Carnegie Mellon University

Title: Probabilistically checkable proofs

  2. "On the Hardness of Coloring 3-Uniform Hyper-Graphs" by Dinur, Regev, Smyth

Probabilistically checkable proofs and their impact on computational complexity, including hardness of approximation results (certain combinatorial problems, for which one can show that deterministically finding a solution, even a suboptimal one, is computationally intractable.)