2 citations · 3 across the 2 of their papers we have counts for
13 papers
On the Pseudo-Mixing of Kac's Walk
Natesh S. Pillai, Aaron Smith, Vinod Vaikuntanathan
Motivated by a conjecture of Vaikuntanathan and Zamir, we study the pseudo-mixing of Kac's walk on : whether short trajectories are indistinguishable from Haar meas…
The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan +1
We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA int…
Cloning Games, Black Holes and Cryptography
Alexander Poremba, Seyoon Ragavan, Vinod Vaikuntanathan
In this work, we introduce a new toolkit for analyzing cloning games, a notion that captures stronger and more quantitative versions of the celebrated quantum no-cloning theorem. T…
Average-Case Complexity of Quantum Stabilizer Decoding
Andrey Boris Khesin, Jonathan Z. Lu, Alexander Poremba +2
Random classical linear codes are widely believed to be hard to decode. While slightly sub-exponential time algorithms exist when the coding rate vanishes sufficiently rapidly, all…
Quantum One-Time Programs, Revisited
Aparna Gupte, Jiahui Liu, Justin Raizes +2
One-time programs (Goldwasser, Kalai and Rothblum, CRYPTO 2008) are functions that can be run on any single input of a user's choice, but not on a second input. Classically, they a…
Symmetric Perceptrons, Number Partitioning and Lattices
Neekon Vafa, Vinod Vaikuntanathan
The symmetric binary perceptron () problem with parameter is an average-case search problem defined as follows: given a random G…