default search action
34th STOC 2002: Montréal, Québec, Canada
- John H. Reif:
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 - 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
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
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 S. 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
Approximate clustering via core-sets. 250-257 - Susanne Albers, Lene M. Favrholdt
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 S. 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
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
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
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
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
The complexity of approximating entropy. 678-687 - Paul Beame
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 R. Klivans, Rocco A. Servedio:
Learnability beyond AC0. 776-784 - Mordecai J. Golin
Huffman coding with unequal letter costs. 785-791 - Moses Charikar
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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-13 23:36 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: