Limit search to available items
Book Cover
E-book

Title Computational complexity and property testing : on the interplay between randomness and computation / Oded Goldreich et al
Published Cham : Springer, 2020

Copies

Description 1 online resource (391 pages)
Series Lecture Notes in Computer Science ; 12050
LNCS sublibrary. SL1, Theoretical computer science and general issues
Lecture notes in computer science ; 12050.
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
Contents Intro -- Preface -- Contents -- A Probabilistic Error-Correcting Scheme that Provides Partial Secrecy -- 1 Original Introduction (Dated April 1997) -- 2 Main Result -- 3 An Efficient Wire-Tap Channel Encoding Scheme -- References -- Bridging a Small Gap in the Gap Amplification of Assignment Testers -- 1 Background -- 1.1 Assignment Testers and Gap Amplification -- 1.2 Overview of the Proof of Theorem 2 -- 2 The Gap -- 3 Bridging the Gap -- 4 Digest -- References -- On (Valiant's) Polynomial-Size Monotone Formula for Majority -- 1 The Statement -- 2 The Proof -- 2.1 The Randomized Reduction
2.2 Solving the Average-Case Problem -- 3 Comparison to Valiant's Proof -- References -- Two Comments on Targeted Canonical Derandomizers -- 1 Introduction -- 2 Preliminaries -- 2.1 Promise Problems -- 2.2 BPP Search Problem -- 3 Definitional Treatment -- 3.1 The Standard (Non-uniformly Strong) Definition -- 3.2 The Original Notion of Targeted Generators -- 3.3 The New Notion of Targeted Generators -- 4 The Main Result -- 5 Targeted Hitters -- 6 Reflections (or De-construction) -- References -- On the Effect of the Proximity Parameter on Property Testers -- 1 Introduction -- 2 Technical Treatment
3 Upper Bounds -- 3.1 A Generic Upper Bound -- 3.2 Improved Upper Bounds for Specific Functions (e.g., Fleqt, n) -- 4 Lower Bounds -- 4.1 On the AN-Complexity of Almost All Multilinear Functions -- 4.2 The AN-Complexity of Bilinear Functions and Matrix Rigidity -- 4.3 On Structured Rigidity -- 5 On Two Restricted Models -- 5.1 On Computing Without Cancellation -- 5.2 Addition and Multiplication Gates of Parameterized Arity -- References -- On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing -- 1 Introduction -- 1.1 The Current Work
1.2 Organization -- 2 Preliminaries -- 3 The General Formulation of the Methodology -- 4 Application to Codeword Testing -- 5 Nonadaptive Testers and One-Way Communication -- 6 On One-Sided Error and Non-binary Alphabets -- 6.1 One-Sided Error Versions -- 6.2 Non-binary Alphabets -- 7 Emulating the General Formulation by the Restricted One -- 7.1 Step 1: A Syntactic Special Case -- 7.2 Step 2: The Case of Deterministic Protocols -- 7.3 Step 3: The General Case -- 8 Conclusions -- References -- Super-Perfect Zero-Knowledge Proofs -- 1 Introduction -- 1.1 Our Results -- 1.2 Models of PPT
Summary This volume contains a collection of studies in the areas of complexity theory and property testing. The 21 pieces of scientific work included were conducted at different times, mostly during the last decade. Although most of these works have been cited in the literature, none of them was formally published before. Within complexity theory the topics include constant-depth Boolean circuits, explicit construction of expander graphs, interactive proof systems, monotone formulae for majority, probabilistically checkable proofs (PCPs), pseudorandomness, worst-case to average-case reductions, and zero-knowledge proofs. Within property testing the topics include distribution testing, linearity testing, lower bounds on the query complexity (of property testing), testing graph properties, and tolerant testing. A common theme in this collection is the interplay between randomness and computation
Bibliography References-On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions-1 Introduction-1.1 The General Context-1.2 The Candidate Functions-1.3 Design by Direct Composition: The D-Canonical Model-1.4 Design by Nested Composition: The ND-Canonical Model-1.5 The Underlying Models of Arithmetic Circuit and AN-Complexity-1.6 Related Work-1.7 Subsequent Work-1.8 Various Conventions-1.9 Organization and Additional Highlights-2 Multilinear Circuits with General Gates-2.1 The Two Complexity Measures-2.2 Relation to Canonical Circuits
Notes 1.3 Organization
Print version record
Subject Computational complexity.
Computer networking & communications.
Maths for computer scientists.
Artificial intelligence.
Information retrieval.
Algorithms & data structures.
Computer science.
Computers -- Networking -- General.
Computers -- Mathematical & Statistical Software.
Computers -- Intelligence (AI) & Semantics.
Computers -- Information Technology.
Computers -- Data Modeling & Design.
Computers -- Computer Science.
Computational complexity
Form Electronic book
Author Goldreich, Oded.
Benjamini, Itai
Decatur, Scott
Leshkowitz, Maya
Meir, Or
Ron, Dana
Rothblum, Guy
Tal, Avishay
Teichner, Liav
Tell, Roei
ISBN 9783030436629
3030436624
3030436616
9783030436612
9783030436636
3030436632