[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Property Testing

Current Research and Surveys

  • Book
  • © 2010

Overview

Editors:
  1. Oded Goldreich

    1. Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Introduction to property testing
  • Survey by leading researchers in the field
  • Subject of intensive research in the last decades

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

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

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

Access this book

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

eBook GBP 35.99
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book GBP 44.99
Price includes VAT (United Kingdom)
  • 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

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.

Similar content being viewed by others

Keywords

Table of contents (30 chapters)

  1. Front Matter

    Download chapter PDF

  2. Editor’s Introduction

    1. A Brief Introduction to Property Testing

      • Oded Goldreich
      Pages 1-5

    2. The Program of the Mini-Workshop

      • Oded Goldreich
      Pages 6-12

  3. Surveys

    1. Limitation on the Rate of Families of Locally Testable Codes

      • Eli Ben-Sasson
      Pages 13-31

    2. Testing Juntas: A Brief Survey

      • Eric Blais
      Pages 32-40

    3. Sublinear-time Algorithms

      • Artur Czumaj, Christian Sohler
      Pages 41-64

    4. Short Locally Testable Codes and Proofs: A Survey in Two Parts

      • Oded Goldreich
      Pages 65-104

    5. Introduction to Testing Graph Properties

      • Oded Goldreich
      Pages 105-141

    6. Property Testing of Massively Parametrized Problems – A Survey

      • Ilan Newman
      Pages 142-157

    7. Sublinear Graph Approximation Algorithms

      • Krzysztof Onak
      Pages 158-166

    8. Transitive-Closure Spanners: A Survey

      • Sofya Raskhodnikova
      Pages 167-196

    9. Testing by Implicit Learning: A Brief Survey

      • Rocco A. Servedio
      Pages 197-210

    10. Invariance in Property Testing

      • Madhu Sudan
      Pages 211-227

  4. Extended Abstracts

    1. Testing Monotone Continuous Distributions on High-Dimensional Real Cubes

      • Michał Adamaszek, Artur Czumaj, Christian Sohler
      Pages 228-233

    2. On Constant Time Approximation of Parameters of Bounded Degree Graphs

      • Noga Alon
      Pages 234-239

    3. Sublinear Algorithms in the External Memory Model

      • Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld
      Pages 240-243

    4. Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

      • Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
      Pages 244-252

    5. Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability

      • Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron
      Pages 253-259

    6. Testing Linear-Invariant Non-linear Properties: A Short Report

      • Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie
      Pages 260-268

    7. Optimal Testing of Reed-Muller Codes

      • Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman
      Pages 269-275
Back to top

Editors and Affiliations

  • Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel

    Oded Goldreich

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation