All reports by Author Arkadev Chattopadhyay:

__
TR23-039
| 28th March 2023
__

Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan#### Query Complexity of Search Problems

__
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

__
TR22-071
| 13th May 2022
__

Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay#### Robustly Separating the Arithmetic Monotone Hierarchy Via Graph Inner-Product

__
TR20-191
| 27th December 2020
__

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay#### Negations Provide Strongly Exponential Savings

__
TR20-166
| 9th November 2020
__

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay#### Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity

Revisions: 1

__
TR20-132
| 7th September 2020
__

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif#### Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture

__
TR19-136
| 23rd September 2019
__

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

__
TR19-103
| 7th August 2019
__

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi#### Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Revisions: 2

__
TR19-007
| 17th January 2019
__

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

__
TR18-206
| 3rd December 2018
__

Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals#### Equality Alone Does Not Simulate Randomness

Revisions: 1

__
TR18-176
| 26th October 2018
__

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

__
TR17-170
| 6th November 2017
__

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay#### Simulation Beats Richness: New Data-Structure Lower Bounds

__
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

__
TR17-014
| 23rd January 2017
__

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay#### Composition and Simulation Theorems via Pseudo-random Properties

__
TR16-165
| 30th October 2016
__

Arkadev Chattopadhyay, Pavel Dvo?ák, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay#### Lower Bounds for Elimination via Weak Regularity

__
TR16-130
| 11th August 2016
__

Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra#### Tight Network Topology Dependent Bounds on Rounds of Communication

__
TR16-095
| 7th June 2016
__

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

Revisions: 1
,
Comments: 1

__
TR14-074
| 14th May 2014
__

Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra#### Topology matters in communication

__
TR14-064
| 24th April 2014
__

Arkadev Chattopadhyay, Michael Saks#### The Power of Super-logarithmic Number of Players

__
TR11-155
| 22nd November 2011
__

Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen#### The NOF Multiparty Communication Complexity of Composed Functions

__
TR10-117
| 22nd July 2010
__

Arkadev Chattopadhyay, Jacobo Toran, Fabian Wagner#### Graph Isomorphism is not AC^0 reducible to Group Isomorphism

__
TR09-084
| 24th September 2009
__

Arkadev Chattopadhyay, Avi Wigderson#### Linear systems over composite moduli

__
TR08-002
| 19th December 2007
__

Arkadev Chattopadhyay, Anil Ada#### Multiparty Communication Complexity of Disjointness

Revisions: 3

__
TR07-050
| 25th May 2007
__

Arkadev Chattopadhyay#### Discrepancy and the power of bottom fan-in in depth-three circuits

__
TR06-117
| 31st August 2006
__

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien#### Languages with Bounded Multiparty Communication Complexity

__
TR06-107
| 26th August 2006
__

Arkadev Chattopadhyay#### An improved bound on correlation between polynomials over Z_m and MOD_q

Revisions: 1

Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan

We relate various complexity measures like sensitivity, block sensitivity, certificate complexity for multi-output functions to the query complexities of such functions. Using these relations, we improve upon the known relationship between pseudo-deterministic query complexity and deterministic query complexity for total search problems: We show that pseudo-deterministic query complexity is at ... more >>>

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

Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay

