List of accepted papers for FOCS 2011: The Grothendieck constant is strictly smaller than Krivine's bound Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor The minimum k-way cut of bounded size is fixed-parameter tractable Mikkel Thorup and Ken-ichi Kawarabayashi Randomness buys depth for approximate counting Emanuele Viola Local Distributed Decision Pierre Fraigniaud and Amos Korman and David Peleg A Small PRG for Polynomial Threshold Functions of Gaussians Daniel M. Kane Evolution with Recombination Varun Kanade Extractors for circuit sources Emanuele Viola The Second-Belief Mechanism. Jing Chen and Silvio Micali New extension of the Weil bound for character sums with applications to coding Tali Kaufman and Shachar Lovett A Two Prover One Round Game with Strong Soundness Subhash Khot and Muli Safra Optimal testing of multivariate polynomials over small prime fields Elad Haramaty and Amir Shpilka and Madhu Sudan Fully dynamic maximal matching in O(log n) update time Surender Baswana and Manoj Gupta and Sandeep Sen Optimal bounds for quantum bit commitment Andre Chailloux and Iordanis Kerenidis Sharp mixing time bounds for sampling random surfaces Pietro Caputo and Fabio Martinelli and Fabio Lucio Toninelli Solving connectivity problems parameterized by treewidth in single exponential time Marek Cygan and Jesper Nederlof and Marcin Pilipczuk and Micha Pilipczuk and Johan M. M. van Rooij and Jakub Onufry Wojtaszczyk How to Play Unique Games Against a Semi-Random Adversary Alexandra Kolla and Konstantin Makarychev and Yury Makarychev Near-Optimal Column-Based Matrix Reconstruction Christos Boutsidis and Petros Drineas and Malik Magdon-Ismail Tight lower bounds for 2-query LCCs over finite fields Arnab Bhattacharyya and Zeev Dvir and Shubhangi Saraf and Amir Shpilka Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications Christian Wulff-Nilsen 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General Timon Hertli On Range Searching in the Group Model and Combinatorial Discrepancy Kasper Green Larsen Coin Flipping with Constant Bias Implies One-Way Functions Iftach Haitner and Eran Omri The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. Paul W. Goldberg and Christos H. Papadimitriou and Rahul Savani Information Equals Amortized Communication Mark Braverman and Anup Rao Graph Connectivities, Network Coding, and Expander Graphs Ho Yee Cheung and Lap Chi Lau and Kai Man Leung Limitations of Randomized Mechanisms for Combinatorial Auctions Shaddin Dughmi and Jan Vondrak How to Store a Secret on Continually Leaky Devices Yevgeniy Dodis and Allison Lewko and Brent Waters and Daniel Wichs A Polylogarithmic-Competitive Algorithm for the k-Server Problem Nikhil Bansal and Niv Buchbinder and Aleksander Madry and Seffi Naor Minimum Weight Cycles and Triangles: Equivalences and Algorithms Liam Roditty and Virginia Vassilevska Williams Streaming Algorithms via Precision Sampling Alexandr Andoni and Robert Krauthgamer and Krzysztof Onak A Parallel Approximation Algorithm for Positive Semidefinite Programming Rahul Jain and Penghui Yao Planar Graphs: Random Walks and Bipartiteness Testing Artur Czumaj and Morteza Monemizadeh and Krzysztof Onak and Christian Sohler Pseudorandomness for read-once formulas Andrej Bogdanov and Periklis Papakonstantinou and Andrew Wan Approximating Graphic TSP by Matchings Tobias Moemke and Ola Svensson Efficient Distributed Medium Access Devavrat Shah and Jinwoo Shin and Prasad Tetali Near Linear Lower Bound for Dimension Reduction in L1 Alexandr Andoni and Moses S. Charikar and Ofer Neiman and Huy L. Nguyen Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2 Loic Seguin-Charbonneau and F. Bruce Shepherd Min-Max Graph Partitioning and Small-Set Expansion Nikhil Bansal and Uriel Feige and Robert Krauthgamer and Konstantin Makarychev and Viswanath Nagarajan and Joseph (Seffi) Naor and Roy Schwartz An FPTAS for #Knapsack and Related Counting Problems Parikshit Gopalan and Adam Klivans and Raghu Meka and Daniel Stefankovic and Santosh Vempala and Eric Vigoda Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets Ricardo Restrepo and Jinwoo Shin and Prasad Tetali and Eric Vigoda and Linji Yang Balls and Bins: Smaller Hash Families and Faster Evaluation L. Elisa Celis and Omer Reingold and Gil Segev and Udi Wieder Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time Glencora Borradaile and Philip N. Klein and Shay Mozes and Yahav Nussbaum and Christian Wulff-Nilsen Quantum query complexity of state conversion Troy Lee and Rajat Mittal and Ben W. Reichardt and Robert Spalek and Mario Szegedy A constant factor approximation algorithm for unsplittable flow on paths Paul Bonsma and Jens Schulz and Andreas Wiese The Graph Minor Algorithm with Parity Conditions Ken-ichi Kawarabayashi and Bruce Reed and Paul Wollan Mutual Exclusion with O(log2 logn) Amortized Work Michael A. Bender and Seth Gilbert How Bad is Forming Your Own Opinion? David Bindel and Jon Kleinberg and Sigal Oren The Complexity of Renaming Dan Alistarh and James Aspnes and Seth Gilbert and Rachid Guerraoui On the Power of Adaptivity in Sparse Recovery Piotr Indyk and Eric Price and David Woodruff Enumerative Lattice Algorithms in any Norm via M-ellipsoid Coverings Daniel Dadush and Chris Peikert and Santosh Vempala Efficient and Explicit Coding for Interactive Communication Ran Gelles and Ankur Moitra and Amit Sahai Dispersers for affine sources with sub-polynomial entropy Ronen Shaltiel Approximation Algorithms for Correlated Knaspacks and Non-Martingale Bandits Anupam Gupta and Ravishankar Krishnaswamy and Marco Molinaro and R. Ravi Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives Venkatesan Guruswami and Ali Kemal Sinop A Unified Continuous Greedy Algorithm for Submodular Maximization Moran Feldman and Joseph (Seffi) Naor and Roy Schwartz Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers Saeed Alaei Extreme-Value Theorems for Optimal Multidimensional Pricing Yang Cai and Constantinos Daskalakis Approximation Algorithms for Submodular Multiway Partition Chandra Chekuri and Alina Ene Delays and the Capacity of Continuous-time Channels Sanjeev Khanna and Madhu Sudan Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits Craig Gentry and Shai Halevi A Randomized Rounding Approach to the Traveling Salesman Problem Shayan Oveis Gharan and Amin Saberi and Mohit Singh Algorithms for the Generalized Sorting Problem Zhiyi Huang and Sampath Kannan and Sanjeev Khanna Privacy Amplification and Non-Malleable Extractors Via Character Sums Xin Li and Trevor D. Wooley and David Zuckerman A nearly mlogn time solver for SDD linear systems Ioannis Koutis and Gary L. Miller and Richard Peng Which Networks Are Least Susceptible to Cascading Failures? Lawrence Blume and David Easley and Jon Kleinberg and Robert Kleinberg and Eva Tardos Online Node-weighted Steiner Tree and Related Problems Joseph (Seffi) Naor and Debmalya Panigrahi and Mohit Singh Welfare and Profit Maximization with Production Costs Avrim Blum and Anupam Gupta and Yishay Mansour and Ankit Sharma On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems Dorit Aharonov and Lior Eldar Efficient Fully Homomorphic Encryption from (Standard) LWE Zvika Brakerski and Vinod Vaikuntanathan Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy Madhav Jha and Sofya Raskhodnikova Lexicographic Products and the Power of Non-Linear Network Coding Anna Blasiak and Robert Kleinberg and Eyal Lubetzky Efficient computation of approximate pure Nash equilibria in congestion games Ioannis Caragiannis and Angelo Fanelli and Nick Gravin and Alexander Skopalik How to Garble Arithmetic Circuits Benny Applebaum and Yuval Ishai and Eyal Kushilevitz Rounding Semidefinite Programming Hierarchies via Global Correlation Boaz Barak and Prasad Raghavendra and David Steurer Efficient Reconstruction of Random Multilinear Formulas Ankit Gupta and Neeraj Kayal and Satya Lokam Markov Layout Flavio Chierichetti and Ravi Kumar and Prabhakar Raghavan (1+eps)-Approximate Sparse Recovery Eric Price and David P. Woodruff Quadratic Goldreich-Levin Theorems Madhur Tulsiani and Julia Wolf Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems Jian Li and Amol Deshpande Stateless Cryptographic Protocols Vipul Goyal and Hemanta K. Maji Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones Michael Elkin and Shay Solomon An algebraic proof of a robust social choice impossibility theorem Dvir Falik and Ehud Friedgut The Power of Linear Estimators Gregory Valiant and Paul Valiant The Randomness Complexity of Parallel Repetition Kai-Min Chung and Rafael Pass The Complexity of Quantum States - a combinatorial approach Dorit Aharonov and Itai Arad and Zeph Landau and Umesh Vazirani