50 citations · 55 across the 6 of their papers we have counts for
4 papers · 1 filter
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…
Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms
Nikhil Bansal, Makrand Sinha, Ronald de Wolf
The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if t…