Linear systems over composite moduli (2010)
Chattopadhyay, Arkadev, Wigderson, Avi
We study solution sets to systems of generalized linear equations of the form ell_i (x_1, x_2, cdots
Languages with Bounded Multiparty Communication Complexity ∗ (2008)
Arkadev Chattopadhyay, Pascal Tesson, Andreas Krebs, Mario Szegedy, Denis Thérien
grateful to Pavel Pudlák for suggesting the use of the Hales-Jewett Theorem. We study languages with bounded communication complexity in the multiparty “input on the forehead model ” with...
Languages with Bounded Multiparty Communication Complexity ∗ (2008)
Arkadev Chattopadhyay, Pascal Tesson, Andreas Krebs, Mario Szegedy, Denis Thérien
for suggesting the use of the Hales-Jewett Theorem. Academy of Sciences Czech Republic We study languages with bounded communication complexity in the multiparty “input on the forehead model ”...
Arkadev Chattopadhyay, Bruce A. Reed
Using the symmetric form of the Lovász Local Lemma, one can conclude that a k-uniform hypergraph H admits a proper 2-colouring if the maximum degree (denoted by ∆) of H is at most 2k 8k...
Arkadev Chattopadhyay, Pavel Pudlák, Navin Goyal, Denis Thérien
Let CC[m] be the class of circuits in which all gates are MODm gates. In this paper we prove lower bounds for circuits in CC[m] and related classes. • Circuits in which all gates are MODm gates...
Multiparty Communication Complexity of Disjointness (2008)
Chattopadhyay, Arkadev, Ada, Anil
We obtain a lower bound of n^Omega(1) on the k-party randomized communication complexity of the Disjointness function in the `Number on the Forehead' model of multiparty communication when k is a...
Multiparty communication complexity of disjointness (2008)
Arkadev Chattopadhyay, Anil Ada
on the k-party randomized communication n 1 k+1 2 2k (k−1)2 k−1 complexity of the Disjointness function in the ‘Number on the Forehead ’ model of multiparty communication. In particular, this...
Discrepancy and the power of bottom fan-in in depth-three circuits (2007)
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...
Lower Bounds for Circuits With Few Modular and Symmetric Gates (2005)
Arkadev Chattopadhyay, Kristoffer Arnsfelt Hansen
circuits augmented with s MODm gates must have size n\Omega ( 1s log 1r-1 n) to compute MAJORITY or MODl, if l has a prime factor not dividing m. For proving the latter result we introduce a new...
Languages recognized by finite categories (2003)
Eilenberg has shown that the notion of varieties in semigroups/monoids can be naturally made to correspond with varieties of languages that they recognize. This has significantly deepened and...