50 citations · 56 across the 9 of their papers we have counts for
16 papers
The Power of Adaptivity in Quantum Query Algorithms
Uma Girish, Makrand Sinha, Avishay Tal +1
Motivated by limitations on the depth of near-term quantum devices, we study the depth-computation trade-off in the query model, where the depth corresponds to the number of adapti…
Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack
Jamico Schade, Makrand Sinha, Stefan Weltge
Standard mixed-integer programming formulations for the stable set problem on -node graphs require integer variables. We prove that this is almost optimal: We give a family…
Fourier Growth of Communication Protocols for XOR Functions
Uma Girish, Makrand Sinha, Avishay Tal +1
The level- -Fourier weight of a Boolean function refers to the sum of absolute values of its level- Fourier coefficients. Fourier growth refers to the growth of these…
Quantum Cryptography in Algorithmica
William Kretschmer, Luowen Qian, Makrand Sinha +1
We construct a classical oracle relative to which yet single-copy secure pseudorandom quantum states exist. In the language of Impagliazzo's five worlds,…
The NISQ Complexity of Collision Finding
Yassine Hamoudi, Qipeng Liu, Makrand Sinha
Collision-resistant hashing, a fundamental primitive in modern cryptography, ensures that there is no efficient way to find distinct inputs that produce the same hash value. This p…
Smoothed Analysis of the Komlós Conjecture
Nikhil Bansal, Haotian Jiang, Raghu Meka +2
The well-known Komlós conjecture states that given vectors in with Euclidean norm at most one, there always exists a coloring such that the $\ell_{\infty…