Randomization and approximation techniques in computer science. 6th international workshop, RANDOM 2002, Cambridge, MA, USA, September 13--15, 2002. Proceedings (Q1850311)

The articles of this volume will be reviewed individually. The preceding workshop (5th, 2001) has been reviewed (see Zbl 0969.00095). Indexed articles: \textit{Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca}, Counting distinct elements in a data stream, 1-10 [Zbl 1028.68949] \textit{Parnas, Michal; Ron, Dana; Rubinfeld, Ronitt}, On testing convexity and submodularity, 11-25 [Zbl 1028.90530] \textit{Chockler, Hana; Kupferman, Orna}, \(\omega\)-regular languages are testable with a constant number of queries, 26-38 [Zbl 1028.68946] \textit{Obata, Kenji}, Optimal lower bounds for 2-query locally decodable linear codes, 39-50 [Zbl 1028.94512] \textit{Dyer, Martin; Goldberg, Leslie A.; Jerrum, Mark}, Counting and sampling \(H\)-colourings, 51-67 [Zbl 1028.68098] \textit{Dyer, Martin; Jerrum, Mark; Vigoda, Eric}, Rapidly mixing Markov chains for dismantleable constraint graphs, 68-77 [Zbl 1028.68099] \textit{Achlioptas, Dimitris; Moore, Cristopher}, On the 2-colorability of random hypergraphs, 78-90 [Zbl 1030.05084] \textit{Malon, Christopher; Pak, Igor}, Percolation on finite Cayley graphs, 91-104 [Zbl 1030.05057] \textit{Friedgut, Ehud; Kahn, Jeff; Wigderson, Avi}, Computing graph properties by randomized subcube partitions, 105-113 [Zbl 1028.68567] \textit{Díaz, J.; Do, N.; Serna, M. J.; Wormald, N. C.}, Bisection of random cubic graphs, 114-125 [Zbl 1028.68565] \textit{Duckworth, William; Mans, Bernard}, Small \(k\)-dominating sets of regular graphs, 126-138 [Zbl 1028.68566] \textit{Coja-Oghlan, Amin}, Finding sparse induced subgraphs of semirandom graphs, 139-148 [Zbl 1028.68097] \textit{Dyer, Martin; Sinclair, Alistair; Vigoda, Eric; Weitz, Dror}, Mixing in time and space for lattice spin systems: A combinatorial view, 149-163 [Zbl 1028.68562] \textit{Moore, Cristopher; Russell, Alexander}, Quantum walks on the hypercube, 164-178 [Zbl 1028.68570] \textit{De Santis, Alfredo; Di Crescenzo, Giovanni; Persiano, Giuseppe}, Randomness-optimal characterization of two NP proof systems, 179-193 [Zbl 1028.68947] \textit{Barak, Boaz}, A probabilistic-time hierarchy theorem for ``slightly non-uniform'' algorithms, 194-208 [Zbl 1028.68058] \textit{Goldreich, Oded; Wigderson, Avi}, Derandomization that is rarely wrong from short advice that is typically good, 209-223 [Zbl 1028.68225] \textit{Engebretsen, Lars; Guruswami, Venkatesan}, Is constraint satisfaction over two variables always easy?, 224-238 [Zbl 1028.68227] \textit{Magen, Avner}, Dimensionality reductions that preserve volumes and distance to affine spaces, and their algorithmic applications, 239-253 [Zbl 1028.68228] \textit{Mihail, Milena; Papadimitriou, Christos}, On the eigenvalue power law, 254-262 [Zbl 1028.68569] \textit{Cooper, Colin}, Classifying special interest groups in web graphs, 263-275 [Zbl 1028.68564]