Complexity theory (Q2577105)

Summary: Computational Complexity Theory is the mathematical study of resources like time, space, or randomness that are required to solve computational problems. The current workshop was focused on recent developments, and the interplay between randomness and computation played a central role in many of them. Contributions: -- Omer Reingold, Undirected ST-Connectivity in Log-Space p. 1437 -- Oded Regev, On Khot's Unique Games Conjecture p. 1440 -- Avi Wigderson, Extracting Randomness from Few Independent Sources p. 1442 -- Irit Dinur, The PCP Theorem via gap amplification p. 1445 -- Sanjeev Arora, Geometry and expansion: A survey of recent results p. 1449 -- Oded Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography p. 1450 -- Yuval Ishai (joint with Benny Applebaum and Eyal Kushilevitz) Cryptography in NC0 p. 1454 -- Amnon Ta-Shma (joint with Dan Gutfreund, Ronen Shaltiel), If NP languages are hard on the worst-case then it is easy to find their hard instances p. 1457 -- Eyal Kushilevitz (joint with A. Beimel, Y. Ishai and J.F. Raymond), 3-Server Information-Theoretic Private-Information Retrieval p. 1460 -- Leslie Valiant, Holographic Algorithms p. 1462 -- Scott Aaronson, Are Quantum States Exponentially Long Vectors? p. 1463 -- Eli Ben-Sasson (joint with Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan), Short PCPs p. 1466 -- Chris Umans (joint with Henry Cohn, Robert Kleinberg, Balsazs Szegedy), A Group-Theoretic Approach to Fast Matrix Multiplication p. 1468 -- Adi Akavia (joint with Oded Goldreich, Shal Goldwasser, Dana Moshkovitz), On Basing One-Way Functions on NP-Hardness p. 1471 -- Julia Chuzhoy, Hardness of Undirected Routing Problems p. 1474 -- Ran Raz, Quantum Information and the PCP Theorem p. 1477 -- Peter Bürgisser (joint with Felipe Cucker and Martin Lotz), The Computational Complexity of the Euler characteristic and the Hilbert Polynomial p. 1478 -- Ronen Shaltiel (joint with Boaz Barak, Guy Kindler, Benny Sudakov, Avi Wigderson), Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors p. 1481 -- Ran Raz, Multi-Linear Formulas for Permanent and Determinant are of Super- Polynomial Size p. 1484 -- Shafi Goldwasser and Moni Naor (Session Chairs), Specialized Session on Cryptography p. 1486 -- Oded Regev (Session Chair), Specialized Session on Complexity of Lattice Problems p. 1490 -- Peter Bürgisser (Session Chair), Specialized Session on Algebraic Complexity p. 1491 - -Boaz Barak (Session Chair), Specialized Session on Randomness Extractors p. 1493 -- Ronen Shaltiel (Session Chair), Specialized Session on Pseudorandomness p. 1495 -- Muli Safre (Session chair), Specialized Session on the Complexity of Low Distortion Embeddings p. 1497