Source author record

Nikhil S. Mande

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity

Catalog footprint

Research overview

2works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

One-way communication complexity and non-adaptive decision trees

We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. Let $IP$ denote Inner Product on $2b$ bits. - If $f$ is a total Boolean function that depends on all of its inputs, the bounded-error one-way quantum communication complexity of $f \circ IP$ equals $Ω(n(b-1))$ . - If $f$ is a partial Boolean function, the deterministic one-way communication complexity of $f \circ IP$ is at least $Ω(b \cdot D_{dt}^{\rightarrow}(f))$ , where $D_{dt}^{\rightarrow}(f)$ denotes the non-adaptive decision tree complexity of $f$ . Montanaro and Osborne [arXiv'09] observed that the deterministic one-way communication complexity of $f \circ XOR_2$ equals the non-adaptive parity decision tree complexity of $f$ . In contrast, we show the following with the gadget $AND_2$ . - There exists a function for which even the quantum non-adaptive AND decision tree complexity of $f$ is exponentially large in the deterministic one-way communication complexity of $f \circ AND_2$ . - For symmetric functions $f$ , the non-adaptive AND decision tree complexity of $f$ is at most quadratic in the (even two-way) communication complexity of $f \circ AND_2$ . In view of the first point, a lower bound on non-adaptive AND decision tree complexity of $f$ does not lift to a lower bound on one-way communication complexity of $f \circ AND_2$ . In our final result we show that for all $f$ , the deterministic one-way communication complexity of $F = f \circ AND_2$ is at most $(rank(M_{F}))(1 - Ω(1))$ , where $M_{F}$ denotes the communication matrix of $F$ . This shows that the rank upper bound on one-way communication complexity (which can be tight in general) is not tight for AND-composed functions.

preprint2020arXiv

On parity decision trees for Fourier-sparse Boolean functions

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 decision tree complexity. Let f be a Boolean function with Fourier support S and Fourier sparsity k. 1) We prove via the probabilistic method that there exists a parity decision tree of depth O(sqrt k) that computes f. This matches the best known upper bound on the parity decision tree complexity of Boolean functions (Tsang, Wong, Xie, and Zhang, FOCS 2013). Moreover, while previous constructions (Tsang et al., FOCS 2013, Shpilka, Tal, and Volk, Comput. Complex. 2017) build the trees by carefully choosing the parities to be queried in each step, our proof shows that a naive sampling of the parities suffices. 2) We generalize the above result by showing that if the Fourier spectra of Boolean functions satisfy a natural "folding property", then the above proof can be adapted to establish existence of a tree of complexity polynomially smaller than O(sqrt k). We make a conjecture in this regard which, if true, implies that the communication complexity of an XOR function is bounded above by the fourth root of the rank of its communication matrix, improving upon the previously known upper bound of square root of rank (Tsang et al., FOCS 2013, Lovett, J. ACM. 2016). 3) It can be shown by elementary techniques that for any Boolean function f and all pairs (alpha, beta) of parities in S, there exists another pair (gamma, delta) of parities in S such that alpha + beta = gamma + delta. We show, among other results, that there must exist several gamma in F_2^n such that there are at least three pairs (alpha_1, alpha_2) of parities in S with alpha_1 + alpha_2 = gamma.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.