000 04659nam a22006495i 4500
001 978-3-030-43662-9
003 DE-He213
005 20240423125304.0
007 cr nn 008mamaa
008 200403s2020 sz | s |||| 0|eng d
020 _a9783030436629
_9978-3-030-43662-9
024 7 _a10.1007/978-3-030-43662-9
_2doi
050 4 _aQA75.5-76.95
072 7 _aUYA
_2bicssc
072 7 _aCOM014000
_2bisacsh
072 7 _aUYA
_2thema
082 0 4 _a004.0151
_223
245 1 0 _aComputational Complexity and Property Testing
_h[electronic resource] :
_bOn the Interplay Between Randomness and Computation /
_cedited by Oded Goldreich.
250 _a1st ed. 2020.
264 1 _aCham :
_bSpringer International Publishing :
_bImprint: Springer,
_c2020.
300 _aX, 382 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v12050
505 0 _aA Probabilistic Error-Correcting Scheme that Provides Partial Secrecy -- Bridging a Small Gap in the Gap Ampli cation of Assignment Testers -- On (Valiant's) Polynomial-Size Monotone Formula for Majority -- Two Comments on Targeted Canonical Derandomizers -- On the Effect of the Proximity Parameter on Property Testers -- On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions -- On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing -- Super-Perfect Zero-Knowledge Proofs -- On the Relation between the Relative Earth Mover Distance and the Variation Distance (an exposition) -- The Uniform Distribution is Complete with respect to Testing Identity to a Fixed Distribution -- A Note on Tolerant Testing with One-Sided Error -- On Emulating Interactive Proofs with Public Coins -- Reducing Testing Affine Spaces to Testing Linearity of Functions -- Deconstructing 1-Local Expanders -- Worst-case to Average-case Reductions forSubclasses of P -- On the Optimal Analysis of the Collision Probability Tester (an exposition) -- On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions -- Constant-Round Interactive Proof Systems for AC0[2] and NC1 -- Flexible Models for Testing Graph Properties -- Pseudo-Mixing Time of Random Walks -- On Constructing Expanders for any Number of Vertices.
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 _aComputer science.
650 0 _aComputer engineering.
650 0 _aComputer networks .
650 0 _aComputer science
_xMathematics.
650 0 _aMathematical statistics.
650 0 _aLogic programming.
650 0 _aApplication software.
650 0 _aData structures (Computer science).
650 0 _aInformation theory.
650 1 4 _aTheory of Computation.
650 2 4 _aComputer Engineering and Networks.
650 2 4 _aProbability and Statistics in Computer Science.
650 2 4 _aLogic in AI.
650 2 4 _aComputer and Information Systems Applications.
650 2 4 _aData Structures and Information Theory.
700 1 _aGoldreich, Oded.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
710 2 _aSpringerLink (Online service)
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783030436612
776 0 8 _iPrinted edition:
_z9783030436636
830 0 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v12050
856 4 0 _uhttps://doi.org/10.1007/978-3-030-43662-9
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
942 _cSPRINGER
999 _c176313
_d176313