An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
type: Item
instance of: scholarly article
title: An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
author: Yanyan Li
published in: Computational Complexity
publication date: 2021-09-10T00:00:00Z
Mathematics Subject Classification ID: 68Q10
zbMATH DE Number: 7393894
zbMATH Keywords: interative proofs
zbMATH Keywords: proofs of proximity
Wikidata QID: Q113906242
MaRDI profile type: Publication
full work available at URL: s00037-021-00212-3
OpenAlex ID: W3194732277
cites work: Q3166192
cites work: Algebrization
cites work: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
cites work: Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation
cites work: Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
cites work: Property testing lower bounds via communication complexity
cites work: Big Data on the Rise?
cites work: Annotations in Data Streams
cites work: Q4601830
cites work: Streaming graph computations with a helpful advisor
cites work: Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
cites work: Fast approximate probabilistically checkable proofs
cites work: Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions
cites work: Partial tests, universal tests and decomposability
cites work: Introduction to Property Testing
cites work: Property testing and its connection to learning and approximation
cites work: Q4578332
cites work: Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
cites work: Q4601820
cites work: Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
cites work: On the randomness complexity of property testing
cites work: Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication
cites work: Arthur-Merlin streaming complexity
cites work: Non-Interactive Proofs of Proximity
cites work: A Hierarchy Theorem for Interactive Proofs of Proximity
cites work: Non-interactive proofs of proximity
cites work: Arguments of Proximity
cites work: The Probabilistic Communication Complexity of Set Intersection
cites work: Q4699282
cites work: Algebraic methods for interactive proof systems
cites work: Private vs. common random bits in communication complexity
cites work: Quantum information and the PCP theorem
cites work: Q4936140
cites work: Constant-round interactive proofs for delegating computation
cites work: Q3615896
cites work: lgorithmic and Analysis Techniques in Property Testing
cites work: Interactive proofs of proximity
cites work: Robust Characterizations of Polynomials with Applications to Program Testing
cites work: The multiparty communication complexity of set disjointness
cites work: Semi-Streaming Algorithms for Annotated Graph Streams
DOI: 10.1007/S00037-021-00212-3
description: scientific article; zbMATH DE number 7393894