Makrand Sinha

According to our database, Makrand Sinha authored at least 26 papers between 2009 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Pseudorandom unitaries with non-adaptive security.

Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen

IACR Cryptol. ePrint Arch., 2024

The NISQ Complexity of Collision Finding.

Yassine Hamoudi, Qipeng Liu, Makrand Sinha

IACR Cryptol. ePrint Arch., 2024

2023

The Power of Adaptivity in Quantum Query Algorithms.

Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu

CoRR, 2023

Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack.

Jamico Schade, Makrand Sinha, Stefan Weltge

CoRR, 2023

Quantum Cryptography in Algorithmica.

William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Fourier Growth of Communication Protocols for XOR Functions.

Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Quantum-Classical Tradeoffs in the Random Oracle Model.

Yassine Hamoudi, Qipeng Liu, Makrand Sinha

CoRR, 2022

Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing.

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Smoothed Analysis of the Komlós Conjecture.

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms.

Nikhil Bansal, Makrand Sinha, Ronald de Wolf

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Online Discrepancy Minimization for Stochastic Arrivals.

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Majorizing Measures for the Optimizer.

Sander Borst, Daniel Dadush, Neil Olver, Makrand Sinha

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020

Edge Estimation with Independent Set Oracles.

Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, Makrand Sinha

ACM Trans. Algorithms, 2020

$k$-Forrelation Optimally Separates Quantum and Classical Query Complexity.

Nikhil Bansal, Makrand Sinha

Electron. Colloquium Comput. Complex., 2020

Online vector balancing and geometric discrepancy.

Nikhil Bansal, Haotian Jiang, Sahil Singla, Makrand Sinha

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2018

Lower Bounds for Interactive Compression and Linear Programs.

Makrand Sinha

PhD thesis, 2018

Simplified Separation of Information and Communication.

Anup Rao, Makrand Sinha

Theory Comput., 2018

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank.

Makrand Sinha, Ronald de Wolf

Electron. Colloquium Comput. Complex., 2018

2017

Lower Bounds for Approximating the Matching Polytope.

Makrand Sinha

Electron. Colloquium Comput. Complex., 2017

2016

A Direct-Sum Theorem for Read-Once Branching Programs.

Anup Rao, Makrand Sinha

Proceedings of the Approximation, 2016

2015

On Parallelizing Streaming Algorithms.

Anup Rao, Makrand Sinha

Electron. Colloquium Comput. Complex., 2015

On the communication complexity of greater-than.

Sivaramakrishnan Natarajan Ramamoorthy, Makrand Sinha

Proceedings of the 53rd Annual Allerton Conference on Communication, 2015

2014

Fooling Pairs in Randomized Communication Complexity.

Shay Moran, Makrand Sinha, Amir Yehudayoff

Electron. Colloquium Comput. Complex., 2014

2012

Vertices of degree <i>k</i> in random unlabeled trees.

Konstantinos Panagiotou, Makrand Sinha

J. Graph Theory, 2012

Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls.

Thomas Holenstein, Makrand Sinha

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2009

Vertices of Degree k in Random Unlabeled Trees.

Konstantinos Panagiotou, Makrand Sinha

Electron. Notes Discret. Math., 2009