5 citations · 5 across the 3 of their papers we have counts for
10 papers
Subcube Stifling
Arjan Cornelissen, Nikhil S. Mande, Nithish Raja
We introduce the subcube stifling number, a new combinatorial measure of total Boolean functions. This measure is the largest integer such that, for every set of at most $k…
Instance complexity of Boolean functions
Alison Hsiang-Hsuan Liu, Nikhil S. Mande
In the area of query complexity of Boolean functions, the most widely studied cost measure of an algorithm is the worst-case number of queries made by it on an input. Motivated by…
Tight Bounds for Quantum Phase Estimation and Related Problems
Nikhil S. Mande, Ronald de Wolf
Phase estimation, due to Kitaev [arXiv'95], is one of the most fundamental subroutines in quantum computing. In the basic scenario, one is given black-box access to a unitary ,…
Quantum Search With Generalized Wildcards
Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro +2
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string . An algorithm may, at unit cost…
Complexity of learning matchings and half graphs via edge queries
Nikhil S. Mande, Swagato Sanyal, Viktor Zamaraev
The problem of learning or reconstructing an unknown graph from a known family via partial-information queries arises as a mathematical model in various contexts. The most basic ty…
Sensitivity and Query Complexity under Uncertainty
Deepu Benson, Balagopal Komarath, Nikhil Mande +3
In this paper, we study the query complexity of Boolean functions in the presence of uncertainty, motivated by parallel computation with an unlimited number of processors where inp…