ACM Symposium on Theory of Computing, STOC 2014


The information below was collected semi-automatically. The authors have not yet been given the opportunity to verify the data.
[?] We ask all authors to verify the information we have about their papers, in particular the location of any supporting artifacts. We send out emails to authors asking them to update or verify this information incrementally, one conference at a time. For conferences where these emails have yet to be sent out we present the information in gray text.
Title/Authors Title Research Artifacts
[?] A research artifact is any by-product of a research project that is not directly included in the published research paper. In Computer Science research this is often source code and data sets, but it could also be media, documentation, inputs to proof assistants, shell-scripts to run experiments, etc.
Details

Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements

Alina Ene, Ali Vakilian

Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements

Details
Discussion Comments: 0
Verification: Authors have not verified information

How to delegate computations: the power of no-signaling proofs

Yael Tauman Kalai, Ran Raz, Ron D. Rothblum

How to delegate computations: the power of no-signaling proofs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Black-box non-black-box zero knowledge

Vipul Goyal, Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti

Black-box non-black-box zero knowledge

Details
Discussion Comments: 0
Verification: Authors have not verified information

Breaking the minsky-papert barrier for constant-depth circuits

Alexander A. Sherstov

Breaking the minsky-papert barrier for constant-depth circuits

Details
Discussion Comments: 0
Verification: Author has not verified information

Lp-testing

Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev

Lp-testing

Details
Discussion Comments: 0
Verification: Authors have not verified information

An almost-optimally fair three-party coin-flipping protocol

Iftach Haitner, Eliad Tsfadia

An almost-optimally fair three-party coin-flipping protocol

Details
Discussion Comments: 0
Verification: Authors have not verified information

The asymptotic k-SAT threshold

Amin Coja-Oghlan

The asymptotic k-SAT threshold

Details
Discussion Comments: 0
Verification: Author has not verified information

A characterization of locally testable affine-invariant properties via decomposition theorems

Yuichi Yoshida

A characterization of locally testable affine-invariant properties via decomposition theorems

Details
Discussion Comments: 0
Verification: Author has not verified information

Embedding and canonizing graphs of bounded genus in logspace

Michael Elberfeld, Ken-ichi Kawarabayashi

Embedding and canonizing graphs of bounded genus in logspace

Details
Discussion Comments: 0
Verification: Authors have not verified information

Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions

Jugal Garg, Ruta Mehta, Vijay V. Vazirani

Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Minimum bisection is fixed parameter tractable

Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh

Minimum bisection is fixed parameter tractable

Details
Discussion Comments: 0
Verification: Authors have not verified information

Analyze gauss: optimal bounds for privacy-preserving principal component analysis

Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, Li Zhang

Analyze gauss: optimal bounds for privacy-preserving principal component analysis

Details
Discussion Comments: 0
Verification: Authors have not verified information

Hitting sets for multilinear read-once algebraic branching programs, in any order

Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka

Hitting sets for multilinear read-once algebraic branching programs, in any order

Details
Discussion Comments: 0
Verification: Authors have not verified information

Circuits resilient to additive attacks with applications to secure computation

Daniel Genkin, Yuval Ishai, Manoj Prabhakaran, Amit Sahai, Eran Tromer

Circuits resilient to additive attacks with applications to secure computation

Details
Discussion Comments: 0
Verification: Authors have not verified information

Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs

Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, Kunal Talwar

Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Lower bounds for depth 4 formulas computing iterated matrix multiplication

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

Lower bounds for depth 4 formulas computing iterated matrix multiplication

Details
Discussion Comments: 0
Verification: Authors have not verified information

Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

An efficient parallel solver for SDD linear systems

Richard Peng, Daniel A. Spielman

An efficient parallel solver for SDD linear systems

Details
Discussion Comments: 0
Verification: Authors have not verified information

Query complexity of approximate nash equilibria

Yakov Babichenko

Query complexity of approximate nash equilibria

Details
Discussion Comments: 0
Verification: Author has not verified information

Parallel algorithms for geometric graph problems

Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev

Parallel algorithms for geometric graph problems

Details
Discussion Comments: 0
Verification: Authors have not verified information

Rounding sum-of-squares relaxations

Boaz Barak, Jonathan A. Kelner, David Steurer

Rounding sum-of-squares relaxations

Details
Discussion Comments: 0
Verification: Authors have not verified information

