FOCS 2013 Accepted Papers (with pdf files)

FOCS 2013 accepted paper list is here. Following are PDF pointers to online versions.

  • OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings, by Jelani Nelson and Huy L. Nguyen [arXiv]
  • A Polynomial Time Algorithm for Lossy Population Recovery, by Ankur Moitra and Michael Saks [arXiv]
  • Direct products in communication complexity, by Mark Braverman, Anup Rao, Omri Weinstein and Amir Yehudayoff [ECCC]
  • Arithmetic circuits: A chasm at depth three, by Ankit Gupta, Pritish Kamath, Neeraj Kayal and Ramprasad Saptharishi [ECCC]
  • Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs, by Joseph Cheriyan and Laszlo A. Vegh [arXiv]
  • The Parity of Directed Hamiltonian Cycles, by Andreas Björklund and Thore Husfeldt [arXiv]
  • Approximating Minimization Diagrams and Generalized Proximity Search, by Sariel Har-Peled and Nirman Kumar [arXiv]
  • Quantum 3-SAT is QMA1-complete, by David Gosset and Daniel Nagaj [arXiv]
  • The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation is Constant, by Vittorio Bilò, Michele Flammini and Luca Moscardelli
  • Strong LTCs with inverse poly-log rate and constant soundness, by Michael Viderman [ECCC]
  • All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs, by Ken-ichi Kawarabayashi and Yusuke Kobayashi
  • Approximating Bin Packing within O(log OPT * log log OPT) bins, by Thomas Rothvoss [arXiv]
  • Common information and unique disjointness, by Gábor Braun, and Sebastian Pokutta [ECCC]
  • Chasing the k-colorability threshold, by Amin Coja-Oghlan and Dan Vilenchik [arXiv]
  • Three-player entangled XOR games are NP-hard to approximate, by Thomas Vidick [arXiv]
  • Fully Dynamic $(1+\epsilon)$-Approximate Matchings, by Manoj Gupta, and Richard Peng [arXiv]
  • Estimating the distance from testable affine-invariant properties, by Hamed Hatami and Shachar Lovett [arXiv]
  • Approximation algorithms for Euler genus and related problems, by Chandra Chekuri and Anastasios Sidiropoulos [arXiv]
  • Polar Codes: Speed of polarization and polynomial gap to capacity, by Venkatesan Guruswami and Patrick Xia [arXiv]
  • An Optimal Randomized Online Algorithm for Reordering Buffer Management, by Noa Avigdor-Elgrabli and Yuval Rabani [arXiv]
  • Approximation Schemes for Maximum Weight Independent Set of Rectangles, by Anna Adamaszek and Andreas Wiese
  • Playing Non-linear Games with Linear Oracles, by Dan Garber, and Elad Hazan
  • Faster Canonical Forms for Strongly Regular Graphs, by Laszlo Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng and John Wilmes
  • Constant rate PCPs for circuit-SAT with sublinear query complexity, by Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir and Henning Stichtenoth [pdf] [video]
  • How to Approximate A Set Without Knowing Its Size In Advance, by Rasmus Pagh, Gil Segev and Udi Wieder [arXiv]
  • Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs, by Michael A. Forbes, and Amir Shpilka [arXiv]
  • On Kinetic Delaunay Triangulations: A Near Quadratic Bound for Unit Speed Motions, by Natan Rubin
  • Element Distinctness, Frequency Moments, and Sliding Windows, by Paul Beame, Raphael Clifford and Widad Machmouchi
  • Spatial mixing and approximation algorithms for graphs with bounded connective constant, by Alistair Sinclair, Piyush Srivastava and Yitong Yin
  • Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors, by Harold N. Gabow and Piotr Sankowski [arXiv]
  • A linear time approximation scheme for Euclidean TSP, by Yair Bartal and Lee-Ad Gottlieb
  • Interactive Coding, Revisited, by Kai-Min Chung, Rafael Pass and Sidharth Telang [ePrint]
  • Improved approximation for 3-dimensional matching via bounded pathwidth local search, by Marek Cygan [arXiv]
  • Strong Backdoors to Bounded Treewidth SAT, by Serge Gaspers and Stefan Szeider [arXiv]
  • Explicit Subspace Designs, by Venkatesan Guruswami and Swastik Kopparty [ECCC]
  • Dynamic Approximate All-Pairs Shortest Paths: Breaking the $ \tilde O(mn) $ Barrier and Derandomization, Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai
  • On Randomized Memoryless Algorithms for the Weighted $k$-server Problem, by Ashish Chiplunkar and Sundar Vishwanathan [arXiv]
  • Constant-Round Concurrent Zero Knowledge From P-Certificates, by Kai-Min Chung, Huijia Lin and Rafael Pass [ePrint]
  • Learning Sums of Independent Integer Random Variables, by Constantinos Daskalakis, Ilias Diakonikolas, Ryan O’Donnell, Rocco A. Servedio and Li-Yang Tan [pdf]
  • Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses, by Parinya Chalermsook, Bundit Laekhanukit, and Danupon Nanongkai
  • Online Node-weighted Steiner Forest and Extensions via Disk Paintings, by Mohammad Taghi Hajiaghayi, Vahid Liaghat, and Debmalya Panigrahi
  • Klee’s Measure Problem Made Easy, by Timothy M. Chan
  • Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy, by Xin Li [arXiv]
  • Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back, by Aleksander Madry
  • Fourier sparsity, spectral norm, and the Log-rank conjecture, Hing Yin Tsang, Chung Hoi Wong, Ning Xie and Shengyu Zhang [arXiv]
  • Layered Separators for Queue Layouts, 3D Graph Drawing and Nonrepetitive Coloring, by Vida Dujmović, Pat Morin, and David R. Wood
  • Average Case Lower Bounds for Monotone Switching Networks, by Yuval Filmus, Toniann Pitassi, Robert Robere and Stephen A. Cook [arXiv]
  • PCPs via low-degree long code and hardness for constrained hypergraph coloring, by Irit Dinur and Venkatesan Guruswami
  • The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable, by Marek Cygan, Dániel Marx, Marcin Pilipczuk and Michał Pilipczuk [arXiv]
  • On the communication complexity of sparse set disjointness and exists-equal problems, Mert Sağlam and Gábor Tardos [arXiv]
  • The Simple Economics of Approximately Optimal Auctions, Saeed Alaei, Hu Fu, Nima Haghpanah and Jason Hartline [arXiv]
  • Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems, by Yin Tat Lee and Aaron Sidford [arXiv]
  • Nearly Maximum Flows in Nearly Linear Time, by Jonah Sherman [arXiv]
  • Improved Average-Case Lower Bounds for DeMorgan Formula Size, by Ilan Komargodski, Ran Raz and Avishay Tal [ECCC]
  • Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas, by Vitaly Feldman and Jan Vondrak
  • Towards a better approximation for Sparsest Cut?, by Sanjeev Arora, Rong Ge and Ali Kemal Sinop [arXiv]
  • Bandits with Knapsacks, Ashwinkumar Badanidiyuru, Robert Kleinberg and Aleksandrs Slivkins [arXiv]
  • Approximate Constraint Satisfaction Requires Large LP Relaxations, by Siu On Chan, James R. Lee, Prasad Raghavendra and David Steurer
  • Simple Tabulation, Fast Expanders, Double Tabulation, and High Independence, by Mikkel Thorup
  • An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree, by Jochen Koenemann, Sina Sadeghian and Laura Sanità [arXiv]
  • A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits, by Russell Impagliazzo, Ramamohan Paturi, and Stefan Schneider [arXiv]
  • The Complexity of Approximating Vertex Expansion, by Anand Louis, Prasad Raghavendra and Santosh Vempala [arXiv]
  • Tight Bounds for Set Disjointness in the Message Passing Model, by Mark Braverman, Faith Ellen, Rotem Oshman, Toni Pitassi and Vinod Vaikuntanathan [arXiv]
  • Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees, Adam Marcus, Daniel A. Spielman and Nikhil Srivastava [arXiv]
  • Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits, by Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters
  • Iterative Row Sampling, by Mu Li, Gary L. Miller, and Richard Peng [arXiv]
  • Simultaneous Resettability from One-Way Functions, Kai-Min Chung, Rafail Ostrovsky, Rafael Pass and Ivan Visconti
  • Rational Protocol Design: Cryptography Against Incentive-driven Adversaries, by Juan Garay , Jonathan Katz, Ueli Maurer, Bjoern Tackmann and Vassilis Zikas
  • Non-positive curvature, and the planar embedding conjecture, by Anastasios Sidiropoulos [arXiv]
  • Local Privacy and Statistical Minimax Rates, by John C. Duchi, Michael I. Jordan, and Martin J. Wainwright [arXiv]
  • The Moser-Tardos Framework with Partial Resampling, by David G. Harris and Aravind Srinivasan
  • On Clustering Induced Voronoi Diagrams, Danny Z. Chen, Ziyun Huang, Yangwei Liu, and Jinhui Xu
  • A forward-backward single-source shortest paths algorithm, by David Wilson and Uri Zwick
  • An O(c^k) n 5-Approximation Algorithm for Treewidth, by Hans L. Bodlaender, Paal G. Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov and Michal Pulipczuk [arXiv]
  • Understanding Incentives: Mechanism Design becomes Algorithm Design, by Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg [arXiv]
  • Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers, by Andrew Drucker
  • From Unprovability to Environementally Friendly Protocols, by Ran Canetti, Huijia Lin and Rafael Pass
  • Adaptive Seeding in Social Networks, by Lior Seeman and Yaron Singer
  • Coupled-Worlds Privacy: Exploiting Adversarial Uncertainty in Statistical Data Privacy, by Raef Bassily, Adam Groce, Jonathan Katz and Adam Smith


