Arbeitsgemeinschaft (WS 05/06):

Komplexität und Programmiersprachen

Organisatorisches

Veranstalter:

Prof. M. Hofmann, Dr. J. Johannsen

Termine:

Zeit: Fr 12-14

Ort: Z1.09

Beginn: 28. Oktober

Links

• Oded Goldreich: Bravely, Moderately: A Common Theme in Four Recent Results
• Omer Reingold: Undirected ST-Connectivity in Log-Space
• Eyal Rozenman, Salil Vadhan: Derandomized Squaring of Graphs
• Omer Reingold, Salil Vadhan, Avi Wigderson: Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders
• David Xiao: The Evolution of Expander Graphs
• Irit Dinur and Omer Reingold: Assignment Testers: Towards a combinatorial proof of the PCP theorem
• Irit Dinur: The PCP Theorem by gap amplification

---