| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Pietro Caputo, Fabio Martinelli, Alistair Sinclair, Alexandre Stauffer |
Random lattice triangulations: structure and algorithms.  |
STOC  |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Deeparnab Chakrabarty, C. Seshadhri |
Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Kshipra Bhawalkar, Sreenivas Gollapudi, Kamesh Munagala |
Coevolutionary opinion formation games. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Stanislav Böhm, Stefan Göller, Petr Jancar |
Equivalence of deterministic one-counter automata is NL-complete. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Xiangrui Meng, Michael W. Mahoney |
Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Ken-ichi Kawarabayashi, Yuichi Yoshida |
Testing subdivision-freeness: property testing meets structural graph theory. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Mary Wootters |
On the list decodability of random linear codes with large error rates. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Fernando G. S. L. Brandão, Aram Wettroth Harrow |
Product-state approximations to quantum ground states. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett |
Every locally characterized affine-invariant property is testable. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao |
Statistical algorithms and a lower bound for detecting planted cliques. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin Cadek, Marek Krcál, Jirí Matousek, Lukás Vokrínek, Uli Wagner |
Extending continuous maps: polynomiality and undecidability. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | James R. Lee, Manor Mendel, Mohammad Moharrami |
A node-capacitated okamura-seymour theorem. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Prateek Jain, Praneeth Netrapalli, Sujay Sanghavi |
Low-rank matrix completion using alternating minimization. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Yael Tauman Kalai, Ran Raz, Ron D. Rothblum |
Delegation for bounded space. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan Williams |
Natural proofs versus derandomization. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Kenneth L. Clarkson, David P. Woodruff |
Low rank approximation and regression in input sparsity time. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Fernando G. S. L. Brandão, Aram Wettroth Harrow |
Quantum de finetti theorems under local measurements with applications. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Assaf Naor, Oded Regev, Thomas Vidick |
Efficient rounding for the noncommutative grothendieck inequality. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | James B. Orlin |
Max flows in O(nm) time, or better. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Moritz Hardt, Aaron Roth |
Beyond worst-case analysis in private singular vector computation. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Gary L. Miller |
Solving large optimization problems using spectral graph theory. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
Lower bounds for RAMs and quantifier elimination. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Elkin, Shay Solomon |
Optimal euclidean spanners: really short, thin and lanky. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Gillat Kol, Ran Raz |
Interactive channel capacity. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Anindya De, Elchanan Mossel, Joe Neeman |
Majority is stablest: discrete and SoS. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Xi Chen, Dimitris Paparas, Mihalis Yannakakis |
The complexity of non-monotone markets. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer |
On the concrete efficiency of probabilistically-checkable proofs. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Siu On Chan |
Approximation resistance from pairwise independent subgroups. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Ventsislav Chonev, Joël Ouaknine, James Worrell |
The orbit problem in higher dimensions. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Xi Chen, Xiaorui Sun, Shang-Hua Teng |
Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilan Komargodski, Ran Raz |
Average-case lower bounds for formula size. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Ankur Moitra |
An information complexity approach to extended formulations. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Liam Roditty, Virginia Vassilevska Williams |
Fast approximation algorithms for the diameter and radius of sparse graphs. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, Damien Stehlé |
Classical hardness of learning with errors. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Jian Li, Wen Yuan |
Stochastic combinatorial optimization via poisson approximation. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-Yi Cai, Heng Guo, Tyson Williams |
A complete dichotomy rises from the capture of vanishing signatures: extended abstract. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Thapper, Stanislav Zivny |
The complexity of finite-valued CSPs. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Abhishek Bhowmick, Zeev Dvir, Shachar Lovett |
New bounds for matching vector families. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Andris Ambainis |
Superlinear advantage for exact quantum algorithms. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Valerie King, Jared Saia |
Byzantine agreement in polynomial expected time: [extended abstract]. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Mikkel Thorup |
Bottom-k and priority sampling, set similarity and subset sums with minimal independence. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Xiaohui Bei, Ning Chen, Shengyu Zhang |
On the complexity of trial and error. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Kai-Min Chung, Rafael Pass, Karn Seth |
Non-black-box simulation from one-way functions and applications to resettable security. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Anupam Gupta, Kunal Talwar, David Witmer |
Sparsest cut on bounded treewidth graphs: algorithms and hardness results. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Sangxia Huang |
Approximation resistance on satisfiable instances for predicates with few accepting inputs. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Keevash, Fiachra Knox, Richard Mycroft |
Polynomial-time perfect matchings in dense hypergraphs. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Bürgisser, Christian Ikenmeyer |
Explicit lower bounds via geometric complexity theory. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Jelani Nelson, Huy L. Nguyen |
Sparsity lower bounds for dimensionality reducing maps. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Chandra Chekuri, Julia Chuzhoy |
Large-treewidth graph decompositions and applications. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Manindra Agrawal, Chandan Saha, Nitin Saxena |
Quasi-polynomial hitting-set for set-depth-Δ formulas. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Moritz Hardt, David P. Woodruff |
How robust are linear sketches to adaptive inputs? |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjam Garg, Craig Gentry, Amit Sahai, Brent Waters |
Witness encryption and its applications. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer |
Recursive composition and bootstrapping for SNARKS and proof-carrying data. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Vasilis Syrgkanis, Éva Tardos |
Composable and efficient mechanisms. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuchi Chawla, Jason D. Hartline, David L. Malec, Balasubramanian Sivan |
Prior-independent mechanisms for scheduling. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Christoph Lenzen, Boaz Patt-Shamir |
Fast routing table construction using small messages: extended abstract. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Ofer Neiman, Shay Solomon |
Simple deterministic algorithms for fully dynamic maximal matching. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Dan Boneh, Tim Roughgarden, Joan Feigenbaum (eds.) |
Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013 |
STOC |
2013 |
DBLP BibTeX RDF |
|
| 1 | Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan |
Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | David Eisenstat, Philip N. Klein |
Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Christopher Beck, Russell Impagliazzo |
Strong ETH holds for regular resolution. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Shi Li, Ola Svensson |
Approximating k-median via pseudo-approximation. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Amnon Ta-Shma |
Inverting well conditioned matrices in quantum logspace. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Sergey Gorbunov, Vinod Vaikuntanathan, Hoeteck Wee |
Attribute-based encryption for circuits. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Chaoping Xing |
List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Yossi Azar, Ilan Reuven Cohen, Iftah Gamzu |
The loss of serving in the dark. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Cygan, Stefan Kratsch, Jesper Nederlof |
Fast hamiltonicity checking via bases of perfect matchings. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu |
A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Aleksandar Nikolov, Kunal Talwar, Li Zhang |
The geometry of differential privacy: the sparse and approximate cases. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Miles, Emanuele Viola |
Shielding circuits with groups. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Michal Feldman, Nick Gravin, Brendan Lucier |
Combinatorial walrasian equilibrium. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Albert Gu, Anupam Gupta, Amit Kumar |
The power of deferral: maintaining a constant-competitive steiner tree online. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Jonathan Ullman |
Answering n{2+o(1)} counting queries with differential privacy is hard. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Amin Coja-Oghlan, Konstantinos Panagiotou |
Going after the k-SAT threshold. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Niv Buchbinder, Joseph Naor, Roy Schwartz |
Simplex partitioning via exponential clocks and the multiway cut problem. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy N. Rothblum, Salil P. Vadhan, Avi Wigderson |
Interactive proofs of proximity: delegating computation in sublinear time. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Yossi Azar, Ilan Reuven Cohen, Seny Kamara, Bruce Shepherd |
Tight bounds for online vector bin packing. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Sariel Har-Peled, Benjamin Adam Raichel |
Net and prune: a linear time algorithm for euclidean distance problems. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Vipul Goyal |
Non-black-box simulation in the fully concurrent setting. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Alistair Sinclair, Piyush Srivastava |
Lee-Yang theorems and the complexity of computing averages. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf |
A new family of locally correctable codes based on degree-lifted algebraic geometry codes. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander A. Sherstov |
Communication lower bounds using directional derivatives. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | László Babai, John Wilmes |
Quasipolynomial-time canonical form for steiner designs. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Bernstein |
Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract]. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Justin Hsu, Aaron Roth, Jonathan Ullman |
Differential privacy for the analyst via private equilibrium computation. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexandr Andoni, Assaf Goldberger, Andrew McGregor, Ely Porat |
Homomorphic fingerprints under misalignments: sketching edit and shift distances. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein |
From information to exact communication. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Deeparnab Chakrabarty, C. Seshadhri |
A o(n) monotonicity tester for boolean functions over the hypercube. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Yin Tat Lee, Satish Rao, Nikhil Srivastava |
A new approach to computing maximum flows using electrical flows. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Karl Bringmann, Kasper Green Larsen |
Succinct sampling from discrete distributions. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Yun Kuen Cheung, Richard Cole, Nikhil R. Devanur |
Tatonnement beyond gross substitutes?: gradient descent to the rescue. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | David G. Harris, Aravind Srinivasan |
Constraint satisfaction, packet routing, and the lovasz local lemma. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Xin Li |
New independent source extractors with exponential improvement. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Troy Lee, Adi Shraibman, Santosh Vempala |
The approximate rank of a matrix and its algorithmic applications: approximate rank. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel M. Kane, Raghu Meka |
A PRG for lipschitz functions of polynomials with applications to sparsest cut. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Michal Feldman, Hu Fu, Nick Gravin, Brendan Lucier |
Simultaneous auctions are (almost) efficient. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Shay Mozes, Christian Sommer |
Structured recursive separator decompositions for planar graphs in linear time. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, Nickolai Zeldovich |
Reusable garbled circuits and succinct functional encryption. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Hammurabi Mendes, Maurice Herlihy |
Multidimensional approximate agreement in Byzantine asynchronous systems. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
| 1 | Nir Bitansky, Omer Paneth |
On the impossibility of approximate obfuscation and applications to resettable cryptography. |
STOC |
2013 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")