STOC 2013 Accepted Papers (with pdf files)

STOC 2013 accepted paper list is here. Following are PDF pointers to online versions.


Max flows in O(nm) time or less [pdf]
James Orlin (MIT)

Multidimensional Approximate Agreement in Byzantine Asynchronous Systems
Hammurabi Mendes (Brown University) and Maurice Herlihy (Brown University)

Non-Black-Box Simulation in the Fully Concurrent Setting
Vipul Goyal (Microsoft Research, India)

Approximation Resistance from Pairwise Independent Subgroups [ECCC]
Siu On Chan (UC Berkeley)

Average-Case Lower Bounds for Formula Size [ECCC]
Ilan Komargodski (Weizmann Institute of Science) and Ran Raz (Weizmann Institute of Science)

New Independent Source Extractors with Exponential Improvement [ECCC]
Xin Li (University of Washington)

Random Lattice Triangulations: Structure and Algorithms [arXiv]
Pietro Caputo (University of Rome III), Fabio Martinelli (University of Rome III), Alistair Sinclair (UC Berkeley), and Alexandre Stauffer (University of Rome III)

The Complexity of Non-Monotone Markets [arXiv]
Xi Chen (Columbia University), Dimitris Paparas (Columbia University), and Mihalis Yannakakis (Columbia University)

Optimal Euclidean spanners: really short, thin and lanky [arXiv]
Michael Elkin (Ben-Gurion University) and Shay Solomon (Weizmann Institute of Science)

Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression [arXiv]
Xiangrui Meng (Stanford University) and Michael W. Mahoney (Stanford University)

Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data [ePrint]
Nir Bitansky (Tel Aviv University), Ran Canetti (Boston University and Tel Aviv University), Alessandro Chiesa (MIT), and Eran Tromer (Tel Aviv University)

Sparsity lower bounds for dimensionality reducing maps [arXiv]
Jelani Nelson (Institute for Advanced Study) and Huy L. Nguyen (Princeton University)

Approximating k-Median via Pseudo-Approximation [arXiv]
Shi Li (Princeton University) and Ola Svensson (EPFL)

Byzantine Agreement in Polynomial Expected Time
Valerie King (University of Victoria) and Jared Saia (University of New Mexico)

Equivalence of Deterministic One-Counter Automata is NL-complete [arXiv]
Stanislav Bohm (Technical University of Ostrava), Stefan Goller (University of Bremen), and Petr Jancar (Technical University of Ostrava)

Answering n^{2+o(1)} Counting Queries with Differential Privacy is Hard [arXiv]
Jonathan Ullman (Harvard University)

Succinct Functional Encryption and Applications: Reusable Garbled Circuits and Beyond [ePrint]
Shafi Goldwasser (MIT), Yael Kalai (Microsoft Research, New England), Raluca Ada Popa (MIT), Vinod Vaikuntanathan (University of Toronto), and Nickolai Zeldovich (MIT)

Lower bounds for RAMs and quantifier elimination
Miklos Ajtai (IBM Almaden Research Center)

New Bounds on Matching Vector Families [arXiv]
Abhishek Bhowmick (University of Texas at Austin), Zeev Dvir (Princeton University), and Shachar Lovett (UC San Diego)

The complexity of finite-valued CSPs [arXiv]
Johan Thapper (Universite Paris-Sud 11) and Stanislav Zivny (University of Warwick)

Structured Recursive Separator Decompositions for Planar Graphs in Linear Time [arXiv]
Philip N. Klein (Brown University), Shay Mozes (MIT), and Christian Sommer (MIT)

Inverting well-conditioned matrices in Quantum Logspace
Amnon Ta-Shma (Tel-Aviv University)

List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound [ECCC]
Venkatesan Guruswami (Carnegie Mellon University) and Chaoping Xing (Nanyang Technological University)

Quasipolynomial-time Canonical Form for Steiner Designs
Laszlo Babai (University of Chicago) and John Wilmes (University of Chicago)

Constraint Satisfaction, Packet Routing, and the Lovasz Local Lemma [pdf]
David G. Harris (University of Maryland) and Aravind Srinivasan (University of Maryland)

Low Rank Approximation and Regression in Input Sparsity Time [arXiv]
Kenneth L. Clarkson (IBM Almaden Research) and David P. Woodruff (IBM Almaden Research)

Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs
Aaron Bernstein (Columbia University)

A o(n) monotonicity tester for boolean functions over the hypercube
Deeparnab Chakrabarty (Microsoft Research, India) and C. Seshadhri (Sandia National Laboratories, Livermore)

On the list decodability of random linear codes with large error rates
Mary Wootters (University of Michigan)

Simple Deterministic Algorithms for Fully Dynamic Maximal Matching [arXiv]
Ofer Neiman (Ben-Gurion University) and Shay Solomon (Weizmann Institute of Science)

Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems [HTML]
Sariel Har-Peled (University of Illinois at Urbana Champaign) and Benjamin Raichel (University of Illinois at Urbana Champaign)

Every locally characterized affine-invariant property is testable [arXiv]
Arnab Bhattacharyya (DIMACS), Eldar Fischer (Technion), Hamed Hatami (McGill), Pooya Hatami (University of Chicago), and Shachar Lovett (UC San Diego)

Superlinear advantage for exact quantum algorithms [arXiv]
Andris Ambainis (University of Latvia)

Efficient rounding for the noncommutative Grothendieck inequality [arXiv]
Assaf Naor (New York University), Oded Regev (New York University), and Thomas Vidick (MIT)

A node-capacitated Okamura-Seymour theorem [arXiv]
James R. Lee (University of Washington), Manor Mendel (Open University), and Mohammad Moharrami (University of Washington)

Lee-Yang Theorems and the Complexity of Computing Averages [arXiv]
Alistair Sinclair (UC Berkeley) and Piyush Srivastava (UC Berkeley)

Beyond Worst-Case Analysis in Private Singular Vector Computation [arXiv]
Moritz Hardt (IBM Almaden Research) and Aaron Roth (University of Pennsylvania)

Classical Hardness of Learning with Errors
Zvika Brakerski (Stanford University), Adeline Langlois (ENS de Lyon), Chris Peikert (Georgia Tech), Oded Regev (New York University), and Damien Stehle (ENS de Lyon)

Coevolutionary Opinion Formation Games
Kshipra Bhawalkar (Stanford University), Sreenivas Gollapudi (Microsoft Research, Silicon Valley), and Kamesh Munagala (Duke University)

Predicate Encryption for Circuits
Sergey Gorbunov (University of Toronto), Vinod Vaikuntanathan (University of Toronto), and Hoeteck Wee (George Washington University)

On the complexity of Trial and Error [arXiv]
Xiaohui Bei (Nanyang Technological University), Ning Chen (Nanyang Technological University), and Shengyu Zhang (The Chinese University of Hong Kong)

Fast Routing Table Construction Using Small Messages [arXiv]
Christoph Lenzen (Weizmann Institute of Science) and Boaz Patt-Shamir (Tel Aviv University)

Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas [arXiv]
Manindra Agrawal (Indian Institute of Technology, Kanpur), Chandan Saha (Indian Institute of Science), and Nitin Saxena (Hausdorff Center for Mathematics)

Explicit Lower Bounds via Geometric Complexity Theory [arXiv]
Peter Burgisser (University of Paderborn) and Christian Ikenmeyer (University of Paderborn)

Shielding circuits with groups [ePrint]
Eric Miles (Northeastern University) and Emanuele Viola (Northeastern University)

Extending continuous maps: polynomiality and undecidability [pdf]
Martin Cadek (Masaryk University Brno), Marek Krcal (Charles University Prague), Jiri Matousek (Charles University Prague and ETH Zurich), Lukas Vokrinek (Masaryk University Brno), and Uli Wagner (EPFL)

Testing Subdivision-Freeness: Property Testing Meets Structural Graph Theory
Ken-ichi Kawarabayashi (National Institute of Informatics and JST ERATO Kawarabayashi Project) and Yuichi Yoshida (National Institute of Informatics and Preferred Infrastructure, Inc.)

Some Trade-off Results for Polynomial Calculus
Chris Beck (Princeton University), Jakob Nordstrom (KTH Royal Institute of Technology), and Bangsheng Tang (Tsinghua University)

Going After the k-SAT Threshold [arXiv]
Amin Coja-Oghlan (Goethe University) and Konstantinos Panagiotou (University of Munich)

Composable and Efficient Mechanisms [arXiv]
Vasilis Syrgkanis (Cornell University) and Eva Tardos (Cornell University)

Tatonnement Beyond Gross Substitutes? Gradient Descent to the Rescue
Yun Kuen Cheung (New York University), Richard Cole (New York University), and Nikhil Devanur (Microsoft Research, Redmond)

Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
David Eisenstat (Brown University) and Philip N. Klein (Brown University)

The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
Albert Gu (Carnegie Mellon University), Anupam Gupta (Carnegie Mellon University), and Amit Kumar (Indian Institute of Technology, Delhi)

On the Non-Uniform Sparsest Cut Problem on Bounded Treewidth Graphs
Anupam Gupta (Carnegie Mellon University), Kunal Talwar (Microsoft Research, Silicon Valley), and David Witmer (Carnegie Mellon University)

Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids [arXiv]
Deeparnab Chakrabarty (Microsoft Research, India), C. Seshadhri (Sandia National Labs, Livermore), and Deeparnab Chakrabarty (Microsoft Research, India)

On the Concrete Efficiency of Probabilistically Checkable Proofs [ECCC]
Eli Ben-Sasson (Technion and MIT), Alessandro Chiesa (MIT), Daniel Genkin (Technion), and Eran Tromer (Tel Aviv University)

Polynomial-time perfect matchings in dense hypergraphs
Peter Keevash (Queen Mary, University of London), Fiachra Knox (Queen Mary, University of London), and Richard Mycroft (University of Birmingham)

Large-Treewidth Graph Decompositions and Applications
Chandra Chekuri (University of Illinois at Urbana-Champaign) and Julia Chuzhoy (Toyota Technological Institute, Chicago)

