:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Bhattacharjee, Sutanay, Panse, Ameya, Sarma, Jayalal
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2605.19702
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Range Avoidance in Boolean Circuits via Turan-type Bounds
by: Kuntewar, Neha, et al.
Published: (2025)

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
by: Komarath, Balagopal, et al.
Published: (2026)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
by: Nalli, Sai Soumya, et al.
Published: (2026)

Hazard-free Decision Trees
by: Benson, Deepu, et al.
Published: (2025)

Almost-catalytic Computation
by: Bisoyi, Sagar, et al.
Published: (2024)

Sensitivity and Query Complexity under Uncertainty
by: Benson, Deepu, et al.
Published: (2025)

Bounds for Hardness Condensation in the Query Model
by: Kayal, Chandrima, et al.
Published: (2026)

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

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

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

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

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

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

One-Way Functions and Polynomial Time Dimension
by: Nandakumar, Satyadev, et al.
Published: (2024)

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

Hierarchies within TFNP: building blocks and collapses
by: Ghentiyala, Surendra, et al.
Published: (2025)

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

Coherence in Property Testing: Quantum-Classical Collapses and Separations
by: Jeronimo, Fernando Granha, et al.
Published: (2024)

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

The Interplay Between Domination and Separation in Graphs
by: Chakraborty, Dipayan, et al.
Published: (2026)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
by: Roberson, David E., et al.
Published: (2023)

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

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

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

Exponential lower bound via exponential sums
by: Bhattacharjee, Somnath, et al.
Published: (2026)

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

Constructive Separations and Their Consequences
by: Chen, Lijie, et al.
Published: (2022)

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

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

MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal
by: Gaikwad, Ajinkya, et al.
Published: (2025)

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

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

A quantum neural network framework for scalable quantum circuit approximation of unitary matrices
by: Sarkar, Rohit Sarma, et al.
Published: (2024)

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

Quantum Algorithms for Approximate Graph Isomorphism Testing
by: Kulkarni, Prateek P.
Published: (2026)

Constructive Separations from Gate Elimination
by: Carmosino, Marco, et al.
Published: (2026)

Ideal Membership Problem for Boolean Minority and Dual Discriminator
by: Bharathi, Arpitha P., et al.
Published: (2024)

Separations between Combinatorial Measures for Transitive Functions
by: Chakraborty, Sourav, et al.
Published: (2021)

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

Linear Space Streaming Lower Bounds for Approximating CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)