default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID44th STOC 2012: New York, NY, USA
- Howard J. Karloff, Toniann Pitassi:
Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012. ACM 2012, ISBN 978-1-4503-1245-5
Session 1A
- Jonathan A. Kelner, Gary L. Miller, Richard Peng
:
Faster approximate multicommodity flow using quadratically coupled flows. 1-18 - Amit Chakrabarti, Lisa Fleischer, Christophe Weibel:
When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks. 19-26 - László A. Végh:
Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. 27-40
Session 1B
- Scott Aaronson, Paul F. Christiano:
Quantum money from hidden subspaces. 41-60 - Umesh V. Vazirani, Thomas Vidick:
Certifiable quantum dice: or, true random number generation secure against quantum adversaries. 61-76 - Aleksandrs Belovs:
Span programs for functions with constant-sized 1-certificates: extended abstract. 77-84
Session 2
- Kasper Green Larsen:
The cell probe complexity of dynamic range counting. 85-94 - Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf:
Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. 95-106
Session 3A
- Gagan Goel, Vahab S. Mirrokni, Renato Paes Leme:
Polyhedral clinching auctions and the adwords polytope. 107-122 - Robert Kleinberg, S. Matthew Weinberg:
Matroid prophet inequalities. 123-136 - Nikhil R. Devanur, Kamal Jain:
Online matching with concave returns. 137-144
Session 3B
- Sanjeev Arora, Rong Ge, Ravindran Kannan, Ankur Moitra:
Computing a nonnegative matrix factorization - provably. 145-162 - Michael A. Forbes, Amir Shpilka:
On identity testing of tensors, low-rank recovery and compressed sensing. 163-172 - Martin Grohe, Dániel Marx:
Structure theorem and isomorphism test for graphs with excluded topological subgraphs. 173-192
Session 4A
- Pavel Hrubes, Iddo Tzameret:
Short proofs for the determinant identities. 193-212 - Paul Beame, Christopher Beck, Russell Impagliazzo:
Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space. 213-232 - Trinh Huynh, Jakob Nordström:
On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity. 233-248 - Miklós Ajtai:
Determinism versus nondeterminism with arithmetic tests and computation: extended abstract. 249-268
Session 4B
- Steven Heilman, Aukosh Jagannath, Assaf Naor:
Solution of the propeller conjecture in R3. 269-276 - Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi:
2log1-ε n hardness for the closest vector problem with preprocessing. 277-288 - Ryan O'Donnell, John Wright:
A new point of NP-hardness for unique games. 289-306 - Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou:
Hypercontractivity, sum-of-squares proofs, and their applications. 307-326
Session 5A
- Klim Efremenko:
From irreducible representations to locally decodable codes. 327-338 - Venkatesan Guruswami, Chaoping Xing:
Folded codes from function field towers and improved optimal rate list decoding. 339-350 - Zeev Dvir, Shachar Lovett:
Subspace evasive sets. 351-358 - Tali Kaufman, Alexander Lubotzky:
Edge transitive ramanujan graphs and symmetric LDPC good codes. 359-366
Session 5B
- Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan:
Approximation algorithms for semi-random partitioning problems. 367-384 - R. Sharathkumar, Pankaj K. Agarwal:
A near-linear time ε-approximation algorithm for geometric bipartite matching. 385-394 - Ittai Abraham, Ofer Neiman:
Using petal-decompositions to build a low stretch spanning tree. 395-406 - Tobias Brunsch, Heiko Röglin:
Improved smoothed analysis of multiobjective optimization. 407-426
Session 6A
- Stefano Leonardi, Tim Roughgarden:
Prior-free auctions with ordered bidders. 427-434 - Shuchi Chawla, Nicole Immorlica, Brendan Lucier:
On the limits of black-box reductions in mechanism design. 435-448 - Xiaohui Bei, Ning Chen, Nick Gravin, Pinyan Lu:
Budget feasible mechanism design: from prior-free to bayesian. 449-458 - Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg:
An algorithmic characterization of multi-dimensional mechanisms. 459-478
Session 6B
- 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. 479-494 - Siu Man Chan, Aaron Potechin:
Tight bounds for monotone switching networks via fourier analysis. 495-504 - Mark Braverman:
Interactive information complexity. 505-524 - Alexander A. Sherstov:
The multiparty communication complexity of set disjointness. 525-548
Session 7A
- Ho Yee Cheung, Tsz Chiu Kwok, Lap Chi Lau:
Fast matrix rank algorithms and applications. 549-562 - Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price:
Nearly optimal sparse fourier transform. 563-578 - Kousha Etessami, Alistair Stewart, Mihalis Yannakakis:
Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars. 579-588 - Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Räcke:
Optimal online buffer scheduling for block devices. 589-598
Session 7B
- 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. 599-614 - Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff:
Separating multilinear branching programs and formulas. 615-624 - Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam:
Reconstruction of depth-4 multilinear circuits with top fan-in 2. 625-642 - Neeraj Kayal:
Affine projections of polynomials: extended abstract. 643-662
Session 8A
- Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer:
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. 663-672 - Julia Chuzhoy:
On vertex sparsifiers with Steiner nodes. 673-688 - Parinya Chalermsook, Julia Chuzhoy, Alina Ene, Shi Li:
Approximation algorithms and hardness of integral concurrent flow. 689-708
Session 8B
- Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio:
Learning poisson binomial distributions. 709-728 - Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio:
Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces. 729-746 - Alexander A. Sherstov:
Making polynomials robust to noise. 747-758
Session 9A
- Sanjeev Goyal, Michael J. Kearns:
Competitive contagion in networks. 759-774 - Manuel Cebrián, Lorenzo Coviello, Andrea Vattani, Panagiotis Voulgaris:
Finding red balloons with split contracts: robustness to individuals' selfishness. 775-788 - Christina Brandt, Nicole Immorlica, Gautam Kamath, Robert Kleinberg:
An analysis of one-dimensional schelling segregation. 789-804
Session 9B
- Benny Applebaum:
Pseudorandom generators with long stretch and low locality from random local one-way functions. 805-816 - Salil P. Vadhan, Colin Jia Zheng:
Characterizing pseudoentropy and simplifying pseudorandom generator constructions. 817-836 - Xin Li:
Design extractors, non-malleable condensers and privacy amplification. 837-854
Session 10
- Julia Chuzhoy:
Routing in undirected graphs with constant congestion. 855-874 - Hyung-Chan An, Robert Kleinberg, David B. Shmoys:
Improving christofides' algorithm for the s-t path TSP. 875-886 - Virginia Vassilevska Williams:
Multiplying matrices faster than coppersmith-winograd. 887-898
Session 11A
- Amin Coja-Oghlan, Konstantinos Panagiotou:
Catching the k-NAESAT threshold. 899-908 - Jin-Yi Cai, Xi Chen:
Complexity of counting CSP with complex weights. 909-920 - Michael Molloy:
The freezing threshold for k-colourings of a random graph. 921-930 - Libor Barto, Marcin Kozik:
Robust satisfiability of constraint satisfaction problems. 931-940
Session 11B
- David P. Woodruff, Qin Zhang:
Tight bounds for distributed functional monitoring. 941-960 - 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. 961-970 - Nikhil Bansal, Vibhor Bhatt, Prasad Jayanti, Ranganath Kondapally:
Tight time-space tradeoff for mutual exclusion. 971-982 - George Giakkoupis, Philipp Woelfel:
A tight RMR lower bound for randomized mutual exclusion. 983-1002
Session 12A
- Jugal Garg, Ruta Mehta, Milind A. Sohoni, Vijay V. Vazirani:
A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities. 1003-1016 - Pablo Daniel Azar, Silvio Micali:
Rational proofs. 1017-1028 - Jacob D. Abernethy, Rafael M. Frongillo, Andre Wibisono:
Minimax option pricing meets black-scholes in the limit. 1029-1040 - Elchanan Mossel, Miklós Z. Rácz:
A quantitative gibbard-satterthwaite theorem without neutrality. 1041-1060
Session 12B
- Jean Bourgain, Amir Yehudayoff:
Monotone expansion. 1061-1078 - Noga Alon, Ankur Moitra, Benny Sudakov:
Nearly complete graphs decomposable into large induced matchings and their applications. 1079-1090 - Greg Kuperberg, Shachar Lovett, Ron Peled:
Probabilistic existence of rigid combinatorial structures. 1091-1106 - Shahar Dobzinski, Jan Vondrák:
From query complexity to computational complexity. 1107-1116
Session 13A
- James R. Lee, Shayan Oveis Gharan, Luca Trevisan:
Multi-way spectral partitioning and higher-order cheeger inequalities. 1117-1130 - Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh S. Vempala:
Many sparse cuts via higher eigenvalues. 1131-1140 - Lorenzo Orecchia, Sushant Sachdeva, Nisheeth K. Vishnoi:
Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator. 1141-1160 - Michel X. Goemans, Neil Olver, Thomas Rothvoß, Rico Zenklusen:
Matroids and integrality gaps for hypergraphic steiner tree relaxations. 1161-1176 - Gerth Stølting Brodal, George Lagogiannis, Robert Endre Tarjan:
Strict fibonacci heaps. 1177-1184 - Jan Bulánek, Michal Koucký, Michael E. Saks:
Tight lower bounds for the online labeling problem. 1185-1198 - Ittai Abraham, Shiri Chechik, Cyril Gavoille:
Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. 1199-1218
Session 13B
- Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan:
On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. 1219-1234 - Elette Boyle, Shafi Goldwasser, Abhishek Jain, Yael Tauman Kalai:
Multiparty computation secure against continual memory leakage. 1235-1254 - Moritz Hardt, Aaron Roth:
Beating randomized response on incoherent matrices. 1255-1268 - Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, Kunal Talwar:
Unconditional differentially private mechanisms for linear queries. 1269-1284 - S. Muthukrishnan, Aleksandar Nikolov:
Optimal private halfspace counting via discrepancy. 1285-1292
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-10-22 02:19 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
