3 citations · 3 across the 2 of their papers we have counts for
7 papers
Tight Chang's-lemma-type bounds for Boolean functions
Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal +3
Chang's lemma (Duke Mathematical Journal, 2002) is a classical result with applications across several areas in mathematics and computer science. For a Boolean function that ta…
On parity decision trees for Fourier-sparse Boolean functions
Nikhil S. Mande, Swagato Sanyal
We study parity decision trees for Boolean functions. The motivation of our study is the log-rank conjecture for XOR functions and its connection to Fourier analysis and parity dec…
Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead
Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande +1
Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function and the two-party bounded-erro…
Approximate degree, secret sharing, and concentration phenomena
Andrej Bogdanov, Nikhil S. Mande, Justin Thaler +1
The -approximate degree of a Boolean function is the least degree of a real-valued polynomial that approximates pointwise to error . The approximate degree…
Sign-Rank Can Increase Under Intersection
Mark Bun, Nikhil S. Mande, Justin Thaler
The communication class is a communication analog of the Turing Machine complexity class . It is characterized by a matrix-analytic complexi…
Lower Bounds for Linear Decision Lists
Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande +1
We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions. We use this technique to prov…