Cover Image

Sensitivity and Query Complexity under Uncertainty

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Benson, Deepu, Komarath, Balagopal, Mande, Nikhil, Nalli, Sai Soumya, Sarma, Jayalal, Sreenivasaiah, Karteek
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

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

Query Complexity with Unknowns
by: Mande, Nikhil S., et al.
Published: (2024)

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)

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

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

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
by: Komarath, Balagopal, et al.
Published: (2025)

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

Improved Quantum Query Upper Bounds Based on Classical Decision Trees
by: Cornelissen, Arjan, et al.
Published: (2022)

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

Lower bounds for quantum-inspired classical algorithms via communication complexity
by: Mande, Nikhil S., et al.
Published: (2024)

Instance complexity of Boolean functions
by: Liu, Alison Hsiang-Hsuan, et al.
Published: (2023)

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

Tight Bounds for Quantum Phase Estimation and Related Problems
by: Mande, Nikhil S., et al.
Published: (2023)

Hardness of Finding Kings and Strong Kings
by: Alaoui, Ziad Ismaili, et al.
Published: (2025)

Complexity of learning matchings and half graphs via edge queries
by: Mande, Nikhil S., et al.
Published: (2025)

Quantum Sabotage Complexity
by: Cornelissen, Arjan, et al.
Published: (2024)

On the communication complexity of finding a king in a tournament
by: Mande, Nikhil S., et al.
Published: (2024)

Quantum Search With Generalized Wildcards
by: Cornelissen, Arjan, et al.
Published: (2025)

Direct Product Theorems for Randomized Query Complexity
by: Ben-David, Shalev, et al.
Published: (2025)

A Strong Direct Sum Theorem for Distributional Query Complexity
by: Blanc, Guy, et al.
Published: (2024)

Query Lower Bounds for Correlation Clustering under Memory Constraints
by: Garg, Sumegha, et al.
Published: (2026)

PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
by: Guruswami, Venkatesan, et al.
Published: (2025)

Parameterised Complexity of Consistent Query Answering via Graph Representations
by: Hankala, Teemu, et al.
Published: (2024)

On the Complexity of Discounted Robust MDPs with $L_p$ Uncertainty Sets
by: Asadi, Ali, et al.
Published: (2026)

A Brief Introduction to Quantum Query Complexity
by: Hamoudi, Yassine
Published: (2025)

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

The Query Complexity of Local Search and Brouwer in Rounds
by: Brânzei, Simina, et al.
Published: (2020)

3-Query RLDCs are Strictly Stronger than 3-Query LDCs
by: Gur, Tom, et al.
Published: (2025)

Query maintenance under batch changes with small-depth circuits
by: Datta, Samir, et al.
Published: (2024)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
by: Chen, Xi, et al.
Published: (2026)

The Query Complexity of Local Search in Rounds on General Graphs
by: Brânzei, Simina, et al.
Published: (2026)

Communication Complexity of Disjointness under Product Distributions
by: Hunter, Zach, et al.
Published: (2026)

Maximizing Phylogenetic Diversity under Ecological Constraints: A Parameterized Complexity Study
by: Komusiewicz, Christian, et al.
Published: (2024)

Consistent Query Answering over SHACL Constraints
by: Ahmetaj, Shqiponja, et al.
Published: (2024)

Reductions Between Code Equivalence Problems
by: Cheraghchi, Mahdi, et al.
Published: (2025)

Quasi-Linear Size PCPs with Small Soundness from HDX
by: Bafna, Mitali, et al.
Published: (2024)

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

Diversity of Answers to Conjunctive Queries
by: Merkl, Timo Camillo, et al.
Published: (2023)

Complexity of Round-Robin Allocation with Potentially Noisy Queries
by: Li, Zihan, et al.
Published: (2024)

Lower Bounds for Conjunctive Query Evaluation
by: Mengel, Stefan
Published: (2025)