Arkadev Chattopadhyay

According to our database, Arkadev Chattopadhyay authored at least 62 papers between 2003 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2025

Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis.

Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett

Electron. Colloquium Comput. Complex., 2025

Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth.

Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay

Electron. Colloquium Comput. Complex., 2025

Sparsity Lower Bounds for Probabilistic Polynomials.

Josh Alman, Arkadev Chattopadhyay, Ryan Williams

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

Super-Critical Trade-Offs in Resolution over Parities via Lifting.

Arkadev Chattopadhyay, Pavel Dvorák

Proceedings of the 40th Computational Complexity Conference, 2025

2024

Exponential Separation Between Powers of Regular and General Resolution over Parities.

Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorák

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Randomized versus Deterministic Decision Tree Size.

Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, Swagato Sanyal

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Query Complexity of Search Problems.

Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

Lifting to Parity Decision Trees via Stifling.

Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020).

Arkadev Chattopadhyay, Marek Cygan, Noga Ron-Zewi, Christian Wulff-Nilsen

SIAM J. Comput., June, 2022

Symmetry and Quantum Query-To-Communication Simulation.

Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil S. Mande, Manaswi Paraashar, Ronald de Wolf

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

Monotone Complexity of Spanning Tree Polynomial Re-Visited.

Arkadev Chattopadhyay, Rajit Datta, Utsab Ghosal, Partha Mukhopadhyay

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Robustly Separating the Arithmetic Monotone Hierarchy via Graph Inner-Product.

Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay

Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

2021

Computing the multilinear factors of lacunary polynomials without heights.

Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki

J. Symb. Comput., 2021

Lower bounds for monotone arithmetic circuits via communication complexity.

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture.

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

2020

Negations Provide Strongly Exponential Savings.

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

Electron. Colloquium Comput. Complex., 2020

Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead.

Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, Manaswi Paraashar

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Lower Bounds for Linear Decision Lists.

Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh

Electron. Colloquium Comput. Complex., 2019

Query-to-Communication Lifting Using Low-Discrepancy Gadgets.

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2019

Simulation Theorems via Pseudo-random Properties.

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

Comput. Complex., 2019

The log-approximate-rank conjecture is false.

Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Query-To-Communication Lifting for BPP Using Inner Product.

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Equality Alone Does not Simulate Randomness.

Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals

Proceedings of the 34th Computational Complexity Conference, 2019

2018

Separation of Unbounded-Error Models in Multi-Party Communication Complexity.

Arkadev Chattopadhyay, Nikhil S. Mande

Theory Comput., 2018

Simulation beats richness: new data-structure lower bounds.

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

A Short List of Equalities Induces Large Sign Rank.

Arkadev Chattopadhyay, Nikhil S. Mande

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Weights at the Bottom Matter When the Top is Heavy.

Arkadev Chattopadhyay, Nikhil S. Mande

Electron. Colloquium Comput. Complex., 2017

Dual polynomials and communication complexity of XOR functions.

Arkadev Chattopadhyay, Nikhil S. Mande

Electron. Colloquium Comput. Complex., 2017

Composition and Simulation Theorems via Pseudo-random Properties.

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

Electron. Colloquium Comput. Complex., 2017

Simulation Theorems via Pseudorandom Properties.

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

CoRR, 2017

Lower Bounds for Elimination via Weak Regularity.

Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Tight Network Topology Dependent Bounds on Rounds of Communication.

Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

A Lifting Theorem with Applications to Symmetric Functions.

Arkadev Chattopadhyay, Nikhil S. Mande

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

2016

Upper and Lower Bounds on the Power of Advice.

Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi

SIAM J. Comput., 2016

Small Error Versus Unbounded Error Protocols in the NOF Model.

Arkadev Chattopadhyay, Nikhil S. Mande

Electron. Colloquium Comput. Complex., 2016

Circuit Complexity of Powering in Fields of Odd Characteristic.

Arkadev Chattopadhyay, Frederic Green, Howard Straubing

Chic. J. Theor. Comput. Sci., 2016

2015

Tribes Is Hard in the Message Passing Model.

Arkadev Chattopadhyay, Sagnik Mukhopadhyay

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

The Range of Topological Effects on Communication.

Arkadev Chattopadhyay, Atri Rudra

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Topology Matters in Communication.

Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

The Power of Super-logarithmic Number of Players.

Arkadev Chattopadhyay, Michael E. Saks

Proceedings of the Approximation, 2014

2013

Graph Isomorphism is Not AC0-Reducible to Group Isomorphism.

Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner

ACM Trans. Comput. Theory, 2013

On the Expressive Power of Restricted Boltzmann Machines.

James Martens, Arkadev Chattopadhyay, Toniann Pitassi, Richard S. Zemel

Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

Factoring bivariate lacunary polynomials without heights.

Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki

Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2013

2012

A little advice can be very helpful.

Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

The NOF Multiparty Communication Complexity of Composed Functions.

Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Lower Bounds on Interactive Compressibility by Constant-Depth Circuits.

Arkadev Chattopadhyay, Rahul Santhanam

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

The Hardness of Being Private.

Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Linear systems over abelian groups.

Arkadev Chattopadhyay, Shachar Lovett

Electron. Colloquium Comput. Complex., 2011

Learning Read-Constant Polynomials of Constant Degree Modulo Composites.

Arkadev Chattopadhyay, Ricard Gavaldà, Kristoffer Arnsfelt Hansen, Denis Thérien

Proceedings of the Computer Science - Theory and Applications, 2011

Linear Systems over Finite Abelian Groups.

Arkadev Chattopadhyay, Shachar Lovett

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010

The story of set disjointness.

Arkadev Chattopadhyay, Toniann Pitassi

SIGACT News, 2010

Multilinear Polynomials Modulo Composites.

Arkadev Chattopadhyay

Bull. EATCS, 2010

Graph Isomorphism is not AC^0 reducible to Group Isomorphism.

Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

2009

Linear Systems over Composite Moduli.

Arkadev Chattopadhyay, Avi Wigderson

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

Multiparty Communication Complexity of Disjointness.

Arkadev Chattopadhyay, Anil Ada

Electron. Colloquium Comput. Complex., 2008

2007

Languages with Bounded Multiparty Communication Complexity.

Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien

Proceedings of the STACS 2007, 2007

Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits.

Arkadev Chattopadhyay

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

Properly 2-Colouring Linear Hypergraphs.

Arkadev Chattopadhyay, Bruce A. Reed

Proceedings of the Approximation, 2007

2006

An improved bound on correlation between polynomials over Z_m and MOD_q.

Arkadev Chattopadhyay

Electron. Colloquium Comput. Complex., 2006

Lower bounds for circuits with MOD_m gates.

Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlák, Denis Thérien

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006

2005

Lower Bounds for Circuits with Few Modular and Symmetric Gates.

Arkadev Chattopadhyay, Kristoffer Arnsfelt Hansen

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2003

Locally Commutative Categories.

Arkadev Chattopadhyay, Denis Thérien

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003