Cover Image

Recursive Jump Operators and Optimal Proof Systems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Egidy, Fabian
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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)

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

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)

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

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

Approximate Degree Composition for Recursive Functions
by: Chakraborty, Sourav, et al.
Published: (2024)

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

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)

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

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

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

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

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

The Computational Boundary of Inference: Capability Internalization, Training, and the Turing Jump
by: Lu, Chien-Ping
Published: (2026)

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

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

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

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

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

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

Recursion and proof theoretical characterizations of small circuit classes with modulo counting via discrete differential equations (long version)
by: Antonelli, Melissa, et al.
Published: (2026)

Monte Carlo to Las Vegas for Recursively Composed Functions
by: Al-Dhalaan, Bandar, et al.
Published: (2026)

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

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

Visibly Recursive Automata
by: Dubrulle, Kévin, et al.
Published: (2026)

The Proof Analysis Problem
by: Arteche, Noel, et al.
Published: (2025)

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

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

Efficiently Batching Unambiguous Interactive Proofs
by: Berger, Bonnie, et al.
Published: (2025)

The Randomness Deficiency Function and the Shift Operator
by: Epstein, Samuel
Published: (2023)

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

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

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

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

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

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

Optimal Communication Complexity of Chained Index
by: Sundaresan, Janani
Published: (2024)