Algebrization

DOI10.1145/1490270.1490272zbMath1322.68080OpenAlexW1984477611MaRDI QIDQ2947539

Avi Wigderson, Scott Aaronson

Publication date: 24 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1490270.1490272

zbMATH Keywords

interactive proofscommunication complexityquery complexityalgebraizationlow-degree polynomialsarithmetizationoracles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (36)

A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ On the limits of gate elimination ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Spatial Isolation Implies Zero Knowledge Even in a Quantum World ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ The landscape of communication complexity classes ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ Circuit Lower Bounds for Average-Case MA ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ On succinct non-interactive arguments in relativized worlds ⋮ Proof-carrying data from arithmetized random oracles ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Unnamed Item ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ On the Power of Statistical Zero Knowledge ⋮ A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma ⋮ Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ Proofs of Proximity for Distribution Testing ⋮ An Exponential Separation Between MA and AM Proofs of Proximity ⋮ Limits on alternation trading proofs for time-space lower bounds ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity ⋮ Non-interactive proofs of proximity ⋮ Oracle separations between quantum and non-interactive zero-knowledge classes ⋮ Rectangles Are Nonnegative Juntas ⋮ Unnamed Item ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Verifiable Stream Computation and Arthur--Merlin Communication ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The complexity of quantum disjointness ⋮ Unnamed Item ⋮ How much randomness is needed to convert MA protocols to AM protocols? ⋮ Unprovability of circuit upper bounds in Cook's theory PV ⋮ Arthur-Merlin streaming complexity

This page was built for publication: Algebrization