Sub-Constant Error Low Degree Test of Almost-Linear Size Dana Moshkovitz and Ran Raz Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources Anup Rao Zero-knowledge against quantum attacks John Watrous Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures Leonid Gurvits Narrow Proofs May Be Spacious: Separating Space and Width in Resolution Jakob Nordstrom The distance trisector curve Tetsuo Asano and Jiri Matousek and Takeshi Tokuyama Reducibility Among Equilibrium Problems Paul W. Goldberg and Christos H. Papadimitriou The Complexity of Computing a Nash Equilibrium Constantinos Daskalakis and Paul W. Goldberg and Christos H. Papadimitriou The PCP Theorem via Gap Amplification Irit Dinur Conditional Hardness for Approximate Coloring Irit Dinur, Elchanan Mossel, Oded Regev Lattice Problems and Norm Embeddings Oded Regev and Ricky Rosen Linear time low tree-width partitions and algorithmic consequences Jaroslav Nesetril and Patrice Ossona de Mendez A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity Noga Alon and Eldar Fischer and Ilan Newman and Asaf Shapira Optimal Phylogenetic Reconstruction Constantinos Daskalakis and Elchanan Mossel and Sebastien Roch On Adequate Performance Measures for Paging Konstantinos Panagiotou and Alexander Souza Linear Degree Extractors and the Inapproximability of Max-Clique and Chromatic Number David Zuckerman On maximizing welfare when utility functions are subadditive Uriel Feige Searching Dynamic Point Sets in Spaces with Bounded Doubling Dimension. Richard Cole and Lee-Ad Gottlieb Time-Space Tradeoffs for Implementations of Snapshots Panagiota Fatourou and Faith Ellen Fich and Eric Ruppert Fast Leader-Election Protocols with Bounded Cheaters' Edge Spyridon Antonakopoulos Edge-Disjoint Paths in Planar Graphs with Constant Congestion C. Chekuri and S. Khanna and F.B. Shepherd An efficient algorithm for solving word equations (extended abstract) Wojciech Plandowski Finding small balanced separators Uriel Feige and Mohammad Mahdian Online Trading Algorithms and Robust Option Pricing Peter DeMarzo and Ilan Kremer and Yishay Mansour Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf Clique-width minimization is NP-hard Michael R. Fellows and Frances A. Rosamond and Udi Rotics and Stefan Szeider Graph limits and parameter testing Christian Borgs and Jennifer T. Chayes and Laszlo Lovasz and Vera T. Sos and Balazs Szegedy and Katalin Vesztergombi On Earthmover Distance, Metric Labeling, and 0-Extension Howard Karloff and Subhash Khot and Aranyak Mehta and Yuval Rabani Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries Vitaly Feldman Explicit Capacity-Achieving List-Decodable Codes Venkatesan Guruswami and Atri Rudra New upper and lower bounds for randomized and quantum Local Search Shengyu Zhang A Quasi-PTAS for Unsplittable Flow on Line Graphs Nikhil Bansal and Amit Chakrabarti and Amir Epstein and Baruch Schieber Learning a Circuit by Injecting Values Dana Angluin and James Aspnes and Jiang Chen and Yinghua Wu Graph Partitioning using Single Commodity Flows Rohit Khandekar and Satish Rao and Umesh Vazirani Provably Near-Optimal Sampling-Based Algorithms for Stochastic Inventory Models Retsef Levi and Robin Roundy and David Shmoys Minimizing Average Flow Time on Related Machines Naveen Garg and Amit Kumar Gowers Uniformity, Influence of Variables, and PCPs Alex Samorodnitsky and Luca Trevisan Time-Space Trade-Offs for Predecessor Search Mihai Patrascu and Mikkel Thorup Approximating chromatic number and list-chromatic number in minor-closed and odd-minor-closed classes of graphs Ken-ichi Kawarabayashi and Bojan Mohar Truthful Randomized Mechanisms for Combinatorial Auctions Shahar Dobzinski and Noam Nisan and Michael Schapira Pricing for Fairness: Distributed Resource Allocation for Multiple Objectives Sung-woo Cho and Ashish Goel Black-Box Constructions of Secure Protocols Yuval Ishai and Eyal Kushilevitz and Yehuda Lindell and Erez Petrank A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs Andris Ambainis, Robert Spalek and Ronald de Wolf Advances in Metric Embedding Theory Ittai Abraham, Yair Bartal and Ofer Neiman On the Randomness Complexity of Efficient Sampling Bella Dubrov and Yuval Ishai Information-Theoretically Secure Protocols and Security under Composition Eyal Kushilevitz and Yehuda Lindell and Tal Rabin Fast Convergence to Wardrop Equilibria by Adaptive Sampling Methods Simon Fischer and Harald Racke and Berthold Vocking The Santa Claus Problem Nikhil Bansal and Maxim Sviridenko New Trade-Offs in Cost-Sharing Mechanisms Tim Roughgarden and Mukund Sundararajan Building triangulations with epsilon-nets Kenneth L. Clarkson Integrality Gaps for Sparsest Cut and Minimum Linear Arrangement Problems Nikhil Devanur and Subhash Khot and Rishi Saket and Nisheeth Vishnoi Counting down the tree Dror Weitz Private Approximation of Search Problems Amos Beimel and Paz Carmi and Kobbi Nissim and Enav Weinreb Hardness of Cut Problems in Directed Graphs Julia Chuzhoy and Sanjeev Khanna Logarithmic Hardness of the Directed Congestion Minimization Problem Matthew Andrews and Lisa Zhang Zero Knowledge with Efficient Provers Minh-Huyen Nguyen and Salil Vadhan On the Fourier tails of bounded functions over the discrete cube Irit Dinur and Ehud Friedgut and Guy Kindler and Ryan O'Donnell Approximate Nearest Neighbors and the Fast Johnson-Lindenstrauss Transform Nir Ailon and Bernard Chazelle The Effect of Collusion in Congestion Games Ara Hayrapetyan and Eva Tardos and Tom Wexler Near-Optimal Algorithms for Unique Games Moses Charikar and Konstantin Makarychev and Yury Makarychev Pseudorandom Walks on Regular Digraphs and the RL vs. L Problem Omer Reingold, Luca Trevisan and Salil Vadhan Simple Cost-sharing Schemes for Multi-Commodity Rent-or-Buy and Stochastic Steiner Tree Lisa Fleischer and Jochen Koenemann and Stefano Leonardi and Guido Schaefer Limitations of Quantum Coset States for Graph Isomorphism Sean Hallgren, Cristopher Moore, Martin Roetteler, Alexander Russell, and Pranab Sen. 2-Source Dispersers for n^o(1) Entropy, and Ramsey Graphs Beating the Frankl-Wilson Construction Boaz Barak and Anup Rao and Ronen Shaltiel and Avi Wigderson A Quasi-Polynomial Time Approximation Scheme for Minimum Weight Triangulation Jan Remy and Angelika Steger On the Importance of Idempotence S. A. Arya and T. Malamatos and D. M. Mount A Randomized Polynomial-Time Simplex Algorithm for Linear Programming Jonathan A. Kelner and Daniel A. Spielman New Approximation Guarantee for Chromatic Number Sanjeev Arora and Eden Chlamtac and Moses Charikar Byzantine Agreement in the Full-Information Model in O(log n) rounds Michael Ben-Or and Elan Pavlov and Vinod Vaikuntanathan On Basing One-Way Functions on NP-Hardness Adi Akavia and Oded Goldreich and Shafi Goldwasser and Dana Moshkovitz Finding a Maximum Weight Triangle in Sub-Cubic Time, With Applications Virginia Vassilevska and Ryan Williams On the Solution-Space Geometry of Random Constraint Satisfaction Problems Dimitris Achlioptas and Federico Ricci-Tersenghi Deterministic Extractors For Small Space Sources Jesse Kamp and Anup Rao and Salil Vadhan and David Zuckerman A Polynomial Quantum Algorithm for Approximating the Jones Polynomial Dorit Aharonov and Vaughan Jones and Zeph Landau A subset spanner for planar graphs,with application to subset TSP Philip N. Klein Local Zero Knowledge Silvio Micali and Rafael Pass Designing Hyperlink Structures - Optimization and Game-Theoretic Questions N. Immorlica and K. Jain and M. Mahdian The DLT Priority Sampling is Essentially Optimal Mario Szegedy