3 citations · 3 across the 7 of their papers we have counts for
14 papers · 1 filter
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…
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…
Hardness of Finding Kings and Strong Kings
Ziad Ismaili Alaoui, Nikhil S. Mande
A king in a directed graph is a vertex such that every other vertex is reachable from via a path of length at most . It is well known that every tournament (a complete g…
Query Complexity with Unknowns
Nikhil S. Mande, Karteek Sreenivasaiah
We initiate the study of a new model of query complexity of Boolean functions where, in addition to 0 and 1, the oracle can answer queries with ``unknown''. The query algorithm is…
On the communication complexity of finding a king in a tournament
Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal +1
A tournament is a complete directed graph. A king in a tournament is a vertex v such that every other vertex is reachable from v via a path of length at most 2. It is well known th…