Arkadev Chattopadhyay


[photograph] Contact: firstname at cs dot toronto dot edu


News: I will be joining the Tata Institute of Fundamental Research (TIFR), Mumbai as a Reader in the School of Technology and Computer Science from September, 2012.


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


I am a postdoc in the Theory Group of the University of Toronto, until August 2012. I was 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 (IIT), 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, to appear in 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:

15. "Lower Bounds for Interactive Compression by Constant-Depth Circuits", with Rahul Santhanam, to appear in the 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, to appear in the 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, to appear in 27th IEEE Conference on Computational Complexity (CCC), 2012.

12. A Little Advice can be Very Helpful, with Jeff Edmonds, Faith Ellen and Toniann Pitassi, to appear in 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.