Randomization and Approximation Techniques in Computer Science: 6th International Workshop, Random 2002, Cambridge, Ma, Usa, September 13-15, 2002, Pr

ISBN-13: 9783540441472 / Angielski / Miękka / 2002 / 284 str.

J. D. P. Rolim; Jose D. P. Rolim; Salil Vadhan

Opis

Constituting the refereed proceedings of the 6th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2002, held in Cambridge, Massachusetts, USA, in September 2002, the 21 revised, full papers presented here have been carefully reviewed and selected from 48 submissions.

Spis treści

Counting 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.