Randomization and Approximation Techniques in Computer Science 6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002, Proceedings
| Other Authors: | , |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
2002, 2002
|
| Edition: | 1st ed. 2002 |
| Series: | Lecture Notes in Computer Science
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- 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