Follow
Makrand Sinha
Makrand Sinha
Assistant Professor, Computer Science, University of Illinois Urbana-Champaign
Verified email at illinois.edu - Homepage
Title
Cited by
Cited by
Year
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
602023
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
562020
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
382020
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
312021
Simplified separation of information and communication
A Rao, M Sinha
Theory of Computing 14 (1), 1-29, 2018
282018
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
282012
Simple constructions of linear-depth t-designs and pseudorandom unitaries
T Metger, A Poremba, M Sinha, H Yuen
arXiv preprint arXiv:2404.12647, 2024
262024
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
252021
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
182019
On the communication complexity of greater-than.
SN Ramamoorthy, M Sinha
Allerton, 442-444, 2015
142015
Prefix discrepancy, smoothed analysis, and combinatorial vector balancing
N Bansal, H Jiang, R Meka, S Singla, M Sinha
arXiv preprint arXiv:2111.07049, 2021
112021
Lower bounds for approximating the matching polytope
M Sinha
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete …, 2018
102018
Quantum-classical tradeoffs in the random oracle model
Y Hamoudi, Q Liu, M Sinha
arXiv preprint arXiv:2211.12954, 2022
82022
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
82022
Vertices of degree k in random unlabeled trees
K Panagiotou, M Sinha
Journal of Graph Theory 69 (2), 114-130, 2012
72012
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
62022
Majorizing measures for the optimizer
S Borst, D Dadush, N Olver, M Sinha
arXiv preprint arXiv:2012.13306, 2020
52020
A direct-sum theorem for read-once branching programs
A Rao, M Sinha
Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2016
52016
Pseudorandom unitaries with non-adaptive security
T Metger, A Poremba, M Sinha, H Yuen
arXiv preprint arXiv:2402.14803, 2024
42024
The NISQ Complexity of Collision Finding
Y Hamoudi, Q Liu, M Sinha
Annual International Conference on the Theory and Applications of …, 2024
32024
The system can't perform the operation now. Try again later.
Articles 1–20