Makrand Sinha

Orcid: 0000-0001-5702-2049

According to our database1, Makrand Sinha authored at least 27 papers between 2009 and 2024.

Collaborative distances:

Timeline

2010
2012
2014
2016
2018
2020
2022
2024
0
1
2
3
4
5
6
2
1
2
1
1
2
1
1
1
3
2
3
2
1
1
1
1
1

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
Pseudorandom unitaries with non-adaptive security.
IACR Cryptol. ePrint Arch., 2024

The NISQ Complexity of Collision Finding.
IACR Cryptol. ePrint Arch., 2024

The Power of Adaptivity in Quantum Query Algorithms.
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.
Proceedings of the Integer Programming and Combinatorial Optimization, 2024

Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries.
Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023
Quantum Cryptography in Algorithmica.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Fourier Growth of Communication Protocols for XOR Functions.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022
Quantum-Classical Tradeoffs in the Random Oracle Model.
CoRR, 2022

Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing.
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Smoothed Analysis of the Komlós Conjecture.
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.
Proceedings of the 37th Computational Complexity Conference, 2022

2021
Online Discrepancy Minimization for Stochastic Arrivals.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Majorizing Measures for the Optimizer.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020
Edge Estimation with Independent Set Oracles.
ACM Trans. Algorithms, 2020

$k$-Forrelation Optimally Separates Quantum and Classical Query Complexity.
Electron. Colloquium Comput. Complex., 2020

Online vector balancing and geometric discrepancy.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2018
Lower Bounds for Interactive Compression and Linear Programs.
PhD thesis, 2018

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank.
Electron. Colloquium Comput. Complex., 2018

2017
Lower Bounds for Approximating the Matching Polytope.
Electron. Colloquium Comput. Complex., 2017

2016
A Direct-Sum Theorem for Read-Once Branching Programs.
Proceedings of the Approximation, 2016

2015
Simplified Separation of Information and Communication.
Electron. Colloquium Comput. Complex., 2015

On Parallelizing Streaming Algorithms.
Electron. Colloquium Comput. Complex., 2015

On the communication complexity of greater-than.
Proceedings of the 53rd Annual Allerton Conference on Communication, 2015

2014
Fooling Pairs in Randomized Communication Complexity.
Electron. Colloquium Comput. Complex., 2014

2012
Vertices of degree <i>k</i> in random unlabeled trees.
J. Graph Theory, 2012

Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2009
Vertices of Degree k in Random Unlabeled Trees.
Electron. Notes Discret. Math., 2009


  Loading...