STOC2014

STOC 2014: 46th Annual Symposium on the Theory of Computing

General Information
Home
Call for Papers
Dates
Call for Workshops
Student Awards
Conference Program
Accepted Papers
Program
Tutorials and Workshops
Attending
Registration
Lodging and Hotels
Room Sharing
Local Information
Day Care
Travel
Travel Support
More Information
Supporters
Contact

Accepted Papers

(with titles as given at time of acceptance)
  1. Every list-decodable code for high noise has abundant near-optimal rate puncturings
    Atri Rudra and Mary Wootters
  2. The Average Sensitivity of an Intersection of Half Spaces
    Daniel M. Kane
  3. Communication is bounded by root of rank
    Shachar Lovett
  4. Approximate Distance Oracles with Constant Query Time
    Shiri Chechik
  5. A Characterization of Locally Testable Affine-Invariant Properties via Decomposition Theorems
    Yuichi Yoshida
  6. Entropy, Optimization and Counting
    Mohit Singh and Nisheeth K. Vishnoi
  7. Non-malleable Codes from Additive Combinatorics
    Divesh Aggarwal, Yevgeniy Dodis and Shachar Lovett
  8. Parallel Algorithms for Geometric Graph Problem
    Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak and Grigory Yaroslavtsev
  9. Strongly polynomial algorithm for generalized flow maximization
    Laszlo A. Vegh
  10. Testing surface area with arbitrary accuracy
    Joe Neeman
  11. On Derandomizing Algorithms that Err Extremely Rarely
    Oded Goldreich and Avi Wigderson
  12. Primal Beats Dual on Online Packing LPs in the Random-Order Model
    Thomas Kesselheim, Klaus Radke, Andreas Toennis and Berthold Voecking
  13. Faster all-pairs shortest paths via circuit complexity
    Ryan Williams
  14. Turnstile Streaming Algorithms Might as Well Be Linear Sketches
    Yi Li, Huy L. Nguyen and David P. Woodruff
  15. Polynomial Bounds for the Grid-Minor Theorem
    Chandra Chekuri and Julia Chuzhoy
  16. How to Delegate Computations: The Power of No-Signaling Proofs
    Yael Tauman Kalai, Ran Raz and Ron D. Rothblum
  17. Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints
    Sungjin Im, Janardhan Kulkarni and Kamesh Munagala
  18. Economic Efficiency Requires Interaction
    Shahar Dobzinski, Noam Nisan and Sigal Oren
  19. Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in any Order
    Michael Forbes, Ramprasad Saptharishi and Amir Shpilka
  20. A Characterization of Approximation Resistance
    Subhash Khot, Madhur Tulsiani and Pratik Worah
  21. Breaking the quadratic barrier for 3 LCC's over the Reals
    Zeev Dvir, Shubhangi Saraf and Avi Wigderson
  22. Optimal CUR Matrix Decompositions
    Christos Boutsidis and David P. Woodruff
  23. From average case complexity to improper learning complexity
    Amit Daniely, Nati Linial and Shai Shalev-Shwartz
  24. Shortest Paths on Polyhedral Surfaces and Terrains
    Siu-Wing Cheng and Jiongxin Jin
  25. The asymptotic k-SAT threshold
    Amin Coja-Oghlan
  26. Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
    Nutan Limaye, Chandan Saha and Srikanth Srinivasan
  27. Lower bounds for depth 4 formulas computing iterated matrix multiplication
    Hervé Fournier, Nutan Limaye, Guillaume Malod and Srikanth Srinivasan
  28. How to Use Indistinguishability Obfuscation: Deniable Encryption, and More
    Amit Sahai and Brent Waters
  29. Private Matchings and Allocations
    Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden and Zhiwei Steven Wu
  30. The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in
    Mrinal Kumar and Shubhangi Saraf
  31. Formulas vs. Circuits for Small Distance Connectivity
    Benjamin Rossman
  32. Query Complexity of Approximate Nash Equilibria
    Yakov Babichenko
  33. Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time
    Michael T. Goodrich
  34. Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing
    Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs and Cliff Stein
  35. An Efficient Parallel Solver for SDD Linear Systems
    Richard Peng and Daniel A. Spielman
  36. Solving SDD Linear Systems in Nearly mlog1/2n Time
    Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup Rao and Shen Chen Xu
  37. The matching polytope has exponential extension complexity
    Thomas Rothvoss
  38. Constant Rank Bimatrix Games are PPAD-hard
    Ruta Mehta
  39. Are Lock-Free Concurrent Algorithms Practically Wait-Free?
    Dan Alistarh, Keren Censor-Hillel and Nir Shavit
  40. Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node-Connectivity Requirements
    Alina Ene and Ali Vakilian
  41. Communication Lower Bounds via Critical Block Sensitivity
    Mika Göös and Toniann Pitassi
  42. The Power of Localization for Efficiently Learning Linear Separators with Noise
    Pranjal Awasthi, Maria Florina Balcan and Philip M. Long
  43. Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications to Distance-Constrained Vehicle Routing
    Zachary Friggstad and Chaitanya Swamy
  44. Constant Factor Approximation for Balanced Cut in the PIE Model
    Konstantin Makarychev, Yury Makarychev and Aravindan Vijayaraghavan
  45. An Almost Optimally-Fair Three-Party Coin-Tossing Protocol
    Iftach Haitner and Eliad Tsfadia
  46. Self-testing quantum dice certified by an uncertainty principle
    Carl A. Miller and Yaoyun Shi
  47. Approximation Algorithms for Bipartite Matching with Metric and Geometric Costs
    Pankaj K. Agarwal and R. Sharathkumar
  48. Coin Flipping of Any Constant Bias Implies One-Way Functions
    Itay Berman, Iftach Haitner and Aris Tentes
  49. A super-polynomial lower bound for regular arithmetic formulas
    Neeraj Kayal, Chandan Saha and Ramprasad Saptharishi
  50. Efficient Density Estimation via Piecewise Polynomial Approximation
    Siu On Chan, Ilias Diakonikolas, Rocco Servedio and Xiaorui Sun
  51. Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
    Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman and Kunal Talwar
  52. Distributed Approximation Algorithms for Weighted Shortest Paths
    Danupon Nanongkai
  53. Deciding first-order properties of nowhere dense graphs
    Martin Grohe, Stephan Kreutzer and Sebastian Siebertz
  54. Efficient deterministic approximate counting for low-degree polynomial threshold functions
    Anindya De and Rocco A. Servedio
  55. Distributed Computability in Byzantine Asynchronous Systems
    Hammurabi Mendes, Christine Tasson and Maurice Herlihy
  56. Optimal Competitive Auctions
    Ning Chen, Pinyan Lu and Nick Gravin
  57. Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture
    Dmitry Gavinsky, Or Meir, Omri Weinstein and Avi Wigderson
  58. Minimum Bisection is Fixed Parameter Tractable
    Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk and Saket Saurabh
  59. Pseudorandom generators with optimal seed length for non-boolean poly-size circuits
    Sergei Artemenko and Ronen Shaltiel
  60. Community detection thresholds and the weak Ramanujan property
    Laurent Massoulie
  61. New algorithms and lower bounds for circuits with linear threshold gates
    Ryan Williams
  62. On the Existence of Extractable One-Way Functions
    Nir Bitansky, Ran Canetti, Omer Paneth and Alon Rosen
  63. A quantum algorithm for computing the unit group of an arbitrary degree number field
    Kirsten Eisentraeger, Sean Hallgren, Alexei Kitaev and Fang Song
  64. Circuits Resilient to Additive Attacks and Secure Multiparty Computation
    Daniel Genkin, Yuval Ishai, Manoj M. Prabhakaran, Amit Sahai and Eran Tromer
  65. Satisfiability threshold for random regular NAE-SAT
    Jian Ding, Allan Sly and Nike Sun
  66. Market Equilibrium: Algorithmic and Complexity Results for a New Class of Non-Separable Utility Functions
    Jugal Garg, Ruta Mehta and Vijay V. Vazirani
  67. From Hierarchical Partitions to Hierarchical Covers: Optimal Fault-Tolerant Spanners for Doubling Metrics
    Shay Solomon
  68. Embedding and Canonizing Graphs of Bounded Genus in Logspace
    Michael Elberfeld and Ken-ichi Kawarabayashi
  69. Multiway Cut, Pairwise Realizable Distributions, and Descending Thresholds
    Ankit Sharma and Jan Vondrak
  70. The Sample Complexity of Revenue Maximization
    Richard Cole and Tim Roughgarden
  71. Exponential improvement in precision for simulating sparse Hamiltonians
    Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari and Rolando D. Somma
  72. Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Path on Directed Graphs
    Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai
  73. Bandits with Switching Costs: T2/3 Regret
    Ofer Dekel, Jian Ding, Tomer Koren and Yuval Peres
  74. Homological product codes
    Sergey Bravyi and Matthew Hastings
  75. Breaking the Minsky-Papert Barrier for Constant-Depth Circuits
    Alexander A. Sherstov
  76. Optimal Error Rates for Interactive Coding: Adaptivity and Other Settings
    Mohsen Ghaffari, Bernhard Haeupler and Madhu Sudan
  77. Infinite Randomness Expansion with a Constant Number of Devices
    Matthew Coudron and Henry Yuen
  78. Computing with a full memory
    Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff and Florian Speelman
  79. Fourier PCA
    Navin Goyal, Santosh Vempala and Ying Xiao
  80. An Excluded Half-Integral Grid Theorem for Digraphs and the Directed Disjoint Paths Problem
    Ken-ichi Kawarabayashi, Yusuke Kobayashi and Stephan Kreutzer
  81. Fingerprinting Codes and the Price of Approximate Differential Privacy
    Mark Bun, Jonathan Ullman and Salil Vadhan
  82. Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region
    Andreas Galanis, Daniel Stefankovic and Eric Vigoda
  83. Black-Box Non-Black-Box Zero Knowledge via Extendable Merkle Trees
    Vipul Goyal, Rafail Ostrovsky, Alessandra Scafuro and Ivan Visconti
  84. Online local learning
    Paul F. Christiano
  85. Smoothed Analysis of Tensor Decompositions
    Aditya Bhaskara, Moses Charikar, Ankur Moitra and Aravindan Vijayaraghavan
  86. Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
    Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan and Girish Varma
  87. Randomized Response Strikes Back: Private Singular Subspace Computation with (Nearly) Optimal Error Guarantees
    Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta and Li Zhang
  88. Analytical Approach to Parallel Repetition
    Irit Dinur and David Steurer
  89. Linear time construction of compressed text indices in compact space
    Djamal Belazzougui
  90. Rounding Sum-of-Squares Relaxations
    Boaz Barak, Jonathan Kelner and David Steurer
  91. Testing with respect to Lp distances
    Piotr Berman, Sofya Raskhodnikova and Grigory Yaroslavtsev