Atjaunināt sīkdatņu piekrišanu

Introduction to Property Testing [Hardback]

(Weizmann Institute of Science, Israel)
  • Formāts: Hardback, 468 pages, height x width x depth: 259x182x30 mm, weight: 990 g, Worked examples or Exercises
  • Izdošanas datums: 23-Nov-2017
  • Izdevniecība: Cambridge University Press
  • ISBN-10: 1107194059
  • ISBN-13: 9781107194052
Citas grāmatas par šo tēmu:
  • Hardback
  • Cena: 109,33 €
  • Grāmatu piegādes laiks ir 3-4 nedēļas, ja grāmata ir uz vietas izdevniecības noliktavā. Ja izdevējam nepieciešams publicēt jaunu tirāžu, grāmatas piegāde var aizkavēties.
  • Daudzums:
  • Ielikt grozā
  • Piegādes laiks - 4-6 nedēļas
  • Pievienot vēlmju sarakstam
Introduction to Property TestingPalielināt
  • Formāts: Hardback, 468 pages, height x width x depth: 259x182x30 mm, weight: 990 g, Worked examples or Exercises
  • Izdošanas datums: 23-Nov-2017
  • Izdevniecība: Cambridge University Press
  • ISBN-10: 1107194059
  • ISBN-13: 9781107194052
Citas grāmatas par šo tēmu:
Permanent link: https://www.kriso.lv/db/9781107194052.html
Keywords:
An extensive and authoritative introduction to property testing, the study of super-fast algorithms for the structural analysis of large quantities of data in order to determine global properties. This book can be used both as a reference book and a textbook, and includes numerous exercises.

Property testing is concerned with the design of super-fast algorithms for the structural analysis of large quantities of data. The aim is to unveil global features of the data, such as determining whether the data has a particular property or estimating global parameters. Remarkably, it is possible for decisions to be made by accessing only a small portion of the data. Property testing focuses on properties and parameters that go beyond simple statistics. This book provides an extensive and authoritative introduction to property testing. It provides a wide range of algorithmic techniques for the design and analysis of tests for algebraic properties, properties of Boolean functions, graph properties, and properties of distributions.

Recenzijas

'The book is an authoritative source for information on property testing, having been written by an expert in the area who has been instrumental in its development The book is laid out as a textbook, with plenty of exercises and didactic comments, and indeed it would form a good basis for a postgraduate course on property testing Researchers in other areas of algorithms and computational complexity theory will find the book useful as a source of concepts and techniques. It is also likely to serve as the standard reference text on property testing in the coming years.' Mark R. Jerrum, MathSciNet 'Overall, the book is an excellent and comprehensive read. The range of topics discussed in this book is sufficient to attract many students to use it as reference. It can definitely be used as a reference to an advanced undergraduate level course or a beginning graduate level course.' Sarvagya Upadhyay, SIGACT News

Papildus informācija