Differential Privacy for the Analyst via Private Equilibrium Computation [arXiv]
Justin Hsu (University of Pennsylvania), Aaron Roth (University of Pennsylvania), and Jonathan Ullman (Harvard University)

Succinct Sampling from Discrete Distributions [pdf]
Karl Bringmann (Max Planck Institute for Informatics) and Kasper Green Larsen (MADALGO, Aarhus University)

The Orbit Problem in Higher Dimensions [pdf]
Ventsislav Chonev (Oxford University), Joel Ouaknine (Oxford University), and James Worrell (Oxford University)

Homomorphic Fingerprints under Misalignments
Alexandr Andoni (Microsoft Research, Silicon Valley), Assaf Goldberger (Tel Aviv University), Andrew McGregor (University of Massachusetts), and Ely Porat (Bar-Ilan University)

Approximation Resistance on Satisfiable Instances for Predicates with Few Accepting Inputs
Sangxia Huang (KTH Royal Institute of Technology)

An Information Complexity Approach to Extended Formulations [ECCC]
Mark Braverman (Princeton University) and Ankur Moitra (Institute for Advanced Study)

Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem
Niv Buchbinder (Tel Aviv University), Joseph (Seffi) Naor (Technion), and Roy Schwartz (Microsoft Research, Redmond)

A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut [arXiv]
Daniel Kane (Stanford University) and Raghu Meka (Institute for Advanced Study and DIMACS)

Analysis of Spectral Partitioning through Higher Order Spectral Gap [arXiv]
Tsz Chiu Kwok (The Chinese University of Hong Kong), Lap Chi Lau (The Chinese University of Hong Kong), Yin Tat Lee (The Chinese University of Hong Kong), Shayan Oveis Gharan (Stanford University), and Luca Trevisan (Stanford University)

Quantum de Finetti Theorems under Local Measurements with Applications [arXiv]
Fernando G.S.L. Brandao (ETH Zurich) and Aram W. Harrow (University of Washington)

Stochastic Combinatorial Optimization via Poisson Approximation [arXiv]
Jian Li (IIIS, Tsinghua University) and Wen Yuan (IIIS, Tsinghua University)

Natural Proofs, Derandomization, and Lower Bounds [arXiv]
Ryan Williams (Stanford University)

Majority is Stablest : Discrete and SoS [arXiv]
Anindya De (UC Berkeley), Elchanan Mossel (UC Berkeley), and Joe Neeman (UC Berkeley)

Combinatorial Walrasian Equilibrium
Michal Feldman (The Hebrew University of Jerusalem and Harvard University), Nikolai Gravin (Nanyang Technological University), and Brendan Lucier (Microsoft Research, New England)

Simultaneous Auctions are (almost) Efficient [arXiv]
Michal Feldman (The Hebrew University of Jerusalem and Harvard University), Hu Fu (Cornell University), Nikolai Gravin (Nanyang Technological University), and Brendan Lucier (Microsoft Research, New England)

The Geometry of Differential Privacy: The Sparse and Approximate Cases [arXiv]
Aleksandar Nikolov (Rutgers University), Kunal Talwar (Microsoft Research, Silicon Valley), and Li Zhang (Microsoft Research, Silicon Valley)

Fully device-independent quantum key distribution [arXiv]
Umesh Vazirani (UC Berkeley) and Thomas Vidick (MIT)

Delegation for Bounded Space
Yael Tauman Kalai (Microsoft Research, New England), Ran Raz (Weizmann Institute of Science), and Ron D. Rothblum (Weizmann Institute of Science)

A new family of locally correctable codes based on degree-lifted algebraic geometry codes [ECCC]
Eli Ben Sasson (Technion and MIT), Ariel Gabizon (Technion), Yohay Kaplan (Technion), Swatik Kopparty (Rutgers University), and Shubangi Saraf (Rutgers University)

Interactive Proofs of Proximity: Delegating Computation in Sublinear Time
Guy Rothblum (Microsoft Research, Silicon Valley), Salil Vadhan (Harvard University), and Avi Wigderson (Institute for Advanced Studies)

How Robust are Linear Sketches to Adaptive Inputs? [arXiv]
Moritz Hardt (IBM Almaden Research) and David P. Woodruff (IBM Almaden Research)

The Approximate Rank of a Matrix and its Algorithmic Applications [ECCC]
Noga Alon (Tel Aviv University) and Santosh Vempala (Georgia Tech)

Communication Lower Bounds Using Directional Derivatives [ECCC]
Alexander A. Sherstov (UC Los Angelos)

Fast approximation algorithms for the diameter and radius of sparse graphs [pdf]
Liam Roditty (Bar Ilan University) and Virginia Vassilevska Williams (UC Berkeley and Stanford University)

Approximation Guarantees for the Quantum Local Hamiltonian Problem and Limitations for Quantum PCPs
Fernando G.S.L. Brandao (ETH Zurich) and Aram W. Harrow (University of Washington)

On the Impossibility of Approximate Obfuscation and Applications to Resettable Cryptography [ePrint]
Omer Paneth (Boston University) and Nir Bitansky (Tel Aviv University)

Yossi Azar (Tel Aviv University), Ilan Cohen (Tel Aviv University), and Iftah Gamzu (Tel Aviv University)

Tight Bounds for Online Vector Bin Packing
Yossi Azar (Tel Aviv University), Ilan Cohen (Tel Aviv University), Seny Kamara (Microsoft Research, Redmond), and Bruce Shepherd (McGill University)

A Complete Dichotomy Rises from the Capture of Vanishing Signatures [arXiv]
Jin-Yi Cai (University of Wisconsin at Madison), Heng Guo (University of Wisconsin at Madison), and Tyson Williams (University of Wisconsin at Madison)

A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time [arXiv]
Jonathan A. Kelner (MIT), Lorenzo Orecchia (MIT), Aaron Sidford (MIT), and Zeyuan Allen Zhu (MIT)

Low-rank Matrix Completion using Alternating Minimization [arXiv]
Prateek Jain (Microsoft Research, India), Praneeth Netrapalli (The University of Texas at Austin), and Sujay Sanghavi (The University of Texas at Austin)

Multi-Stage Propagation and Quasipolynomial-Time Isomorphism Testing of Steiner 2-Systems
Xi Chen (Columbia University), Xiaorui Sun (Columbia University), and Shang-Hua Teng (University of Southern California)

Strong ETH Holds For Regular Resolution
Chris Beck (Princeton University) and Russell Impagliazzo (UC San Diego)

