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

6 thoughts on “STOC 2012 Accepted Papers (with pdf files)

  1. Hi Shiva,
    I thought of the following method to encourage publishing the paper (especially in light of the recent Elsevier boycott): mention in your list ONLY the papers that are publicly accessible.

    • Hi Dan,

      Sometimes authors wait for reviewers’ comments, so that they can incorporate the changes suggested by reviewers before making their paper public.


      • We have a long way to make the community of TCS “open-access”.
        If we don’t make steps towards there, it won’t happen.
        I do not question the various reasons (I would really call it excuses) why authors wouldn’t post the papers – now, before submitting, or never.
        BUT: you sent the paper to STOC and it got accepted? POST YOUR PAPER!
        If not, your paper won’t be in the list of files with pdfs on this blog, that’s it.

  2. I second Dan!
    This list is a compilation of PDF’s. If someone just wants to see the list of accepted papers, they can go to the STOC site instead.
    Another alternative is to have two lists, one only with those papers available online, and the other like the one you have now.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s