Skip to main content
SpringerLink
Log in

Randomization and Approximation Techniques in Computer Science

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

  • Conference proceedings
  • © 2002

Overview

Editors:
  1. José D. P. Rolim

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Salil Vadhan

    1. Harvard University, DEAS, Cambridge, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 2483)

Included in the following conference series:

Conference proceedings info: RANDOM 2002.

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

Access this book

Log in via an institution
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

Licence this eBook for your library

Institutional subscriptions

Table of contents (21 papers)

  1. Front Matter

    Pages I-VIII
    Download chapter PDF

  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. ω-Regular Languages Are Testable with a Constant Number of Queries

    • Hana Chockler, Orna Kupferman
    Pages 26-38

  5. Optimal Lower Bounds for 2-Query Locally Decodable Linear Codes

    • Kenji Obata
    Pages 39-50

  6. Counting and Sampling H-Colourings

    • Martin Dyer, Leslie A. Goldberg, Mark Jerrum
    Pages 51-67

  7. Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs

    • Martin Dyer, Mark Jerrum, Eric Vigoda
    Pages 68-77

  8. On the 2-Colorability of Random Hypergraphs

    • Dimitris Achlioptas, Cristopher Moore
    Pages 78-90

  9. Percolation on Finite Cayley Graphs

    • Christopher Malon, Igor Pak
    Pages 91-104

  10. Computing Graph Properties by Randomized Subcube Partitions

    • Ehud Friedgut, Jeff Kahn, Avi Wigderson
    Pages 105-113

  11. Bisection of Random Cubic Graphs

    • J. Díaz, N. Do, M. J. Sernal, N. C. Wormald
    Pages 114-125

  12. Small k-Dominating Sets of Regular Graphs

    • William Duckworth, Bernard Mans
    Pages 126-138

  13. Finding Sparse Induced Subgraphs of Semirandom Graphs

    • Amin Coja-Oghlan
    Pages 139-148

  14. Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View

    • Martin Dyer, Alistair Sinclair, Eric Vigoda, Dror Weitz
    Pages 149-163

  15. Quantum Walks on the Hypercube

    • Cristopher Moore, Alexander Russell
    Pages 164-178

  16. Randomness-Optimal Characterization of Two NP Proof Systems

    • Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano
    Pages 179-193

  17. A Probabilistic-Time Hierarchy Theorem for “Slightly Non-uniform” Algorithms

    • Boaz Barak
    Pages 194-208

  18. Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good

    • Oded Goldreich, Avi Wigderson
    Pages 209-223

  19. Is Constraint Satisfaction Over Two Variables Always Easy?

    • Lars Engebretsen, Venkatesan Guruswami
    Pages 224-238

  20. Dimensionality Reductions That Preserve Volumes and Distance to Affine Spaces, and Their Algorithmic Applications

    • Avner Magen
    Pages 239-253
Back to top

Other volumes

  1. Randomization and Approximation Techniques in Computer Science

Keywords

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

Publish with us

Policies and ethics

Back to top

Search

Navigation