000 07900cam a2200985 a 4500
001 on1150154692
003 OCoLC
005 20250707092951.0
006 m o d
007 cr un|---aucuu
008 200411s2020 sz o 000 0 eng d
040 _aEBLCP
_beng
_epn
_cEBLCP
_dGW5XE
_dEBLCP
_dLQU
_dOCLCF
_dVT2
_dNLW
_dDCT
_dOCLCQ
_dOCLCO
_dCOM
_dOCLCQ
_dAUD
_dOCLCQ
_dOCLCO
_dOCLCQ
_dOCLCL
019 _a1156327383
_a1162779404
_a1181902610
_a1203978847
_a1224378989
_a1237473955
_a1244634875
_a1246359084
020 _a9783030436629
_q(electronic bk.)
020 _a3030436624
_q(electronic bk.)
020 _a3030436616
020 _a9783030436612
020 _a9783030436636
_q(print)
020 _a3030436632
020 _z9783030436612
024 7 _a10.1007/978-3-030-43662-9
_2doi
029 1 _aAU@
_b000067124617
029 1 _aAU@
_b000067504543
029 1 _aAU@
_b000068811319
029 1 _aDKDLA
_b820120-katalog:999890133105765
035 _a(OCoLC)1150154692
_z(OCoLC)1156327383
_z(OCoLC)1162779404
_z(OCoLC)1181902610
_z(OCoLC)1203978847
_z(OCoLC)1224378989
_z(OCoLC)1237473955
_z(OCoLC)1244634875
_z(OCoLC)1246359084
037 _bSpringer
050 4 _aQA267.7
072 7 _aUY
_2bicssc
072 7 _aCOM014000
_2bisacsh
072 7 _aUY
_2thema
072 7 _aUYA
_2thema
082 0 4 _a511.3/52
_223
049 _aMAIN
245 0 0 _aComputational complexity and property testing :
_bon the interplay between randomness and computation /
_cOded Goldreich et al.
260 _aCham :
_bSpringer,
_c2020.
300 _a1 online resource (391 pages)
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
347 _bPDF
490 1 _aLecture Notes in Computer Science ;
_v12050
490 1 _aLNCS sublibrary. SL1, Theoretical computer science and general issues
588 0 _aPrint version record.
505 0 _aIntro -- 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
505 8 _a2.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
504 _aReferences-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
505 8 _a3 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
505 8 _a1.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
500 _a1.3 Organization
520 _aThis 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.
650 0 _aComputational complexity.
_9391
650 6 _aComplexité de calcul (Informatique)
650 7 _aComputer networking & communications.
_2bicssc
_953942
650 7 _aMaths for computer scientists.
_2bicssc
_953449
650 7 _aArtificial intelligence.
_2bicssc
_91340
650 7 _aInformation retrieval.
_2bicssc
650 7 _aAlgorithms & data structures.
_2bicssc
_953448
650 7 _aComputer science.
_2bicssc
_9941
650 7 _aComputers
_xNetworking
_xGeneral.
_2bisacsh
_917954
650 7 _aComputers
_xMathematical & Statistical Software.
_2bisacsh
_954021
650 7 _aComputers
_xIntelligence (AI) & Semantics.
_2bisacsh
_917680
650 7 _aComputers
_xInformation Technology.
_2bisacsh
_914211
650 7 _aComputers
_xData Modeling & Design.
_2bisacsh
_927222
650 7 _aComputers
_xComputer Science.
_2bisacsh
_917992
650 7 _aComputational complexity
_2fast
_9391
700 1 _aGoldreich, Oded.
_9172
700 1 _aBenjamini, Itai.
_9212025
700 1 _aDecatur, Scott.
_9212026
700 1 _aLeshkowitz, Maya.
_9212027
700 1 _aMeir, Or.
_9212028
700 1 _aRon, Dana.
_995611
700 1 _aRothblum, Guy.
_9212029
700 1 _aTal, Avishay.
_9212030
700 1 _aTeichner, Liav.
_9212031
700 1 _aTell, Roei.
_9212032
758 _ihas work:
_aComputational complexity and property testing (Text)
_1https://id.oclc.org/worldcat/entity/E39PCGCvRwqDy6KmVPfTG8gYRq
_4https://id.oclc.org/worldcat/ontology/hasWork
776 0 8 _iPrint version:
_aGoldreich, Oded.
_tComputational Complexity and Property Testing : On the Interplay Between Randomness and Computation.
_dCham : Springer International Publishing AG, ©2020
_z9783030436612
830 0 _aLecture notes in computer science ;
_v12050.
830 0 _aLNCS sublibrary.
_nSL 1,
_pTheoretical computer science and general issues.
_920736
856 4 0 _uhttps://link.springer.com/10.1007/978-3-030-43662-9
938 _aProQuest Ebook Central
_bEBLB
_nEBL6157930
994 _a92
_bATIST
999 _c647032
_d647032