Edge estimation with independent set oracles P Beame, S Har-Peled, SN Ramamoorthy, C Rashtchian, M Sinha ACM Transactions on Algorithms (TALG) 16 (4), 1-27, 2020 | 52 | 2020 |
Online vector balancing and geometric discrepancy N Bansal, H Jiang, S Singla, M Sinha Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing …, 2020 | 38 | 2020 |
Quantum cryptography in algorithmica W Kretschmer, L Qian, M Sinha, A Tal Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 1589-1602, 2023 | 35 | 2023 |
Online discrepancy minimization for stochastic arrivals N Bansal, H Jiang, R Meka, S Singla, M Sinha Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA …, 2021 | 29 | 2021 |
Simplified separation of information and communication A Rao, M Sinha Theory of Computing 14 (1), 1-29, 2018 | 27 | 2018 |
Constructing a pseudorandom generator requires an almost linear number of calls T Holenstein, M Sinha 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, 698-707, 2012 | 27 | 2012 |
k-Forrelation optimally separates quantum and classical query complexity N Bansal, M Sinha Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing …, 2021 | 23 | 2021 |
Exponential separation between quantum communication and logarithm of approximate rank M Sinha, R De Wolf 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS …, 2019 | 17 | 2019 |
On the communication complexity of greater-than. SN Ramamoorthy, M Sinha Allerton, 442-444, 2015 | 14 | 2015 |
Prefix discrepancy, smoothed analysis, and combinatorial vector balancing N Bansal, H Jiang, R Meka, S Singla, M Sinha arXiv preprint arXiv:2111.07049, 2021 | 10 | 2021 |
Lower bounds for approximating the matching polytope M Sinha Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete …, 2018 | 9 | 2018 |
Influence in completely bounded block-multilinear forms and classical simulation of quantum algorithms N Bansal, M Sinha, R de Wolf arXiv preprint arXiv:2203.00212, 2022 | 6 | 2022 |
Vertices of degree k in random unlabeled trees K Panagiotou, M Sinha Journal of Graph Theory 69 (2), 114-130, 2012 | 6 | 2012 |
Simple constructions of linear-depth t-designs and pseudorandom unitaries T Metger, A Poremba, M Sinha, H Yuen arXiv preprint arXiv:2404.12647, 2024 | 5 | 2024 |
Quantum-classical tradeoffs in the random oracle model Y Hamoudi, Q Liu, M Sinha arXiv preprint arXiv:2211.12954, 2022 | 5 | 2022 |
Smoothed analysis of the Komlós conjecture N Bansal, H Jiang, R Meka, S Singla, M Sinha 49th International Colloquium on Automata, Languages, and Programming (ICALP …, 2022 | 5 | 2022 |
A direct-sum theorem for read-once branching programs A Rao, M Sinha Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2016 | 4 | 2016 |
Majorizing measures for the optimizer S Borst, D Dadush, N Olver, M Sinha arXiv preprint arXiv:2012.13306, 2020 | 3 | 2020 |
Pseudorandom unitaries with non-adaptive security T Metger, A Poremba, M Sinha, H Yuen arXiv preprint arXiv:2402.14803, 2024 | 2 | 2024 |
Fourier Growth of Communication Protocols for XOR Functions U Girish, M Sinha, A Tal, K Wu 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS …, 2023 | 2 | 2023 |