Statistical Algorithms and a Lower Bound for Detecting Planted Cliques [arXiv]
Vitaly Feldman (IBM Research Almaden), Elena Grigorescu (Purdue University), Lev Reyzin (University of Illinois at Chicago), Santosh Vempala (Georgia Tech), and Ying Xiao (Georgia Tech)

Bottom-k and Priority Sampling, Set Similarity and Subset Sums with Minimal Independence
Mikkel Thorup (AT&T Labs-Research and University of Copenhagen)

Prior-Independent Mechanisms for Scheduling
Shuchi Chawla (University of Wisconsin at Madison), Jason D. Hartline (Northwestern University), David Malec (University of Wisconsin at Madison), and Balasubramanian Sivan (University of Wisconsin at Madison)

From information to exact communication [ECCC]
Mark Braverman (Princeton University), Ankit Garg (Princeton Unviersity), Denis Pankratov (University of Chicago), and Omri Weinstein (Princeton University)

Interactive Channel Capacity [ECCC]
Gillat Kol (Weizmann Institute of Science) and Ran Raz (Weizmann Institute of Science)

Fast Hamiltonicity checking via bases of perfect matchings [arXiv]
Marek Cygan (University of Warsaw), Stefan Kratsch (Max Planck Institute), and Jesper Nederlof (Utrecht University)

Witness Encryption and its Applications
Sanjam Garg (UC Los Angelos), Craig Gentry (IBM Watson Research Lab), Amit Sahai (UC Los Angelos), and Brent Waters (The University of Texas at Austin)

Non-Black-Box Simulation from One-Way Functions And Applications to Resettable Security [ePrint]
Kai-Min Chung (Cornell University), Rafael Pass (Cornell University), and Karn Seth (Cornell University)

A New Approach to Computing Maximum Flows using Electrical Flows
Satish Rao (UC Berkeley) and Nikhil Srivastava (Microsoft Research, India)


FOCS 2012 Accepted Papers (with pdf files)

FOCS 2012 accepted paper list is here. Following are PDF pointers to online versions.

Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies [arXiv]
Thomas Sauerwald and He Sun 

Population Recovery and Partial Identification [pdf]
Avi Wigderson and Amir Yehudayoff 

A direct product theorem for the two-party bounded-round public-coin communication 
complexity [pdf]
Rahul Jain and Attila Pereszlenyi and Penghui Yao 

Positive Results for Concurrently Secure Computation in the Plain Model [pdf]
Vipul Goyal 

Constructive Discrepancy Minimization by Walking on The Edges [arXiv]
Shachar Lovett and Raghu Meka 

Making the Long Code Shorter [pdf]
Boaz Barak and Parikshit Gopalan and Johan Hastad and Raghu Meka and Prasad 
Raghavendra and David Steurer 

On the homotopy test on surfaces [arXiv]
Francis Lazarus and Julien Rivaud 

Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls [arXiv]
Thomas Holenstein and Makrand Sinha 

Partially Symmetric Functions are Efficiently Isomorphism-Testable [arXiv]
Eric Blais and Amit Weinstein and Yuichi Yoshida 

The computational hardness of counting in two-spin models on d-regular graphs [arXiv]
Allan Sly and Nike Sun 

A PTAS for Computing the Supremum of Gaussian Processes	[arXiv]
Raghu Meka 

The tile assembly model is intrinsically universal [arXiv]
David Doty and Jack H. Lutz and Matthew J. Patitz and Robert T. Schweller and 
Scott M. Summers and Damien Woods 

Hardness of Finding Independent Sets in Almost q-Colorable Graphs
Subhash Khot and Rishi Saket 

The Privacy of the Analyst and The Power of the State
Cynthia Dwork and Moni Naor and Salil Vadhan 

Higher Cell Probe Lower Bounds for Evaluating Polynomials
Kasper Green Larsen 

Faster Algorithms for Rectangular Matrix Multiplication	[arXiv]
Francois Le Gall 

A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths 
with Congestion 2
Julia Chuzhoy and Shi Li 

Iterative rounding approximation algorithms for degree-bounded node-connectivity 
network design	[arXiv]
Takuro Fukunaga and R. Ravi 

Pseudorandomness from Shrinkage	[ECCC]
Russell Impagliazzo and Raghu Meka and David Zuckerman 

An additive combinatorics approach relating rank to communication complexity [ECCC]
Eli Ben-Sasson and Shachar Lovett and Noga Ron-Zewi 

Designing FPT algorithms for cut problems using randomized contractions	
Rajesh Chitnis and Marek Cygan and MohammadTaghi Hajiaghayi and Marcin Pilipczuk and 
Micha� Pilipczuk 

Sparse affine-invariant linear codes are locally testable [ECCC]
Eli Ben-Sasson and Noga Ron-Zewi and Madhu Sudan 

A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications 
to the Study of Polynomial Threshold Functions [arXiv]
Daniel M. Kane 

How to Construct Quantum Random Functions [ePrint]
Mark Zhandry 

A weight-scaling algorithm for min-cost imperfect matchings in bipartite graphs	[pdf]
Lyle Ramshaw and Robert E. Tarjan 

Matching with our Eyes Closed	
Gagan Goel and Pushkar Tripathi 

A New Infinity of Distance Oracles for Sparse Graphs
Mihai Patrascu and Liam Roditty and Mikkel Thorup 

A Permanent Approach to the Traveling Salesman Problem
Nisheeth K. Vishnoi 

Everywhere-Sparse Spanners via Dense Subgraphs [arXiv]
Eden Chlamtac and Michael Dinitz and Robert Krauthgamer 

Learning-graph-based Quantum Algorithm for k-distinctness [arXiv]
Aleksandrs Belovs 

Beck's three permutations conjecture: A counterexample and some consequences
Alantha Newman and Ofer Neiman and Aleksandar Nikolov 

Down the Rabbit Hole: Robust Proximity Search and Density Estimation in 
Sublinear Space	[pdf]
Sariel Har-Peled and Nirman Kumar 

On the complexity of finding narrow proofs [arXiv]
Christoph Berkholz 

Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths
Fabrizio Grandoni and Virginia Vassilevska Williams 

LP Rounding for k-Centers with Non-uniform Hard Capacities
Marek Cygan and MohammadTaghi Hajiaghayi and Samir Khuller 

A Tight Combinatorial Algorithm for Submodular Maximization Subject to a 
Matroid Constraint [arXiv]
Yuval Filmus and Justin Ward 

Faster SDP hierarchy solvers for local rounding algorithms
Venkatesan Guruswami and Ali Kemal Sinop 

Combinatorial coloring of 3-colorable graphs [arXiv]
Ken-ichi Kawarabayashi and Mikkel Thorup 

