STOC2012

List of Accepted Papers

  • Separating multilinear branching programs and formulas
    Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff

  • $2^{log^{1-\epsilon} n}$ Hardness for Closest Vector Problem with Preprocessing
    Subhash Khot, Preyas Popat, Nisheeth Vishnoi

  • Determinism versus Nondeterminism with Arithmetic Tests and Computation
    Miklos Ajtai

  • Short Proofs for the Determinant Identities
    Pavel Hrubes, Iddo Tzameret

  • The Cell Probe Complexity of Dynamic Range Counting
    Kasper Green Larsen

  • Subspace Evasive Sets
    Zeev Dvir, Shachar Lovett

  • Monotone expansion
    Jean Bourgain, Amir Yehudayoff

  • Solution of the propeller conjecture in $R^3$
    Steven Heilman, Aukosh Jagannath, Assaf Naor

  • Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds
    Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf

  • On Vertex Sparsifiers with Steiner Nodes
    Julia Chuzhoy

  • Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
    Laszlo A. Vegh

  • Routing in Undirected Graphs with Constant Congestion
    Julia Chuzhoy

  • Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions
    Benny Applebaum

  • Catching the k-NAESAT threshold
    Amin Coja-Oghlan, Konstantinos Panagiotou

  • Edge Transitive Ramanujan Graphs and Highly Symmetric LDPC Good Codes
    Tali Kaufman, Alexander Lubotzky

  • A quantitative Gibbard-Satterthwaite theorem without neutrality
    Elchanan Mossel, Miklos Z. Racz

  • From Irreducible Representations to Locally Decodable Codes
    Klim Efremenko

  • Reconstruction of Depth-4 Multlinear circuits with Top Fan-in 2
    Ankit Gupta, Neeraj Kayal, Satya Lokam

  • Approximation Algorithms and Hardness of Integral Concurrent Flow
    Parinya Chalermsook, Julia Chuzhoy, Alina Ene, Shi Li

  • Interactive Information Complexity
    Mark Braverman

  • Finding red balloons with split contracts: robustness to individuals' selfishness
    Manuel Cebrian, Lorenzo Coviello, Andrea Vattani, Panagiotis Voulgaris

  • Span Programs for Functions with Constant-Sized 1-certificates
    Aleksandrs Belovs

  • Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
    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
    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
    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
    David P. Woodruff, Qin Zhang

  • Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance
    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
    Tobias Brunsch, Heiko Roglin

  • Improving Chrisofides' Algorithm for the s-t Path TSP
    Hyung-Chan An, Robert Kleinberg, David B. Shmoys

  • Probabilistic existence of rigid combinatorial structures
    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
    Constantinos Daskalakis, Ilias Diakonikolas, Rocco Servedio

  • Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
    Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

  • Polyhedral Clinching Auctions and the Adwords Polytope
    Gagan Goel, Vahab Mirrokni, Renato Paes Leme

  • Complexity of Counting CSP with Complex Weights
    Jin-Yi Cai, Xi Chen

  • Beating Randomized Response on Incoherent Matrices
    Moritz Hardt, Aaron Roth

  • The Multiparty Communication Complexity of Set Disjointness
    Alexander A. Sherstov

  • Nearly Optimal Sparse Fourier Transform
    Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price

  • Certifiable Quantum Dice -- Or, testable exponential randomness expansion
    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
    Michael A. Forbes, Amir Shpilka

  • The traveling salesman problem: low dimensionality implies a polynomial time approximation scheme
    Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer

  • Competitive Contagion in Networks
    Sanjeev Goyal, Michael Kearns

  • Jacobian hit circuits: Hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits
    Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

  • A new point of NP-hardness for Unique Games
    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
    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
    Neeraj Kayal

  • From Query Complexity to Computational Complexity
    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
    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
    Jan Bulanek, Michal Koucky, Michael Saks

  • Computing a Nonnegative Matrix Factorization - Provably
    Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra

  • Many Sparse Cuts via Higher Eigenvalues
    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
    R. Sharathkumar, Pankaj K. Agarwal

  • Matroid Prophet Inequalities
    Robert Kleinberg, Matthew Weinberg

  • Rational Proofs
    Pablo Azar, Silvio Micali

  • Robust satisfiability of constraint satisfaction problems
    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
    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
    Virginia Vassilevska Williams

  • Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations
    Michel X. Goemans, Neil Olver, Thomas Rothvoss, Rico Zenklusen

  • Minimax Option Pricing Meets Black-Scholes in the Limit
    Jacob Abernethy, Rafael Frongillo, Andre Wibisono

  • Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions
    Salil Vadhan, Colin Jia Zheng

  • Optimal 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
    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 Characterization of Multi-Dimensional Mechanisms
    Yang Cai, Constantinos Daskalakis, 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