1 citations · 1 across the 9 of their papers we have counts for
12 papers
Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation
Alexandru Gheorghiu, Aparna Gupte, Vojtěch Havlíček +1
We construct protocols for classically verifiable quantum advantage and classical verification of computations using \emph{quantum indistinguishability obfuscation}…
A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms
Aparna Gupte, Seyoon Ragavan, Mark Zhandry
We establish a no-go theorem for a broad class of quantum algorithms for the dihedral coset problem (DCP). We consider the Fourier-sampling and subset-sum-measurement template prop…
Marton's conjecture in polynomial time
Srinivasan Arunachalam, Arkopal Dutt, Sabee Grewal +1
Gowers, Green, Manners, and Tao (Annals '25) recently resolved Marton's polynomial Freiman-Ruzsa conjecture. We give an algorithmic counterpart to their result: given uniform sampl…
Exponentially Fewer-Server PIR from Sparser -Decoding Polynomials
Aparna Gupte, Seyoon Ragavan
We show that under a plausible number-theoretic conjecture, for any constant there exists an -server private information retrieval (PIR) protocol that on an -bit database…
On Best-Possible One-Time Programs
Aparna Gupte, Jiahui Liu, Luowen Qian +3
One-time programs (OTPs) aim to let a user evaluate a program on a single input while revealing nothing else. Classical OTPs require hardware. Quantum measurement suggests a physic…
Classical Obfuscation of Quantum Circuits via Publicly-Verifiable QFHE
James Bartusek, Aparna Gupte, Saachi Mutreja +1
A classical obfuscator for quantum circuits is a classical program that, given the classical description of a quantum circuit , outputs the classical description of a functional…
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…
SGD and Weight Decay Secretly Minimize the Rank of Your Neural Network
Tomer Galanti, Zachary S. Siegel, Aparna Gupte +1
We investigate the inherent bias of Stochastic Gradient Descent (SGD) toward learning low-rank weight matrices during the training of deep neural networks. Our results demonstrate…
Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures
Aparna Gupte, Neekon Vafa, Vinod Vaikuntanathan
We show direct and conceptually simple reductions between the classical learning with errors (LWE) problem and its continuous analog, CLWE (Bruna, Regev, Song and Tang, STOC 2021).…
The Fine-Grained Hardness of Sparse Linear Regression
Aparna Gupte, Vinod Vaikuntanathan
Sparse linear regression is the well-studied inference problem where one is given a design matrix and a response vector $\mathbf{b} \in \mat…