Approximation Limits of Linear Programs (Beyond Hierarchies) [arXiv]
Gábor Braun and Samuel Fiorini and Sebastian Pokutta and David Steurer 

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular 
Niv Buchbinder and Moran Feldman and Joseph (Seffi) Naor and Roy Schwartz 

Lower bounds on Information Complexity via zero-communication protocols 
and applications [arXiv]
Iordanis Kerenidis and Sophie Laplante and Virginie Lerays and Jeremie Roland 
and David Xiao 

Better Pseudorandom Generators from Milder Pseudorandom Restrictions
Parikshit Gopalan and Raghu Meka and Omer Reingold and Luca Trevisan and Salil Vadhan 

Almost Optimal Canonical Property Testers for Satisfiability
Christian Sohler 

On Range Searching with Semialgebraic Sets II
Pankaj K. Agarwal and Jiri Matousek and Micha Sharir 

MIP* contains NEXP
Tsuyoshi Ito and Thomas Vidick 

Geometric Complexity Theory V: Equivalence between blackbox derandomization 
of polynomial identity testing and derandomization of Noether's normalization lemma
Ketan D. Mulmuley 

Single Source - All Sinks Max Flows in Planar Digraphs 
Jakub Lacki and Yahav Nussbaum and Piotr Sankowski and Christian Wulff-Nilsen 

The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy [arXiv] 
Jeremiah Blocki and Avrim Blum and Anupam Datta and Or Sheffet 

Formulas Resilient to Short-Circuit Errors
Yael Kalai and Allison Lewko and Anup Rao 

Efficient Interactive Coding Against Adversarial Noise [ECCC]
Zvika Brakerski and Yael Tauman Kalai 

How to Allocate Tasks Asynchronously
Dan Alistarh and Michael A. Bender and Seth Gilbert and Rachid Guerraoui 

New Limits to Classical and Quantum Instance Compression [pdf]
Andrew Drucker 

Large Deviation Bounds for Decision Trees and Sampling Lower Bounds 
for AC0-circuits [ECCC]
Chris Beck and Russell Impagliazzo and Shachar Lovett 

The Locality of Distributed Symmetry Breaking [arXiv]
Leonid Barenboim and Michael Elkin and Seth Pettie and Johannes Schneider 

Representative sets and irrelevant vertices: New tools for kernelization [arXiv]
Stefan Kratsch and Magnus Wahlström 

Approximating the Expansion Profile and Almost Optimal Local 
Graph Clustering [arXiv]
Shayan Oveis Gharan and Luca Trevisan 

Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, 
Diameter and Matchings [arXiv]
Marek Cygan and Harold N. Gabow and Piotr Sankowski 

Learning Topic Models --- Going beyond SVD [arXiv]	  
Sanjeev Arora and Rong Ge and Ankur Moitra 

Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification
Xin Li 

The power of linear programming for valued CSPs	[arXiv]
Johan Thapper and Stanislav Zivny 

Constructing Non-Malleable Commitments: A Black-Box Approach
Vipul Goyal and Chen-Kuei Lee and Rafail Ostrovsky and Ivan Visconti 

Active Property Testing [pdf]
Maria-Florina Balcan and Eric Blais and Avrim Blum and Liu Yang 

The Dynamics of Influence Systems [arXiv]
Bernard Chazelle 

Online Matching with Stochastic Rewards	
Aranyak Mehta and Debmalya Panigrahi 

Finding Correlations in Subquadratic Time, with Applications to 
Learning Parities and Juntas [ECCC]
Gregory Valiant 

The Exponential Mechanism for Social Welfare: Private, Truthful, 
and Nearly Optimal [arXiv]
Zhiyi Huang and Sampath Kannan 

How to Compute in the Presence of Leakage [ECCC]
Shafi Goldwasser and Guy Rothblum 

On-line Indexing for General Alphabets
Tsvi Kopelowitz 

Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to 
Welfare Maximization
Yang Cai and Constantinos Daskalakis and S. Matthew Weinberg 

Split and Join: Strong Partitions and Universal Steiner Trees for Graphs [arXiv]
Costas Busch and Chinmoy Dutta and Jaikumar Radhakrishnan and 
Rajmohan Rajaraman and Srivathsan Srinivasagopalan 

From the Impossibility of Obfuscation to a New Non-Black-Box 
Simulation Technique  
Nir Bitansky and Omer Paneth 

Quasi-optimal multiplication of linear differential operators
Alexandre Benoit and Alin Bostan and Joris van der Hoeven 

Randomized Greedy Algorithms for the Maximum Matching Problem 
with New Analysis	
Matthias Poloczek and Mario Szegedy 

Concave Generalized Flows with Applications to Market Equilibria [arXiv]
Laszlo A. Vegh 

The Cutting Plane Method is Polynomial for Perfect Matchings
Karthekeyan Chandrasekaran and Laszlo A. Vegh and Santosh S. Vempala 

Computing Multiplicities of Lie Group Representations [arXiv]
Matthias Christandl and Brent Doran and Michael Walter 

A New Direction for Counting Perfect Matchings
Taisuke Izumi and Tadashi Wadayama 

Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms [pdf]
Fedor Fomin and Daniel Lokshtanov and Neeldhara Misra and Saket Saurabh 

Lower Bounds for Interactive Compression by Constant-Depth Circuits
Arkadev Chattopadhyay and Rahul Santhanam

Turing Centennial Celebration – Day 3

Welcome to Day 3 proceedings of Turing Centennial Celebration. See also Day 1 and Day 2.

  • David Harel’s talk titled “Standing on the Shoulders of a Giant”

  • An entertaining musical video about Turing test

  • Avi Wigderson’s tak titled “The Hardness of Proving Computational Hardness”. It is always exciting to watch Avi’s talks.

  • Avi says “Easiness and Hardness are two sides of the same Mobius strip”.

  • Shafi Goldwasser’s talk titled “Pseudo Deterministic Algorithms”

  • Bob Tarjan’s talk titled “Search Tree Mysteries”.

  • Dick Lipton’s talk titled “What Would Turing Be Doing Today?”. As usual Dick’s talk is very entertaining. So I took more pictures.

  • “Making Projectors work” is a grand challenge 🙂

  • Birds vs Frogs
  • End of Dick’s talk

  • Christos Papadimitriou’s talk titled “The Origin of Computable Numbers”. Amazing talk comparing Turing and Darwin.


The three day Turing Centennial celebration comes to an end 😦


Turing Centennial Celebration – Day 2

