6 citations · 14 across the 14 of their papers we have counts for
4 papers · 1 filter
The Role of Symmetry in Quantum Query-to-Communication Simulation
Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer +3
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}^n to {-1,1} and G in {AND_2, XOR_2}, the bounded-error quantum communication complexity of…
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…
Improved Approximate Degree Bounds For k-distinctness
Nikhil S. Mande, Justin Thaler, Shuchen Zhu
An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the k-distinctness function on inputs…