Cover Image

Low-soundness direct-product testers and PCPs from Kaufman--Oppenheim complexes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	O'Donnell, Ryan, Singer, Noah G.
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Pseudorandom Permutations from Random Reversible Circuits
by: He, William, et al.
Published: (2024)

Improved quantum data analysis
by: Bădescu, Costin, et al.
Published: (2020)

Ideals, Macaulay Bases, and PCPs
by: Amireddy, Prashanth, et al.
Published: (2025)

Quasi-Linear Size PCPs with Small Soundness from HDX
by: Bafna, Mitali, et al.
Published: (2024)

Quartic quantum speedups for planted inference
by: Schmidhuber, Alexander, et al.
Published: (2024)

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

Nine lower bound conjectures on streaming approximation algorithms for CSPs
by: Singer, Noah G.
Published: (2025)

Uniformity testing when you have the source code
by: Canonne, Clément L., et al.
Published: (2024)

No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore
by: Kothari, Robin, et al.
Published: (2025)

Near Optimal Alphabet-Soundness Tradeoff PCPs
by: Minzer, Dor, et al.
Published: (2024)

Coboundary expansion inside Chevalley coset complex HDXs
by: O'Donnell, Ryan, et al.
Published: (2024)

Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
by: Buhrman, Harry, et al.
Published: (2024)

Classical versus quantum queries in quantum PCPs with classical proofs
by: Buhrman, Harry, et al.
Published: (2024)

Sparsifying Suprema of Gaussian Processes
by: De, Anindya, et al.
Published: (2024)

Sketching approximations and LP approximations for finite CSPs are related
by: Singer, Noah G., et al.
Published: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
by: Singer, Noah G., et al.
Published: (2026)

Streaming approximation resistance of every ordering CSP
by: Singer, Noah G., et al.
Published: (2021)

Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
by: Hsieh, Jun-Ting, et al.
Published: (2024)

Streaming Complexity Separations for Dense and Sparse Graphs
by: Liu, Yang P., et al.
Published: (2026)

On the complexity of embedding in graph products
by: Biedl, Therese, et al.
Published: (2023)

The complexity of knapsack problems in wreath products
by: Figelius, Michael, et al.
Published: (2020)

Separations above TFNP from Sherali-Adams Lower Bounds
by: Fleming, Noah, et al.
Published: (2026)

The complexity of computing in continuous time: space complexity is precision
by: Blanc, Manon, et al.
Published: (2024)

The complexity of convexity number and percolation time in the cycle convexity
by: Lima, Carlos V. G. C., et al.
Published: (2024)

On the complexity of Multipacking
by: Das, Sandip, et al.
Published: (2026)

Maximization of Approximately Submodular Functions
by: Horel, Thibaut, et al.
Published: (2024)

Complexity Theory meets Ordinary Differential Equations
by: Fono, Adalbert, et al.
Published: (2026)

Instance complexity of Boolean functions
by: Liu, Alison Hsiang-Hsuan, et al.
Published: (2023)

Unambiguous parity-query complexity
by: Gavinsky, Dmytro
Published: (2024)

Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers
by: Dikstein, Yotam, et al.
Published: (2023)

On complexity of restricted fragments of Decision DNNF
by: Calí, Andrea, et al.
Published: (2025)

Between the deterministic and non-deterministic query complexity
by: Gerbner, Dániel
Published: (2019)

Simulating Time With Square-Root Space
by: Williams, R. Ryan
Published: (2025)

Some structural complexity results for $\exists\mathbb R$
by: Meer, Klaus, et al.
Published: (2025)

Unconventional complexity classes in unconventional computing (extended abstract)
by: Porreca, Antonio E.
Published: (2024)

A new metric for evaluating the performance and complexity of computer programs: A new approach to the traditional ways of measuring the complexity of algorithms and estimating running times
by: Folea, Rares, et al.
Published: (2025)

A primer on the closure of algebraic complexity classes under factoring
by: Bhargav, C. S., et al.
Published: (2025)

Communication complexity of pointer chasing via the fixed-set lemma
by: Viola, Emanuele
Published: (2025)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
by: Cai, Jin-Yi, et al.
Published: (2024)

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
by: Bender, Matías, et al.
Published: (2025)