Arkadev Chattopadhyay

Professor

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 member of the faculty 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.

Editorial Work:

1. Associate Editor, ACM Transactions on Computation Theory (TOCT)

Program Committee Chair:

1. Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2019.

Program Committee:

FOCS 2015, STACS 2016, FSTTCS 2016, ICALP 2017, STOC 2020, CCC 2021 , STOC 2023, FOCS 2023, SODA 2026

Current Graduate Students

1. Sreejata Kishore Bhattacharya, (Sept, 2022 -- ).

Past Graduate Students

3. Suhail Sherif, (Jan, 2017 -- May, 2021), postdoc at the University of Lisbon, Portugal.

2. Nikhil Mande, (Mar, 2015 -- Aug, 2018), Lecturer (Assistant Professor) at the University of Liverpool, UK.

1. Sagnik Mukhopadhyay, (Aug, 2013 -- July, 2017), Associate Professor in the School of Computer Science at the University of Birmingham, UK.

Postdocs

1. Yogesh Dahiya (2024--).

2. Pavel Dvořák (2022-24), second post-doc at Charles University, Prague.

3. Marc Vinyals (2017-19), Lecturer at the University of Auckland, New Zealand.

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:

47. "Restriction Trees for Sparsity and Applications", with Yogesh Dahiya and Shachar Lovett, ECCC Report, Subsumes earlier reports below.

"Exact Versus Approximate Representations of Boolean Functions in the De Morgan Basis", with Yogesh Dahiya and Shachar Lovett, ECCC Report , Arxiv Report, Older reports subsumed by above.

46. "Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth", with Sreejata Bhattacharya, ECCC Report, ArXiv Report, New!

45. "Super-critical Trade-offs in Resolution Over Parities via Lifting", with Pavel Dvořák, ECCC Report, 40th Computational Complexity Conference (CCC), 2025 , New!

44. "Sparsity Lower Bounds for Probabilistic Polynomials", with Josh Alman and Ryan Williams, 16th Innovations in Theoretical Computer Science (ITCS), 2025, New!

43. "Exponential Separation Between Powers of Regular and General Resolution over Parities", with Sreejata Bhattacharya and Pavel Dvořák, ECCC Report, ArXiv Report, 39th Computational Complexity Conference (CCC), 2024 New!

42. "Query Complexity of Search Problems", with Yogesh Dahiya and Meena Mahajan, ECCC Report, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2023

41. "Randomized Versus Deterministic Decision Tree Size", with Yogesh Dahiya, Nikhil Mande, Jaikumar Radhakrishnan and Swagato Sanyal, ECCC Report, 55th ACM Symposium on Theory of Computing (STOC), 2023

40. "Lifiting to Parity Decision Trees Via Stifling", with Nikhil Mande, Swagato Sanyal and Suhail Sherif, ArXiv Report and ECCC Report, 14th Innovations in Theoretical Computer Science (ITCS), 2023

39. "Robustly Separating the Arithmetic Monotone Hierarchy via Graph Inner-Product", with Utsab Ghosal and Partha Mukhopadhyay, ECCC Report, 42nd Foundations of Software Technology & Theoretical Computer Science (FSTTCS), 2022

38. "Monotone Complexity of Spanning Tree Polynomial Re-visited", with Rajit Datta, Utsab Ghosal and Partha Mukhopadhyay, ArXiv Report, 13th Innovations in Theoretical Computer Science (ITCS), 2022 Subsumes the earlier report below.

"Negations Provide Strongly Exponential Savings", with Rajit Datta and Partha Mukhopadhyay, ECCC Report , Older report subsumed by above.

37. "Symmetry and Quantum Query-to-Communication Simulation", with Sourav Chakraborty, Peter Hoyer, Nikhil Mande, Manaswi Paraashar and Ronald de Wolf, ArXiv Report , 39th International Symposium on Theoretical Aspects of Computer Science (STACS), 2022

36. "Lower Bounds for Monotone Arithmetic Circuits via Communication Complexity ", with Rajit Datta and Partha Mukhopadhyay, ECCC Report, 53rd ACM Symposium on Theory of Computing (STOC), 2021

35. "Towards Stronger Counter-examples to the Log-Approximate-Rank Conjecture ", with Ankit Garg and Suhail Sherif, ECCC Report, 41st Foundations of Software Technology & Theoretical Computer Science (FSTTCS), 2021

34. "Quantum Query-to-communication simulation needs a logarithmic overhead", with Sourav Chakraborty, Nikhil Mande and Manaswi Paraashar, ArXiv Report , ECCC Report, Conference on Computational Complexity (CCC), 2020; also presented at Quantum Information Processing (QIP), 2020.

33. "Query-to-communication lifting for BPP using inner product", with Yuval Filmus, Sajin Koroth, Or Meir and Toniann Pitassi, 46th International Colloquium on Automata, Languages and Programming (ICALP), 2019.

32. "Equality Alone Does Not Simulate Randomness", with Shachar Lovett and Marc Vinyals, ECCC Report, Computational Complexity Conference (CCC), 2019.

31. "The Log-Approximate-Rank Conjecture is False", with Nikhil Mande and Suhail Sherif, ECCC Report, 51st ACM Symposium on Theory of Computing (STOC), 2019; full version at the Journal of the ACM, June 2020.
Invited to STOC special issue
Invited to Theory of Computing (TOC)
to be presented as an Invited Talk at Highlights of Algorithms (HALG) 2020, Zurich

30. "A Short List of Equalities Induces Large Sign Rank", with Nikhil Mande, ECCC Report, 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2018.

29. "Lower Bounds for Linear Decision Lists", with Meena Mahajan, Nikhil Mande and Nitin Saurabh, Chicago Journal of Theoretical Computer Science (CJTCS), 2020.

28. "Simulation Beats Richness: New Data-Structure Lower Bounds", with Michal Koucký, Bruno Loff and Sagnik Mukhopadhyay,ECCC Report, 50th ACM Symposium on Theory of Computing (STOC), 2018

27. "Dual Polynomials and Communication Complexity of XOR Functions", with Nikhil Mande, ECCC Report, part of it in Foundations of Software Technology & Theoretical Computer Science (FSTTCS), 2017

26. "Composition and Simulation Theorems via Pseudo-random Properties", with Michal Koucký, Bruno Loff and Sagnik Mukhopadhyay, ECCC Report, Computational Complexity, vol 28 (617-659), 2019.

25. "Lower Bounds for Elimination via Weak Regularity", with Pavel Dvorak, Michal Koucký, Bruno Loff and Sagnik Mukhopadhyay, ECCC Report, 34th Symposium on Theoretical Aspects of Computer Science (STACS), 2017

24. "Tight Network Topology Dependent Bounds on Rounds of Communication", with Michael Langberg, Shi Li and Atri Rudra, ECCC Report, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017.

23. "Small Error Versus Unbounded Error Protocols in the NOF Model", with Nikhil Mande, ECCC Report, Theory of Computing, vol 14(1): 1-23, 2018.

22. Circuit Complexity of Powering in Fields of Odd Characteristic, with Frederic Green and Howard Straubing, Chicago Journal of Theoretical Computer Science, 2016.

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

20. "Tribes is Hard in the Message Passing Model", with Sagnik Mukhopadhyay, ECCC Report,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, ECCC Report, 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.