40. STOC 2008: Victoria, British Columbia, Canada

Richard E. Ladner, Cynthia Dwork (Eds.): 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 BibTeX

1A

Anup Rao:
Parallel repetition in projection games and a concentration bound. 1-10
Electronic Edition (ACM DL) BibTeX
Rajsekar Manokaran, Joseph Naor, Prasad Raghavendra, Roy Schwartz:
Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling. 11-20
Electronic Edition (ACM DL) BibTeX
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
Electronic Edition (ACM DL) BibTeX

1B

Manuel Bodirsky, Jan Kára:
The complexity of temporal constraint satisfaction problems. 29-38
Electronic Edition (ACM DL) BibTeX
Satyadev Nandakumar:
An effective ergodic theorem and some applications. 39-44
Electronic Edition (ACM DL) BibTeX
Abhimanyu Das, David Kempe:
Algorithms for subset selection in linear regression. 45-54
Electronic Edition (ACM DL) BibTeX

Invited talk

Jennifer Rexford:
Rethinking internet routing. 55-56
Electronic Edition (ACM DL) BibTeX

3A

Hagay Levin, Michael Schapira, Aviv Zohar:
Interdomain routing and games. 57-66
Electronic Edition (ACM DL) BibTeX
Jan Vondrák:
Optimal approximation for the submodular welfare problem in the value oracle model. 67-74
Electronic Edition (ACM DL) BibTeX
Jason D. Hartline, Tim Roughgarden:
Optimal mechanism design and money burning. 75-84
Electronic Edition (ACM DL) BibTeX

3B

Alexander A. Sherstov:
The pattern matrix method for lower bounds on quantum communication. 85-94
Electronic Edition (ACM DL) BibTeX
Dmitry Gavinsky:
Classical interaction cannot replace a quantum message. 95-102
Electronic Edition (ACM DL) BibTeX
Ben Reichardt, Robert Spalek:
Span-program-based quantum algorithm for evaluating formulas. 103-112
Electronic Edition (ACM DL) BibTeX

4A

Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum:
Delegating computation: interactive proofs for muggles. 113-122
Electronic Edition (ACM DL) BibTeX
Brendan Juba, Madhu Sudan:
Universal semantic communication I. 123-132
Electronic Edition (ACM DL) BibTeX
Lance Fortnow, Rahul Santhanam:
Infeasibility of instance compression and succinct PCPs for NP. 133-142
Electronic Edition (ACM DL) BibTeX
Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy N. Rothblum:
A (de)constructive approach to program checking. 143-152
Electronic Edition (ACM DL) BibTeX

4B

Jittat Fakcharoenphol, Bundit Laekhanukit:
An o(log² k)-approximation algorithm for the k-vertex connected spanning subgraph problem. 153-158
Electronic Edition (ACM DL) BibTeX
Mikkel Thorup:
Minimum k-way cuts via deterministic greedy tree packing. 159-166
Electronic Edition (ACM DL) BibTeX
Tanmoy Chakraborty, Julia Chuzhoy, Sanjeev Khanna:
Network design for vertex connectivity. 167-176
Electronic Edition (ACM DL) BibTeX
Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon:
A fixed-parameter algorithm for the directed feedback vertex set problem. 177-186
Electronic Edition (ACM DL) BibTeX

5A

Chris Peikert, Brent Waters:
Lossy trapdoor functions and their applications. 187-196
Electronic Edition (ACM DL) BibTeX
Craig Gentry, Chris Peikert, Vinod Vaikuntanathan:
Trapdoors for hard lattices and new cryptographic constructions. 197-206
Electronic Edition (ACM DL) BibTeX
Nicolas Gama, Phong Q. Nguyen:
Finding short lattice vectors within mordell's inequality. 207-216
Electronic Edition (ACM DL) BibTeX

5B

Hagit Attiya, Danny Hendler, Philipp Woelfel:
Tight rmr lower bounds for mutual exclusion and other problems. 217-226
Electronic Edition (ACM DL) BibTeX
Aaron Cote, Adam Meyerson, Laura J. Poplawski:
Randomized k-server on hierarchical binary trees. 227-234
Electronic Edition (ACM DL) BibTeX
Nikhil Bansal, Niv Buchbinder, Joseph Naor:
Randomized competitive algorithms for generalized caching. 235-244
Electronic Edition (ACM DL) BibTeX

6

Prasad Raghavendra:
Optimal algorithms and inapproximability results for every CSP? 245-254
Electronic Edition (ACM DL) BibTeX
Harald Räcke:
Optimal hierarchical decompositions for congestion minimization in networks. 255-264
Electronic Edition (ACM DL) BibTeX