Welcome to Day 2 proceedings of Turing Centennial Celebration. Click here for yesterday’s events. Thanks to a comment of Noman, live VIDEO is also  available.

  • Martin Davis talks about “Universality is Ubiquitous”. The following slide is from Turing’s 1947 Lecture to the London Mathematical Society.

  • James Murray starts his talk titled “Mathematical Biology, Past, Present and Future: from animal coat patterns to brain tumors to saving marriages”

  • Now I understand “How the leopard gets its spots ?”

  • Barbara Liskov’s talk titled “Programming the Turing Machine”.

  • Tom Mitchell’s talk titled “Never-Ending Language Learning”. The following slide has a quote of Alan Turing, “What we want is a machine that can learn from experience”.

  • Andrew Odlyzko’s talk titled “Turing and the Riemann zeta function”.

  • Ron Rivest’s talk titled “The Growth of Cryptography”

  • Getting ready for dinner

  • Books about Alan Turing

  • Andrew Appel talking about “Turing, Gödel, and Church at Princeton in the 1930s”. This is an inspiring talk about the history of the origins of computing and programming languages at Princeton in 1930s.

  • Jack Emery, producer of the movie talking about his inspiration behind making “Breaking the Code

  • I expected this movie to be a slow documentary. But it exceeded all my expectations. It has sharp dialogues, slick editing and top-notch performances.
  • Here is a sample of a mathematical conversation


  • Here is another sample
  • That’s all for today. Tune in tomorrow for Day 3 proceedings.

Turing Centennial Celebration – Day 1

Let me start this post with a couple of Turing Machine jokes I made up.

How many Turing machines does it take to change a lightbulb ? Just one. Turing machines can simulate each other.

A Turing machine walks into a bar. The bartender asks “what would you like to order”. Turing machine says “I am still deciding”.

As you already know, 2012 is the Year of Turing. Here at Princeton University we are celebrating this occasion from May 10 to 12. For a quick overview of the role of Princeton in the origins of computing watch the following video :

This post is a live blog of the events.

  • Les Valiant’s talk titled “Computer Science as a Natural Science”. I like the following slide saying “Darwin was a computer Scientist. Turing was a natural scientist

  • Andy Yao’s talk titled “Quantum Computing: A Great Science in the Making”. He says “Quantum Computers are coming sooner than you think. Coming soon to a store near you“.

  • Robert Kahn is starting his talk titled “A Systems Approach to Managing Distributed Information”. Among the Turing Award winners invited to this celebration, he is the only one from industry.

  • Richard Karp is starting his talk titled “Theory of Computation as an Enabling Tool for the Sciences”.

  • Richard Karp answering questions.

  • Eric Schmidt’s talk.


That’s all for today. Tune in tomorrow for Day 2 proceedings.


STOC 2012 Accepted Papers (with pdf files)

