Nikhil S. Mande

MFCS Conference 2025 Conference Paper

Sensitivity and Query Complexity Under Uncertainty

• Deepu Benson
• Balagopal Komarath
• Nikhil S. Mande
• Nalli Sai Soumya
• Jayalal Sarma
• Karteek Sreenivasaiah

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 inputs are allowed to be unknown. We allow each query to produce three results: zero, one, or unknown. The output could also be: zero, one, or unknown, with the constraint that we should output "unknown" only when we cannot determine the answer from the revealed input bits. Such an extension of a Boolean function is called its hazard-free extension. - We prove an analogue of Huang’s celebrated sensitivity theorem [Annals of Mathematics, 2019] in our model of query complexity with uncertainty. - We show that the deterministic query complexity of the hazard-free extension of a Boolean function is at most quadratic in its randomized query complexity and quartic in its quantum query complexity, improving upon the best-known bounds in the Boolean world. - We exhibit an exponential gap between the smallest depth (size) of decision trees computing a Boolean function, and those computing its hazard-free extension. - We present general methods to convert decision trees for Boolean functions to those for their hazard-free counterparts, and show optimality of this construction. We also parameterize this result by the maximum number of unknown values in the input. - We show lower bounds on size complexity of decision trees for hazard-free extensions of Boolean functions in terms of the number of prime implicants and prime implicates of the underlying Boolean function.

STOC Conference 2023 Conference Paper

Randomized versus Deterministic Decision Tree Size

• Arkadev Chattopadhyay
• Yogesh Dahiya
• Nikhil S. Mande
• Jaikumar Radhakrishnan
• Swagato Sanyal

STOC Conference 2019 Conference Paper

The log-approximate-rank conjecture is false

• Arkadev Chattopadhyay
• Nikhil S. Mande
• Suhail Sherif

FOCS Conference 2018 Conference Paper

A Short List of Equalities Induces Large Sign Rank

• Arkadev Chattopadhyay
• Nikhil S. Mande

We exhibit a natural function F, that can be computed by just a linear sized decision list of 'Equalities', but whose sign rank is exponentially large. This yields the following two new unconditional complexity class separations. The first is an exponential separation between the depth-two threshold circuit classes Threshold-of Majority and Threshold-of-Threshold, answering an open question posed by Amano and Maruoka [MFCS '05] and Hansen and Podolskii [CCC '10]. The second separation shows that the communication complexity class P^MA is not contained in UPP, strongly resolving a recent open problem posed by Goos, Pitassi and Watson [ICALP '16]. In order to prove our main result, we view F as an XOR function and develop a technique to lower bound the sign rank of such functions. This requires novel approximation theoretic arguments against polynomials of unrestricted degree. Further, our work highlights for the first time the class 'decision lists of exact thresholds' as a common frontier for making progress on longstanding open problems in Threshold circuits and communication complexity.