zbMATH — the first resource for mathematics

Proceedings of the thirty-fourth annual ACM symposium on theory of computing, STOC 2002. Montreal, Quebec, Canada, May 19–21, 2002. (English) Zbl 1074.68502
New York, NY: ACM Press (ISBN 1-581-13495-9). xv, 824 p. (2002).

Show indexed articles as search result.

Contents: Marcus Schaefer, Eric Sedgwick and Daniel Štefankovič, Recognizing string graphs in NP 1–6; Timothy M. Chan, Dynamic subgraph connectivity with geometric applications 7–13; Thomas Eiter, Georg Gottlob and Kazuhisa Makino, New results on monotone dualization and generating hypergraph transversals 14–22; Len Adleman, Qi Cheng, Ashish Goel, Ming-Deh Huang, David Kempe, Pablo Moisset de Espanés and Paul Wilhelm Karl Rothemund, Combinatorial optimization problems in self-assembly 23–32; Irit Dinur and Shmuel Safra, The importance of being biased 33–42; Johan Håstad and S. Venkatesh, On the advantage over a random assignment 43–52; Leslie Ann Goldberg, Steven Kelk and Mike Paterson, The complexity of choosing an \(H\)-colouring (nearly) uniformly at random 53–62; David R. Karger and Matthew S. Levine, Random sampling in residual graphs 63–66; Xiaotie Deng, Christos Papadimitriou and Shmuel Safra, On the complexity of equilibria 67–71; Amos Fiat, Andrew V. Goldberg, Jason D. Hartline and Anna R. Karlin, Competitive generalized auctions 72–81.
Petros Drineas, Iordanis Kerenidis and 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; Peter Gács, Clairvoyant scheduling of random walks 99–108; Dimitris Bertsimas and Santosh Vempala, Solving convex programs by random walks 109–115; Christos H. Papadimitriou, The joy of theory 116; Surender Baswana, Ramesh Hariharan and Sandeep Sen, Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths 117–123; Spyros 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; A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan and M. Strauss, Near-optimal sparse Fourier representations via sampling 152–161.
Sanjeev Arora and Subhash Khot, Fitting algebraic curves to noisy data 162–169; Mark Scharbrodt, Thomas Schickinger and Angelika Steger, A new average case analysis for completion time scheduling 170–178; Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting and Wai-Ha Wong, A unified analysis of hot video schedulers 179–188; Anand Srinivasan and James H. Anderson, Optimal rate-based scheduling on multiprocessors 189–198; Dimitris Achlioptas and 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 Smyth, Reimer’s inequality and Tardos’ conjecture 218–221; Steve Chien, Lars Rasmussen and Alistair Sinclair, Clifford algebras and approximating the permanent 222–231; Noga Alon, W. Fernandez de la Vega, Ravi Kannan and Marek Karpinski, Random sampling and approximation of MAX-CSP problems 232–239; Mary Cryan and Martin Dyer, A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant 240–249.
Mihai Bādoiu, Sariel Har-Peled and Piotr Indyk, Approximate clustering via core-sets 250–257; Susanne Albers, Lene M. Favrholdt and Oliver Giel, On paging with locality of reference 258–267; Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley and J. Ian Munro, Cache-oblivious priority queue and graph algorithm applications 268–276; E. Bachmat, Average case analysis for batched disk scheduling and increasing subsequences 277–286; Artur Czumaj, Piotr Krysta and Berthold Vöcking, Selfish traffic allocation for server farms 287–296; Chandra Chekuri and Sanjeev Khanna, Approximation schemes for preemptive weighted flow time 297–305; Joseph Cheriyan, Santosh Vempala and Adrian Vetta, Approximation algorithms for minimum-cost \(k\)-vertex connected subgraphs 306–312; Kamal Jain and Vijay V. Vazirani, Equitable cost allocations via primal-dual-type algorithms 313–321; Cynthia Dwork and Larry Stockmeyer, 2-round zero knowledge and proof auditors 322–331; Oded Goldreich, Concurrent zero-knowledge with timing, revisited 332–340.
Stefan Dziembowski and Ueli Maurer, Tight security proofs for the bounded-storage model 341–350; Subhash Khot, Hardness results for approximate hypergraph coloring 351–359; Michael Saks and Xiaodong Sun, Space lower bounds for distance approximation in the data stream model 360–369; Miklós Ajtai, T. S. Jayram, Ravi Kumar and D. Sivakumar, Approximate counting of inversions in a data stream 370–379; Moses S. Charikar, Similarity estimation techniques from rounding algorithms 380–388; Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan and Martin J. Strauss, Fast, small-space algorithms for approximate histogram maintenance 389–398; Elliot Anshelevich, David Kempe and Jon 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 and Alan Frieze, Crawling on web graphs 419–427; Tim Roughgarden, The price of anarchy is independent of the network topology 428–437.
Michael Elkin and Guy Kortsarz, Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem 438–447; Michael Alekhnovich, Jan Johannsen, Toniann Pitassi and Alasdair Urquhart, An exponential separation between regular and general resolution 448–456; Eli Ben-Sasson, Size space tradeoffs for resolution 457–464; Lisa Hellerstein and Vijay Raghavan, Exact learning of DNF formulas using DNF hypotheses 465–473; Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld and Alex Samorodnitsky, Monotonicity testing over general poset domains 474–483; Boaz Barak and Yehuda Lindell, Strict polynomial-time in simulation and extraction 484–493; Ran Canetti, Yehuda Lindell, Rafail Ostrovsky and 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 and Tal Rabin, On the composition of authenticated Byzantine agreement 514–523; James Aspnes, Gauri Shah and 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 and Robert E. Tarjan, Meldable heaps and Boolean union-find 573–582; Gerth Stølting Brodal, George Lagogiannis, Christos Makris, Athanasios Tsakalidis and Kostas Tsichlas, Optimal finger search trees in the pointer machine 583–591; Richard Cole and Ramesh Hariharan, Verifying candidate matches in sparse and wildcard matching 592–601; Yijie Han, Deterministic sorting in \(O(n\log\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 and 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 Capalbo, Omer Reingold, Salil Vadhan and Avi Wigderson, Randomness conductors and constant-degree lossless expanders 659–668; Roy Meshulam and Avi Wigderson, Expanders from symmetric codes 669–677; Tuǧkan Batu, Sanjoy Dasgupta, Ravi Kumar and Ronitt Rubinfeld, The complexity of approximating entropy 678–687; Paul Beame and Erik Vee, Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems 688–697; Ashwin Nayak and Julia Salzman, On communication over an entanglement-assisted quantum channel 698–704; Nathan Linial, Avner Magen and Assaf Naor, Girth and Euclidean distortion 705–711; Saugata Basu, Computing the Betti numbers of arrangements 712–720.
Sunil Arya, Theocharis Malamatos and David M. Mount, Space-efficient approximate Voronoi diagrams 721–730; Kamal Jain, Mohammad Mahdian and Amin Saberi, A new greedy approach for facility location problems 731–740; David R. Karger and Matthias Ruhl, Finding nearest neighbors in growth-restricted metrics 741–750; Ryan O’Donnell, Hardness amplification within NP 751–760; Ian Agol, Joel Hass and William Thurston, 3-manifold knot genus is NP-complete 761–766; Subhash Khot, On the power of unique 2-prover 1-round games 767–775; Jeffrey C. Jackson, Adam R. Klivans and Rocco A. Servedio, Learnability beyond \(\text{AC}^0\) 776–784; Mordecai J. Golin, Claire Kenyon and 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 and 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 and Piotr Indyk, Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets 812–821.
The articles of this volume will not be indexed individually. The preceding conference has been reviewed (see Zbl 1074.68500).

68-06 Proceedings, conferences, collections, etc. pertaining to computer science
00B25 Proceedings of conferences of miscellaneous specific interest
68Qxx Theory of computing
Full Text: Link