:: Library Catalog

Copertina

Salvato in:

Dettagli Bibliografici
Autori principali:	Bhattacharjee, Sutanay, Panse, Ameya, Sarma, Jayalal
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity
Accesso online:	https://arxiv.org/abs/2605.19702
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

Hazard-free Decision Trees
di: Benson, Deepu, et al.
Pubblicazione: (2025)

Almost-catalytic Computation
di: Bisoyi, Sagar, et al.
Pubblicazione: (2024)

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

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

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

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

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

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

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

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

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

Width Hierarchy for k-OBDD of Small Width
di: Khadiev, Kamil
Pubblicazione: (2015)

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

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

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

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

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

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

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

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

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

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

Hausdorff Reductions and the Exponential Hierarchies
di: Malizia, Enrico
Pubblicazione: (2024)

Constructive Separations and Their Consequences
di: Chen, Lijie, et al.
Pubblicazione: (2022)

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

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

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

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

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

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

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

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

Constructive Separations from Gate Elimination
di: Carmosino, Marco, et al.
Pubblicazione: (2026)

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

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

Testing Isomorphism of Graphs in Polynomial Time
di: Xue, Rui
Pubblicazione: (2023)

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