34. STOC 2002: Montréal, Québec, Canada
John H. Reif (Ed.): Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada. ACM 2002 ISBN 1-58113-495-9- 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
- Leslie Ann Goldberg, Steven Kelk, Mike Paterson: The complexity of choosing an H-colouring (nearly) uniformly at random. 53-62
- Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin: Competitive generalized auctions. 72-81
- 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
- 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
- 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
- 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
- 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
- Joseph Cheriyan, Santosh Vempala, Adrian Vetta: Approximation algorithms for minimum-cost k-vertex connected subgraphs. 306-312
- Oded Goldreich: Concurrent zero-knowledge with timing, revisited. 332-340
- 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
- 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
- Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky: Monotonicity testing over general poset domains. 474-483
- 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
- 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
- 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
- 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
- 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
- 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
- Ryan O'Donnell: Hardness amplification within NP. 751-760
- Subhash Khot: On the power of unique 2-prover 1-round games. 767-775
- 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team