Skip to main content
  • Conference proceedings
  • © 2002

Randomization and Approximation Techniques in Computer Science

6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002, Proceedings

Conference proceedings info: RANDOM 2002.

Buy it now

Buying options

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (21 papers)

  1. Front Matter

    Pages I-VIII
  2. Counting Distinct Elements in a Data Stream

    • Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, Luca Trevisan
    Pages 1-10
  3. On Testing Convexity and Submodularity

    • Michal Parnas, Dana Ron, Ronitt Rubinfeld
    Pages 11-25
  4. Counting and Sampling H-Colourings

    • Martin Dyer, Leslie A. Goldberg, Mark Jerrum
    Pages 51-67
  5. Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs

    • Martin Dyer, Mark Jerrum, Eric Vigoda
    Pages 68-77
  6. On the 2-Colorability of Random Hypergraphs

    • Dimitris Achlioptas, Cristopher Moore
    Pages 78-90
  7. Percolation on Finite Cayley Graphs

    • Christopher Malon, Igor Pak
    Pages 91-104
  8. Computing Graph Properties by Randomized Subcube Partitions

    • Ehud Friedgut, Jeff Kahn, Avi Wigderson
    Pages 105-113
  9. Bisection of Random Cubic Graphs

    • J. Díaz, N. Do, M. J. Sernal, N. C. Wormald
    Pages 114-125
  10. Small k-Dominating Sets of Regular Graphs

    • William Duckworth, Bernard Mans
    Pages 126-138
  11. Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View

    • Martin Dyer, Alistair Sinclair, Eric Vigoda, Dror Weitz
    Pages 149-163
  12. Quantum Walks on the Hypercube

    • Cristopher Moore, Alexander Russell
    Pages 164-178
  13. Randomness-Optimal Characterization of Two NP Proof Systems

    • Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano
    Pages 179-193
  14. Is Constraint Satisfaction Over Two Variables Always Easy?

    • Lars Engebretsen, Venkatesan Guruswami
    Pages 224-238

Other Volumes

  1. Randomization and Approximation Techniques in Computer Science

Editors and Affiliations

  • Centre Universitaire d’Informatique, University of Geneva, Genéve 4, Switzerland

    José D. P. Rolim

  • Harvard University, DEAS, Cambridge, USA

    Salil Vadhan

Bibliographic Information

Buy it now

Buying options

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access