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
References:
  1. http://theory.lcs.mit.edu/~madhu/pcp/course.html
  2. "On the Hardness of Coloring 3-Uniform Hyper-Graphs" by Dinur, Regev, Smyth
Abstract:
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.)