Imagen de Portada

The SPARSE-Relativization Framework and Applications to Optimal Proof Systems

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Egidy, Fabian
Formato:	Preprint
Publicado:	2026
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Recursive Jump Operators and Optimal Proof Systems
por: Egidy, Fabian
Publicado: (2026)

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

An Oracle with no $\mathrm{UP}$-Complete Sets, but $\mathrm{NP}=\mathrm{PSPACE}$
por: Dingel, David, et al.
Publicado: (2024)

A Relativizing MIP for BQP
por: Aaronson, Scott, et al.
Publicado: (2026)

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

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

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

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

A Survey on the Applications of Zero-Knowledge Proofs
por: Lavin, Ryan, et al.
Publicado: (2024)

Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem
por: Garcia, Baruch
Publicado: (2026)

Distribution-Free Proofs of Proximity
por: Aaronson, Hugo, et al.
Publicado: (2023)

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

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

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
por: Hirahara, Shuichi, et al.
Publicado: (2024)

Multi-Prover Interactive Proof Systems with Leakage
por: Asadi, Vahid R., et al.
Publicado: (2026)

The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
por: Gay, William, et al.
Publicado: (2026)

On the Interplay of Cube Learning and Dependency Schemes in QCDCL Proof Systems
por: Choudhury, Abhimanyu, et al.
Publicado: (2025)

NP-Completeness Proofs of Puzzles using the T-Metacell Framework
por: Kiatchaipipat, Nattapol, et al.
Publicado: (2025)

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

Proof Complexity and Feasible Interpolation
por: Tabatabai, Amirhossein Akbar
Publicado: (2025)

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

Proof complexity of Mal'tsev CSP
por: Gaysin, Azza
Publicado: (2025)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
por: de Rezende, Susanna F., et al.
Publicado: (2026)

Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth
por: Bhattacharya, Sreejata Kishor, et al.
Publicado: (2025)

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

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
por: Behera, Amik Raj, et al.
Publicado: (2026)

Quantum Interactive Oracle Proofs
por: Sun, Baocheng, et al.
Publicado: (2026)

Proofs of NP = coNP = PSPACE: Current upgrade
por: Gordeev, Lev, et al.
Publicado: (2023)

The Proof Analysis Problem
por: Arteche, Noel, et al.
Publicado: (2025)

On the Degree Automatability of Sum-of-Squares Proofs
por: Bortolotti, Alex, et al.
Publicado: (2025)

Two Simple Proofs of Müller's Theorem
por: Epstein, Samuel
Publicado: (2024)

Efficiently Batching Unambiguous Interactive Proofs
por: Berger, Bonnie, et al.
Publicado: (2025)

Proof Complexity of Linear Logics
por: Tabatabai, Amirhossein Akbar, et al.
Publicado: (2026)

Rational-Valued Affine Verifiers in Arthur--Merlin Proof Systems
por: Chen, Zeyu, et al.
Publicado: (2025)

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
por: Garg, Abhibhav, et al.
Publicado: (2025)

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

Streaming Zero-Knowledge Proofs
por: Cormode, Graham, et al.
Publicado: (2023)

Optimal Communication Complexity of Chained Index
por: Sundaresan, Janani
Publicado: (2024)

Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs
por: Grewal, Sabee, et al.
Publicado: (2025)

The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
por: Jeronimo, Fernando Granha, et al.
Publicado: (2024)