Papers accepted to STOC 2008 Unconditional pseudorandom generators for low degree polynomials Shachar Lovett Classical Interaction Cannot Replace a Quantum Message Dmitry Gavinsky Optimal approximation for the Submodular Welfare Problem in the value oracle model Jan Vondrak Minimum k-way cuts via deterministic greedy tree packing Mikkel Thorup Elusive Functions and Lower Bounds for Arithmetic Circuits Ran Raz The Pattern Matrix Method for Lower Bounds on Quantum Communication Alexander A. Sherstov Universal Semantic Communication I Brendan Juba and Madhu Sudan Complete Fairness in Secure Two-Party Computation S. Dov Gordon and Carmit Hazay and Jonathan Katz and Yehuda Lindell Interdomain Routing and Games Hagay Levin Michael Schapira and Aviv Zohar Additive Guarantees for Degree Bounded Directed Network Design Nikhil Bansal and Rohit Khandekar and Viswanath Nagarajan Optimal Algorithms and Inapproximability Results For Every CSP? Prasad Raghavendra A Fixed-Parameter Algorithm for the Directed Feedback Vertex Set Problem Jianer Chen and Yang Liu and Songjian Lu and Barry O'Sullivan and Igor Razgon Testing Symmetric Properties of Distributions Paul Valiant Regret Minimization and the Price of Total Anarchy Avrim Blum and MohammadTaghi Hajiaghayi and Katrina Ligett and Aaron Roth Lossy Trapdoor Functions and Their Applications Chris Peikert and Brent Waters Every Minor-Closed Property of Sparse Graphs is Testable Itai Benjamini and Oded Schramm and Asaf Shapira A quadratic lower bound for the permanent and determinant problem over any characteristic $\not=$ 2 Jin-Yi Cai and Xi Chen and Dong Li Algebraic Property Testing: The Role of Invariance Tali Kaufman and Madhu Sudan Stateless distributed gradient descent for positive linear programs Baruch Awerbuch and Rohit Khandekar Pricing Combinatorial Markets for Tournaments Yiling Chen and Sharad Goel and David Pennock On Hardness of Learning Intersection of Two Halfspaces Subhash Khot and Rishi Saket Games for Exchanging Information Gillat Kol and Moni Naor The Complexity of Temporal Constraint Satisfaction Problems Manuel Bodirsky and Jan Kara Combinatorial Construction of Locally Testable Codes Or Meir Span-program-based quantum algorithm for evaluating formulas Ben W. Reichardt and Robert Spalek Fast Integer Multiplication Using Modular Arithmetic Anindya De and Piyush P Kurur and Chandan Saha and Ramprasad Saptharishi Fast polynomial factorization and modular composition in small characteristic Christopher Umans Balanced Outcomes in Social Exchange Networks Jon Kleinberg and Eva Tardos Towards an Optimal Separation of Space and Length in Resolution Jakob Nordström and Johan Håstad Hardness Amplification Proofs Require Majority Ronen Shaltiel and Emanuele Viola Infeasibility of Instance Compression and Succinct PCPs for NP Lance Fortnow and Rahul Santhanam Sketching in Adversarial Environments Ilya Mironov and Moni Naor and Gil Segev Inapproximability of Pure Nash Equilibria Alexander Skopalik and Berthold Vöcking SDP Gaps and UGC Hardness for Multiway Cut, 0-Extension and Metric Labeling Rajeskar Manokaran and Joseph (Seffi) Naor and Prasad Raghavendra and Roy Schwartz The Myth of the Folk Theorem Christian Borgs and Jennifer Chayes and Nicole Immorlica and Adam Tauman Kalai and Vahab Mirrokni and Christos Papadimitriou An $O(\log^2 k)$-approximation algorithm for the $k$-vertex connected subgraph problem Jittat Fakcharoenphol and Bundit Laekhanukit Random projection trees and low dimensional manifolds Sanjoy Dasgupta and Yoav Freund Randomized Competitive Algorithms for Generalized Caching Nikhil Bansal and Niv Buchbinder and Joseph (Seffi) Naor Graphs, polymorphisms and the complexity of homomorphism problems Libor Barto and Marcin Kozik and Todd Niven Algebrization: A New Barrier in Complexity Theory Scott Aaronson and Avi Wigderson Unique Games on Expanding Constraint Graphs are Easy Sanjeev Arora and Subhash A. Khot and Alexandra Kolla and David Steurer and Madhur Tulsiani and Nisheeth K. Vishnoi Additive Approximation for Bounded Degree Survivable Network Design Lap Chi Lau and Mohit Singh Inverse Conjecture for the Gowers norm is false Shachar Lovett and Roy Meshulam and Alex Samorodnitsky On Partitioning Graphs via Single Commodity Flows Lorenzo Orecchia and Leonard Schulman and Umesh V. Vazirani and Nisheeth K. Vishnoi List-Decoding Reed-Muller Codes over Small Fields Parikshit Gopalan and Adam R. Klivans and David Zuckerman A combinatorial construction of almost-Ramanujan graphs using the zig-zag product Avraham Ben-Aroya and Amnon Ta-Shma Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits Zeev Dvir and Amir Shpilka and Amir Yehudayoff Optimal Hierarchical Decompositions for Congestion Minimization in Networks Harald Raecke Decodability of Group Homomorphisms Beyond the Johnson Bound Irit Dinur and Elena Grigorescu and Swastik Kopparty and Madhu Sudan Robust Lower Bounds for Communication and Stream Computation Amit Chakrabarti and Graham Cormode and Andrew McGregor Agnostically Learning Decision Trees Parikshit Gopalan and Adam Tauman Kalai and Adam R. Klivans An optimal SDP algorithm for Max-Cut, and equally optimal Long Code tests Ryan O'Donnell and Yi Wu On Agnostic Boosting and Parity Learning Adam Tauman Kalai and Yishay Mansour and Elad Verbin Logconcave Random Graphs Alan Frieze and Santosh Vempala and Juan Vera On the constant-depth complexity of k-clique Benjamin Rossman A (De)constructive Approach to Program Checking Shafi Goldwasser and Dan Gutfreund and Alex Healy and Tali Kaufman and Guy Rothblum The Chow Parameters Problem Ryan O'Donnell and Rocco A. Servedio Trapdoors for Hard Lattices and New Cryptographic Constructions Craig Gentry and Chris Peikert and Vinod Vaikuntanathan Fast-Converging Tatonnement Algorithms for One-Time and Ongoing Market Problems Richard Cole and Lisa Fleischer Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized Russell Impagliazzo and Ragesh Jaiswal and Valentine Kabanets and Avi Wigderson A Learning Theoretic Framework for Clustering with Similarity Functions Maria-Florina Balcan and Avrim Blum and Santosh Vempala Optimal Algorithms for Finding Graphs Sung-Soon Choi and Jeong Han Kim Network Design for Vertex Connectivity Tanmoy Chakraborty and Julia Chuzhoy and Sanjeev Khanna Algorithms for Subset Selection in Linear Regression Abhimanyu Das and David Kempe A Learning Theory Approach to Non-Interactive Database Privacy Avrim Blum and Katrina Ligett and Aaron Roth Parallel Repetition in Projection Games and a Concentration Bound Anup Rao Multi-Armed Bandits on Metric Spaces Robert Kleinberg and Aleksandrs Slivkins and Eli Upfal Randomized K-Server on Hierarchical Binary Trees Aaron Cote and Adam Meyerson and Laura Poplawski Cryptography with Constant Computational Overhead Yuval Ishai and Eyal Kushilevitz and Rafail Ostrovsky and Amit Sahai Graph and Map Isomorphism and All Polyhedral Embeddings In Linear Time Ken-ichi Kawarabayashi and Bojan Mohar The VPN Conjecture is True Navin Goyal and Neil Olver and F. B. Shepherd Tight RMR Lower Bounds for Mutual Exclusion and Other Problems Hagit Attiya and Danny Hendler and Philipp Woelfel An Effective Ergodic Theorem and Some Applications Satyadev Nandakumar Money Burning and Mechanism Design Jason Hartline and Tim Roughgarden Read-once Polynomial Identity Testing Amir Shpilka and Ilya Volkovich Faster Approximate Lossy Generalized Flow via Interior Point Algorithms Samuel I. Daitch and Daniel A. Spielman Communication in the Presence of Replication Omer Barkol and Yuval Ishai and Enav Weinreb Evolvability from Learning Algorithms Vitaly Feldman Graph Sparsification by Effective Resistances Daniel Spielman and Nikhil Srivastava Delegating Computation: Interactive Proofs for Muggles Shafi Goldwasswer and Yael Tauman and Guy Rothblum Finding Short Lattice Vectors within Mordell's Inequality Nicolas Gama and Phong Q. Nguyen Direct Product Theorems for Classical Communication Complexity via Subdistribution Bounds Rahul Jain and Hartmut Klauck and Ashwin Nayak