Cover Image

Interactive Proofs For Distribution Testing With Conditional Oracles

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Biswas, Ari, Bun, Mark, Canonne, Clément, Sivakumar, Satchit
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Refuting Perfect Matchings in Spectral Expanders is Hard
by: Biswas, Ari, et al.
Published: (2025)

Quantum Interactive Oracle Proofs
by: Sun, Baocheng, et al.
Published: (2026)

A Fast Coloring Oracle for Average Case Hypergraphs
by: Marcussen, Cassandra, et al.
Published: (2025)

The Quantumly Fast and the Classically Forrious
by: Canonne, Clément L., et al.
Published: (2026)

Direct Product Primality Testing of Graphs is GI-hard
by: Calderoni, Luca, et al.
Published: (2020)

Communication Complexity of Disjointness under Product Distributions
by: Hunter, Zach, et al.
Published: (2026)

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

An Invariance Principle for the Multi-slice, with Applications
by: Braverman, Mark, et al.
Published: (2021)

Testing Isomorphism of Graphs in Polynomial Time
by: Xue, Rui
Published: (2023)

Hierarchies of Minion Tests for PCSPs through Tensors
by: Ciardo, Lorenzo, et al.
Published: (2022)

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
by: Dinur, Itai, et al.
Published: (2021)

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
by: Dikstein, Yotam, et al.
Published: (2024)

Testing Sumsets is Hard
by: Chen, Xi, et al.
Published: (2024)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
by: Eagling-Vose, Tala, et al.
Published: (2025)

Monotone Circuit Complexity of Matching
by: Cavalar, Bruno, et al.
Published: (2025)

Hunting a rabbit: complexity, approximability and some characterizations
by: Ben-Ameur, Walid, et al.
Published: (2025)

Finding large $k$-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs
by: Hodur, Nadzieja, et al.
Published: (2025)

Improved Small Set Expansion in High Dimensional Expanders
by: Kaufman, Tali, et al.
Published: (2025)

A near-optimal Quadratic Goldreich-Levin algorithm
by: Briët, Jop, et al.
Published: (2025)

Assembly Addition Chains
by: Cronin, Leroy, et al.
Published: (2025)

Tensor rank and dimension expanders
by: Dvir, Zeev
Published: (2025)

Matchgate signatures under variable permutations
by: Meng, Boning, et al.
Published: (2025)

Hardness of Hypergraph Edge Modification Problems
by: Gishboliner, Lior, et al.
Published: (2025)

Sensitivity and Hamming graphs
by: Asensio, Sara, et al.
Published: (2025)

Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics
by: Mittal, Kunal
Published: (2025)

The Log-Rank Conjecture: New Equivalent Formulations
by: Hambardzumyan, Lianna, et al.
Published: (2025)

Finding a HIST: Chordality, Structural Parameters, and Diameter
by: Hanaka, Tesshu, et al.
Published: (2025)

Factorization norms and Zarankiewicz problems
by: Tomon, István
Published: (2025)

Low-Degree Polynomials Are Good Extractors
by: Alrabiah, Omar, et al.
Published: (2024)

A Note on the Complexity of Directed Clique
by: Gutowski, Grzegorz, et al.
Published: (2026)

On the Keevash-Knox-Mycroft Conjecture
by: Gan, Luyining, et al.
Published: (2022)

On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
by: Borzechowski, Michaela, et al.
Published: (2023)

Sparse juntas on the biased hypercube
by: Dinur, Irit, et al.
Published: (2017)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
by: Basu, Arpon, et al.
Published: (2024)

On Approximability of Satisfiable $k$-CSPs: VI
by: Bhangale, Amey, et al.
Published: (2024)

Flat origami is Turing Complete
by: Hull, Thomas C., et al.
Published: (2023)

On Approximability of Satisfiable $k$-CSPs: VII
by: Bhangale, Amey, et al.
Published: (2024)

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
by: Hsieh, Jun-Ting, et al.
Published: (2024)

Systems of Discrete Differential Equations, Constructive Algebraicity of the Solutions
by: Notarantonio, Hadrien, et al.
Published: (2023)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
by: Baril, Ambroise, et al.
Published: (2024)