Arkadev Chattopadhyay


[photograph] Contact: firstname dot c at tifr dot res dot in





Research Interests:
1. Computational Complexity.
2. Algorithms and Discrete Mathematics.
3. Algebraic Automata Theory.


I am a faculty member in the School of Technology and Computer Science at the Tata Institute of Fundamental Research, Mumbai, since September, 2012. I was a postdoctoral fellow in the Theory Group of the University of Toronto from September, 2009 to August, 2012, a member of the School of Mathematics at the Institute for Advanced Study, Princeton, in 2008-2009, with the group of Avi Wigderson. Before that, I was a graduate student in the School of Computer Science, at McGill University, Montreal from 2002 to 2008, advised by Denis Thérien. I got my undergraduate degree in Electronics and Electrical Communication Engineering from the Indian Institute of Technology, Kharagpur, India in 1994.

From 1995 to 2002, I was in the industry of developing software for telecommunications applications.

Publicatons: Note that the usual copyright restrictions apply for the information provided below

Surveys:

1. The Story of Set-Disjointness, with Toniann Pitassi ACM SIGACT News, September 2010.

2. Multilinear Polynomials Modulo Composites, Bulletin of the European Association of Theoretical Computer Science (EATCS), February 2010.

Theses:

1. Circuits, Communication and Polynomials, Ph.D thesis, McGill University, Dec, 2008.

2. Languages Recognized by Finite Categories, Master's thesis, McGill University, Feb, 2004.

Papers:

21. "The Range of Topological Effects on Communication", with Atri Rudra, Manuscript, to appear in the 42nd International Colloquium on Automata, Languages and Programming (ICALP), 2015.

20. "Tribes is Hard in the Message Passing Model", with Sagnik Mukhopadhyay, to appear in the 32nd Symposium on Theoretical Aspects of Computer Science (STACS), 2015.

19. "Topology Matters in Communication", with Jaikumar Radhakrishnan and Atri Rudra, ECCC Report, 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2014.

18. "The Power of Super-logarithmic Number of Players", with Michael Saks, ECCC Report, 18th International Workshop on Randomization and Computation (RANDOM), 2014.

17. "On the Expressive Power of Restricted Boltzmann Machines", with James Martens, Toniann Pitassi and Richard Zemel, Neural Information Processing Systems (NIPS), 2013.

16. "Factoring Bivariate Lacunary Polynomials without Heights", with Bruno Grenet, Pascal Koiran, Natacha Portier and Yann Strozecki, International Symposium on Symbolic and Algebraic Computation (ISSAC), 2013.

15. "Lower Bounds for Interactive Compression by Constant-Depth Circuits", with Rahul Santhanam, 53rd IEEE Symposium on Foundations of Computer Science (FOCS), 2012.

14. "The NOF Multiparty Communication Complexity of Composed Functions", with Anil Ada, Omar Fawzi, and Phuong Nguyen, ECCC Link, 39th International Colloquium on Automata, Languages and Programming (ICALP), Warwick, UK, 2012.

13. "The Hardness of Being Private", with Anil Ada, Stephen Cook, Lila Fontes, Michal Koucky and Toniann Pitassi, 27th IEEE Conference on Computational Complexity (CCC), 2012.

12. A Little Advice can be Very Helpful, with Jeff Edmonds, Faith Ellen and Toniann Pitassi, ACM-SIAM Symposium on Discrete Algorithms (SODA), Kyoto, Japan 2012.

11. Linear Systems over Finite Abelian Groups, with Shachar Lovett, 26th IEEE Annual Conference on Computational Complexity (CCC), San Jose, 2011.

10. Learning Read-constant Polynomials of Constant Degree over Arbitrary Moduli, with Kristoffer Hansen, Ricard Gavaldà and Denis Thérien, 6th International Computer Science Symposium in Russia (CSR), St-Petersburg, Russia, 2011.

9. "Graph Isomorphism is not AC^0 Reducible to Group Isomorphism", with Jacobo Torán and Fabian Wagner, ECCC Link, Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2010, Chennai, India.

8. Linear Systems over Composite Moduli, with Avi Wigderson, 50th IEEE Symposium on Foundations of Computer Science (FOCS), Atlanta, 2009.

7. Multiparty Communication Complexity of Disjointness, with Anil Ada, Manuscript, ECCC TR08-002.

6. Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits, 48th IEEE Symposium on Foundations of Computer Science (FOCS), Providence, 2007.

5. Properly 2-Colouring Linear Hypergraphs, with Bruce Reed, 11th International Workshop on Randomization and Computation (RANDOM), Princeton, 2007.

4. "Languages with Bounded Multiparty Communication Complexity", with Andreas Krebs, Michal Koucky, Mario Szegedy, Pascal Tesson and Denis Thérien, ECCC Link, 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Aachen, 2007.

3. Lower Bounds for Circuits with MOD m gates, with Navin Goyal, Pavel Pudlak and Denis Thérien, 47th IEEE Symposium on Foundations of Computer Science (FOCS), Berkeley, 2006.

2. Lower Bounds for Circuits with Few Modular and Symmetric Gates, with Kristoffer Arnsfelt Hansen, 32nd International Colloquium on Automata, Languages and Programming (ICALP), Lisbon, 2005.

1. Locally Commutative Categories, with Denis Thérien, 30th International Colloquium on Automata, Languages and Programming (ICALP), Eindhoven, 2003.