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