Nikhil S. Mande

activity

20172026

most citedTight Bounds for Quantum Phase Estimation and Related Problems

6 citations · 24 across the 17 of their papers we have counts for

collaborators

Showing 2019Show all

4 papers · 1 filter

quant-ph2019

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 $f : {- 1, 1}^{n} \to {- 1, 1}$ and $∙ : {- 1, 1}^{2} \to {- 1, 1}$ the two-party bounded-erro…

cs.CC2019

Approximate degree, secret sharing, and concentration phenomena

Andrej Bogdanov, Nikhil S. Mande, Justin Thaler +1

The $ε$ -approximate degree $d e g_{ε} (f)$ of a Boolean function $f$ is the least degree of a real-valued polynomial that approximates $f$ pointwise to error $ε$ . The approximate degree…

cs.CC2019

Sign-Rank Can Increase Under Intersection

Mark Bun, Nikhil S. Mande, Justin Thaler

The communication class $UPP^{cc}$ is a communication analog of the Turing Machine complexity class $PP$ . It is characterized by a matrix-analytic complexi…

cs.CC2019★ 3 cited

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…