MARC details
| 000 -LEADER |
|---|
| fixed length control field |
07900cam a2200985 a 4500 |
| 001 - CONTROL NUMBER |
|---|
| control field |
on1150154692 |
| 003 - CONTROL NUMBER IDENTIFIER |
|---|
| control field |
OCoLC |
| 005 - DATE AND TIME OF LATEST TRANSACTION |
|---|
| control field |
20250707092951.0 |
| 006 - FIXED-LENGTH DATA ELEMENTS--ADDITIONAL MATERIAL CHARACTERISTICS |
|---|
| fixed length control field |
m o d |
| 007 - PHYSICAL DESCRIPTION FIXED FIELD--GENERAL INFORMATION |
|---|
| fixed length control field |
cr un|---aucuu |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION |
|---|
| fixed length control field |
200411s2020 sz o 000 0 eng d |
| 040 ## - CATALOGING SOURCE |
|---|
| Original cataloging agency |
EBLCP |
| Language of cataloging |
eng |
| Description conventions |
pn |
| Transcribing agency |
EBLCP |
| Modifying agency |
GW5XE |
| -- |
EBLCP |
| -- |
LQU |
| -- |
OCLCF |
| -- |
VT2 |
| -- |
NLW |
| -- |
DCT |
| -- |
OCLCQ |
| -- |
OCLCO |
| -- |
COM |
| -- |
OCLCQ |
| -- |
AUD |
| -- |
OCLCQ |
| -- |
OCLCO |
| -- |
OCLCQ |
| -- |
OCLCL |
| 019 ## - |
|---|
| -- |
1156327383 |
| -- |
1162779404 |
| -- |
1181902610 |
| -- |
1203978847 |
| -- |
1224378989 |
| -- |
1237473955 |
| -- |
1244634875 |
| -- |
1246359084 |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER |
|---|
| International Standard Book Number |
9783030436629 |
| Qualifying information |
(electronic bk.) |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER |
|---|
| International Standard Book Number |
3030436624 |
| Qualifying information |
(electronic bk.) |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER |
|---|
| International Standard Book Number |
3030436616 |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER |
|---|
| International Standard Book Number |
9783030436612 |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER |
|---|
| International Standard Book Number |
9783030436636 |
| Qualifying information |
(print) |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER |
|---|
| International Standard Book Number |
3030436632 |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER |
|---|
| Canceled/invalid ISBN |
9783030436612 |
| 024 7# - OTHER STANDARD IDENTIFIER |
|---|
| Standard number or code |
10.1007/978-3-030-43662-9 |
| Source of number or code |
doi |
| 029 1# - (OCLC) |
|---|
| OCLC library identifier |
AU@ |
| System control number |
000067124617 |
| 029 1# - (OCLC) |
|---|
| OCLC library identifier |
AU@ |
| System control number |
000067504543 |
| 029 1# - (OCLC) |
|---|
| OCLC library identifier |
AU@ |
| System control number |
000068811319 |
| 029 1# - (OCLC) |
|---|
| OCLC library identifier |
DKDLA |
| System control number |
820120-katalog:999890133105765 |
| 035 ## - SYSTEM CONTROL NUMBER |
|---|
| System control number |
(OCoLC)1150154692 |
| Canceled/invalid control number |
(OCoLC)1156327383 |
| -- |
(OCoLC)1162779404 |
| -- |
(OCoLC)1181902610 |
| -- |
(OCoLC)1203978847 |
| -- |
(OCoLC)1224378989 |
| -- |
(OCoLC)1237473955 |
| -- |
(OCoLC)1244634875 |
| -- |
(OCoLC)1246359084 |
| 037 ## - SOURCE OF ACQUISITION |
|---|
| Source of stock number/acquisition |
Springer |
| 050 #4 - LIBRARY OF CONGRESS CALL NUMBER |
|---|
| Classification number |
QA267.7 |
| 072 #7 - SUBJECT CATEGORY CODE |
|---|
| Subject category code |
UY |
| Source |
bicssc |
| 072 #7 - SUBJECT CATEGORY CODE |
|---|
| Subject category code |
COM014000 |
| Source |
bisacsh |
| 072 #7 - SUBJECT CATEGORY CODE |
|---|
| Subject category code |
UY |
| Source |
thema |
| 072 #7 - SUBJECT CATEGORY CODE |
|---|
| Subject category code |
UYA |
| Source |
thema |
| 082 04 - DEWEY DECIMAL CLASSIFICATION NUMBER |
|---|
| Classification number |
511.3/52 |
| Edition number |
23 |
| 049 ## - LOCAL HOLDINGS (OCLC) |
|---|
| Holding library |
MAIN |
| 245 00 - TITLE STATEMENT |
|---|
| Title |
Computational complexity and property testing : |
| Remainder of title |
on the interplay between randomness and computation / |
| Statement of responsibility, etc. |
Oded Goldreich et al. |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) |
|---|
| Place of publication, distribution, etc. |
Cham : |
| Name of publisher, distributor, etc. |
Springer, |
| Date of publication, distribution, etc. |
2020. |
| 300 ## - PHYSICAL DESCRIPTION |
|---|
| Extent |
1 online resource (391 pages) |
| 336 ## - CONTENT TYPE |
|---|
| Content type term |
text |
| Content type code |
txt |
| Source |
rdacontent |
| 337 ## - MEDIA TYPE |
|---|
| Media type term |
computer |
| Media type code |
c |
| Source |
rdamedia |
| 338 ## - CARRIER TYPE |
|---|
| Carrier type term |
online resource |
| Carrier type code |
cr |
| Source |
rdacarrier |
| 347 ## - DIGITAL FILE CHARACTERISTICS |
|---|
| File type |
text file |
| 347 ## - DIGITAL FILE CHARACTERISTICS |
|---|
| Encoding format |
PDF |
| 490 1# - SERIES STATEMENT |
|---|
| Series statement |
Lecture Notes in Computer Science ; |
| Volume/sequential designation |
12050 |
| 490 1# - SERIES STATEMENT |
|---|
| Series statement |
LNCS sublibrary. SL1, Theoretical computer science and general issues |
| 588 0# - SOURCE OF DESCRIPTION NOTE |
|---|
| Source of description note |
Print version record. |
| 505 0# - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
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 |
| 505 8# - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
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 |
| 504 ## - BIBLIOGRAPHY, ETC. NOTE |
|---|
| Bibliography, etc |
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 |
| 505 8# - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
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 |
| 505 8# - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
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 |
| 500 ## - GENERAL NOTE |
|---|
| General note |
1.3 Organization |
| 520 ## - SUMMARY, ETC. |
|---|
| Summary, etc. |
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. |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name as entry element |
Computational complexity. |
| 9 (RLIN) |
391 |
| 650 #6 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name as entry element |
Complexité de calcul (Informatique) |
| 650 #7 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name as entry element |
Computer networking & communications. |
| Source of heading or term |
bicssc |
| 9 (RLIN) |
53942 |
| 650 #7 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name as entry element |
Maths for computer scientists. |
| Source of heading or term |
bicssc |
| 9 (RLIN) |
53449 |
| 650 #7 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name as entry element |
Artificial intelligence. |
| Source of heading or term |
bicssc |
| 9 (RLIN) |
1340 |
| 650 #7 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name as entry element |
Information retrieval. |
| Source of heading or term |
bicssc |
| 650 #7 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name as entry element |
Algorithms & data structures. |
| Source of heading or term |
bicssc |
| 9 (RLIN) |
53448 |
| 650 #7 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name as entry element |
Computer science. |
| Source of heading or term |
bicssc |
| 9 (RLIN) |
941 |
| 650 #7 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name as entry element |
Computers |
| General subdivision |
Networking |
| -- |
General. |
| Source of heading or term |
bisacsh |
| 9 (RLIN) |
17954 |
| 650 #7 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name as entry element |
Computers |
| General subdivision |
Mathematical & Statistical Software. |
| Source of heading or term |
bisacsh |
| 9 (RLIN) |
54021 |
| 650 #7 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name as entry element |
Computers |
| General subdivision |
Intelligence (AI) & Semantics. |
| Source of heading or term |
bisacsh |
| 9 (RLIN) |
17680 |
| 650 #7 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name as entry element |
Computers |
| General subdivision |
Information Technology. |
| Source of heading or term |
bisacsh |
| 9 (RLIN) |
14211 |
| 650 #7 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name as entry element |
Computers |
| General subdivision |
Data Modeling & Design. |
| Source of heading or term |
bisacsh |
| 9 (RLIN) |
27222 |
| 650 #7 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name as entry element |
Computers |
| General subdivision |
Computer Science. |
| Source of heading or term |
bisacsh |
| 9 (RLIN) |
17992 |
| 650 #7 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name as entry element |
Computational complexity |
| Source of heading or term |
fast |
| 9 (RLIN) |
391 |
| 700 1# - ADDED ENTRY--PERSONAL NAME |
|---|
| Personal name |
Goldreich, Oded. |
| 9 (RLIN) |
172 |
| 700 1# - ADDED ENTRY--PERSONAL NAME |
|---|
| Personal name |
Benjamini, Itai. |
| 9 (RLIN) |
212025 |
| 700 1# - ADDED ENTRY--PERSONAL NAME |
|---|
| Personal name |
Decatur, Scott. |
| 9 (RLIN) |
212026 |
| 700 1# - ADDED ENTRY--PERSONAL NAME |
|---|
| Personal name |
Leshkowitz, Maya. |
| 9 (RLIN) |
212027 |
| 700 1# - ADDED ENTRY--PERSONAL NAME |
|---|
| Personal name |
Meir, Or. |
| 9 (RLIN) |
212028 |
| 700 1# - ADDED ENTRY--PERSONAL NAME |
|---|
| Personal name |
Ron, Dana. |
| 9 (RLIN) |
95611 |
| 700 1# - ADDED ENTRY--PERSONAL NAME |
|---|
| Personal name |
Rothblum, Guy. |
| 9 (RLIN) |
212029 |
| 700 1# - ADDED ENTRY--PERSONAL NAME |
|---|
| Personal name |
Tal, Avishay. |
| 9 (RLIN) |
212030 |
| 700 1# - ADDED ENTRY--PERSONAL NAME |
|---|
| Personal name |
Teichner, Liav. |
| 9 (RLIN) |
212031 |
| 700 1# - ADDED ENTRY--PERSONAL NAME |
|---|
| Personal name |
Tell, Roei. |
| 9 (RLIN) |
212032 |
| 758 ## - |
|---|
| -- |
has work: |
| -- |
Computational complexity and property testing (Text) |
| -- |
https://id.oclc.org/worldcat/entity/E39PCGCvRwqDy6KmVPfTG8gYRq |
| -- |
https://id.oclc.org/worldcat/ontology/hasWork |
| 776 08 - ADDITIONAL PHYSICAL FORM ENTRY |
|---|
| Relationship information |
Print version: |
| Main entry heading |
Goldreich, Oded. |
| Title |
Computational Complexity and Property Testing : On the Interplay Between Randomness and Computation. |
| Place, publisher, and date of publication |
Cham : Springer International Publishing AG, ©2020 |
| International Standard Book Number |
9783030436612 |
| 830 #0 - SERIES ADDED ENTRY--UNIFORM TITLE |
|---|
| Uniform title |
Lecture notes in computer science ; |
| Volume number/sequential designation |
12050. |
| 830 #0 - SERIES ADDED ENTRY--UNIFORM TITLE |
|---|
| Uniform title |
LNCS sublibrary. |
| Number of part/section of a work |
SL 1, |
| Name of part/section of a work |
Theoretical computer science and general issues. |
| 9 (RLIN) |
20736 |
| 856 40 - ELECTRONIC LOCATION AND ACCESS |
|---|
| Uniform Resource Identifier |
<a href="https://link.springer.com/10.1007/978-3-030-43662-9">https://link.springer.com/10.1007/978-3-030-43662-9</a> |
| 938 ## - |
|---|
| -- |
ProQuest Ebook Central |
| -- |
EBLB |
| -- |
EBL6157930 |
| 994 ## - |
|---|
| -- |
92 |
| -- |
ATIST |