Theoretical Computer Science and General Issues

Property Testing

Current Research and Surveys

Editors: Goldreich, Oded (Ed.)

  • Provides an introduction to property testing
  • Presents a survey by leading researchers in the field
  • Covers a subject of intensive research in the last decades
see more benefits

Buy this book

eBook $74.99
price for USA (gross)
  • ISBN 978-3-642-16367-8
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Softcover $99.00
price for USA
  • ISBN 978-3-642-16366-1
  • Free shipping for individuals worldwide
  • This title is currently reprinting. You can pre-order your copy now.
About this book

Property Testing is the study of super-fast (randomized) algorithms for approximate decision making. These algorithms are given direct access to items of a huge data set, and determine, whether this data set has some predetermined (global) property or is far from having this property. Remarkably, this approximate decision is made by accessing a small portion of the data set. This state-of-the-art survey presents a collection of extended abstracts and surveys of leading researchers in property testing and related areas; it reflects the program of a mini-workshop on property testing that took place in January 2010 at the Institute for Computer Science (ITCS), Tsinghua University, Beijing, China. The volume contains two editor's introductions, 10 survey papers and 18 extended abstracts.

Table of contents (30 chapters)

  • A Brief Introduction to Property Testing

    Goldreich, Oded

    Pages 1-5

  • The Program of the Mini-Workshop

    Goldreich, Oded

    Pages 6-12

  • Limitation on the Rate of Families of Locally Testable Codes

    Ben-Sasson, Eli

    Pages 13-31

  • Testing Juntas: A Brief Survey

    Blais, Eric

    Pages 32-40

  • Sublinear-time Algorithms

    Czumaj, Artur (et al.)

    Pages 41-64

Buy this book

eBook $74.99
price for USA (gross)
  • ISBN 978-3-642-16367-8
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Softcover $99.00
price for USA
  • ISBN 978-3-642-16366-1
  • Free shipping for individuals worldwide
  • This title is currently reprinting. You can pre-order your copy now.
Loading...

Recommended for you

Loading...

Bibliographic Information

Bibliographic Information
Book Title
Property Testing
Book Subtitle
Current Research and Surveys
Editors
  • Oded Goldreich
Series Title
Theoretical Computer Science and General Issues
Series Volume
6390
Copyright
2010
Publisher
Springer-Verlag Berlin Heidelberg
Copyright Holder
Springer Berlin Heidelberg
eBook ISBN
978-3-642-16367-8
DOI
10.1007/978-3-642-16367-8
Softcover ISBN
978-3-642-16366-1
Edition Number
1
Number of Pages
XI, 359
Number of Illustrations and Tables
5 b/w illustrations
Topics