We establish an $\epsilon$-sensitive hierarchy separation for monotone arithmetic computations. The notion of $\epsilon$-sensitive monotone lower bounds was recently introduced by Hrubes [Computational Complexity'20]. We show the following:

(1) There exists a monotone polynomial over $n$ variables in VNP that cannot be computed by $2^{o(n)}$ size monotone ...
more >>>

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

We show that there is a family of monotone multilinear polynomials over $n$ variables in VP, such that any monotone arithmetic circuit for it would be of size $2^{\Omega(n)}$. Before our result, strongly exponential lower bounds on the size of monotone circuits were known only for computing explicit polynomials in ... more >>>

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first qualitative improvement to this classical result: we construct a family of polynomials $P_n$ in $n$ variables, each of its monomials has positive coefficient, such that $P_n$ can be computed ... more >>>

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif

We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $\Theta(n)$. This improves upon the ... 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 >>>

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Lifting theorems are theorems that relate the query complexity of a function $f:\left\{ 0,1 \right\}^n\to \left\{ 0,1 \right\}$ to the communication complexity of the composed function $f\circ g^n$, for some “gadget” $g:\left\{ 0,1 \right\}^b\times \left\{ 0,1 \right\}^b\to \left\{ 0,1 \right\}$. Such theorems allow transferring lower bounds from query complexity to ... 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, Shachar Lovett, Marc Vinyals

The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is `Equality'. In this work, we show that even allowing access to an `Equality' oracle, deterministic protocols remain exponentially weaker than randomized ones. More precisely, we exhibit a total function ... 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, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We develop a technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC'94) and Miltersen, Nisan, Safra and Wigderson (STOC'95). At the core of our technique is a novel simulation theorem: Alice gets a $p \times n$ ... 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, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We prove a randomized communication-complexity lower bound for a composed OrderedSearch $\circ$ IP — by lifting the randomized query-complexity lower-bound of OrderedSearch to the communication-complexity setting. We do this by extending ideas from a paper of Raz and Wigderson. We think that the techniques we develop will be useful in ... more >>>

Arkadev Chattopadhyay, Pavel Dvo?ák, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. and later studied by Beimel et al. for its connection to the famous direct sum question. In this problem, let $f:\{0,1\}^n \to \{0,1\}$ be any boolean function. Alice and Bob get $k$ inputs ... more >>>

Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra

We prove tight network topology dependent bounds on the round complexity of computing well studied $k$-party functions such as set disjointness and element distinctness. Unlike the usual case in the CONGEST model in distributed computing, we fix the function and then vary the underlying network topology. This complements the recent ... 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 >>>

Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra

We provide the first communication lower bounds that are sensitive to the network topology for computing natural and simple functions by point to point message passing protocols for the `Number in Hand' model. All previous lower bounds were either for the broadcast model or assumed full connectivity of the network. ... more >>>

Arkadev Chattopadhyay, Michael Saks

In the `Number-on-Forehead' (NOF) model of multiparty communication, the input is a $k \times m$ boolean matrix $A$ (where $k$ is the number of players) and Player $i$ sees all bits except those in the $i$-th row, and the players communicate by broadcast in order to evaluate a specified ... more >>>

Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen

We study the $k$-party `number on the forehead' communication complexity of composed functions $f \circ \vec{g}$, where $f:\{0,1\}^n \to \{\pm 1\}$, $\vec{g} = (g_1,\ldots,g_n)$, $g_i : \{0,1\}^k \to \{0,1\}$ and for $(x_1,\ldots,x_k) \in (\{0,1\}^n)^k$, $f \circ \vec{g}(x_1,\ldots,x_k) = f(\ldots,g_i(x_{1,i},\ldots,x_{k,i}), \ldots)$. When $\vec{g} = (g,g,\ldots,g)$ we denote $f \circ \vec{g}$ by ... more >>>

Arkadev Chattopadhyay, Jacobo Toran, Fabian Wagner

We give a new upper bound for the Group and Quasigroup

Isomorphism problems when the input structures

are given explicitly by multiplication tables. We show that these problems can be computed by polynomial size nondeterministic circuits of unbounded fan-in with $O(\log\log n)$ depth and $O(\log^2 n)$ nondeterministic bits, ...
more >>>

Arkadev Chattopadhyay, Avi Wigderson

We study solution sets to systems of generalized linear equations of the following form:

$\ell_i (x_1, x_2, \cdots , x_n)\, \in \,A_i \,\, (\text{mod } m)$,

where $\ell_1, \ldots ,\ell_t$ are linear forms in $n$ Boolean variables, each $A_i$ is an arbitrary subset of $\mathbb{Z}_m$, and $m$ is a composite ...
more >>>

Arkadev Chattopadhyay, Anil Ada

We extend the 'Generalized Discrepancy' technique suggested by Sherstov to the `Number on the Forehead' model of multiparty communication. This allows us to prove strong lower bounds of n^{\Omega(1)} on the communication needed by k players to compute the Disjointness function, provided $k$ is a constant. In general, our method ... more >>>

Arkadev Chattopadhyay

We develop a new technique of proving lower bounds for the randomized communication complexity of boolean functions in the multiparty 'Number on the Forehead' model. Our method is based on the notion of voting polynomial degree of functions and extends the Degree-Discrepancy Lemma in the recent work of Sherstov (STOC'07). ... more >>>

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien

We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case, it is known that such languages are exactly those that are recognized by programs over commutative monoids. This can be used to show that these languages can ... more >>>

Arkadev Chattopadhyay

Let m,q > 1 be two integers that are co-prime and A be any subset of Z_m. Let P be any multi-linear polynomial of degree d in n variables over Z_m. We show that the MOD_q boolean function on n variables has correlation at most exp(-\Omega(n/(m2^{m-1})^d)) with the boolean function ... more >>>