Arkadev Chattopadhyay

According to our database, Arkadev Chattopadhyay authored at least 59 papers between 2003 and 2024.

Collaborative distances:

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

2024

Super-critical Trade-offs in Resolution over Parities Via Lifting.

Arkadev Chattopadhyay, Pavel Dvorak

Electron. Colloquium Comput. Complex., 2024

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

Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorak

Electron. Colloquium Comput. Complex., 2024

2023

Query Complexity of Search Problems.

Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan

Electron. Colloquium Comput. Complex., 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

A Short List of Equalities Induces Large Sign-Rank.

Arkadev Chattopadhyay, Nikhil S. Mande

SIAM J. Comput., 2022

Lifting to Parity Decision Trees Via Stifling.

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

Electron. Colloquium Comput. Complex., 2022

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

Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay

Electron. Colloquium Comput. Complex., 2022

Randomized versus Deterministic Decision Tree Size.

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

Electron. Colloquium Comput. Complex., 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

2021

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

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

SIAM J. Comput., 2021

Computing the multilinear factors of lacunary polynomials without heights.

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

J. Symb. Comput., 2021

2020

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

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif

Electron. Colloquium Comput. Complex., 2020

Negations Provide Strongly Exponential Savings.

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

Electron. Colloquium Comput. Complex., 2020

Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity.

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

Electron. Colloquium Comput. Complex., 2020

Lower bounds for linear decision lists.

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

Chic. J. Theor. Comput. Sci., 2020

2019

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

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

Electron. Colloquium Comput. Complex., 2019

Simulation Theorems via Pseudo-random Properties.

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

Comput. Complex., 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

2018

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

Arkadev Chattopadhyay, Nikhil S. Mande

Theory Comput., 2018

The Log-Approximate-Rank Conjecture is False.

Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif

Electron. Colloquium Comput. Complex., 2018

Equality Alone Does Not Simulate Randomness.

Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals

Electron. Colloquium Comput. Complex., 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

Simulation Beats Richness: New Data-Structure Lower Bounds.

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

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

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

Tight Network Topology Dependent Bounds on Rounds of Communication.

Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra

Electron. Colloquium Comput. Complex., 2016

Lower Bounds for Elimination via Weak Regularity.

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

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

The NOF Multiparty Communication Complexity of Composed Functions.

Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen

Comput. Complex., 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

The Hardness of Being Private.

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

ACM Trans. Comput. Theory, 2014

Learning Read-Constant Polynomials of Constant Degree Modulo Composites.

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

Theory Comput. Syst., 2014

The Power of Super-logarithmic Number of Players.

Arkadev Chattopadhyay, Michael E. Saks

Electron. Colloquium Comput. Complex., 2014

Topology matters in communication.

Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra

Electron. Colloquium Comput. Complex., 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

Lower Bounds on Interactive Compressibility by Constant-Depth Circuits.

Arkadev Chattopadhyay, Rahul Santhanam

Electron. Colloquium Comput. Complex., 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

2011

Linear systems over abelian groups.

Arkadev Chattopadhyay, Shachar Lovett

Electron. Colloquium Comput. Complex., 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

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

Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner

Electron. Colloquium Comput. Complex., 2010

Multilinear Polynomials Modulo Composites.

Arkadev Chattopadhyay

Bull. EATCS, 2010

2009

Linear systems over composite moduli.

Arkadev Chattopadhyay, Avi Wigderson

Electron. Colloquium Comput. Complex., 2009

2008

Multiparty Communication Complexity of Disjointness.

Arkadev Chattopadhyay, Anil Ada

Electron. Colloquium Comput. Complex., 2008

2007

Discrepancy and the power of bottom fan-in in depth-three circuits.

Arkadev Chattopadhyay

Electron. Colloquium Comput. Complex., 2007

Properly 2-Colouring Linear Hypergraphs.

Arkadev Chattopadhyay, Bruce A. Reed

Proceedings of the Approximation, 2007

2006

Languages with Bounded Multiparty Communication Complexity.

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

Electron. Colloquium Comput. Complex., 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 (FOCS 2006), 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