A quantum algorithm for computing the unit group of an arbitrary degree number field

Kirsten Eisenträger, Sean Hallgren, Alexei Y. Kitaev, Fang Song

A quantum algorithm for computing the unit group of an arbitrary degree number field

Details
Discussion Comments: 0
Verification: Authors have not verified information

On derandomizing algorithms that err extremely rarely

Oded Goldreich, Avi Wigderson

On derandomizing algorithms that err extremely rarely

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fingerprinting codes and the price of approximate differential privacy

Mark Bun, Jonathan Ullman, Salil P. Vadhan

Fingerprinting codes and the price of approximate differential privacy

Details
Discussion Comments: 0
Verification: Authors have not verified information

Economic efficiency requires interaction

Shahar Dobzinski, Noam Nisan, Sigal Oren

Economic efficiency requires interaction

Details
Discussion Comments: 0
Verification: Authors have not verified information

Primal beats dual on online packing LPs in the random-order model

Thomas Kesselheim, Klaus Radke, Andreas Tönnis, Berthold Vöcking

Primal beats dual on online packing LPs in the random-order model

Details
Discussion Comments: 0
Verification: Authors have not verified information

Analytical approach to parallel repetition

Irit Dinur, David Steurer

Analytical approach to parallel repetition

Details
Discussion Comments: 0
Verification: Authors have not verified information

Testing surface area with arbitrary accuracy

Joe Neeman

Testing surface area with arbitrary accuracy

Details
Discussion Comments: 0
Verification: Author has not verified information

Shortest paths on polyhedral surfaces and terrains

Siu-Wing Cheng, Jiongxin Jin

Shortest paths on polyhedral surfaces and terrains

Details
Discussion Comments: 0
Verification: Authors have not verified information

Private matchings and allocations

Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, Zhiwei Steven Wu

Private matchings and allocations

Details
Discussion Comments: 0
Verification: Authors have not verified information

A super-polynomial lower bound for regular arithmetic formulas

Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi

A super-polynomial lower bound for regular arithmetic formulas

Details
Discussion Comments: 0
Verification: Authors have not verified information

Constant rank bimatrix games are PPAD-hard

Ruta Mehta

Constant rank bimatrix games are PPAD-hard

Details
Discussion Comments: 0
Verification: Author has not verified information

Entropy, optimization and counting

Mohit Singh, Nisheeth K. Vishnoi

Entropy, optimization and counting

Details
Discussion Comments: 0
Verification: Authors have not verified information

A strongly polynomial algorithm for generalized flow maximization

László A. Végh

A strongly polynomial algorithm for generalized flow maximization

Details
Discussion Comments: 0
Verification: Author has not verified information

Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture

Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson

Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture

Details
Discussion Comments: 0
Verification: Authors have not verified information

Formulas vs. circuits for small distance connectivity

Benjamin Rossman

Formulas vs. circuits for small distance connectivity

Details
Discussion Comments: 0
Verification: Author has not verified information

Non-malleable codes from additive combinatorics

Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett

Non-malleable codes from additive combinatorics

Details
Discussion Comments: 0
Verification: Authors have not verified information

Coin flipping of any constant bias implies one-way functions

Itay Berman, Iftach Haitner, Aris Tentes

Coin flipping of any constant bias implies one-way functions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Polynomial bounds for the grid-minor theorem

Chandra Chekuri, Julia Chuzhoy

Polynomial bounds for the grid-minor theorem

Details
Discussion Comments: 0
Verification: Authors have not verified information

Pseudorandom generators with optimal seed length for non-boolean poly-size circuits

Sergei Artemenko, Ronen Shaltiel

Pseudorandom generators with optimal seed length for non-boolean poly-size circuits

Details
Discussion Comments: 0
Verification: Authors have not verified information

Communication lower bounds via critical block sensitivity

Mika Göös, Toniann Pitassi

Communication lower bounds via critical block sensitivity

Details
Discussion Comments: 0
Verification: Authors have not verified information

Distributed approximation algorithms for weighted shortest paths

Danupon Nanongkai

Distributed approximation algorithms for weighted shortest paths

Details
Discussion Comments: 0
Verification: Author has not verified information

Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas

Details
Discussion Comments: 0
Verification: Authors have not verified information

Exponential improvement in precision for simulating sparse Hamiltonians

Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, Rolando D. Somma