7A

Parikshit Gopalan, Adam R. Klivans, David Zuckerman:
List-decoding reed-muller codes over small fields. 265-274
Electronic Edition (ACM DL) BibTeX
Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan:
Decodability of group homomorphisms beyond the johnson bound. 275-284
Electronic Edition (ACM DL) BibTeX
Or Meir:
Combinatorial construction of locally testable codes. 285-294
Electronic Edition (ACM DL) BibTeX

7B

Jon M. Kleinberg, Éva Tardos:
Balanced outcomes in social exchange networks. 295-304
Electronic Edition (ACM DL) BibTeX
Yiling Chen, Sharad Goel, David M. Pennock:
Pricing combinatorial markets for tournaments. 305-314
Electronic Edition (ACM DL) BibTeX
Richard Cole, Lisa Fleischer:
Fast-converging tatonnement algorithms for one-time and ongoing market problems. 315-324
Electronic Edition (ACM DL) BibTeX

8A

Avraham Ben-Aroya, Amnon Ta-Shma:
A combinatorial construction of almost-ramanujan graphs using the zig-zag product. 325-334
Electronic Edition (ACM DL) BibTeX
Ryan O'Donnell, Yi Wu:
An optimal sdp algorithm for max-cut, and equally optimal long code tests. 335-344
Electronic Edition (ACM DL) BibTeX
Subhash Khot, Rishi Saket:
On hardness of learning intersection of two halfspaces. 345-354
Electronic Edition (ACM DL) BibTeX

8B

Alexander Skopalik, Berthold Vöcking:
Inapproximability of pure nash equilibria. 355-364
Electronic Edition (ACM DL) BibTeX
Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab S. Mirrokni, Christos H. Papadimitriou:
The myth of the folk theorem. 365-372
Electronic Edition (ACM DL) BibTeX
Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett, Aaron Roth:
Regret minimization and the price of total anarchy. 373-382
Electronic Edition (ACM DL) BibTeX

9A

Paul Valiant:
Testing symmetric properties of distributions. 383-392
Electronic Edition (ACM DL) BibTeX
Itai Benjamini, Oded Schramm, Asaf Shapira:
Every minor-closed property of sparse graphs is testable. 393-402
Electronic Edition (ACM DL) BibTeX
Tali Kaufman, Madhu Sudan:
Algebraic property testing: the role of invariance. 403-412
Electronic Edition (ACM DL) BibTeX

9B

S. Dov Gordon, Carmit Hazay, Jonathan Katz, Yehuda Lindell:
Complete fairness in secure two-party computation. 413-422
Electronic Edition (ACM DL) BibTeX
Gillat Kol, Moni Naor:
Games for exchanging information. 423-432
Electronic Edition (ACM DL) BibTeX
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai:
Cryptography with constant computational overhead. 433-442
Electronic Edition (ACM DL) BibTeX

10A

Navin Goyal, Neil Olver, F. Bruce Shepherd:
The vpn conjecture is true. 443-450
Electronic Edition (ACM DL) BibTeX
Samuel I. Daitch, Daniel A. Spielman:
Faster approximate lossy generalized flow via interior point algorithms. 451-460
Electronic Edition (ACM DL) BibTeX
Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, Nisheeth K. Vishnoi:
On partitioning graphs via single commodity flows. 461-470
Electronic Edition (ACM DL) BibTeX
Ken-ichi Kawarabayashi, Bojan Mohar:
Graph and map isomorphism and all polyhedral embeddings in linear time. 471-480
Electronic Edition (ACM DL) BibTeX

10B

Christopher Umans:
Fast polynomial factorization and modular composition in small characteristic. 481-490
Electronic Edition (ACM DL) BibTeX
Jin-yi Cai, Xi Chen, Dong Li:
A quadratic lower bound for the permanent and determinant problem over any characteristic != 2. 491-498
Electronic Edition (ACM DL) BibTeX
Anindya De, Piyush P. Kurur, Chandan Saha, Ramprasad Saptharishi:
Fast integer multiplication using modular arithmetic. 499-506
Electronic Edition (ACM DL) BibTeX
Amir Shpilka, Ilya Volkovich:
Read-once polynomial identity testing. 507-516
Electronic Edition (ACM DL) BibTeX

11A

Ryan O'Donnell, Rocco A. Servedio:
The chow parameters problem. 517-526
Electronic Edition (ACM DL) BibTeX
Parikshit Gopalan, Adam Tauman Kalai, Adam R. Klivans:
Agnostically learning decision trees. 527-536
Electronic Edition (ACM DL) BibTeX
Sanjoy Dasgupta, Yoav Freund:
Random projection trees and low dimensional manifolds. 537-546
Electronic Edition (ACM DL) BibTeX