An extensive and authoritative introduction to property testing, the study of super-fast algorithms for analyzing large quantities of data.
Preface xi
Organization and
Chapter Summaries		 xv
Notation xxiii
Standard Notation
xxiii
Specific Notation Used Extensively
xxiv
Acknowledgments xxv
1 The Main Themes: Approximate Decision and Sublinear Complexity
1(39)
1.1 Introduction
1(5)
1.1.1 Property Testing at a Glance
2(1)
1.1.2 On the Potential Benefits of Property Testers
3(1)
1.1.3 On the Flavor of Property Testing Research
4(1)
1.1.4 Organization and Some Notations
5(1)
1.2 Approximate Decisions
6(8)
1.2.1 A Detour: Approximate Search Problems
6(1)
1.2.2 Property Testing: Approximate Decision Problems
6(1)
1.2.3 Property Testing: Sublinear Complexity
7(3)
1.2.4 Symmetries and Invariants
10(3)
1.2.5 Objects and Representation
13(1)
1.3 Notions, Definitions, Goals, and Basic Observations
14(14)
1.3.1 Basics
15(3)
1.3.2 Ramifications
18(1)
1.3.3 Proximity-Oblivious Testers (POTS)
19(3)
1.3.4 The Algebra of Property Testing
22(4)
1.3.5 Testing via Learning
26(2)
1.4 Historical Notes
28(2)
1.5 Suggested Reading and Exercises
30(8)
Basic Exercises
31(5)
Additional Exercises
36(2)
1.6 Digest: The Most Important Points
38(2)
2 Testing Linearity (Group Homomorphism)
40(9)
2.1 Preliminaries
40(1)
2.2 The Tester
40(5)
2.3
Chapter Notes
45(4)
3 Low-Degree Tests
49(20)
3.1 A Brief Introduction
49(1)
3.2 A Kind of Intuition (which may be skipped)
50(3)
3.2.1 The Univariate Case
50(1)
3.2.2 The Multivariate Case
51(1)
3.2.3 Linking the Above Intuition to the Actual Proof
52(1)
3.3 Background
53(4)
3.4 The Tester
57(8)
3.4.1 Analysis of the Tester
58(6)
3.4.2 Digest (or an Abstraction)
64(1)
3.5
Chapter Notes
65(2)
Exercises
67(2)
4 Testing Monotonicity
69(23)
4.1 Introduction
69(1)
4.2 Boolean Functions on the Boolean Hypercube
70(7)
4.2.1 The Edge Test
70(5)
4.2.2 Path Tests
75(2)
4.3 Multivalued Functions on the Discrete Line
77(5)
4.3.1 A Tester Based on Binary Search
77(4)
4.3.2 Other Testers
81(1)
4.4 Multivalued Functions on the Hypergrid
82(5)
4.4.1 Dimension Reduction (Proof of Lemma 4.13)
84(1)
4.4.2 Range Reduction (Overview of the Proof of Lemma 4.14)
85(2)
4.5
Chapter Notes
87(5)
4.5.1 History and Credits
87(1)
4.5.2 Related Problems
88(1)
4.5.3 Exercises
89(3)
5 Testing Dictatorships, Juntas, and Monomials
92(28)
5.1 Introduction
92(1)
5.2 Testing Dictatorship via Self-correction
93(12)
5.2.1 The Tester
94(3)
5.2.2 Testing Monomials
97(4)
5.2.3 The Self-correction Paradigm: An Abstraction
101(4)
5.3 Testing Juntas
105(7)
5.4
Chapter Notes
112(1)
Basic Exercises
112(3)
Additional Exercises
115(5)
6 Testing by Implicit Sampling
120(14)
6.1 Introduction
120(1)
6.2 Testing Subsets of k-Juntas
121(7)
6.3 Extension to Properties Approximated by Subsets of k-Juntas
128(3)
6.4
Chapter Notes
131(1)
On Testing Problems Associated with Sets of Boolean Functions
131(1)
Exercises
132(2)
7 Lower Bounds Techniques
134(28)
7.1 Introduction
134(1)
7.2 Indistinguishability of Distributions
135(7)
7.2.1 The Actual Method
137(3)
7.2.2 Illustrating the Application of the Method
140(1)
7.2.3 Further Reflections
141(1)
7.3 Reduction from Communication Complexity
142(7)
7.3.1 Communication Complexity
143(1)
7.3.2 The Methodology
144(2)
7.3.3 Illustrating the Application of the Methodology
146(3)
7.4 Reduction among Testing Problems
149(4)
7.5 Lower Bounds for Restricted Testers
153(4)
7.5.1 One-Sided Error Testers
153(1)
7.5.2 Nonadaptive Testers
154(3)
7.6
Chapter Notes
157(1)
Exercises
157(5)
8 Testing Graph Properties in the Dense Graph Model
162(51)
8.1 The General Context: Introduction to Testing Graph Properties
163(4)
8.1.1 Basic Background
163(1)
8.1.2 Three Models of Testing Graph Properties
164(3)
8.2 The Dense Graph Model: Some Basics
167(9)
8.2.1 The Actual Definition
167(2)
8.2.2 Abuses of the Model: Trivial and Sparse Properties
169(1)
8.2.3 Testing Degree Regularity
170(5)
8.2.4 Digest: Levin's Economical Work Investment Strategy
175(1)
8.3 Graph Partition Problems
176(11)
8.3.1 Testing Bipartiteness
180(4)
8.3.2 The Actual Definition and the General Result
184(3)
8.4 Connection to Szemei-edi's Regularity Lemma
187(10)
8.4.1 The Regularity Lemma
188(1)
8.4.2 Subgraph Freeness
189(7)
8.4.3 The Structure of Properties That Have Size-Oblivious Testers
196(1)
8.5 A Taxonomy of the Known Results
197(7)
8.5.1 Testability in q(element of) Queries, for any Function q
199(1)
8.5.2 Testability in poly(1/element of) Queries
200(1)
8.5.3 Testability in Otilde(1/element of) Queries
201(1)
8.5.4 Additional Issues
202(2)
8.6
Chapter Notes
204(9)
8.6.1 Historical Perspective and Credits
204(2)
8.6.2 Testing versus Other Forms of Approximation
206(1)
8.6.3 A Contrast with Recognizing Graph Properties
207(1)
8.6.4 Exercises
208(5)
9 Testing Graph Properties in the Bounded-Degree Graph Model
213(58)
9.1 The Bounded-Degree Model: Definitions and Issues
214(4)
9.2 Testing by a Local Search
218(12)
9.2.1 Testing Subgraph Freeness
218(1)
9.2.2 Testing Degree Regularity
219(2)
9.2.3 Testing Connectivity
221(2)
9.2.4 Testing t-Connectivity (Overview and One Detail)
223(4)
9.2.5 Testing Cycle-Freeness (with Two-Sided Error)
227(3)
9.3 Lower Bounds
230(6)
9.3.1 Bipartiteness
230(2)
9.3.2 Applications to Other Properties
232(3)
9.3.3 Linear Lower Bounds
235(1)
9.4 Testing by Random Walks
236(12)
9.4.1 Testing Bipartiteness
236(7)
9.4.2 One-Sided Error Tester for Cycle-Freeness
243(5)
9.5 Testing by Implementing and Utilizing Partition Oracles
248(11)
9.5.1 The Simpler Implementation
252(5)
9.5.2 The Better Implementation
257(2)
9.6 A Taxonomy of the Known Results
259(3)
9.6.1 Testability in q(element of) Queries, for Any Function q
259(1)
9.6.2 Testability in Otilde(k1/2) · poly(l/element of) Queries
260(1)
9.6.3 Additional Issues
261(1)
9.7
Chapter Notes
262(9)
9.7.1 Historical Perspective and Credits
262(1)
9.7.2 Directed Graphs
263(1)
9.7.3 Exercises
264(7)
10 Testing Graph Properties in the General Graph Model
271(33)
10.1 The General Graph Model: Definitions and Issues
272(3)
10.1.1 Perspective: Comparison to the Two Previous Models
272(1)
10.1.2 The Actual Definition
273(2)
10.2 On Obtaining Testers for the Current Model
275(6)
10.2.1 An Explicit Adaptation: The Case of Connectivity
276(1)
10.2.2 Using a Reduction: The Case of Bipartiteness
277(4)
10.3 Estimating the Average Degree and Selecting Random Edges
281(12)
10.3.1 Lower Bounds
282(1)
10.3.2 Algorithms
283(10)
10.4 Using Adjacency Queries: The Case of Bipartiteness
293(3)
10.5
Chapter Notes
296(8)
10.5.1 Gaps between the General Graph Model and the Bounded-Degree Model
296(2)
10.5.2 History and Credits
298(1)
10.5.3 Reflections
298(2)
10.5.4 Exercises
300(4)
11 Testing Properties of Distributions
304(44)
11.1 The Model
304(5)
11.1.1 Testing Properties of Single Distributions
305(2)
11.1.2 Testing Properties of Pairs of Distributions
307(1)
11.1.3 Label-invariant Properties
308(1)
11.1.4 Organization
309(1)
11.2 Testing Equality to a Fixed Distribution
309(11)
11.2.1 The Collision Probability Tester and Its Analysis
310(3)
11.2.2 The General Case (Treated by a Reduction to Testing Uniformity)
313(6)
11.2.3 A Lower Bound
319(1)
11.3 Testing Equality between Two Unknown Distributions
320(15)
11.3.1 Detour: Poisson Distributions
321(3)
11.3.2 The Actual Algorithm and Its Analysis
324(6)
11.3.3 Applications: Reduction to the Case of Small Norms
330(5)
11.4 On the Complexity of Testing Properties of Distributions
335(5)
11.5
Chapter Notes
340(8)
11.5.1 History and Credits
340(1)
11.5.2 Exercises
341(7)
12 Ramifications and Related Topics
348(22)
12.1 Tolerant Testing and Distance Approximation
348(3)
12.2 Additional Promises on the Input
351(1)
12.3 Sample-Based Testers
352(1)
12.4 Testing with Respect to Other Distance Measures
353(2)
12.5 Local Computation Algorithms
355(6)
12.5.1 Definitions
356(2)
12.5.2 Finding Huge Structures
358(2)
12.5.3 Local Reconstruction
360(1)
12.6 Noninteractive Proofs of Proximity (MAPS)
361(4)
12.7
Chapter Notes
365(5)
12.7.1 Historical Notes
365(1)
12.7.2 Massively Parameterized Properties
366(1)
12.7.3 Exercises
366(4)
13 Locally Testable Codes and Proofs
370(41)
13.1 Introduction
371(1)
13.2 Definitions
372(11)
13.2.1 Codeword Testers
372(2)
13.2.2 Proof Testers
374(2)
13.2.3 Ramifications and Relation to Property Testing
376(6)
13.2.4 On Relating Locally Testable Codes and Proofs
382(1)
13.3 Results and Ideas
383(20)
13.3.1 The Mere Existence of Locally Testable Codes and Proofs
384(3)
13.3.2 Locally Testable Codes and Proofs of Polynomial Length
387(10)
13.3.3 Locally Testable Codes and Proofs of Nearly Linear Length
397(6)
13.4
Chapter Notes
403(12)
13.4.1 Historical Notes
403(1)
13.4.2 On Obtaining Superfast testers
404(1)
13.4.3 The Alternative Regime: LTCs of Linear Length
405(2)
13.4.4 Locally Decodable Codes
407(1)
13.4.5 Exercises
408(3)
Appendix A: Probabilistic Preliminaries 411(12)
A.1 Notational Conventions
411(1)
A.2 Some Basic Notions and Facts
412(1)
A.3 Basic Facts Regarding Expectation and Variance
413(2)
A.4 Three Inequalities
415(8)
A.4.1 Markov's Inequality
415(1)
A.4.2 Chebyshev's Inequality
416(3)
A.4.3 Chernoff Bound
419(3)
A.4.4 Pairwise Independent versus Totally Independent Sampling
422(1)
Appendix B: A Mini-Compendium of General Results 423(4)
Appendix C: An Index of Specific Results 427(2)
References 429(14)
Index 443
Oded Goldreich is Professor of Computer Science at the Weizmann Institute of Science and holds the Meyer W. Weisgal Professorial Chair. He has made numerous contributions to property testing and to the theory of computation at large. He is the author of several books, including the two-volume Foundations of Cryptography (Cambridge, Vol. 1 2008, Vol. 2 2009) and Computational Complexity: A Conceptual Perspective (Cambridge, 2008). He is an associate editor of the journal Computational Complexity, former editor of the Journal of Cryptology and SIAM Journal on Computing, and has been invited to speak at numerous conferences, including the 1994 International Congress of Mathematicians. Oded Goldreich was awarded the 2017 Donald E. Knuth prize for outstanding contributions to the foundation of computer science.