Exponential improvement in precision for simulating sparse Hamiltonians

Details
Discussion Comments: 0
Verification: Authors have not verified information

Optimal competitive auctions

Ning Chen, Nick Gravin, Pinyan Lu

Optimal competitive auctions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Constant factor approximation for balanced cut in the PIE model

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

Constant factor approximation for balanced cut in the PIE model

Details
Discussion Comments: 0
Verification: Authors have not verified information

Community detection thresholds and the weak Ramanujan property

Laurent Massoulié

Community detection thresholds and the weak Ramanujan property

Details
Discussion Comments: 0
Verification: Author has not verified information

Linear time construction of compressed text indices in compact space

Djamal Belazzougui

Linear time construction of compressed text indices in compact space

Details
Discussion Comments: 0
Verification: Author has not verified information

Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices

Carl A. Miller, Yaoyun Shi

Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices

Details
Discussion Comments: 0
Verification: Authors have not verified information

Deciding first-order properties of nowhere dense graphs

Martin Grohe, Stephan Kreutzer, Sebastian Siebertz

Deciding first-order properties of nowhere dense graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Faster all-pairs shortest paths via circuit complexity

Ryan Williams

Faster all-pairs shortest paths via circuit complexity

Details
Discussion Comments: 0
Verification: Author has not verified information

Efficient deterministic approximate counting for low-degree polynomial threshold functions

Anindya De, Rocco A. Servedio

Efficient deterministic approximate counting for low-degree polynomial threshold functions

Details
Discussion Comments: 0
Verification: Authors have not verified information

The sample complexity of revenue maximization

Richard Cole, Tim Roughgarden

The sample complexity of revenue maximization

Details
Discussion Comments: 0
Verification: Authors have not verified information

The average sensitivity of an intersection of half spaces

Daniel M. Kane

The average sensitivity of an intersection of half spaces

Details
Discussion Comments: 0
Verification: Author has not verified information

Bandits with switching costs: T2/3 regret

Ofer Dekel, Jian Ding, Tomer Koren, Yuval Peres

Bandits with switching costs: T2/3 regret

Details
Discussion Comments: 0
Verification: Authors have not verified information

Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region

Andreas Galanis, Daniel Stefankovic, Eric Vigoda

Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region

Details
Discussion Comments: 0
Verification: Authors have not verified information

Communication is bounded by root of rank

Shachar Lovett

Communication is bounded by root of rank

Details
Discussion Comments: 0
Verification: Author has not verified information

Every list-decodable code for high noise has abundant near-optimal rate puncturings

Atri Rudra, Mary Wootters

Every list-decodable code for high noise has abundant near-optimal rate puncturings

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing

Zachary Friggstad, Chaitanya Swamy

Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing

Details
Discussion Comments: 0
Verification: Authors have not verified information

Computing with a full memory: catalytic space

Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman

Computing with a full memory: catalytic space

Details
Discussion Comments: 0
Verification: Authors have not verified information

Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing

Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein

Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximate distance oracles with constant query time

Shiri Chechik

Approximate distance oracles with constant query time

Details
Discussion Comments: 0
Verification: Author has not verified information

New algorithms and lower bounds for circuits with linear threshold gates

Ryan Williams

New algorithms and lower bounds for circuits with linear threshold gates

Details
Discussion Comments: 0
Verification: Author has not verified information

The limits of depth reduction for arithmetic formulas: it's all about the top fan-in

Mrinal Kumar, Shubhangi Saraf

The limits of depth reduction for arithmetic formulas: it's all about the top fan-in

Details
Discussion Comments: 0
Verification: Authors have not verified information

Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time

Michael T. Goodrich

Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time

Details
Discussion Comments: 0
Verification: Author has not verified information

From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics

Shay Solomon

From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics

Details
Discussion Comments: 0
Verification: Author has not verified information

Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints

Sungjin Im, Janardhan Kulkarni, Kamesh Munagala

Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints

Details
Discussion Comments: 0
Verification: Authors have not verified information

Infinite randomness expansion with a constant number of devices

Matthew Coudron, Henry Yuen

Infinite randomness expansion with a constant number of devices

Details
Discussion Comments: 0
Verification: Authors have not verified information

How to use indistinguishability obfuscation: deniable encryption, and more

Amit Sahai, Brent Waters

