Follow
Arkadev Chattopadhyay
Title
Cited by
Cited by
Year
Multiparty communication complexity of disjointness
A Chattopadhyay, A Ada
arXiv preprint arXiv:0801.3624, 2008
1022008
On the representational efficiency of restricted boltzmann machines
J Martens, A Chattopadhya, T Pitassi, R Zemel
Advances in Neural Information Processing Systems 26, 2013
892013
The story of set disjointness
A Chattopadhyay, T Pitassi
ACM SIGACT News 41 (3), 59-85, 2010
712010
Discrepancy and the power of bottom fan-in in depth-three circuits
A Chattopadhyay
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 449-458, 2007
652007
The log-approximate-rank conjecture is false
A Chattopadhyay, NS Mande, S Sherif
Journal of the ACM (JACM) 67 (4), 1-28, 2020
452020
Simulation theorems via pseudo-random properties
A Chattopadhyay, M Koucký, B Loff, S Mukhopadhyay
computational complexity 28, 617-659, 2019
432019
Topology matters in communication
A Chattopadhyay, J Radhakrishnan, A Rudra
2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 631-640, 2014
422014
Query-to-communication lifting using low-discrepancy gadgets
A Chattopadhyay, Y Filmus, S Koroth, O Meir, T Pitassi
SIAM Journal on Computing 50 (1), 171-210, 2021
302021
Lower bounds for circuits with MOD_m gates
A Chattopadhyay, N Goyal, P Pudlák, D Thérien
2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06 …, 2006
302006
Simulation beats richness: new data-structure lower bounds
A Chattopadhyay, M Koucký, B Loff, S Mukhopadhyay
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing …, 2018
282018
Equality alone does not simulate randomness
A Chattopadhyay, S Lovett, M Vinyals
34th Computational Complexity Conference (CCC 2019), 2019
252019
The hardness of being private
A Ada, A Chattopadhyay, SA Cook, L Fontes, M Koucký, T Pitassi
ACM Transactions on Computation Theory (TOCT) 6 (1), 1-24, 2014
252014
Graph isomorphism is not AC0-reducible to group isomorphism
A Chattopadhyay, J Torán, F Wagner
ACM Transactions on Computation Theory (TOCT) 5 (4), 1-13, 2013
252013
Circuits, Communication and Polynomials
A Chattopadhyay
McGill University, 2008
252008
Query-to-communication lifting for BPP using inner product
A Chattopadhyay, Y Filmus, S Koroth, O Meir, T Pitassi
46th International Colloquium on Automata, Languages, and Programming (ICALP …, 2019
242019
The NOF multiparty communication complexity of composed functions
A Ada, A Chattopadhyay, O Fawzi, P Nguyen
computational complexity 24, 645-694, 2015
212015
Linear systems over composite moduli
A Chattopadhyay, A Wigderson
2009 50th Annual IEEE Symposium on Foundations of Computer Science, 43-52, 2009
192009
A short list of equalities induces large sign rank
A Chattopadhyay, N Mande
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 47-58, 2018
172018
Lower bounds for circuits with few modular and symmetric gates
A Chattopadhyay, KA Hansen
International Colloquium on Automata, Languages, and Programming, 994-1005, 2005
172005
The range of topological effects on communication
A Chattopadhyay, A Rudra
International Colloquium on Automata, Languages, and Programming, 540-551, 2015
152015
The system can't perform the operation now. Try again later.
Articles 1–20