| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Räcke |
Optimal online buffer scheduling for block devices.  |
STOC  |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Stefano Leonardi, Tim Roughgarden |
Prior-free auctions with ordered bidders. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Howard J. Karloff, Toniann Pitassi (eds.) |
Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012 |
STOC |
2012 |
DBLP BibTeX RDF |
|
| 1 | Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov |
Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Lisa Fleischer, Christophe Weibel |
When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael A. Forbes, Amir Shpilka |
On identity testing of tensors, low-rank recovery and compressed sensing. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Jonathan A. Kelner, Gary L. Miller, Richard Peng |
Faster approximate multicommodity flow using quadratically coupled flows. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Virginia Vassilevska Williams |
Multiplying matrices faster than coppersmith-winograd. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Trinh Huynh, Jakob Nordström |
On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Siu Man Chan, Aaron Potechin |
Tight bounds for monotone switching networks via fourier analysis. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin Grohe, Dániel Marx |
Structure theorem and isomorphism test for graphs with excluded topological subgraphs. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio |
Learning poisson binomial distributions. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Manuel Cebrián, Lorenzo Coviello, Andrea Vattani, Panagiotis Voulgaris |
Finding red balloons with split contracts: robustness to individuals' selfishness. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Neeraj Kayal |
Affine projections of polynomials: extended abstract. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, Kunal Talwar |
Unconditional differentially private mechanisms for linear queries. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Gerth Stølting Brodal, George Lagogiannis, Robert Endre Tarjan |
Strict fibonacci heaps. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Christina Brandt, Nicole Immorlica, Gautam Kamath, Robert Kleinberg |
An analysis of one-dimensional schelling segregation. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul Beame, Christopher Beck, Russell Impagliazzo |
Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi |
2log1-ε n hardness for the closest vector problem with preprocessing. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeev Dvir, Shachar Lovett |
Subspace evasive sets. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Klim Efremenko |
From irreducible representations to locally decodable codes. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuchi Chawla, Nicole Immorlica, Brendan Lucier |
On the limits of black-box reductions in mechanism design. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price |
Nearly optimal sparse fourier transform. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Hyung-Chan An, Robert Kleinberg, David B. Shmoys |
Improving christofides' algorithm for the s-t path TSP. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Michel X. Goemans, Neil Olver, Thomas Rothvoß, Rico Zenklusen |
Matroids and integrality gaps for hypergraphic steiner tree relaxations. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjeev Arora, Rong Ge, Ravindran Kannan, Ankur Moitra |
Computing a nonnegative matrix factorization - provably. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer |
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan |
Approximation algorithms for semi-random partitioning problems. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Steven Heilman, Aukosh Jagannath, Assaf Naor |
Solution of the propeller conjecture in R3. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | George Giakkoupis, Philipp Woelfel |
A tight RMR lower bound for randomized mutual exclusion. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Jean Bourgain, Amir Yehudayoff |
Monotone expansion. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjeev Goyal, Michael Kearns |
Competitive contagion in networks. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Elette Boyle, Shafi Goldwasser, Abhishek Jain 0002, Yael Tauman Kalai |
Multiparty computation secure against continual memory leakage. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-Yi Cai, Xi Chen |
Complexity of counting CSP with complex weights. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Ittai Abraham, Ofer Neiman |
Using petal-decompositions to build a low stretch spanning tree. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Julia Chuzhoy |
Routing in undirected graphs with constant congestion. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg |
An algorithmic characterization of multi-dimensional mechanisms. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam |
Reconstruction of depth-4 multilinear circuits with top fan-in 2. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Ankur Moitra, Benny Sudakov |
Nearly complete graphs decomposable into large induced matchings and their applications. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Chaoping Xing |
Folded codes from function field towers and improved optimal rate list decoding. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Parinya Chalermsook, Julia Chuzhoy, Alina Ene, Shi Li |
Approximation algorithms and hardness of integral concurrent flow. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Robert Kleinberg, S. Matthew Weinberg |
Matroid prophet inequalities. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander A. Sherstov |
The multiparty communication complexity of set disjointness. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | S. Muthukrishnan, Aleksandar Nikolov |
Optimal private halfspace counting via discrepancy. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Jan Bulánek, Michal Koucký, Michael Saks |
Tight lower bounds for the online labeling problem. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan |
On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Fernando G. S. L. Brandão, Aram Wettroth Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou |
Hypercontractivity, sum-of-squares proofs, and their applications. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil R. Devanur, Kamal Jain |
Online matching with concave returns. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Umesh V. Vazirani, Thomas Vidick |
Certifiable quantum dice: or, true random number generation secure against quantum adversaries. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Elchanan Mossel, Miklós Z. Rácz |
A quantitative gibbard-satterthwaite theorem without neutrality. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal, Vibhor Bhatt, Prasad Jayanti, Ranganath Kondapally |
Tight time-space tradeoff for mutual exclusion. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio |
Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Shahar Dobzinski, Jan Vondrák |
From query complexity to computational complexity. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola |
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | R. Sharathkumar, Pankaj K. Agarwal |
A near-linear time ε-approximation algorithm for geometric bipartite matching. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Julia Chuzhoy |
On vertex sparsifiers with Steiner nodes. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Lorenzo Orecchia, Sushant Sachdeva, Nisheeth K. Vishnoi |
Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Amin Coja-Oghlan, Konstantinos Panagiotou |
Catching the k-NAESAT threshold. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Xin Li |
Design extractors, non-malleable condensers and privacy amplification. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman |
Interactive information complexity. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Pablo Daniel Azar, Silvio Micali |
Rational proofs. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Salil P. Vadhan, Colin Jia Zheng |
Characterizing pseudoentropy and simplifying pseudorandom generator constructions. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Tali Kaufman, Alexander Lubotzky |
Edge transitive ramanujan graphs and symmetric LDPC good codes. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
Determinism versus nondeterminism with arithmetic tests and computation: extended abstract. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | David P. Woodruff, Qin Zhang |
Tight bounds for distributed functional monitoring. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Kousha Etessami, Alistair Stewart, Mihalis Yannakakis |
Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Hrubes, Iddo Tzameret |
Short proofs for the determinant identities. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff |
Separating multilinear branching programs and formulas. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Moritz Hardt, Aaron Roth |
Beating randomized response on incoherent matrices. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | James R. Lee, Shayan Oveis Gharan, Luca Trevisan |
Multi-way spectral partitioning and higher-order cheeger inequalities. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander A. Sherstov |
Making polynomials robust to noise. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Tobias Brunsch, Heiko Röglin |
Improved smoothed analysis of multiobjective optimization. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Ittai Abraham, Shiri Chechik, Cyril Gavoille |
Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Scott Aaronson, Paul Christiano |
Quantum money from hidden subspaces. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Jacob Abernethy, Rafael M. Frongillo, Andre Wibisono |
Minimax option pricing meets black-scholes in the limit. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Greg Kuperberg, Shachar Lovett, Ron Peled |
Probabilistic existence of rigid combinatorial structures. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Ho Yee Cheung, Tsz Chiu Kwok, Lap Chi Lau |
Fast matrix rank algorithms and applications. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Gagan Goel, Vahab S. Mirrokni, Renato Paes Leme |
Polyhedral clinching auctions and the adwords polytope. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Xiaohui Bei, Ning Chen, Nick Gravin, Pinyan Lu |
Budget feasible mechanism design: from prior-free to bayesian. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena |
Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Libor Barto, Marcin Kozik |
Robust satisfiability of constraint satisfaction problems. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan O'Donnell, John Wright |
A new point of NP-hardness for unique games. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Jugal Garg, Ruta Mehta, Milind A. Sohoni, Vijay V. Vazirani |
A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala |
Many sparse cuts via higher eigenvalues. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf |
Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Molloy |
The freezing threshold for k-colourings of a random graph. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Kasper Green Larsen |
The cell probe complexity of dynamic range counting. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Aleksandrs Belovs |
Span programs for functions with constant-sized 1-certificates: extended abstract. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | László A. Végh |
Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Benny Applebaum |
Pseudorandom generators with long stretch and low locality from random local one-way functions. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer |
Distributed verification and hardness of distributed approximation. |
STOC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Bharat Adsul, Jugal Garg, Ruta Mehta, Milind A. Sohoni |
Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm. |
STOC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Huijia Lin, Rafael Pass |
Constant-round non-malleable commitments from any one-way function. |
STOC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Shahar Dobzinski |
An impossibility result for truthful combinatorial auctions with submodular valuations. |
STOC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrew Novocin, Damien Stehlé, Gilles Villard |
An LLL-reduction algorithm with quasi-linear time complexity: extended abstract. |
STOC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Mohammad Mahdian, Qiqi Yan |
Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. |
STOC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
Secure computation with information leaking to an adversary. |
STOC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin |
High-rate codes with sublinear-time decoding. |
STOC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Nicolas Bousquet, Jean Daligault, Stéphan Thomassé |
Multicut is FPT. |
STOC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | James R. Lee, Anastasios Sidiropoulos |
Near-optimal distortion bounds for embedding doubling spaces into L1. |
STOC |
2011 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")