stoc2014-papers

STOC is the Symposium on Theory of Computation. The 2014 edition will be held May 31 to June 3, in New York, New York. The list of accepted papers is available here; this is an attempt to collect the preprints in one place.

Patches are welcome. Please send a pull request or an email. (Thanks to gasche for the idea.)

STOC

• Every list-decodable code for high noise has abundant near-optimal rate puncturings.
  (arXiv).
  Atri Rudra and Mary Wootters

• The Average Sensitivity of an Intersection of Half Spaces.
  (arXiv).
  Daniel M. Kane

• Communication is bounded by root of rank.
  (arXiv).
  Shachar Lovett

• Approximate Distance Oracles with Constant Query Time.
  (arXiv).
  Shiri Chechik

• A Characterization of Locally Testable Affine-Invariant Properties via Decomposition Theorems.
  (arXiv).
  Yuichi Yoshida

• Entropy, Optimization and Counting.
  (arXiv).
  Mohit Singh and Nisheeth K. Vishnoi

• Non-malleable Codes from Additive Combinatorics.
  (IACR).
  Divesh Aggarwal, Yevgeniy Dodis and Shachar Lovett

• Parallel Algorithms for Geometric Graph Problem.
  (arXiv).
  Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak and Grigory Yaroslavtsev

• Strongly polynomial algorithm for generalized flow maximization.
  (arXiv).
  Laszlo A. Vegh

• Testing surface area with arbitrary accuracy.
  (arXiv).
  Joe Neeman

• On Derandomizing Algorithms that Err Extremely Rarely.
  (ECCC).
  Oded Goldreich and Avi Wigderson

• Primal Beats Dual on Online Packing LPs in the Random-Order Model.
  (arXiv).
  Thomas Kesselheim, Klaus Radke, Andreas Toennis and Berthold Voecking

• Faster all-pairs shortest paths via circuit complexity.
  (arXiv).
  Ryan Williams

• Turnstile Streaming Algorithms Might as Well Be Linear Sketches.
  (Preprint).
  Yi Li, Huy L. Nguyen and David P. Woodruff

• Polynomial Bounds for the Grid-Minor Theorem.
  (arXiv).
  Chandra Chekuri and Julia Chuzhoy

• How to Delegate Computations: The Power of No-Signaling Proofs.
  (IACR).
  Yael Tauman Kalai, Ran Raz and Ron D. Rothblum

• Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints.
  (arXiv).
  Sungjin Im, Janardhan Kulkarni and Kamesh Munagala

• Economic Efficiency Requires Interaction.
  (arXiv).
  Shahar Dobzinski, Noam Nisan and Sigal Oren

• Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in any Order.
  (arXiv).
  Michael Forbes, Ramprasad Saptharishi and Amir Shpilka

• A Characterization of Approximation Resistance.
  (arXiv).
  Subhash Khot, Madhur Tulsiani and Pratik Worah

• Breaking the quadratic barrier for 3 LCC's over the Reals.
  (arXiv).
  Zeev Dvir, Shubhangi Saraf and Avi Wigderson

• Optimal CUR Matrix Decompositions.
  (No preprint found).
  Christos Boutsidis and David P. Woodruff

• From average case complexity to improper learning complexity.
  (arXiv).
  Amit Daniely, Nati Linial and Shai Shalev-Shwartz

• Shortest Paths on Polyhedral Surfaces and Terrains.
  (No preprint found).
  Siu-Wing Cheng and Jiongxin Jin

• The asymptotic k-SAT threshold.
  (arXiv).
  Amin Coja-Oghlan

• Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas.
  (Preprint).
  Nutan Limaye, Chandan Saha and Srikanth Srinivasan

• Lower bounds for depth 4 formulas computing iterated matrix multiplication.
  (ECCC).
  Hervé Fournier, Nutan Limaye, Guillaume Malod and Srikanth Srinivasan

• How to Use Indistinguishability Obfuscation: Deniable Encryption, and More.
  (IACR).
  Amit Sahai and Brent Waters

• Private Matchings and Allocations.
  (arXiv).
  Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden and Zhiwei Steven Wu

• The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in.
  (arXiv).
  Mrinal Kumar and Shubhangi Saraf

