Google
Google Scholar
MS Academic
CiteSeerX
CORE
Semantic Scholar40. STOC 2008: Victoria, British Columbia, Canada
Cynthia Dwork:
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008. ACM 2008, ISBN 978-1-60558-047-0
1A
- Rajsekar Manokaran, Joseph Naor, Prasad Raghavendra, Roy Schwartz:
Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling. 11-20 - Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, Nisheeth K. Vishnoi:
Unique games on expanding constraint graphs are easy: extended abstract. 21-28
1B
Invited talk
3A
- Jan Vondrák:
Optimal approximation for the submodular welfare problem in the value oracle model. 67-74
3B
4A
- Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum:
Delegating computation: interactive proofs for muggles. 113-122 - Lance Fortnow, Rahul Santhanam:
Infeasibility of instance compression and succinct PCPs for NP. 133-142 - Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy N. Rothblum:
A (de)constructive approach to program checking. 143-152
4B
- Jittat Fakcharoenphol, Bundit Laekhanukit:
An o(log2 k)-approximation algorithm for the k-vertex connected spanning subgraph problem. 153-158 - Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon:
A fixed-parameter algorithm for the directed feedback vertex set problem. 177-186
5A
- Craig Gentry, Chris Peikert, Vinod Vaikuntanathan:
Trapdoors for hard lattices and new cryptographic constructions. 197-206
5B
- Hagit Attiya, Danny Hendler, Philipp Woelfel:
Tight rmr lower bounds for mutual exclusion and other problems. 217-226 - Aaron Cote, Adam Meyerson, Laura J. Poplawski:
Randomized k-server on hierarchical binary trees. 227-234 - Nikhil Bansal, Niv Buchbinder, Joseph Naor:
Randomized competitive algorithms for generalized caching. 235-244
6
7A
- Parikshit Gopalan, Adam R. Klivans, David Zuckerman:
List-decoding reed-muller codes over small fields. 265-274 - Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan:
Decodability of group homomorphisms beyond the johnson bound. 275-284
7B
- Richard Cole, Lisa Fleischer:
Fast-converging tatonnement algorithms for one-time and ongoing market problems. 315-324
8A
- Avraham Ben-Aroya, Amnon Ta-Shma:
A combinatorial construction of almost-ramanujan graphs using the zig-zag product. 325-334 - Ryan O'Donnell, Yi Wu:
An optimal sdp algorithm for max-cut, and equally optimal long code tests. 335-344
8B
- Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab S. Mirrokni, Christos H. Papadimitriou:
The myth of the folk theorem. 365-372 - Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett, Aaron Roth:
Regret minimization and the price of total anarchy. 373-382
9A
- Itai Benjamini, Oded Schramm, Asaf Shapira:
Every minor-closed property of sparse graphs is testable. 393-402
9B
- S. Dov Gordon, Carmit Hazay, Jonathan Katz, Yehuda Lindell:
Complete fairness in secure two-party computation. 413-422 - Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai:
Cryptography with constant computational overhead. 433-442
10A
- Samuel I. Daitch, Daniel A. Spielman:
Faster approximate lossy generalized flow via interior point algorithms. 451-460 - Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, Nisheeth K. Vishnoi:
On partitioning graphs via single commodity flows. 461-470 - Ken-ichi Kawarabayashi, Bojan Mohar:
Graph and map isomorphism and all polyhedral embeddings in linear time. 471-480
10B
- Christopher Umans:
Fast polynomial factorization and modular composition in small characteristic. 481-490 - Jin-yi Cai, Xi Chen, Dong Li:
A quadratic lower bound for the permanent and determinant problem over any characteristic != 2. 491-498 - Anindya De, Piyush P. Kurur, Chandan Saha, Ramprasad Saptharishi:
Fast integer multiplication using modular arithmetic. 499-506
11A
- Parikshit Gopalan, Adam Tauman Kalai, Adam R. Klivans:
Agnostically learning decision trees. 527-536
11B
- Shachar Lovett, Roy Meshulam, Alex Samorodnitsky:
Inverse conjecture for the gowers norm is false. 547-556
Tutorial
13A
- Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson:
Uniform direct product theorems: simplified, optimized, and derandomized. 579-588 - Rahul Jain, Hartmut Klauck, Ashwin Nayak:
Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract. 599-608
13B
- Avrim Blum, Katrina Ligett, Aaron Roth:
A learning theory approach to non-interactive database privacy. 609-618
Invited talk
15A
- Amit Chakrabarti, Graham Cormode, Andrew McGregor:
Robust lower bounds for communication and stream computation. 641-650
15B
- Maria-Florina Balcan, Avrim Blum, Santosh Vempala:
A discriminative framework for clustering via similarity functions. 671-680 - Baruch Awerbuch, Rohit Khandekar:
Stateless distributed gradient descent for positive linear programs. 691-700
16A
- Jakob Nordström, Johan Håstad:
Towards an optimal separation of space and length in resolution. 701-710 - Zeev Dvir, Amir Shpilka, Amir Yehudayoff:
Hardness-randomness tradeoffs for bounded depth arithmetic circuits. 741-748
16B
- Lap Chi Lau, Mohit Singh:
Additive approximation for bounded degree survivable network design. 759-768 - Nikhil Bansal, Rohit Khandekar, Viswanath Nagarajan:
Additive guarantees for degree bounded directed network design. 769-778 - Libor Barto, Marcin Kozik, Todd Niven:
Graphs, polymorphisms and the complexity of homomorphism problems. 789-796
maintained by 
at 
at 
data released under the ODC-BY 1.0 license; see also our legal information page
last updated on 2018-04-19 21:38 CEST by the dblp team