Makrand Sinha

According to our database, Makrand Sinha authored at least 28 papers between 2009 and 2025.

Collaborative distances:

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

2025

The Hardness of Learning Quantum Circuits and its Cryptographic Applications.

Bill Fefferman, Soumik Ghosh, Makrand Sinha, Henry Yuen

IACR Cryptol. ePrint Arch., 2025

2024

Pseudorandom unitaries with non-adaptive security.

Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen

IACR Cryptol. ePrint Arch., 2024

The Power of Adaptivity in Quantum Query Algorithms.

Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

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

Jamico Schade, Makrand Sinha, Stefan Weltge

Proceedings of the Integer Programming and Combinatorial Optimization, 2024

Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries.

Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

The NISQ Complexity of Collision Finding.

Yassine Hamoudi, Qipeng Liu, Makrand Sinha

Proceedings of the Advances in Cryptology - EUROCRYPT 2024, 2024

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

k-forrelation optimally separates Quantum and classical query complexity.

Nikhil Bansal, Makrand Sinha

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 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

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

2019

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank.

Makrand Sinha, Ronald de Wolf

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Lower Bounds for Interactive Compression and Linear Programs.

Makrand Sinha

PhD thesis, 2018

Lower Bounds for Approximating the Matching Polytope.

Makrand Sinha

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Edge Estimation with Independent Set Oracles.

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

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2016

Fooling Pairs in Randomized Communication Complexity.

Shay Moran, Makrand Sinha, Amir Yehudayoff

Proceedings of the Structural Information and Communication Complexity, 2016

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

Anup Rao, Makrand Sinha

Proceedings of the Approximation, 2016

2015

Simplified Separation of Information and Communication.

Anup Rao, Makrand Sinha

Electron. Colloquium Comput. Complex., 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

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