How to use indistinguishability obfuscation: deniable encryption, and more

Details
Discussion Comments: 0
Verification: Authors have not verified information

Smoothed analysis of tensor decompositions

Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan

Smoothed analysis of tensor decompositions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Homological product codes

Sergey Bravyi, Matthew B. Hastings

Homological product codes

Details
Discussion Comments: 0
Verification: Authors have not verified information

Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma

Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the existence of extractable one-way functions

Nir Bitansky, Ran Canetti, Omer Paneth, Alon Rosen

On the existence of extractable one-way functions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Solving SDD linear systems in nearly mlog1/2n time

Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup Rao, Shen Chen Xu

Solving SDD linear systems in nearly mlog1/2n time

Details
Discussion Comments: 0
Verification: Authors have not verified information

The matching polytope has exponential extension complexity

Thomas Rothvoß

The matching polytope has exponential extension complexity

Details
Discussion Comments: 0
Verification: Author has not verified information

Optimal CUR matrix decompositions

Christos Boutsidis, David P. Woodruff

Optimal CUR matrix decompositions

Details
Discussion Comments: 0
Verification: Authors have not verified information

A characterization of strong approximation resistance

Subhash Khot, Madhur Tulsiani, Pratik Worah

A characterization of strong approximation resistance

Details
Discussion Comments: 0
Verification: Authors have not verified information

Distributed computability in Byzantine asynchronous systems

Hammurabi Mendes, Christine Tasson, Maurice Herlihy

Distributed computability in Byzantine asynchronous systems

Details
Discussion Comments: 0
Verification: Authors have not verified information

Turnstile streaming algorithms might as well be linear sketches

Yi Li, Huy L. Nguyen, David P. Woodruff

Turnstile streaming algorithms might as well be linear sketches

Details
Discussion Comments: 0
Verification: Authors have not verified information

Multiway cut, pairwise realizable distributions, and descending thresholds

Ankit Sharma, Jan Vondrák

Multiway cut, pairwise realizable distributions, and descending thresholds

Details
Discussion Comments: 0
Verification: Authors have not verified information

Are lock-free concurrent algorithms practically wait-free?

Dan Alistarh, Keren Censor-Hillel, Nir Shavit

Are lock-free concurrent algorithms practically wait-free?

Details
Discussion Comments: 0
Verification: Authors have not verified information

An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem

Ken-ichi Kawarabayashi, Yusuke Kobayashi, Stephan Kreutzer

An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem

Details
Discussion Comments: 0
Verification: Authors have not verified information

The power of localization for efficiently learning linear separators with noise

Pranjal Awasthi, Maria-Florina Balcan, Philip M. Long

The power of localization for efficiently learning linear separators with noise

Details
Discussion Comments: 0
Verification: Authors have not verified information

Efficient density estimation via piecewise polynomial approximation

Siu-on Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun

Efficient density estimation via piecewise polynomial approximation

Details
Discussion Comments: 0
Verification: Authors have not verified information

Online local learning via semidefinite programming

Paul Christiano

Online local learning via semidefinite programming

Details
Discussion Comments: 0
Verification: Author has not verified information

Satisfiability threshold for random regular NAE-SAT

Jian Ding, Allan Sly, Nike Sun

Satisfiability threshold for random regular NAE-SAT

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximation algorithms for bipartite matching with metric and geometric costs

Pankaj K. Agarwal, R. Sharathkumar

Approximation algorithms for bipartite matching with metric and geometric costs

Details
Discussion Comments: 0
Verification: Authors have not verified information

From average case complexity to improper learning complexity

Amit Daniely, Nati Linial, Shai Shalev-Shwartz

From average case complexity to improper learning complexity

Details
Discussion Comments: 0
Verification: Authors have not verified information

Breaking the quadratic barrier for 3-LCC's over the reals

Zeev Dvir, Shubhangi Saraf, Avi Wigderson

Breaking the quadratic barrier for 3-LCC's over the reals

Details
Discussion Comments: 0
Verification: Authors have not verified information

Optimal error rates for interactive coding I: adaptivity and other settings

Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan

Optimal error rates for interactive coding I: adaptivity and other settings

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fourier PCA and robust tensor decomposition

Navin Goyal, Santosh Vempala, Ying Xiao

Fourier PCA and robust tensor decomposition

Details
Discussion Comments: 0
Verification: Authors have not verified information