All reports by Author Nikhil Mande:

__
TR22-185
| 29th December 2022
__

Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil Mande, Jaikumar Radhakrishnan, Swagato Sanyal#### Randomized versus Deterministic Decision Tree Size

__
TR22-172
| 2nd December 2022
__

Arkadev Chattopadhyay, Nikhil Mande, Swagato Sanyal, Suhail Sherif#### Lifting to Parity Decision Trees Via Stifling

__
TR21-113
| 25th July 2021
__

Nikhil Mande, Ronald de Wolf#### Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error

__
TR21-065
| 5th May 2021
__

Nikhil Mande, Swagato Sanyal#### One-way communication complexity and non-adaptive decision trees

Revisions: 1

__
TR20-119
| 1st August 2020
__

Nikhil Mande, Swagato Sanyal#### On parity decision trees for Fourier-sparse Boolean functions

__
TR19-136
| 23rd September 2019
__

Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil Mande, Manaswi Paraashar#### Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead

__
TR19-082
| 2nd June 2019
__

Andrej Bogdanov, Nikhil Mande, Justin Thaler, Christopher Williamson#### Approximate degree, secret sharing, and concentration phenomena

__
TR19-027
| 1st March 2019
__

Mark Bun, Nikhil Mande, Justin Thaler#### Sign-Rank Can Increase Under Intersection

__
TR19-007
| 17th January 2019
__

Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh#### Lower Bounds for Linear Decision Lists

__
TR18-176
| 26th October 2018
__

Arkadev Chattopadhyay, Nikhil Mande, Suhail Sherif#### The Log-Approximate-Rank Conjecture is False

__
TR17-083
| 5th May 2017
__

Arkadev Chattopadhyay, Nikhil Mande#### Weights at the Bottom Matter When the Top is Heavy

Revisions: 1

__
TR17-062
| 9th April 2017
__

Arkadev Chattopadhyay, Nikhil Mande#### Dual polynomials and communication complexity of XOR functions

__
TR16-095
| 7th June 2016
__

Arkadev Chattopadhyay, Nikhil Mande#### Small Error Versus Unbounded Error Protocols in the NOF Model

Revisions: 1
,
Comments: 1

Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil Mande, Jaikumar Radhakrishnan, Swagato Sanyal

A classic result of Nisan [SICOMP '91] states that the deterministic decision tree depth complexity of every total Boolean function is at most the cube of its randomized decision tree depth complexity. The question whether randomness helps in significantly reducing the size of decision trees appears not to have been ... more >>>

Arkadev Chattopadhyay, Nikhil Mande, Swagato Sanyal, Suhail Sherif

We show that the deterministic decision tree complexity of a (partial) function or relation $f$ lifts to the deterministic parity decision tree (PDT) size complexity of the composed function/relation $f \circ g$ as long as the gadget $g$ satisfies a property that we call stifling. We observe that several simple ... more >>>

Nikhil Mande, Ronald de Wolf

We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability $\epsilon$, getting the optimal constant factors in the leading terms in a number of different models.

The following are our results in the randomized model:

1) We give a general technique to convert ... more >>>

Nikhil Mande, Swagato Sanyal

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 ... more >>>

Nikhil 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 decision tree complexity. Our contributions are as follows. Let $f : \mathbb{F}_2^n \to \{-1, 1\}$ be a Boolean function with Fourier support ... more >>>

Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil Mande, Manaswi Paraashar

Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function $f : \{-1, 1\}^n \to \{-1, 1\}$ and $\bullet : \{-1, 1\}^2 \to \{-1, 1\}$ the two-party bounded-error quantum communication complexity of $(f \circ \bullet)$ is $O(Q(f) \log n)$, where $Q(f)$ is the bounded-error quantum query complexity of $f$. ... more >>>

Andrej Bogdanov, Nikhil Mande, Justin Thaler, Christopher Williamson

The $\epsilon$-approximate degree $\widetilde{\text{deg}}_\epsilon(f)$ of a Boolean function $f$ is the least degree of a real-valued polynomial that approximates $f$ pointwise to error $\epsilon$. The approximate degree of $f$ is at least $k$ iff there exists a pair of probability distributions, also known as a dual polynomial, that are perfectly ... more >>>

Mark Bun, Nikhil 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 complexity measure called sign-rank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds.

For a communication problem ... more >>>

Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh

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 prove an explicit lower bound by showing that any linear decision list computing the function $MAJ \circ XOR$ requires size $2^{0.18 n}$. This ...
more >>>

Arkadev Chattopadhyay, Nikhil Mande, Suhail Sherif

We construct a simple and total XOR function $F$ on $2n$ variables that has only $O(\sqrt{n})$ spectral norm, $O(n^2)$ approximate rank and $n^{O(\log n)}$ approximate nonnegative rank. We show it has polynomially large randomized bounded-error communication complexity of $\Omega(\sqrt{n})$. This yields the first exponential gap between the logarithm of the ... more >>>

Arkadev Chattopadhyay, Nikhil Mande

Proving super-polynomial lower bounds against depth-2 threshold circuits of the form THR of THR is a well-known open problem that represents a frontier of our understanding in boolean circuit complexity. By contrast, exponential lower bounds on the size of THR of MAJ circuits were shown by Razborov and Sherstov (SIAM ... more >>>

Arkadev Chattopadhyay, Nikhil Mande

We show a new duality between the polynomial margin complexity of $f$ and the discrepancy of the function $f \circ$ XOR, called an XOR function. Using this duality,

we develop polynomial based techniques for understanding the bounded error (BPP) and the weakly-unbounded error (PP) communication complexities of XOR functions. ...
more >>>

Arkadev Chattopadhyay, Nikhil Mande

We show that a simple function has small unbounded error communication complexity in the $k$-party number-on-forehead (NOF) model but every probabilistic protocol that solves it with sub-exponential advantage over random guessing has cost essentially $\Omega\left(\frac{\sqrt{n}}{4^k}\right)$ bits. Such a separation was first shown for $k=2$ independently by Buhrman et al. ['07] ... more >>>