Arkadev Chattopadhyay

Affiliations:
  • Tata Institute of Fundamental Research, School of Technology and Computer Science
  • University of Toronto, Department of Computer Science
  • Institute for Advanced Study, School of Mathematics


According to our database1, Arkadev Chattopadhyay authored at least 58 papers between 2003 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Exponential Separation Between Powers of Regular and General Resolution Over Parities.
Electron. Colloquium Comput. Complex., 2024

2023
Query Complexity of Search Problems.
Electron. Colloquium Comput. Complex., 2023

2022
Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020).
SIAM J. Comput., June, 2022

A Short List of Equalities Induces Large Sign-Rank.
SIAM J. Comput., 2022

Lifting to Parity Decision Trees Via Stifling.
Electron. Colloquium Comput. Complex., 2022

Robustly Separating the Arithmetic Monotone Hierarchy Via Graph Inner-Product.
Electron. Colloquium Comput. Complex., 2022

Randomized versus Deterministic Decision Tree Size.
Electron. Colloquium Comput. Complex., 2022

Symmetry and Quantum Query-To-Communication Simulation.
Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

Monotone Complexity of Spanning Tree Polynomial Re-Visited.
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021
Computing the multilinear factors of lacunary polynomials without heights.
J. Symb. Comput., 2021

2020
The Log-Approximate-Rank Conjecture Is False.
J. ACM, 2020

Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture.
Electron. Colloquium Comput. Complex., 2020

Negations Provide Strongly Exponential Savings.
Electron. Colloquium Comput. Complex., 2020

Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity.
Electron. Colloquium Comput. Complex., 2020

Lower bounds for linear decision lists.
Chic. J. Theor. Comput. Sci., 2020

2019
Query-to-Communication Lifting Using Low-Discrepancy Gadgets.
Electron. Colloquium Comput. Complex., 2019

Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead.
Electron. Colloquium Comput. Complex., 2019

Simulation Theorems via Pseudo-random Properties.
Comput. Complex., 2019

Query-To-Communication Lifting for BPP Using Inner Product.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
Separation of Unbounded-Error Models in Multi-Party Communication Complexity.
Theory Comput., 2018

Equality Alone Does Not Simulate Randomness.
Electron. Colloquium Comput. Complex., 2018

2017
Weights at the Bottom Matter When the Top is Heavy.
Electron. Colloquium Comput. Complex., 2017

Dual polynomials and communication complexity of XOR functions.
Electron. Colloquium Comput. Complex., 2017

Simulation Beats Richness: New Data-Structure Lower Bounds.
Electron. Colloquium Comput. Complex., 2017

Composition and Simulation Theorems via Pseudo-random Properties.
Electron. Colloquium Comput. Complex., 2017

Simulation Theorems via Pseudorandom Properties.
CoRR, 2017

A Lifting Theorem with Applications to Symmetric Functions.
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.
SIAM J. Comput., 2016

Small Error Versus Unbounded Error Protocols in the NOF Model.
Electron. Colloquium Comput. Complex., 2016

Tight Network Topology Dependent Bounds on Rounds of Communication.
Electron. Colloquium Comput. Complex., 2016

Lower Bounds for Elimination via Weak Regularity.
Electron. Colloquium Comput. Complex., 2016

Circuit Complexity of Powering in Fields of Odd Characteristic.
Chic. J. Theor. Comput. Sci., 2016

2015
The NOF Multiparty Communication Complexity of Composed Functions.
Comput. Complex., 2015

Tribes Is Hard in the Message Passing Model.
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

The Range of Topological Effects on Communication.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
The Hardness of Being Private.
ACM Trans. Comput. Theory, 2014

Learning Read-Constant Polynomials of Constant Degree Modulo Composites.
Theory Comput. Syst., 2014

The Power of Super-logarithmic Number of Players.
Electron. Colloquium Comput. Complex., 2014

Topology matters in communication.
Electron. Colloquium Comput. Complex., 2014

2013
Graph Isomorphism is Not AC0-Reducible to Group Isomorphism.
ACM Trans. Comput. Theory, 2013

On the Expressive Power of Restricted Boltzmann Machines.
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.
Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2013

2012
Lower Bounds on Interactive Compressibility by Constant-Depth Circuits.
Electron. Colloquium Comput. Complex., 2012

A little advice can be very helpful.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011
Linear systems over abelian groups.
Electron. Colloquium Comput. Complex., 2011

Linear Systems over Finite Abelian Groups.
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010
The story of set disjointness.
SIGACT News, 2010

Graph Isomorphism is not AC^0 reducible to Group Isomorphism.
Electron. Colloquium Comput. Complex., 2010

Multilinear Polynomials Modulo Composites.
Bull. EATCS, 2010

2009
Linear systems over composite moduli.
Electron. Colloquium Comput. Complex., 2009

2008
Multiparty Communication Complexity of Disjointness.
Electron. Colloquium Comput. Complex., 2008

2007
Discrepancy and the power of bottom fan-in in depth-three circuits.
Electron. Colloquium Comput. Complex., 2007

Properly 2-Colouring Linear Hypergraphs.
Proceedings of the Approximation, 2007

2006
Languages with Bounded Multiparty Communication Complexity.
Electron. Colloquium Comput. Complex., 2006

An improved bound on correlation between polynomials over Z_m and MOD_q.
Electron. Colloquium Comput. Complex., 2006

Lower bounds for circuits with MOD_m gates.
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.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2003
Locally Commutative Categories.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003


  Loading...