Arkadev Chattopadhyay

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