11B

Shachar Lovett, Roy Meshulam, Alex Samorodnitsky:
Inverse conjecture for the gowers norm is false. 547-556
Electronic Edition (ACM DL) BibTeX
Shachar Lovett:
Unconditional pseudorandom generators for low degree polynomials. 557-562
Electronic Edition (ACM DL) BibTeX
Daniel A. Spielman, Nikhil Srivastava:
Graph sparsification by effective resistances. 563-568
Electronic Edition (ACM DL) BibTeX

Tutorial

Ryan O'Donnell:
Some topics in analysis of boolean functions. 569-578
Electronic Edition (ACM DL) BibTeX

13A

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson:
Uniform direct product theorems: simplified, optimized, and derandomized. 579-588
Electronic Edition (ACM DL) BibTeX
Ronen Shaltiel, Emanuele Viola:
Hardness amplification proofs require majority. 589-598
Electronic Edition (ACM DL) BibTeX
Rahul Jain, Hartmut Klauck, Ashwin Nayak:
Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract. 599-608
Electronic Edition (ACM DL) BibTeX

13B

Avrim Blum, Katrina Ligett, Aaron Roth:
A learning theory approach to non-interactive database privacy. 609-618
Electronic Edition (ACM DL) BibTeX
Vitaly Feldman:
Evolvability from learning algorithms. 619-628
Electronic Edition (ACM DL) BibTeX
Adam Tauman Kalai, Yishay Mansour, Elad Verbin:
On agnostic boosting and parity learning. 629-638
Electronic Edition (ACM DL) BibTeX

Invited talk

David Haussler:
Computing how we became human. 639-640
Electronic Edition (ACM DL) BibTeX

15A

Amit Chakrabarti, Graham Cormode, Andrew McGregor:
Robust lower bounds for communication and stream computation. 641-650
Electronic Edition (ACM DL) BibTeX
Ilya Mironov, Moni Naor, Gil Segev:
Sketching in adversarial environments. 651-660
Electronic Edition (ACM DL) BibTeX
Omer Barkol, Yuval Ishai, Enav Weinreb:
Communication in the presence of replication. 661-670
Electronic Edition (ACM DL) BibTeX

15B

Maria-Florina Balcan, Avrim Blum, Santosh Vempala:
A discriminative framework for clustering via similarity functions. 671-680
Electronic Edition (ACM DL) BibTeX
Robert Kleinberg, Aleksandrs Slivkins, Eli Upfal:
Multi-armed bandits in metric spaces. 681-690
Electronic Edition (ACM DL) BibTeX
Baruch Awerbuch, Rohit Khandekar:
Stateless distributed gradient descent for positive linear programs. 691-700
Electronic Edition (ACM DL) BibTeX

16A

Jakob Nordström, Johan Håstad:
Towards an optimal separation of space and length in resolution. 701-710
Electronic Edition (ACM DL) BibTeX
Ran Raz:
Elusive functions and lower bounds for arithmetic circuits. 711-720
Electronic Edition (ACM DL) BibTeX
Benjamin Rossman:
On the constant-depth complexity of k-clique. 721-730
Electronic Edition (ACM DL) BibTeX
Scott Aaronson, Avi Wigderson:
Algebrization: a new barrier in complexity theory. 731-740
Electronic Edition (ACM DL) BibTeX
Zeev Dvir, Amir Shpilka, Amir Yehudayoff:
Hardness-randomness tradeoffs for bounded depth arithmetic circuits. 741-748
Electronic Edition (ACM DL) BibTeX

16B

Sung-Soon Choi, Jeong Han Kim:
Optimal query complexity bounds for finding graphs. 749-758
Electronic Edition (ACM DL) BibTeX
Lap Chi Lau, Mohit Singh:
Additive approximation for bounded degree survivable network design. 759-768
Electronic Edition (ACM DL) BibTeX
Nikhil Bansal, Rohit Khandekar, Viswanath Nagarajan:
Additive guarantees for degree bounded directed network design. 769-778
Electronic Edition (ACM DL) BibTeX
Alan M. Frieze, Santosh Vempala, Juan Vera:
Logconcave random graphs. 779-788
Electronic Edition (ACM DL) BibTeX
Libor Barto, Marcin Kozik, Todd Niven:
Graphs, polymorphisms and the complexity of homomorphism problems. 789-796
Electronic Edition (ACM DL) BibTeX