Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Arkadev Chattopadhyay:

TR20-191 | 27th December 2020
Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

Negations Provide Strongly Exponential Savings

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

TR20-166 | 9th November 2020
Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity

Revisions: 1

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

TR20-132 | 7th September 2020
Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif

Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture

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

TR19-136 | 23rd September 2019
Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil Mande, Manaswi Paraashar

Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead

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

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

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

TR19-007 | 17th January 2019
Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh

Lower Bounds for Linear Decision Lists

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

TR18-206 | 3rd December 2018
Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals

Equality Alone Does Not Simulate Randomness

Revisions: 1

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

TR18-176 | 26th October 2018
Arkadev Chattopadhyay, Nikhil Mande, Suhail Sherif

The Log-Approximate-Rank Conjecture is False

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

TR17-170 | 6th November 2017
Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

Simulation Beats Richness: New Data-Structure Lower Bounds

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

TR17-083 | 5th May 2017
Arkadev Chattopadhyay, Nikhil Mande

Weights at the Bottom Matter When the Top is Heavy

Revisions: 1

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

TR17-062 | 9th April 2017
Arkadev Chattopadhyay, Nikhil Mande

Dual polynomials and communication complexity of XOR functions

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

TR17-014 | 23rd January 2017
Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

Composition and Simulation Theorems via Pseudo-random Properties

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

TR16-165 | 30th October 2016
Arkadev Chattopadhyay, Pavel Dvo?ák, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

Lower Bounds for Elimination via Weak Regularity

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

TR16-130 | 11th August 2016
Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra

Tight Network Topology Dependent Bounds on Rounds of Communication

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

TR16-095 | 7th June 2016
Arkadev Chattopadhyay, Nikhil Mande

Small Error Versus Unbounded Error Protocols in the NOF Model

Revisions: 1 , Comments: 1

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

TR14-074 | 14th May 2014
Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra

Topology matters in communication

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

TR14-064 | 24th April 2014
Arkadev Chattopadhyay, Michael Saks

The Power of Super-logarithmic Number of Players

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

TR11-155 | 22nd November 2011
Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen

The NOF Multiparty Communication Complexity of Composed Functions

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

TR10-117 | 22nd July 2010
Arkadev Chattopadhyay, Jacobo Toran, Fabian Wagner

Graph Isomorphism is not AC^0 reducible to Group Isomorphism

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

TR09-084 | 24th September 2009
Arkadev Chattopadhyay, Avi Wigderson

Linear systems over composite moduli

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

TR08-002 | 19th December 2007
Arkadev Chattopadhyay, Anil Ada

Multiparty Communication Complexity of Disjointness

Revisions: 3

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

TR07-050 | 25th May 2007
Arkadev Chattopadhyay

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

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

TR06-117 | 31st August 2006
Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien

Languages with Bounded Multiparty Communication Complexity

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

TR06-107 | 26th August 2006
Arkadev Chattopadhyay

An improved bound on correlation between polynomials over Z_m and MOD_q

Revisions: 1

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

ISSN 1433-8092 | Imprint