Computational Complexity and Property Testing: On the Interplay Between Randomness and Computation - Couverture souple

Couverture souple

ISBN 10 : 3030436632 ISBN 13 : 9783030436636

Editeur : Springer, 2020

Synopsis

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.

Détails de l'édition

• Éditeur: Springer
• Date d'édition: 2020
• ISBN 10: 3030436632
• ISBN 13: 9783030436636
• Reliure: Paperback
• Langue: anglais
• Coordonnées du fabricant: non disponible