LEADER 05845nam 22007575 450 001 9910143898803321 005 20251116234256.0 010 $a3-540-45726-7 024 7 $a10.1007/3-540-45726-7 035 $a(CKB)1000000000211794 035 $a(SSID)ssj0000326085 035 $a(PQKBManifestationID)11230933 035 $a(PQKBTitleCode)TC0000326085 035 $a(PQKBWorkID)10265897 035 $a(PQKB)11626665 035 $a(DE-He213)978-3-540-45726-8 035 $a(MiAaPQ)EBC3072369 035 $a(PPN)155232878 035 $a(BIP)7887492 035 $a(EXLCZ)991000000000211794 100 $a20121227d2002 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aRandomization and Approximation Techniques in Computer Science $e6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002, Proceedings /$fedited by Jose D.P. Rolim, Salil Vadhan 205 $a1st ed. 2002. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2002. 215 $a1 online resource (VIII, 284 p.) 225 1 $aLecture Notes in Computer Science,$x0302-9743 ;$v2483 300 $aBibliographic Level Mode of Issuance: Monograph 311 08$a3-540-44147-6 320 $aIncludes bibliographical references and index. 327 $aCounting Distinct Elements in a Data Stream -- On Testing Convexity and Submodularity -- ?-Regular Languages Are Testable with a Constant Number of Queries -- Optimal Lower Bounds for 2-Query Locally Decodable Linear Codes -- Counting and Sampling H-Colourings -- Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs -- On the 2-Colorability of Random Hypergraphs -- Percolation on Finite Cayley Graphs -- Computing Graph Properties by Randomized Subcube Partitions -- Bisection of Random Cubic Graphs -- Small k-Dominating Sets of Regular Graphs -- Finding Sparse Induced Subgraphs of Semirandom Graphs -- Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View -- Quantum Walks on the Hypercube -- Randomness-Optimal Characterization of Two NP Proof Systems -- A Probabilistic-Time Hierarchy Theorem for ?Slightly Non-uniform? Algorithms -- Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good -- Is Constraint Satisfaction Over Two Variables Always Easy? -- Dimensionality Reductions That Preserve Volumes and Distance to Affine Spaces, and Their Algorithmic Applications -- On the Eigenvalue Power Law -- Classifying Special Interest Groups in Web Graphs. 330 $aThis volume contains the papers presented at the 6th International Workshop on Randomization and Approximation Techniques in Computer Science (RAN- DOM 2002), which took place at Harvard University, Cambridge, Massachusetts, from September 13-15, 2002. RANDOM 2002 was concerned with applications of randomness to computational and combinatorial problems, and was the sixth workshop in the series following Bologna, Barcelona, Berkeley, Geneva, and B- keley again. The volume contains 21 contributed papers, selected by the program c- mittee from 48 submissions received in response to the call for papers. We thank all of the authors who submitted papers, our invited speakers, the members of the program committee: Dimitris Achlioptas, Microsoft Research Martin Dyer, U. of Leeds Uriel Feige, Weizmann Institute Russell Impagliazzo, UC San Diego Sampath Kannan, U. of Pennsylvania David Karger, MIT Nati Linial, Hebrew U. Rafail Ostrovsky, Telcordia Technologies Paul Spirakis, U. of Patras and CTI Angelika Steger, TU Munich Ršudiger Urbanke, Swiss Federal Inst. of Tech. Salil Vadhan, Harvard U., chair, and the external reviewers: N. Alon, R. Alur, A. Ambainis, T. Batu, J. Feig- baum, S. Gerke, Y. Gertner, A. Goerdt, L. Goldberg, J. Hastad, C. Iliopoulos, Y. Ishai, V. Kabanets, S. Khot, L. Kirousis, S. Kontogiannis, M. Krivelevich, M. Mavronicolas, A. McGregor, F. McSherry, D. van Melkebeek, M. Molloy, E. Mossel, S. Nikoletseas, R. Raz, D. Ron, P. Tetali, L. Trevisan, E. Vigoda, J. Watrous, and P. Winkler. 410 0$aLecture Notes in Computer Science,$x0302-9743 ;$v2483 606 $aComputer programming 606 $aComputer science?Mathematics 606 $aAlgorithms 606 $aNumerical analysis 606 $aProgramming Techniques$3https://scigraph.springernature.com/ontologies/product-market-codes/I14010 606 $aMathematics of Computing$3https://scigraph.springernature.com/ontologies/product-market-codes/I17001 606 $aAlgorithm Analysis and Problem Complexity$3https://scigraph.springernature.com/ontologies/product-market-codes/I16021 606 $aNumeric Computing$3https://scigraph.springernature.com/ontologies/product-market-codes/I1701X 606 $aDiscrete Mathematics in Computer Science$3https://scigraph.springernature.com/ontologies/product-market-codes/I17028 615 0$aComputer programming. 615 0$aComputer science?Mathematics. 615 0$aAlgorithms. 615 0$aNumerical analysis. 615 14$aProgramming Techniques. 615 24$aMathematics of Computing. 615 24$aAlgorithm Analysis and Problem Complexity. 615 24$aNumeric Computing. 615 24$aDiscrete Mathematics in Computer Science. 676 $a004/.07/27 702 $aRolim$b Jose D.P$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aVadhan$b Salil$4edt$4http://id.loc.gov/vocabulary/relators/edt 712 12$aInternational Workshop on Randomization and Approximation Techniques in Computer Science 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910143898803321 996 $aRandomization and Approximation Techniques in Computer Science$92072177 997 $aUNINA