6 citations · 24 across the 17 of their papers we have counts for
4 papers · 1 filter
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…
Quantum Sabotage Complexity
Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro
Given a Boolean function , the goal in the usual query model is to compute on an unknown input while minimizing the number of queries t…
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…
Lower bounds for quantum-inspired classical algorithms via communication complexity
Nikhil S. Mande, Changpeng Shao
Quantum-inspired classical algorithms provide us with a new way to understand the computational power of quantum computers for practically-relevant problems, especially in machine…