• Formulas vs. Circuits for Small Distance Connectivity.
  (arXiv).
  Benjamin Rossman

• Query Complexity of Approximate Nash Equilibria.
  (arXiv).
  Yakov Babichenko

• Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in $O(n \log n)$ Time.
  (arXiv).
  Michael T. Goodrich

• Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing.
  (arXiv).
  Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs and Cliff Stein

• An Efficient Parallel Solver for SDD Linear Systems.
  (arXiv).
  Richard Peng and Daniel A. Spielman

• Solving SDD Linear Systems in Nearly $m \log^{1/2} n$ Time.
  (No preprint found).
  Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup Rao and Shen Chen Xu

• The matching polytope has exponential extension complexity.
  (arXiv).
  Thomas Rothvoss

• Constant Rank Bimatrix Games are PPAD-hard.
  (arXiv).
  Ruta Mehta

• Are Lock-Free Concurrent Algorithms Practically Wait-Free?
  (arXiv).
  Dan Alistarh, Keren Censor-Hillel and Nir Shavit

• Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node-Connectivity Requirements.
  (No preprint found).
  Alina Ene and Ali Vakilian

• Communication Lower Bounds via Critical Block Sensitivity.
  (arXiv).
  Mika Göös and Toniann Pitassi

• The Power of Localization for Efficiently Learning Linear Separators with Noise.
  (arXiv).
  Pranjal Awasthi, Maria Florina Balcan and Philip M. Long

• Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications to Distance-Constrained Vehicle Routing.
  (arXiv).
  Zachary Friggstad and Chaitanya Swamy

• Constant Factor Approximation for Balanced Cut in the PIE Model.
  (No preprint found).
  Konstantin Makarychev, Yury Makarychev and Aravindan Vijayaraghavan

• An Almost Optimally-Fair Three-Party Coin-Tossing Protocol.
  (Preprint).
  Iftach Haitner and Eliad Tsfadia

• Self-testing quantum dice certified by an uncertainty principle.
  (No preprint found).
  Carl A. Miller and Yaoyun Shi

• Approximation Algorithms for Bipartite Matching with Metric and Geometric Costs.
  (Preprint).
  Pankaj K. Agarwal and R. Sharathkumar

• Coin Flipping of Any Constant Bias Implies One-Way Functions.
  (No preprint found).
  Itay Berman, Iftach Haitner and Aris Tentes

• A super-polynomial lower bound for regular arithmetic formulas.
  (ECCC).
  Neeraj Kayal, Chandan Saha and Ramprasad Saptharishi

• Efficient Density Estimation via Piecewise Polynomial Approximation.
  (arXiv).
  Siu On Chan, Ilias Diakonikolas, Rocco Servedio and Xiaorui Sun

• Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs.
  (arXiv).
  Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman and Kunal Talwar

• Distributed Approximation Algorithms for Weighted Shortest Paths.
  (arXiv).
  Danupon Nanongkai

• Deciding first-order properties of nowhere dense graphs.
  (arXiv).
  Martin Grohe, Stephan Kreutzer and Sebastian Siebertz

• Efficient deterministic approximate counting for low-degree polynomial threshold functions.
  (arXiv).
  Anindya De and Rocco A. Servedio

• Distributed Computability in Byzantine Asynchronous Systems.
  (arXiv).
  Hammurabi Mendes, Christine Tasson and Maurice Herlihy

• Optimal Competitive Auctions.
  (arXiv).
  Ning Chen, Pinyan Lu and Nick Gravin

• Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture.
  (ECCC).
  Dmitry Gavinsky, Or Meir, Omri Weinstein and Avi Wigderson

• Minimum Bisection is Fixed Parameter Tractable.
  (arXiv).
  Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk and Saket Saurabh

• Pseudorandom generators with optimal seed length for non-boolean poly-size circuits.
  (No preprint found).
  Sergei Artemenko and Ronen Shaltiel

• Community detection thresholds and the weak Ramanujan property.
  (arXiv).
  Laurent Massoulie

• New algorithms and lower bounds for circuits with linear threshold gates.
  (arXiv).
  Ryan Williams

• On the Existence of Extractable One-Way Functions.
  (ECCC).
  Nir Bitansky, Ran Canetti, Omer Paneth and Alon Rosen

