Computational Complexity and Property Testing : On the Interplay Between Randomness and Computation /: On the Interplay Between Randomness and Computation. (2020)

• Record Type: Book
• Further Information: Note: Oded Goldreich, Itai Benjamini, Scott Decatur, Maya Leshkowitz, Or Meir, Dana Ron, Guy Rothblum, Avishay Tal, Liav Teichner, Roei Tell, Avi Wigderson.
• Editors: Goldreich, Oded
• Other Names: Benjamini, Itai contributor.; Decatur, Scott contributor.; Leshkowitz, Maya contributor.; Meir, Or contributor.; Ron, Dana contributor.; Rothblum, Guy contributor.; Tal, Avishay contributor.; Teichner, Liav contributor.; Tell, Roei contributor.; Wigderson, Avi contributor.
• Contents: A 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 for Subclasses 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.
• Publisher Details: Cham : Springer
• Publication Date: 2020
• Copyright Date: 2020
• Extent: 1 online resource (382 pages)
• Subjects: Computer science; Computers; Computer organization; Mathematical statistics; Artificial intelligence; Computer logic; Application software; Data structures (Computer science); Computers -- Networking -- General; Computers -- Mathematical & Statistical Software; Computers -- Intelligence (AI) & Semantics; Computers -- Information Technology; Computers -- Data Modeling & Design; Computer networking & communications; Maths for computer scientists; Artificial intelligence; Information retrieval; Algorithms & data structures; Computers -- Computer Science; Computer science
• Languages: English
• ISBNs: 9783030436629
• Related ISBNs: 9783030436612
• Access Rights: Legal Deposit; Only available on premises controlled by the deposit library and to one user at any one time; The Legal Deposit Libraries (Non-Print Works) Regulations (UK).
• Access Usage: Restricted: Printing from this resource is governed by The Legal Deposit Libraries (Non-Print Works) Regulations (UK) and UK copyright law currently in force.