34. STOC 2002: Montréal, Québec, Canada

• Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic:
  Recognizing string graphs in NP. 1-6
  
• Timothy M. Chan:
  Dynamic subgraph connectivity with geometric applications. 7-13
  
• Thomas Eiter, Georg Gottlob, Kazuhisa Makino:
  New results on monotone dualization and generating hypergraph transversals. 14-22
  
• Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo Moisset de Espanés, Paul W. K. Rothemund:
  Combinatorial optimization problems in self-assembly. 23-32
  
• Irit Dinur, Shmuel Safra:
  The importance of being biased. 33-42
  
• Johan Håstad, Srinivasan Venkatesh:
  On the advantage over a random assignment. 43-52
  
• Leslie Ann Goldberg, Steven Kelk, Mike Paterson:
  The complexity of choosing an H-colouring (nearly) uniformly at random. 53-62
  
• David R. Karger, Matthew S. Levine:
  Random sampling in residual graphs. 63-66
  
• Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra:
  On the complexity of equilibria. 67-71
  
• Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin:
  Competitive generalized auctions. 72-81
  
• Petros Drineas, Iordanis Kerenidis, Prabhakar Raghavan:
  Competitive recommendation systems. 82-90
  
• Michael Molloy:
  The Glauber dynamics on colourings of a graph with high girth and maximum degree. 91-98
  
• Péter Gács:
  Clairvoyant scheduling of random walks. 99-108
  
• Dimitris Bertsimas, Santosh Vempala:
  Solving convex programs by random walks. 109-115
  
• Christos H. Papadimitriou:
  The Joy of Theory. 116
  
• Surender Baswana, Ramesh Hariharan, Sandeep Sen:
  Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths. 117-123
  
• Spyros C. Kontogiannis:
  Lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machines. 124-133
  
• Susanne Albers:
  On randomized online scheduling. 134-143
  
• Ran Raz:
  On the complexity of matrix product. 144-151
  
• Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss:
  Near-optimal sparse fourier representations via sampling. 152-161
  
• Sanjeev Arora, Subhash Khot:
  Fitting algebraic curves to noisy data. 162-169
  
• Mark Scharbrodt, Thomas Schickinger, Angelika Steger:
  A new average case analysis for completion time scheduling. 170-178
  
• Wun-Tat Chan, Tak Wah Lam, Hing-Fung Ting, Prudence W. H. Wong:
  A unified analysis of hot video schedulers. 179-188
  
• Anand Srinivasan, James H. Anderson:
  Optimal rate-based scheduling on multiprocessors. 189-198
  
• Dimitris Achlioptas, Cristopher Moore:
  Almost all graphs with average degree 4 are 3-colorable. 199-208
  
• Michael Molloy:
  Models and thresholds for random constraint satisfaction problems. 209-217
  
• Clifford D. Smyth:
  Reimer's inequality and tardos' conjecture. 218-221
  
• Steve Chien, Lars Eilstrup Rasmussen, Alistair Sinclair:
  Clifford algebras and approximating the permanent. 222-231
  
• Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski:
  Random sampling and approximation of MAX-CSP problems. 232-239
  
• Mary Cryan, Martin E. Dyer:
  A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant. 240-249
  
• Mihai Badoiu, Sariel Har-Peled, Piotr Indyk:
  Approximate clustering via core-sets. 250-257
  
• Susanne Albers, Lene M. Favrholdt, Oliver Giel:
  On paging with locality of reference. 258-267
  
• Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, J. Ian Munro:
  Cache-oblivious priority queue and graph algorithm applications. 268-276
  
• Eitan Bachmat:
  Average case analysis for batched disk scheduling and increasing subsequences. 277-286
  
• Artur Czumaj, Piotr Krysta, Berthold Vöcking:
  Selfish traffic allocation for server farms. 287-296
  
• Chandra Chekuri, Sanjeev Khanna:
  Approximation schemes for preemptive weighted flow time. 297-305
  
• Joseph Cheriyan, Santosh Vempala, Adrian Vetta:
  Approximation algorithms for minimum-cost k-vertex connected subgraphs. 306-312
  
• Kamal Jain, Vijay V. Vazirani:
  Equitable cost allocations via primal-dual-type algorithms. 313-321
  
• Cynthia Dwork, Larry J. Stockmeyer:
  2-round zero knowledge and proof auditors. 322-331
  
• Oded Goldreich:
  Concurrent zero-knowledge with timing, revisited. 332-340
  
• Stefan Dziembowski, Ueli M. Maurer:
  Tight security proofs for the bounded-storage model. 341-350
  
• Subhash Khot:
  Hardness results for approximate hypergraph coloring. 351-359
  
• Michael E. Saks, Xiaodong Sun:
  Space lower bounds for distance approximation in the data stream model. 360-369
  
• Miklós Ajtai, T. S. Jayram, Ravi Kumar, D. Sivakumar:
  Approximate counting of inversions in a data stream. 370-379
  
• Moses Charikar:
  Similarity estimation techniques from rounding algorithms. 380-388
  
• Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, Martin Strauss:
  Fast, small-space algorithms for approximate histogram maintenance. 389-398
  
• Elliot Anshelevich, David Kempe, Jon M. Kleinberg:
  Stability of load balancing algorithms in dynamic adversarial systems. 399-406
  
• Micah Adler:
  Tradeoffs in probabilistic packet marking for IP traceback. 407-418
  
• Colin Cooper, Alan M. Frieze:
  Crawling on web graphs. 419-427
  
• Tim Roughgarden:
  The price of anarchy is independent of the network topology. 428-437
  
• Michael Elkin, Guy Kortsarz:
  Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem. 438-447
  
• Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart:
  An exponential separation between regular and general resolution. 448-456
  
• Eli Ben-Sasson:
  Size space tradeoffs for resolution. 457-464
  
• Lisa Hellerstein, Vijay Raghavan:
  Exact learning of DNF formulas using DNF hypotheses. 465-473
  
• Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky:
  Monotonicity testing over general poset domains. 474-483
  
• Boaz Barak, Yehuda Lindell:
  Strict polynomial-time in simulation and extraction. 484-493
  
• Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai:
  Universally composable two-party and multi-party secure computation. 494-503
  
• Miklós Ajtai:
  The invasiveness of off-line memory checking. 504-513
  
• Yehuda Lindell, Anna Lysyanskaya, Tal Rabin:
  On the composition of authenticated byzantine agreement. 514-523
  
• James Aspnes, Gauri Shah, Jatin Shah:
  Wait-free consensus with infinite arrivals. 524-533
  
• Uriel Feige:
  Relations between average case complexity and approximation complexity. 534-543
  
• Jonas Holmerin:
  Vertex cover on 4-regular hyper-graphs is hard to approximate within 2-epsilon. 544-552
  
• Ran Raz:
  Resolution lower bounds for the weak pigeonhole principle. 553-562
  
• Eli Ben-Sasson:
  Hard examples for bounded depth frege. 563-572
  
• Haim Kaplan, Nira Shafrir, Robert Endre Tarjan:
  Meldable heaps and boolean union-find. 573-582
  
• Gerth Stølting Brodal, George Lagogiannis, Christos Makris, Athanasios K. Tsakalidis, Kostas Tsichlas:
  Optimal finger search trees in the pointer machine. 583-591
  
• Richard Cole, Ramesh Hariharan:
  Verifying candidate matches in sparse and wildcard matching. 592-601
  
• Yijie Han:
  Deterministic sorting in O(nlog log n) time and linear space. 602-608
  
• Daniele Micciancio:
  Improved cryptographic hash functions with worst-case/average-case connection. 609-618
  
• D. Sivakumar:
  Algorithmic derandomization via complexity theory. 619-626
  
• Christopher Umans:
  Pseudo-random generators for all hardnesses. 627-634
  
• Scott Aaronson:
  Quantum lower bound for the collision problem. 635-642
  
• Claude Crépeau, Daniel Gottesman, Adam Smith:
  Secure multi-party quantum computation. 643-652
  
• Sean Hallgren:
  Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem. 653-658
  
• Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson:
  Randomness conductors and constant-degree lossless expanders. 659-668
  
• Roy Meshulam, Avi Wigderson:
  Expanders from symmetric codes. 669-677
  
• Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld:
  The complexity of approximating entropy. 678-687
  
• Paul Beame, Erik Vee:
  Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems. 688-697
  
• Ashwin Nayak, Julia Salzman:
  On communication over an entanglement-assisted quantum channel. 698-704
  
• Nathan Linial, Avner Magen, Assaf Naor:
  Girth and euclidean distortion. 705-711
  
• Saugata Basu:
  Computing the betti numbers of arrangements. 712-720
  
• Sunil Arya, Theocharis Malamatos, David M. Mount:
  Space-efficient approximate Voronoi diagrams. 721-730
  
• Kamal Jain, Mohammad Mahdian, Amin Saberi:
  A new greedy approach for facility location problems. 731-740
  
• David R. Karger, Matthias Ruhl:
  Finding nearest neighbors in growth-restricted metrics. 741-750
  
• Ryan O'Donnell:
  Hardness amplification within NP. 751-760
  
• Ian Agol, Joel Hass, William P. Thurston:
  3-manifold knot genus is NP-complet. 761-766
  
• Subhash Khot:
  On the power of unique 2-prover 1-round games. 767-775
  
• Jeffrey C. Jackson, Adam Klivans, Rocco A. Servedio:
  Learnability beyond AC0. 776-784
  
• Mordecai J. Golin, Claire Kenyon, Neal E. Young:
  Huffman coding with unequal letter costs. 785-791
  
• Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, April Rasala, Amit Sahai, Abhi Shelat:
  Approximating the smallest grammar: Kolmogorov complexity in natural models. 792-801
  
• Venkatesan Guruswami:
  Limits to list decodability of linear codes. 802-811
  
• Venkatesan Guruswami, Piotr Indyk:
  Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. 812-821