• A quantum algorithm for computing the unit group of an arbitrary degree number field.
  (No preprint found).
  Kirsten Eisentraeger, Sean Hallgren, Alexei Kitaev and Fang Song

• Circuits Resilient to Additive Attacks and Secure Multiparty Computation.
  (No preprint found).
  Daniel Genkin, Yuval Ishai, Manoj M. Prabhakaran, Amit Sahai and Eran Tromer

• Satisfiability threshold for random regular NAE-SAT.
  (arXiv).
  Jian Ding, Allan Sly and Nike Sun

• Market Equilibrium: Algorithmic and Complexity Results for a New Class of Non-Separable Utility Functions.
  (Preprint).
  Jugal Garg, Ruta Mehta and Vijay V. Vazirani

• From Hierarchical Partitions to Hierarchical Covers: Optimal Fault-Tolerant Spanners for Doubling Metrics.
  (arXiv).
  Shay Solomon

• Embedding and Canonizing Graphs of Bounded Genus in Logspace.
  (No preprint found).
  Michael Elberfeld and Ken-ichi Kawarabayashi

• Multiway Cut, Pairwise Realizable Distributions, and Descending Thresholds.
  (arXiv).
  Ankit Sharma and Jan Vondrak

• The Sample Complexity of Revenue Maximization.
  (Preprint).
  Richard Cole and Tim Roughgarden

• Exponential improvement in precision for simulating sparse Hamiltonians.
  (arXiv).
  Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari and Rolando D. Somma

• Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Path on Directed Graphs.
  (No preprint found).
  Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai

• Bandits with Switching Costs: $T^{2/3}$ Regret.
  (arXiv).
  Ofer Dekel, Jian Ding, Tomer Koren and Yuval Peres

• Homological product codes.
  (arXiv).
  Sergey Bravyi and Matthew Hastings

• Breaking the Minsky-Papert Barrier for Constant-Depth Circuits.
  (ECCC).
  Alexander A. Sherstov

• Optimal Error Rates for Interactive Coding: Adaptivity and Other Settings.
  (arXiv).
  Mohsen Ghaffari, Bernhard Haeupler and Madhu Sudan

• Infinite Randomness Expansion with a Constant Number of Devices.
  (arXiv).
  Matthew Coudron and Henry Yuen

• Computing with a full memory.
  (ECCC).
  Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff and Florian Speelman

• Fourier PCA.
  (arXiv).
  Navin Goyal, Santosh Vempala and Ying Xiao

• An Excluded Half-Integral Grid Theorem for Digraphs and the Directed Disjoint Paths Problem.
  (No preprint found).
  Ken-ichi Kawarabayashi, Yusuke Kobayashi and Stephan Kreutzer

• Fingerprinting Codes and the Price of Approximate Differential Privacy.
  (arXiv).
  Mark Bun, Jonathan Ullman and Salil Vadhan

• Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region.
  (arXiv).
  Andreas Galanis, Daniel Stefankovic and Eric Vigoda

• Black-Box Non-Black-Box Zero Knowledge via Extendable Merkle Trees.
  (No preprint found).
  Vipul Goyal, Rafail Ostrovsky, Alessandra Scafuro and Ivan Visconti

• Online local learning.
  (arXiv).
  Paul F. Christiano

• Smoothed Analysis of Tensor Decompositions.
  (arXiv).
  Aditya Bhaskara, Moses Charikar, Ankur Moitra and Aravindan Vijayaraghavan

• Super-polylogarithmic hypergraph coloring hardness via low-degree long codes.
  (arXiv).
  Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan and Girish Varma

• Randomized Response Strikes Back: Private Singular Subspace Computation with (Nearly) Optimal Error Guarantees.
  (No preprint found).
  Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta and Li Zhang

• Analytical Approach to Parallel Repetition.
  (arXiv).
  Irit Dinur and David Steurer

• Linear time construction of compressed text indices in compact space.
  (arXiv).
  Djamal Belazzougui

• Rounding Sum-of-Squares Relaxations.
  (arXiv).
  Boaz Barak, Jonathan Kelner and David Steurer

• Testing with respect to $L_p$ distances.
  (No preprint found).
  Piotr Berman, Sofya Raskhodnikova and Grigory Yaroslavtsev