2 citations · 6 across the 11 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…
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…
Asymptotically Good Quantum Codes with Addressable and Transversal Non-Clifford Gates
Zhiyang He, Vinod Vaikuntanathan, Adam Wills +1
Constructing quantum codes with good parameters and useful transversal gates is a central problem in quantum error correction. In this paper, we continue our work in arXiv:2502.018…
Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
Andrej Bogdanov, Alon Rosen, Neekon Vafa +1
Johnson and Lindenstrauss (Contemporary Mathematics, 1984) showed that for , a scaled random projection from to is an approximate…
Quantum Codes with Addressable and Transversal Non-Clifford Gates
Zhiyang He, Vinod Vaikuntanathan, Adam Wills +1
The development of quantum codes with good error correction parameters and useful sets of transversal gates is a problem of major interest in quantum error-correction. Abundant pri…
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 Gau…
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…
Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
Kiril Bangachev, Guy Bresler, Stefan Tiegel +1
We present a polynomial-time reduction from solving noisy linear equations over in dimension with a un…
Oblivious Defense in ML Models: Backdoor Removal without Detection
Shafi Goldwasser, Jonathan Shafer, Neekon Vafa +1
As society grows more reliant on machine learning, ensuring the security of machine learning systems against sophisticated attacks becomes a pressing concern. A recent result of Go…
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…
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…
How to Construct Quantum FHE, Generically
Aparna Gupte, Vinod Vaikuntanathan
We construct a (compact) quantum fully homomorphic encryption (QFHE) scheme starting from (compact) classical fully homomorphic encryption scheme with decryption in $\mathsf{NC}^{1…
Sparse Linear Regression and Lattice Problems
Aparna Gupte, Neekon Vafa, Vinod Vaikuntanathan
Sparse linear regression (SLR) is a well-studied problem in statistics where one is given a design matrix and a response vector for a -sp…