I agree that this site is using cookies. You can find further informations here.
X
Chattopadhyay, Arkadev
60  results:
Search for persons X
?
1

Randomized versus Deterministic Decision Tree Size:

, In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing,
Chattopadhyay, Arkadev ; Dahiya, Yogesh ; Mande, Nikhil S... - p. 867-880 , 2023
Link: https://dl.acm.org/doi/1..
 
?
2

A Short List of Equalities Induces Large Sign-Rank:

Chattopadhyay, Arkadev ; Mande, Nikhil S.
SIAM Journal on Computing.  51 (2022)  3 - p. 820-848 , 2022
Link: https://doi.org/10.1137/..
 
?
3

Special Section on the Fifty-Second Annual ACM Symposium on..:

Chattopadhyay, Arkadev ; Cygan, Marek ; Ron-Zewi, Noga.
SIAM Journal on Computing.  51 (2022)  3 - p. STOC20-i-STOC20-i , 2022
Link: https://doi.org/10.1137/..
 
?
4

Lower bounds for monotone arithmetic circuits via communica..:

, In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing,
Chattopadhyay, Arkadev ; Datta, Rajit ; Mukhopadhyay, Partha - p. 786-799 , 2021
Link: https://dl.acm.org/doi/1..
 
?
5

Computing the multilinear factors of lacunary polynomials w..:

Chattopadhyay, Arkadev ; Grenet, Bruno ; Koiran, Pascal..
Journal of Symbolic Computation.  104 (2021)  - p. 183-206 , 2021
Link: https://doi.org/10.1016/..
 
?
6

Query-to-Communication Lifting Using Low-Discrepancy Gadget:

Chattopadhyay, Arkadev ; Filmus, Yuval ; Koroth, Sajin..
SIAM Journal on Computing.  50 (2021)  1 - p. 171-210 , 2021
Link: https://doi.org/10.1137/..
 
?
7

The Log-Approximate-Rank Conjecture Is False:

Chattopadhyay, Arkadev ; Mande, Nikhil S. ; Sherif, Suhail
Journal of the ACM (JACM).  67 (2020)  4 - p. 1-28 , 2020
Link: https://dl.acm.org/doi/1..
 
?
8

Quantum query-to-communication simulation needs a logarithm..:

, In: Proceedings of the 35th Computational Complexity Conference,
Chakraborty, Sourav ; Chattopadhyay, Arkadev ; Mande, Nikhil S.. - p. 1-15 , 2020
Link: https://dl.acm.org/doi/1..
 
?
9

The Log-Approximate-Rank Conjecture Is False:

Chattopadhyay, Arkadev ; Mande, Nikhil S. ; Sherif, Suhail
Journal of the ACM.  67 (2020)  4 - p. 1-28 , 2020
Link: https://doi.org/10.1145/..
 
?
10

Equality alone does not simulate randomness:

, In: Proceedings of the 34th Computational Complexity Conference,
Chattopadhyay, Arkadev ; Lovett, Shachar ; Vinyals, Marc - p. 1-11 , 2019
Link: https://dl.acm.org/doi/1..
 
?
11

The log-approximate-rank conjecture is false:

, In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing,
Chattopadhyay, Arkadev ; Mande, Nikhil S. ; Sherif, Suhail - p. 42-53 , 2019
Link: https://dl.acm.org/doi/1..
 
?
12

Simulation Theorems via Pseudo-random Properties:

Chattopadhyay, Arkadev ; Koucký, Michal ; Loff, Bruno.
computational complexity.  28 (2019)  4 - p. 617-659 , 2019
Link: https://doi.org/10.1007/..
 
?
13

Simulation beats richness: new data-structure lower bounds:

, In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing,
Chattopadhyay, Arkadev ; Koucký, Michal ; Loff, Bruno. - p. 1013-1020 , 2018
Link: https://dl.acm.org/doi/1..
 
?
14

Tight network topology dependent bounds on rounds of commun..:

, In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms,
Chattopadhyay, Arkadev ; Langberg, Michael ; Li, Shi. - p. 2524-2539 , 2017
Link: https://dl.acm.org/doi/1..
 
?
15

Upper and Lower Bounds on the Power of Advice:

Chattopadhyay, Arkadev ; Edmonds, Jeff ; Ellen, Faith.
SIAM Journal on Computing.  45 (2016)  4 - p. 1412-1432 , 2016
Link: https://doi.org/10.1137/..
 
1-15