40. 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

• 
  Anup Rao:
  Parallel repetition in projection games and a concentration bound. 1-10
• 
  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

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

Invited talk

• 
  Jennifer Rexford:
  Rethinking internet routing. 55-56

3A

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

3B

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

4A

• 
  Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum:
  Delegating computation: interactive proofs for muggles. 113-122
• 
  Brendan Juba, Madhu Sudan:
  Universal semantic communication I. 123-132
• 
  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(log² k)-approximation algorithm for the k-vertex connected spanning subgraph problem. 153-158
• 
  Mikkel Thorup:
  Minimum k-way cuts via deterministic greedy tree packing. 159-166
• 
  Tanmoy Chakraborty, Julia Chuzhoy, Sanjeev Khanna:
  Network design for vertex connectivity. 167-176
• 
  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

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

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

• 
  Prasad Raghavendra:
  Optimal algorithms and inapproximability results for every CSP? 245-254
• 
  Harald Räcke:
  Optimal hierarchical decompositions for congestion minimization in networks. 255-264

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
• 
  Or Meir:
  Combinatorial construction of locally testable codes. 285-294

7B

• 
  Jon M. Kleinberg, Éva Tardos:
  Balanced outcomes in social exchange networks. 295-304
• 
  Yiling Chen, Sharad Goel, David M. Pennock:
  Pricing combinatorial markets for tournaments. 305-314
• 
  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
• 
  Subhash Khot, Rishi Saket:
  On hardness of learning intersection of two halfspaces. 345-354

8B

• 
  Alexander Skopalik, Berthold Vöcking:
  Inapproximability of pure nash equilibria. 355-364
• 
  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

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

9B

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

10A

• 
  Navin Goyal, Neil Olver, F. Bruce Shepherd:
  The vpn conjecture is true. 443-450
• 
  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
• 
  Amir Shpilka, Ilya Volkovich:
  Read-once polynomial identity testing. 507-516

11A

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

11B

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

Tutorial

• 
  Ryan O'Donnell:
  Some topics in analysis of boolean functions. 569-578

13A

• 
  Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson:
  Uniform direct product theorems: simplified, optimized, and derandomized. 579-588
• 
  Ronen Shaltiel, Emanuele Viola:
  Hardness amplification proofs require majority. 589-598
• 
  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
• 
  Vitaly Feldman:
  Evolvability from learning algorithms. 619-628
• 
  Adam Tauman Kalai, Yishay Mansour, Elad Verbin:
  On agnostic boosting and parity learning. 629-638

Invited talk

• 
  David Haussler:
  Computing how we became human. 639-640

15A

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

15B

• 
  Maria-Florina Balcan, Avrim Blum, Santosh Vempala:
  A discriminative framework for clustering via similarity functions. 671-680
• 
  Robert Kleinberg, Aleksandrs Slivkins, Eli Upfal:
  Multi-armed bandits in metric spaces. 681-690
• 
  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
• 
  Ran Raz:
  Elusive functions and lower bounds for arithmetic circuits. 711-720
• 
  Benjamin Rossman:
  On the constant-depth complexity of k-clique. 721-730
• 
  Scott Aaronson, Avi Wigderson:
  Algebrization: a new barrier in complexity theory. 731-740
• 
  Zeev Dvir, Amir Shpilka, Amir Yehudayoff:
  Hardness-randomness tradeoffs for bounded depth arithmetic circuits. 741-748

16B

• 
  Sung-Soon Choi, Jeong Han Kim:
  Optimal query complexity bounds for finding graphs. 749-758
• 
  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
• 
  Alan M. Frieze, Santosh Vempala, Juan Vera:
  Logconcave random graphs. 779-788
• 
  Libor Barto, Marcin Kozik, Todd Niven:
  Graphs, polymorphisms and the complexity of homomorphism problems. 789-796