| 2014 | A characterization of locally testable affine-invariant properties via decomposition theorems. Yuichi Yoshida |
| 2014 | A characterization of strong approximation resistance. Subhash Khot, Madhur Tulsiani, Pratik Worah |
| 2014 | A quantum algorithm for computing the unit group of an arbitrary degree number field. Kirsten Eisenträger, Sean Hallgren, Alexei Y. Kitaev, Fang Song |
| 2014 | A strongly polynomial algorithm for generalized flow maximization. László A. Végh |
| 2014 | A super-polynomial lower bound for regular arithmetic formulas. Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi |
| 2014 | An almost-optimally fair three-party coin-flipping protocol. Iftach Haitner, Eliad Tsfadia |
| 2014 | An efficient parallel solver for SDD linear systems. Richard Peng, Daniel A. Spielman |
| 2014 | An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. Ken-ichi Kawarabayashi, Yusuke Kobayashi, Stephan Kreutzer |
| 2014 | Analytical approach to parallel repetition. Irit Dinur, David Steurer |
| 2014 | Analyze gauss: optimal bounds for privacy-preserving principal component analysis. Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, Li Zhang |
| 2014 | Approximate distance oracles with constant query time. Shiri Chechik |
| 2014 | Approximation algorithms for bipartite matching with metric and geometric costs. Pankaj K. Agarwal, R. Sharathkumar |
| 2014 | Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing. Zachary Friggstad, Chaitanya Swamy |
| 2014 | Are lock-free concurrent algorithms practically wait-free? Dan Alistarh, Keren Censor-Hillel, Nir Shavit |
| 2014 | Bandits with switching costs: Ofer Dekel, Jian Ding, Tomer Koren, Yuval Peres |
| 2014 | Black-box non-black-box zero knowledge. Vipul Goyal, Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti |
| 2014 | Breaking the minsky-papert barrier for constant-depth circuits. Alexander A. Sherstov |
| 2014 | Breaking the quadratic barrier for 3-LCC's over the reals. Zeev Dvir, Shubhangi Saraf, Avi Wigderson |
| 2014 | Circuits resilient to additive attacks with applications to secure computation. Daniel Genkin, Yuval Ishai, Manoj Prabhakaran, Amit Sahai, Eran Tromer |
| 2014 | Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing. Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein |
| 2014 | Coin flipping of Itay Berman, Iftach Haitner, Aris Tentes |
| 2014 | Communication is bounded by root of rank. Shachar Lovett |
| 2014 | Communication lower bounds via critical block sensitivity. Mika Göös, Toniann Pitassi |
| 2014 | Community detection thresholds and the weak Ramanujan property. Laurent Massoulié |
| 2014 | Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints. Sungjin Im, Janardhan Kulkarni, Kamesh Munagala |
| 2014 | Computing with a full memory: catalytic space. Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman |
| 2014 | Constant factor approximation for balanced cut in the PIE model. Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan |
| 2014 | Constant rank bimatrix games are PPAD-hard. Ruta Mehta |
| 2014 | Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs. Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, Kunal Talwar |
| 2014 | Deciding first-order properties of nowhere dense graphs. Martin Grohe, Stephan Kreutzer, Sebastian Siebertz |
| 2014 | Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions. Jugal Garg, Ruta Mehta, Vijay V. Vazirani |
| 2014 | Distributed approximation algorithms for weighted shortest paths. Danupon Nanongkai |
| 2014 | Distributed computability in Byzantine asynchronous systems. Hammurabi Mendes, Christine Tasson, Maurice Herlihy |
| 2014 | Economic efficiency requires interaction. Shahar Dobzinski, Noam Nisan, Sigal Oren |
| 2014 | Efficient density estimation via piecewise polynomial approximation. Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun |
| 2014 | Efficient deterministic approximate counting for low-degree polynomial threshold functions. Anindya De, Rocco A. Servedio |
| 2014 | Embedding and canonizing graphs of bounded genus in logspace. Michael Elberfeld, Ken-ichi Kawarabayashi |
| 2014 | Entropy, optimization and counting. Mohit Singh, Nisheeth K. Vishnoi |
| 2014 | Every list-decodable code for high noise has abundant near-optimal rate puncturings. Atri Rudra, Mary Wootters |
| 2014 | Exponential improvement in precision for simulating sparse Hamiltonians. Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, Rolando D. Somma |
| 2014 | Faster all-pairs shortest paths via circuit complexity. Ryan Williams |
| 2014 | Fingerprinting codes and the price of approximate differential privacy. Mark Bun, Jonathan R. Ullman, Salil P. Vadhan |
| 2014 | Formulas vs. circuits for small distance connectivity. Benjamin Rossman |
| 2014 | Fourier PCA and robust tensor decomposition. Navin Goyal, Santosh S. Vempala, Ying Xiao |
| 2014 | From average case complexity to improper learning complexity. Amit Daniely, Nati Linial, Shai Shalev-Shwartz |
| 2014 | From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics. Shay Solomon |
| 2014 | Hitting sets for multilinear read-once algebraic branching programs, in any order. Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka |
| 2014 | Homological product codes. Sergey Bravyi, Matthew B. Hastings |
| 2014 | How to delegate computations: the power of no-signaling proofs. Yael Tauman Kalai, Ran Raz, Ron D. Rothblum |
| 2014 | How to use indistinguishability obfuscation: deniable encryption, and more. Amit Sahai, Brent Waters |
| 2014 | Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements. Alina Ene, Ali Vakilian |
| 2014 | Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region. Andreas Galanis, Daniel Stefankovic, Eric Vigoda |
| 2014 | Infinite randomness expansion with a constant number of devices. Matthew Coudron, Henry Yuen |
| 2014 | L Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev |
| 2014 | Linear time construction of compressed text indices in compact space. Djamal Belazzougui |
| 2014 | Lower bounds for depth 4 formulas computing iterated matrix multiplication. Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan |
| 2014 | Minimum bisection is fixed parameter tractable. Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh |
| 2014 | Multiway cut, pairwise realizable distributions, and descending thresholds. Ankit Sharma, Jan Vondrák |
| 2014 | New algorithms and lower bounds for circuits with linear threshold gates. Ryan Williams |
| 2014 | Non-malleable codes from additive combinatorics. Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett |
| 2014 | On derandomizing algorithms that err extremely rarely. Oded Goldreich, Avi Wigderson |
| 2014 | On the existence of extractable one-way functions. Nir Bitansky, Ran Canetti, Omer Paneth, Alon Rosen |
| 2014 | Online local learning via semidefinite programming. Paul F. Christiano |
| 2014 | Optimal CUR matrix decompositions. Christos Boutsidis, David P. Woodruff |
| 2014 | Optimal competitive auctions. Ning Chen, Nick Gravin, Pinyan Lu |
| 2014 | Optimal error rates for interactive coding I: adaptivity and other settings. Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan |
| 2014 | Parallel algorithms for geometric graph problems. Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev |
| 2014 | Polynomial bounds for the grid-minor theorem. Chandra Chekuri, Julia Chuzhoy |
| 2014 | Primal beats dual on online packing LPs in the random-order model. Thomas Kesselheim, Klaus Radke, Andreas Tönnis, Berthold Vöcking |
| 2014 | Private matchings and allocations. Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, Zhiwei Steven Wu |
| 2014 | Pseudorandom generators with optimal seed length for non-boolean poly-size circuits. Sergei Artemenko, Ronen Shaltiel |
| 2014 | Query complexity of approximate nash equilibria. Yakov Babichenko |
| 2014 | Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices. Carl A. Miller, Yaoyun Shi |
| 2014 | Rounding sum-of-squares relaxations. Boaz Barak, Jonathan A. Kelner, David Steurer |
| 2014 | Satisfiability threshold for random regular NAE-SAT. Jian Ding, Allan Sly, Nike Sun |
| 2014 | Shortest paths on polyhedral surfaces and terrains. Siu-Wing Cheng, Jiongxin Jin |
| 2014 | Smoothed analysis of tensor decompositions. Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan |
| 2014 | Solving SDD linear systems in nearly Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, Shen Chen Xu |
| 2014 | Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai |
| 2014 | Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma |
| 2014 | Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas. Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan |
| 2014 | Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014 David B. Shmoys |
| 2014 | Testing surface area with arbitrary accuracy. Joe Neeman |
| 2014 | The asymptotic k-SAT threshold. Amin Coja-Oghlan |
| 2014 | The average sensitivity of an intersection of half spaces. Daniel M. Kane |
| 2014 | The limits of depth reduction for arithmetic formulas: it's all about the top fan-in. Mrinal Kumar, Shubhangi Saraf |
| 2014 | The matching polytope has exponential extension complexity. Thomas Rothvoß |
| 2014 | The power of localization for efficiently learning linear separators with noise. Pranjal Awasthi, Maria-Florina Balcan, Philip M. Long |
| 2014 | The sample complexity of revenue maximization. Richard Cole, Tim Roughgarden |
| 2014 | Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture. Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson |
| 2014 | Turnstile streaming algorithms might as well be linear sketches. Yi Li, Huy L. Nguyen, David P. Woodruff |
| 2014 | Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time. Michael T. Goodrich |