Makrand Sinha

Publication Activity (10 Years)

Years Active: 2009-2024
Publications (10 Years): 41

Top Topics

Quantum Mechanics

Query Complexity

Communication Protocol

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen
Pseudorandom unitaries with non-adaptive security. IACR Cryptol. ePrint Arch. 2024 (2024)
Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen
Pseudorandom unitaries with non-adaptive security. CoRR (2024)
Yassine Hamoudi, Qipeng Liu, Makrand Sinha
The NISQ Complexity of Collision Finding. IACR Cryptol. ePrint Arch. 2024 (2024)
Jamico Schade, Makrand Sinha, Stefan Weltge
Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack. IPCO (2024)
Yassine Hamoudi, Qipeng Liu, Makrand Sinha
The NISQ Complexity of Collision Finding. EUROCRYPT (4) (2024)
Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen
Simple constructions of linear-depth t-designs and pseudorandom unitaries. CoRR (2024)
Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu
The Power of Adaptivity in Quantum Query Algorithms. STOC (2024)
Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu
The Power of Adaptivity in Quantum Query Algorithms. CoRR (2023)
William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal
Quantum Cryptography in Algorithmica. STOC (2023)
Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu
Fourier Growth of Communication Protocols for XOR Functions. CoRR (2023)
Jamico Schade, Makrand Sinha, Stefan Weltge
Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack. CoRR (2023)
Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu
Fourier Growth of Communication Protocols for XOR Functions. FOCS (2023)
William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal
Quantum Cryptography in Algorithmica. CoRR (2022)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Smoothed Analysis of the Komlós Conjecture. CoRR (2022)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing. ITCS (2022)
Yassine Hamoudi, Qipeng Liu, Makrand Sinha
Quantum-Classical Tradeoffs in the Random Oracle Model. CoRR (2022)
Nikhil Bansal, Makrand Sinha, Ronald de Wolf
Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms. CoRR (2022)
Nikhil Bansal, Makrand Sinha, Ronald de Wolf
Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms. CCC (2022)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Smoothed Analysis of the Komlós Conjecture. ICALP (2022)
Sander Borst, Daniel Dadush, Neil Olver, Makrand Sinha
Majorizing Measures for the Optimizer. ITCS (2021)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Online Discrepancy Minimization for Stochastic Arrivals. SODA (2021)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing. CoRR (2021)
Nikhil Bansal, Makrand Sinha
k-forrelation optimally separates Quantum and classical query complexity. STOC (2021)
Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, Makrand Sinha
Edge Estimation with Independent Set Oracles. ACM Trans. Algorithms 16 (4) (2020)
Sander Borst, Daniel Dadush, Neil Olver, Makrand Sinha
Majorizing Measures for the Optimizer. CoRR (2020)
Nikhil Bansal, Makrand Sinha
k-Forrelation Optimally Separates Quantum and Classical Query Complexity. CoRR (2020)
Nikhil Bansal, Haotian Jiang, Sahil Singla, Makrand Sinha
Online vector balancing and geometric discrepancy. STOC (2020)
Nikhil Bansal, Makrand Sinha
$k$-Forrelation Optimally Separates Quantum and Classical Query Complexity. Electron. Colloquium Comput. Complex. 27 (2020)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Online Discrepancy Minimization for Stochastic Arrivals. CoRR (2020)
Nikhil Bansal, Haotian Jiang, Sahil Singla, Makrand Sinha
Online Vector Balancing and Geometric Discrepancy. CoRR (2019)
Makrand Sinha, Ronald de Wolf
Exponential Separation between Quantum Communication and Logarithm of Approximate Rank. FOCS (2019)
Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, Makrand Sinha
Edge Estimation with Independent Set Oracles. ITCS (2018)
Anup Rao, Makrand Sinha
Simplified Separation of Information and Communication. Theory Comput. 14 (1) (2018)
Makrand Sinha, Ronald de Wolf
Exponential Separation between Quantum Communication and Logarithm of Approximate Rank. CoRR (2018)
Makrand Sinha, Ronald de Wolf
Exponential Separation between Quantum Communication and Logarithm of Approximate Rank. Electron. Colloquium Comput. Complex. 25 (2018)
Makrand Sinha
Lower Bounds for Approximating the Matching Polytope. SODA (2018)
Makrand Sinha
Lower Bounds for Approximating the Matching Polytope. Electron. Colloquium Comput. Complex. 24 (2017)
Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, Makrand Sinha
Edge Estimation with Independent Set Oracles. CoRR (2017)
Makrand Sinha
Lower Bounds for Approximating the Matching Polytope. CoRR (2017)
Shay Moran, Makrand Sinha, Amir Yehudayoff
Fooling Pairs in Randomized Communication Complexity. SIROCCO (2016)
Anup Rao, Makrand Sinha
A Direct-Sum Theorem for Read-Once Branching Programs. APPROX-RANDOM (2016)
Sivaramakrishnan Natarajan Ramamoorthy, Makrand Sinha
On the communication complexity of greater-than. Allerton (2015)
Anup Rao, Makrand Sinha
On Parallelizing Streaming Algorithms. Electron. Colloquium Comput. Complex. 22 (2015)
Anup Rao, Makrand Sinha
Simplified Separation of Information and Communication. Electron. Colloquium Comput. Complex. 22 (2015)
Shay Moran, Makrand Sinha, Amir Yehudayoff
Fooling Pairs in Randomized Communication Complexity. Electron. Colloquium Comput. Complex. 21 (2014)
Thomas Holenstein, Makrand Sinha
Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls CoRR (2012)
Thomas Holenstein, Makrand Sinha
Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls. FOCS (2012)
Konstantinos Panagiotou, Makrand Sinha
in random unlabeled trees. J. Graph Theory 69 (2) (2012)
Konstantinos Panagiotou, Makrand Sinha
Vertices of Degree k in Random Unlabeled Trees. Electron. Notes Discret. Math. 34 (2009)