Cover Image

Hierarchies within TFNP: building blocks and collapses

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ghentiyala, Surendra, Li, Zeyong
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

Downward self-reducibility in the total function polynomial hierarchy
by: Gajulapalli, Karthik, et al.
Published: (2025)

Efficient derandomization of differentially private counting queries
by: Ghentiyala, Surendra
Published: (2025)

New constructions of pseudorandom codes
by: Ghentiyala, Surendra, et al.
Published: (2024)

Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
by: Gajulapalli, Karthik, et al.
Published: (2025)

On Pigeonhole Principles and Ramsey in TFNP
by: Jain, Siddhartha, et al.
Published: (2024)

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

Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
by: Li, Zeyong
Published: (2023)

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

The Structure of In-Place Space-Bounded Computation
by: Cook, James, et al.
Published: (2025)

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

How to fit large complexity classes into TFNP
by: Thapen, Neil
Published: (2024)

An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
by: Aldi, Marco, et al.
Published: (2024)

Hardness Amplification for (Sparse) LPN
by: Aggarwal, Divesh, et al.
Published: (2026)

A Hierarchy for Constant Communication Complexity
by: Ambainis, Andris, et al.
Published: (2025)

Width Hierarchy for k-OBDD of Small Width
by: Khadiev, Kamil
Published: (2015)

Hilbert's Nullstellensatz is in the Counting Hierarchy
by: Andrews, Robert, et al.
Published: (2026)

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
by: Bhattacharjee, Sutanay, et al.
Published: (2026)

On a Hierarchy of Spectral Invariants for Graphs
by: Arvind, V., et al.
Published: (2023)

On the Hierarchies for Deterministic, Nondeterministic and Probabilistic Ordered Read-k-times Branching Programs
by: Khadiev, Kamil
Published: (2016)

The Entangled Quantum Polynomial Hierarchy Collapses
by: Grewal, Sabee, et al.
Published: (2024)

A SUBSET-SUM Characterisation of the A-Hierarchy
by: Gutleben, Jan, et al.
Published: (2024)

Superposition detection and QMA with non-collapsing measurements
by: Bassirian, Roozbeh, et al.
Published: (2024)

Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy
by: Ganian, Robert, et al.
Published: (2025)

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
by: Agarwal, Avantika, et al.
Published: (2024)

Hausdorff Reductions and the Exponential Hierarchies
by: Malizia, Enrico
Published: (2024)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
by: Grüne, Christoph, et al.
Published: (2026)

On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
by: Grewal, Sabee, et al.
Published: (2025)

Orbit-blocking words in free groups
by: Koch-Hyde, Lucy, et al.
Published: (2025)

Lower bounds for set-blocked clauses proofs
by: Yolcu, Emre
Published: (2024)

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

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

The Polynomial Hierarchy does not collapse
by: Czerwinski, Reiner
Published: (2024)

Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
by: Khadiev, Kamil, et al.
Published: (2017)

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
by: Chia, Nai-Hui, et al.
Published: (2024)

From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy
by: Dörfler, Julian, et al.
Published: (2024)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
by: Agarwal, Avantika, et al.
Published: (2024)

Complexity of Boolean automata networks under block-parallel update modes
by: Perrot, Kévin, et al.
Published: (2024)

Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions
by: Podolskii, Vladimir, et al.
Published: (2024)

Some Applications and Limitations of Convex Optimization Hierarchies for Discrete and Continuous Optimization Problems
by: Ghosh, Mrinalkanti
Published: (2025)

Uniformity within Parameterized Circuit Classes
by: Hegeman, Steef, et al.
Published: (2025)