Buchumschlag

Query Complexity with Unknowns

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Mande, Nikhil S., Sreenivasaiah, Karteek
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Sensitivity and Query Complexity under Uncertainty
von: Benson, Deepu, et al.
Veröffentlicht: (2025)

Improved Quantum Query Upper Bounds Based on Classical Decision Trees
von: Cornelissen, Arjan, et al.
Veröffentlicht: (2022)

Lower bounds for quantum-inspired classical algorithms via communication complexity
von: Mande, Nikhil S., et al.
Veröffentlicht: (2024)

Instance complexity of Boolean functions
von: Liu, Alison Hsiang-Hsuan, et al.
Veröffentlicht: (2023)

Tight Bounds for Quantum Phase Estimation and Related Problems
von: Mande, Nikhil S., et al.
Veröffentlicht: (2023)

Hardness of Finding Kings and Strong Kings
von: Alaoui, Ziad Ismaili, et al.
Veröffentlicht: (2025)

Complexity of learning matchings and half graphs via edge queries
von: Mande, Nikhil S., et al.
Veröffentlicht: (2025)

Quantum Sabotage Complexity
von: Cornelissen, Arjan, et al.
Veröffentlicht: (2024)

On the communication complexity of finding a king in a tournament
von: Mande, Nikhil S., et al.
Veröffentlicht: (2024)

Quantum Search With Generalized Wildcards
von: Cornelissen, Arjan, et al.
Veröffentlicht: (2025)

Direct Product Theorems for Randomized Query Complexity
von: Ben-David, Shalev, et al.
Veröffentlicht: (2025)

A Strong Direct Sum Theorem for Distributional Query Complexity
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

Parameterised Complexity of Consistent Query Answering via Graph Representations
von: Hankala, Teemu, et al.
Veröffentlicht: (2024)

PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2025)

A Brief Introduction to Quantum Query Complexity
von: Hamoudi, Yassine
Veröffentlicht: (2025)

The Query Complexity of Local Search and Brouwer in Rounds
von: Brânzei, Simina, et al.
Veröffentlicht: (2020)

3-Query RLDCs are Strictly Stronger than 3-Query LDCs
von: Gur, Tom, et al.
Veröffentlicht: (2025)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
von: Chen, Xi, et al.
Veröffentlicht: (2026)

The Query Complexity of Local Search in Rounds on General Graphs
von: Brânzei, Simina, et al.
Veröffentlicht: (2026)

Bounds for Hardness Condensation in the Query Model
von: Kayal, Chandrima, et al.
Veröffentlicht: (2026)

Consistent Query Answering over SHACL Constraints
von: Ahmetaj, Shqiponja, et al.
Veröffentlicht: (2024)

Quasi-Linear Size PCPs with Small Soundness from HDX
von: Bafna, Mitali, et al.
Veröffentlicht: (2024)

Reductions Between Code Equivalence Problems
von: Cheraghchi, Mahdi, et al.
Veröffentlicht: (2025)

The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube
von: Brânzei, Simina, et al.
Veröffentlicht: (2024)

Diversity of Answers to Conjunctive Queries
von: Merkl, Timo Camillo, et al.
Veröffentlicht: (2023)

Complexity of Round-Robin Allocation with Potentially Noisy Queries
von: Li, Zihan, et al.
Veröffentlicht: (2024)

Query Lower Bounds for Correlation Clustering under Memory Constraints
von: Garg, Sumegha, et al.
Veröffentlicht: (2026)

Lower Bounds for Conjunctive Query Evaluation
von: Mengel, Stefan
Veröffentlicht: (2025)

Good Locally Testable Codes with Small Alphabet and Small Query Size
von: First, Uriya, et al.
Veröffentlicht: (2025)

Query-Efficient Fixpoints of $\ell_p$-Contractions
von: Haslebacher, Sebastian, et al.
Veröffentlicht: (2025)

Towards Parameterized Hardness on Maintaining Conjunctive Queries
von: Wang, Qichen
Veröffentlicht: (2026)

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
von: Grigorescu, Elena, et al.
Veröffentlicht: (2025)

A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting
von: Chen, Kean, et al.
Veröffentlicht: (2025)

Structure in Communication Complexity and Constant-Cost Complexity Classes
von: Hatami, Hamed, et al.
Veröffentlicht: (2024)

Query complexity of Boolean functions on the middle slice of the cube
von: Gerbner, Dániel, et al.
Veröffentlicht: (2023)

From Proof Complexity to Circuit Complexity via Interactive Protocols
von: Arteche, Noel, et al.
Veröffentlicht: (2024)

On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)
von: Artale, Alessandro, et al.
Veröffentlicht: (2025)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
von: Zheng, Bojin, et al.
Veröffentlicht: (2026)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
von: Przybyłek, Michał R., et al.
Veröffentlicht: (2026)

Tight Fine-Grained Bounds for Direct Access on Join Queries
von: Bringmann, Karl, et al.
Veröffentlicht: (2022)