Arkadev Chattopadhyay

Publication Activity (10 Years)

Years Active: 2003-2024
Publications (10 Years): 61

Top Venues

Electron. Colloquium Comput. Complex.

CoRR

STOC

SIAM J. Comput.

Publications

Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorak
Exponential Separation Between Powers of Regular and General Resolution Over Parities. Electron. Colloquium Comput. Complex. (2024)
Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorák
Exponential Separation Between Powers of Regular and General Resolution over Parities. CCC (2024)
Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorák
Exponential Separation Between Powers of Regular and General Resolution Over Parities. CoRR (2024)
Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, Swagato Sanyal
Randomized versus Deterministic Decision Tree Size. STOC (2023)
Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan
Query Complexity of Search Problems. Electron. Colloquium Comput. Complex. (2023)
Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan
Query Complexity of Search Problems. MFCS (2023)
Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif
Lifting to Parity Decision Trees via Stifling. ITCS (2023)
Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay
Robustly Separating the Arithmetic Monotone Hierarchy Via Graph Inner-Product. Electron. Colloquium Comput. Complex. (2022)
Arkadev Chattopadhyay, Rajit Datta, Utsab Ghosal, Partha Mukhopadhyay
Monotone Complexity of Spanning Tree Polynomial Re-Visited. ITCS (2022)
Arkadev Chattopadhyay, Nikhil S. Mande
A Short List of Equalities Induces Large Sign-Rank. SIAM J. Comput. 51 (3) (2022)
Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay
Robustly Separating the Arithmetic Monotone Hierarchy via Graph Inner-Product. FSTTCS (2022)
Arkadev Chattopadhyay, Marek Cygan, Noga Ron-Zewi, Christian Wulff-Nilsen
Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020). SIAM J. Comput. 51 (3) (2022)
Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil S. Mande, Manaswi Paraashar, Ronald de Wolf
Symmetry and Quantum Query-To-Communication Simulation. STACS (2022)
Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif
Lifting to Parity Decision Trees Via Stifling. CoRR (2022)
Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif
Lifting to Parity Decision Trees Via Stifling. Electron. Colloquium Comput. Complex. (2022)
Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, Swagato Sanyal
Randomized versus Deterministic Decision Tree Size. Electron. Colloquium Comput. Complex. (2022)
Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki
Computing the multilinear factors of lacunary polynomials without heights. J. Symb. Comput. 104 (2021)
Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay
Lower bounds for monotone arithmetic circuits via communication complexity. STOC (2021)
Arkadev Chattopadhyay, Rajit Datta, Utsab Ghosal, Partha Mukhopadhyay
Monotone Complexity of Spanning Tree Polynomial Re-visited. CoRR (2021)
Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi
Query-to-Communication Lifting Using Low-Discrepancy Gadgets. SIAM J. Comput. 50 (1) (2021)
Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif
Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture. FSTTCS (2021)
Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil S. Mande, Manaswi Paraashar, Ronald de Wolf
Symmetry and Quantum Query-to-Communication Simulation. CoRR (2020)
Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh
Lower bounds for linear decision lists. Chic. J. Theor. Comput. Sci. 2020 (2020)
Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, Manaswi Paraashar
Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead. Computational Complexity Conference (2020)
Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay
Negations Provide Strongly Exponential Savings. Electron. Colloquium Comput. Complex. 27 (2020)
Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif
Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture. CoRR (2020)
Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif
Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture. Electron. Colloquium Comput. Complex. 27 (2020)
Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif
The Log-Approximate-Rank Conjecture Is False. J. ACM 67 (4) (2020)
Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay
Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity. Electron. Colloquium Comput. Complex. 27 (2020)
Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif
The log-approximate-rank conjecture is false. STOC (2019)
Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, Manaswi Paraashar
Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead. Electron. Colloquium Comput. Complex. 26 (2019)
Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi
Query-To-Communication Lifting for BPP Using Inner Product. ICALP (2019)
Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, Manaswi Paraashar
Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead. CoRR (2019)
Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh
Lower Bounds for Linear Decision Lists. CoRR (2019)
Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi
Query-to-Communication Lifting Using Low-Discrepancy Gadgets. Electron. Colloquium Comput. Complex. 26 (2019)
Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi
Query-to-communication lifting for BPP using inner product. CoRR (2019)
Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals
Equality Alone Does not Simulate Randomness. Computational Complexity Conference (2019)
Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh
Lower Bounds for Linear Decision Lists. Electron. Colloquium Comput. Complex. 26 (2019)
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Simulation Theorems via Pseudo-random Properties. Comput. Complex. 28 (4) (2019)
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Simulation beats richness: new data-structure lower bounds. STOC (2018)
Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals
Equality Alone Does Not Simulate Randomness. Electron. Colloquium Comput. Complex. 25 (2018)
Arkadev Chattopadhyay, Nikhil S. Mande
Separation of Unbounded-Error Models in Multi-Party Communication Complexity. Theory Comput. 14 (1) (2018)
Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif
The Log-Approximate-Rank Conjecture is False. Electron. Colloquium Comput. Complex. 25 (2018)
Arkadev Chattopadhyay, Nikhil S. Mande
A Short List of Equalities Induces Large Sign Rank. FOCS (2018)
Arkadev Chattopadhyay, Nikhil S. Mande
Weights at the Bottom Matter When the Top is Heavy. CoRR (2017)
Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra
Tight Network Topology Dependent Bounds on Rounds of Communication. SODA (2017)
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Composition and Simulation Theorems via Pseudo-random Properties. Electron. Colloquium Comput. Complex. 24 (2017)
Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Lower Bounds for Elimination via Weak Regularity. STACS (2017)
Arkadev Chattopadhyay, Nikhil S. Mande
Dual polynomials and communication complexity of XOR functions. CoRR (2017)
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Simulation Theorems via Pseudorandom Properties. CoRR (2017)
Arkadev Chattopadhyay, Nikhil S. Mande
A Lifting Theorem with Applications to Symmetric Functions. FSTTCS (2017)
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Simulation Beats Richness: New Data-Structure Lower Bounds. Electron. Colloquium Comput. Complex. 24 (2017)
Arkadev Chattopadhyay, Nikhil S. Mande
Dual polynomials and communication complexity of XOR functions. Electron. Colloquium Comput. Complex. 24 (2017)
Arkadev Chattopadhyay, Nikhil S. Mande
Weights at the Bottom Matter When the Top is Heavy. Electron. Colloquium Comput. Complex. 24 (2017)
Arkadev Chattopadhyay, Nikhil S. Mande
Small Error Versus Unbounded Error Protocols in the NOF Model. Electron. Colloquium Comput. Complex. 23 (2016)
Arkadev Chattopadhyay, Sagnik Mukhopadhyay
Tribes Is Hard in the Message Passing Model. CoRR (2016)
Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra
Tight Network Topology Dependent Bounds on Rounds of Communication. CoRR (2016)
Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Lower Bounds for Elimination via Weak Regularity. Electron. Colloquium Comput. Complex. 23 (2016)
Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi
Upper and Lower Bounds on the Power of Advice. SIAM J. Comput. 45 (4) (2016)
Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra
Tight Network Topology Dependent Bounds on Rounds of Communication. Electron. Colloquium Comput. Complex. 23 (2016)
Arkadev Chattopadhyay, Frederic Green, Howard Straubing
Circuit Complexity of Powering in Fields of Odd Characteristic. Chic. J. Theor. Comput. Sci. 2016 (2016)
Arkadev Chattopadhyay, Sagnik Mukhopadhyay
Tribes Is Hard in the Message Passing Model. STACS (2015)
Arkadev Chattopadhyay, Atri Rudra
The Range of Topological Effects on Communication. CoRR (2015)
Arkadev Chattopadhyay, Atri Rudra
The Range of Topological Effects on Communication. ICALP (2) (2015)
Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen
The NOF Multiparty Communication Complexity of Composed Functions. Comput. Complex. 24 (3) (2015)
Arkadev Chattopadhyay, Michael E. Saks
The Power of Super-logarithmic Number of Players. Electron. Colloquium Comput. Complex. 21 (2014)
Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi
The Hardness of Being Private. ACM Trans. Comput. Theory 6 (1) (2014)
Arkadev Chattopadhyay, Ricard Gavaldà, Kristoffer Arnsfelt Hansen, Denis Thérien
Learning Read-Constant Polynomials of Constant Degree Modulo Composites. Theory Comput. Syst. 55 (2) (2014)
Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra
Topology Matters in Communication. FOCS (2014)
Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra
Topology matters in communication. Electron. Colloquium Comput. Complex. 21 (2014)
Arkadev Chattopadhyay, Michael E. Saks
The Power of Super-logarithmic Number of Players. APPROX-RANDOM (2014)
James Martens, Arkadev Chattopadhyay, Toniann Pitassi, Richard S. Zemel
On the Expressive Power of Restricted Boltzmann Machines. NIPS (2013)
Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki
Computing the multilinear factors of lacunary polynomials without heights. CoRR (2013)
Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki
Factoring bivariate lacunary polynomials without heights. ISSAC (2013)
Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner
Graph Isomorphism is Not AC0-Reducible to Group Isomorphism. ACM Trans. Comput. Theory 5 (4) (2013)
Arkadev Chattopadhyay, Rahul Santhanam
Lower Bounds on Interactive Compressibility by Constant-Depth Circuits. FOCS (2012)
Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen
The NOF Multiparty Communication Complexity of Composed Functions. ICALP (1) (2012)
Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki
Factoring bivariate lacunary polynomials without heights CoRR (2012)
Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi
The Hardness of Being Private. Computational Complexity Conference (2012)
Arkadev Chattopadhyay, Rahul Santhanam
Lower Bounds on Interactive Compressibility by Constant-Depth Circuits. Electron. Colloquium Comput. Complex. 19 (2012)
Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi
A little advice can be very helpful. SODA (2012)
Arkadev Chattopadhyay, Ricard Gavaldà, Kristoffer Arnsfelt Hansen, Denis Thérien
Learning Read-Constant Polynomials of Constant Degree Modulo Composites. CSR (2011)
Arkadev Chattopadhyay, Shachar Lovett
Linear Systems over Finite Abelian Groups. Computational Complexity Conference (2011)
Arkadev Chattopadhyay, Shachar Lovett
Linear systems over abelian groups. Electron. Colloquium Comput. Complex. 18 (2011)
Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen
The NOF Multiparty Communication Complexity of Composed Functions. Electron. Colloquium Comput. Complex. 18 (2011)
Arkadev Chattopadhyay, Toniann Pitassi
The story of set disjointness. SIGACT News 41 (3) (2010)
Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner
Graph Isomorphism is not AC^0 reducible to Group Isomorphism. FSTTCS (2010)
Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner
Graph Isomorphism is not AC^0 reducible to Group Isomorphism. Electron. Colloquium Comput. Complex. 17 (2010)
Arkadev Chattopadhyay
Multilinear Polynomials Modulo Composites. Bull. EATCS 100 (2010)
Arkadev Chattopadhyay, Avi Wigderson
Linear Systems over Composite Moduli. FOCS (2009)
Arkadev Chattopadhyay, Avi Wigderson
Linear systems over composite moduli. Electron. Colloquium Comput. Complex. 16 (2009)
Arkadev Chattopadhyay, Anil Ada
Multiparty Communication Complexity of Disjointness CoRR (2008)
Arkadev Chattopadhyay, Anil Ada
Multiparty Communication Complexity of Disjointness. Electron. Colloquium Comput. Complex. 15 (002) (2008)
Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien
Languages with Bounded Multiparty Communication Complexity. STACS (2007)
Arkadev Chattopadhyay
Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits. FOCS (2007)
Arkadev Chattopadhyay
Discrepancy and the power of bottom fan-in in depth-three circuits. Electron. Colloquium Comput. Complex. 14 (050) (2007)
Arkadev Chattopadhyay, Bruce A. Reed
Properly 2-Colouring Linear Hypergraphs. APPROX-RANDOM (2007)
Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlák, Denis Thérien
Lower bounds for circuits with MOD_m gates. FOCS (2006)
Arkadev Chattopadhyay
An improved bound on correlation between polynomials over Z_m and MOD_q. Electron. Colloquium Comput. Complex. 13 (107) (2006)
Arkadev Chattopadhyay, Michal Koucký, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien
Languages with Bounded Multiparty Communication Complexity. Electron. Colloquium Comput. Complex. 13 (117) (2006)

Arkadev Chattopadhyay.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Arkadev Chattopadhyay