Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar (auth.), José D. P. Rolim, Salil Vadhan (eds.)3540441476, 9783540441472
The 21 revised full papers presented were carefully reviewed and selected from 48 submissions. Among the topics addressed are coding, geometric computations, graph colorings, random hypergraphs, graph computations, lattice computations, proof systems, probabilistic algorithms, derandomization, constraint satisfaction, and web graphs analysis.
Table of contents :
Counting Distinct Elements in a Data Stream….Pages 1-10
On Testing Convexity and Submodularity….Pages 11-25
ω-Regular Languages Are Testable with a Constant Number of Queries….Pages 26-38
Optimal Lower Bounds for 2-Query Locally Decodable Linear Codes….Pages 39-50
Counting and Sampling H -Colourings….Pages 51-67
Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs….Pages 68-77
On the 2-Colorability of Random Hypergraphs….Pages 78-90
Percolation on Finite Cayley Graphs….Pages 91-104
Computing Graph Properties by Randomized Subcube Partitions….Pages 105-113
Bisection of Random Cubic Graphs….Pages 114-125
Small k -Dominating Sets of Regular Graphs….Pages 126-138
Finding Sparse Induced Subgraphs of Semirandom Graphs….Pages 139-148
Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View….Pages 149-163
Quantum Walks on the Hypercube….Pages 164-178
Randomness-Optimal Characterization of Two NP Proof Systems….Pages 179-193
A Probabilistic-Time Hierarchy Theorem for “Slightly Non-uniform” Algorithms….Pages 194-208
Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good….Pages 209-223
Is Constraint Satisfaction Over Two Variables Always Easy?….Pages 224-238
Dimensionality Reductions That Preserve Volumes and Distance to Affine Spaces, and Their Algorithmic Applications….Pages 239-253
On the Eigenvalue Power Law….Pages 254-262
Classifying Special Interest Groups in Web Graphs….Pages 263-275
Reviews
There are no reviews yet.