Cover Image

Distribution-Free Proofs of Proximity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Aaronson, Hugo, Gur, Tom, Rajgopal, Ninad, Rothblum, Ron D.
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Pseudo-deterministic Quantum Algorithms
by: Aaronson, Hugo, et al.
Published: (2026)

On the Power of Interactive Proofs for Learning
by: Gur, Tom, et al.
Published: (2024)

Quantum Channel Testing in Average-Case Distance
by: Rosenthal, Gregory, et al.
Published: (2024)

How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions
by: Herman, Tal, et al.
Published: (2024)

Streaming Zero-Knowledge Proofs
by: Cormode, Graham, et al.
Published: (2023)

Interactive Oracle Proofs of Proximity to Codes on Graphs
by: Delavenne, Hugo, et al.
Published: (2025)

Frontier Space-Time Algorithms Using Only Full Memory
by: Chmel, Petr, et al.
Published: (2026)

Property Testing in Bounded Degree Hypergraphs
by: Aaronson, Hugo, et al.
Published: (2025)

Why Philosophers Should Care About Computational Complexity
by: Aaronson, Scott
Published: (2011)

3-Query RLDCs are Strictly Stronger than 3-Query LDCs
by: Gur, Tom, et al.
Published: (2025)

Symmetric quantum computation
by: Castro-Silva, Davi, et al.
Published: (2025)

A Zero-Knowledge PCP Theorem
by: Gur, Tom, et al.
Published: (2024)

Quantum Communication Advantage in TFNP
by: Göös, Mika, et al.
Published: (2024)

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
by: Aaronson, Scott, et al.
Published: (2023)

Models That Prove Their Own Correctness
by: Amit, Noga, et al.
Published: (2024)

The Acrobatics of BQP
by: Aaronson, Scott, et al.
Published: (2021)

Improved separation between quantum and classical computers for sampling and functional tasks
by: Marshall, Simon C., et al.
Published: (2024)

Interactive Proofs For Distribution Testing With Conditional Oracles
by: Biswas, Ari, et al.
Published: (2025)

A Relativizing MIP for BQP
by: Aaronson, Scott, et al.
Published: (2026)

Perfect Zero-Knowledge PCPs for #P
by: Gur, Tom, et al.
Published: (2024)

On Computationally Efficient Multi-Class Calibration
by: Gopalan, Parikshit, et al.
Published: (2024)

Parity Tests with Ties
by: Kupfer, Ron
Published: (2026)

PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements
by: Aaronson, Scott, et al.
Published: (2024)

Separations in Proof Complexity and TFNP
by: Göös, Mika, et al.
Published: (2022)

On the Existence of Algebraic Natural Proofs
by: Chatterjee, Prerona, et al.
Published: (2020)

Symmetric Proofs in the Ideal Proof System
by: Dawar, Anuj, et al.
Published: (2025)

Proof Systems Based on Structured Circuits
by: Micun, Matthäus, et al.
Published: (2026)

Recursive Jump Operators and Optimal Proof Systems
by: Egidy, Fabian
Published: (2026)

Hard CNF Instances for Ideal Proof Systems
by: Hakoniemi, Tuomas, et al.
Published: (2026)

On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
by: Bortolotti, Alex, et al.
Published: (2025)

The SPARSE-Relativization Framework and Applications to Optimal Proof Systems
by: Egidy, Fabian
Published: (2026)

Optimal Proof Systems for Complex Sets are Hard to Find
by: Egidy, Fabian, et al.
Published: (2024)

Proof Complexity and Feasible Interpolation
by: Tabatabai, Amirhossein Akbar
Published: (2025)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
by: Abboud, Amir, et al.
Published: (2026)

From Proof Complexity to Circuit Complexity via Interactive Protocols
by: Arteche, Noel, et al.
Published: (2024)

Lower Bounds against the Ideal Proof System in Finite Fields
by: Elbaz, Tal, et al.
Published: (2025)

Free Fermion Distributions Are Hard to Learn
by: Nietner, Alexander
Published: (2023)

Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)
by: Ron-Zewi, Noga, et al.
Published: (2024)

Proximity to Losslessly Compressible Parameters
by: Farrugia-Roberts, Matthew
Published: (2023)

Proof complexity of Mal'tsev CSP
by: Gaysin, Azza
Published: (2025)