STOC 2012 accepted paper list is here. Following are PDF pointers to online versions.

    • Separating multilinear branching programs and formulas [ECCC]
      Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff
    • $2^{log^{1-\epsilon} n}$ Hardness for Closest Vector Problem with Preprocessing [ECCC]
      Subhash Khot, Preyas Popat, Nisheeth Vishnoi
    • Determinism versus Nondeterminism with Arithmetic Tests and Computation [ECCC]
      Miklos Ajtai
    • Short Proofs for the Determinant Identities [arXiv]
      Pavel Hrubes, Iddo Tzameret
    • The Cell Probe Complexity of Dynamic Range Counting [arXiv]
      Kasper Green Larsen
    • Subspace Evasive Sets [arXiv]
      Zeev Dvir, Shachar Lovett
    • Monotone expansion [arXiv]
      Jean Bourgain, Amir Yehudayoff
    • Solution of the propeller conjecture in $R^3$ [arXiv]
      Steven Heilman, Aukosh Jagannath, Assaf Naor
    • Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds [arXiv]
      Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald deWolf
    • On Vertex Sparsifiers with Steiner Nodes 
      Julia Chuzhoy
    • Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives [arXiv]
      Laszlo A. Vegh
    • Routing in Undirected Graphs with Constant Congestion [arXiv]
      Julia Chuzoy
    • Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions [ECCC]
      Benny Applebaum
    • Catching the k-NAESAT threshold [arXiv]
      Amin Coja-Oghlan, Konstantinos Panagiotou
    • Edge Transitive Ramanujan Graphs and Highly Symmetric LDPC Good Codes [arXiv]
      Tali Kaufman, Alexander Lubotzky
    • A quantitative Gibbard-Satterthwaite theorem without neutrality [arXiv]
      Elchanan Mossel, Miklos Z. Racz
    • From Irreducible Representations to Locally Decodable Codes [arXiv]
      Kim Efremenko
    • Reconstruction of Depth-4 Multlinear circuits with Top Fan-in 2 [arXiv]
      Ankit Gupta, Neeraj Kayal, Satya Lokam
    • Approximation Algorithms and Hardness of Integral Concurrent Flow 
      Parinya Chalermsook, Julia Chuzoy, Alina Ene, Shi Li
    • Interactive Information Complexity [ECCC]
      Mark Braverman
    • Finding red balloons with split contracts: robustness to individuals’ selfishness [pdf]
      Manuel Cebrian, Lorenzo Coviello, Andrea Vattani, Panagiotis Voulgaris
    • Span Programs for Functions with Constant-Sized 1-certificates [arXiv]
      Aleksandrs Belovs
    • Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space [ECCC]
      Paul Beame, Chris Beck, Russell Impagliazzo
    • Fast Matrix Rank Algorithms and Applications 
      Ho Yee Cheung, Tsz Chiu Kwok, Lap Chi Lau
    • Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications [arXiv]
      Noga Alon, Ankur Moitra, Benny Sudakov
    • When the Cut Condition is Enough; A Complete Characterization for Multiflow Problems in Series-Parallel Networks 
      Amit Chakrabarti, Lisa Fleisher, Christophe Weibel
    • Approximating the Exponential, the Lancoz Method and an $\tilde{O}(m)$-Time Spectral Algorithm for Balanced Separator [arXiv]
      Lorenzo Orecchia, Sushant Sachdeva, Nisheeth Vishnoi
    • Tight Bounds for Monotone Switching Networks via Fourier Analysis
      Siu Man Chan, Aaron Potechin
    • Tight Bounds for Distributed Functional Monitoring [arXiv]
      David P. Woodruff, Qin Zhang
    • Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance [arXiv]
      Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov
    • Folded Codes from Function Field Towers and Improved List Decoding 
      Venkatesan Guruswami, Chaoping Xing
    • Improved Smoothed Analysis of Multiobjective Optimization [arXiv]
      Tobias Brunsch, Heiko Roglin
    • Improving Chrisofides’ Algorithm for the s-t Path TSP [arXiv]
      Hyung-Chan An, Robert Kleinberg, David B. Shmoys
    • Probabilistic existence of rigid combinatorial structures [arXiv]
      Greg Kuperberg, Shachar Lovett, Ron Peled
    • Quantum Money from Hidden Subspaces 
      Scott Aaronson, Paul Christiano
    • A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities 
      Jugal Garg, Ruta Mehta, Milind Sohoni, Vijay V. Vazirani
    • Making Polynomials Robust to Noise 
      Alexander A. Sherstov
    • Online matching with concave returns 
      Nikhil R. Devanur, Kamal Jain
    • Learning Poisson Binomial Distributions [arXiv]
      Constantinos Daskalakis, Ilias Diakonikolas, Rocco Servedio
    • Homomorphic encryption from codes [pdf]
      Andrej Bogdanov, Chin Ho Lee
    • Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates [pdf]
      Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola
    • Polyhedral Clinching Auctions and the Adwords Polytope [arXiv]
      Gagan Goel, Vahab Mirrokni, Renato Paes Leme
    • Complexity of Counting CSP with Complex Weights [arXiv]
      Jin-Yi Cai, Xi Chen
    • Beating Randomized Response on Incoherent Matrices [arXiv]
      Moritz Hardt, Aaron Roth
    • The Multiparty Communication Complexity of Set Disjointness [arXiv]
      Alexander A. Sherstov
    • Nearly Optimal Sparse Fourier Transform [arXiv]
      Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price
    • Certifiable Quantum Dice — Or, testable exponential randomness expansion [arXiv]
      Umesh Vazirani, Thomas Vidick
    • Prior-Free Auctions with Ordered Bidders 
      Stefano Leonardi, Tim Roughgarden
    • Using Petal-Decompositions to Build a Low Stretch Spanning Tree 
      Ittai Abraham, Ofer Neiman
    • On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing [arXiv]
      Michael A. Forbes, Amir Shpilka
    • The traveling salesman problem: low dimensionality implies a polynomial time approximation scheme [arXiv]
      Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer
    • Competitive Contagion in Networks [arXiv]
      Sanjeev Goyal, Michael Kearns
    • Jacobian hit circuits: Hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits [arXiv]
      Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
    • A new point of NP-hardness for Unique Games [pdf]
      Ryan O’Donnell, John Wright
    • Approximation Algorithms for Semi-random Graph Partitioning Problems 
      Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
    • Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs [arXiv]
      Martin Grohe, Daniel Marx
    • On the limits of black-box reductions in mechanism design 
      Shuchi Chawla, Nicole Immorlica, Brendan Lucier
    • Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance labels
      Ittai Abraham, Shiri Chechik, Cyril Gavoille
    • Affine Projections of Polynomials [ECCC]
      Neeraj Kayal
    • From Query Complexity to Computational Complexity [pdf]
      Shahar Dobzinski, Jan Vondrak
    • Multiparty Computation Secure Against Continual Memory Leakage 
      Elette Boyle, Shafi Goldwasser, Abhishek Jain, Yael Tauman Kalai
    • Multiway spectral partitioning and higher-order Cheeger inequalities [arXiv]
      Shayan Oveis Gharan, James R. Lee, Luca Trevisan
    • Budget Feasible Mechanism Design: From Prior-Free to Bayesian 
      Xiaohui Bei, Ning Chen, Nick Gravin, Pinyan Lu
    • Nearly optimal solutions for the Chow Parameters Problem and low- weight approximation of halfspaces 
      Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio
    • The freezing threshold for k-colourings of a random graph 
      Michael Molloy
    • Tight lower bounds for the online labelling problem [arXiv]
      Jan Bulanek, Michal Koucky, Michael Saks
    • Computing a Nonnegative Matrix Factorization – Provably [arXiv]
      Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra
    • Many Sparse Cuts via Higher Eigenvalues [arXiv]
      Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala
    • A Rigorous Analyis of One-Dimensional Schelling Segregation 
      Christina Brandt, Nicole Immorlica, Gautam Kamath, Robert Kleinberg
    • A Near-Linear Time $\eps$-Approximation Algorithm for Geometric Bipartite Matching [pdf]
      R. Sharathkumar, Pankaj K. Agarwal
    • Matroid Prophet Inequalities [arXiv]
      Robert Kleinberg, Matthew Weinberg
    • Rational Proofs 
      Pablo Azar, Silvio Micali
    • Robust satisfiability of constraint satisfaction problems [ECCC]
      Libor Barto, Marcin Kozik
    • On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption 
      Adriana Lopez-Alt, Eran Tromer, Vinod Vaikuntanathan
    • Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars [arXiv]
      Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
    • Unconditionally Differentially Private Mechanisms for Linear Queries 
      Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, Kunal Talwar
    • Multiplying Matrices Faster Than Coppersmith-Winograd [pdf]
      Virginia Vassilevska Williams
    • Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations [arXiv]
      Michel X. Goemans, Neil Olver, Thomas Rothvoss, Rico Zenklusen
    • Minimax Option Pricing Meets Black-Scholes in the Limit [arXiv]
      Jacob Abernethy, Rafael Frongillo, Andre Wibisono
    • Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions [ECCC]
      Salil Vadhan, Colin Jia Zheng
    • Optmal Online Buffer Scheduling for Block Devices 
      Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Raecke
    • On the Virtue of Succinct Proofs: Amplifying Communication Complexity Hardness to Time-Space Trade-offs in Proof Complexity 
      Trinh Huynh, Jacob Nordstrom
    • Strict Fibonacci Heaps 
      Gerth Stolting Brodal, George Lagogiannis, Robert E. Tarjan
    • Design Extractors, Non-Malleable Condensers and Privacy Amplification [ECCC]
      Xin Li
    • Optimal Private Halfspace Counting via Discrepancy 
      S. Muthukrishnan, Aleksandar Nikolov
    • Beyond Laplacians: Faster Approximations of Multicommodity Flow in Undirected Graphs Using Quadratically Coupled Electrical Flows 
      Jonathan A. Kelner, Gary L. Miller, Richard Peng
    • An Algorithmic Characerization of Multi-Dimensional Mechanisms [arXiv]
      Yang Cai, Constantinos Deskalakis, S. Matthew Weinberg
    • Tight Time-Space Tradeoff for Mutual Exclusion 
      Nikhil Bansal, Vibhor Bhatt, Prasad Jayanti, Ranganath Kondapally
    • Hypercontractivity, Sum-of-Squares Proofs, and their Applications 
      Boaz Barak, Aram W. Harrow, Jonathan Kelner, David Steurer, Yuan Zhou
    • Tight RMR Lower Bounds for Randomized Mutual Exclusion George Giakkoupis, Philipp Woelfel