6 papers
Refuting a Conjecture of Umans and Wang on Arithmetic-Progression Divisor Covers
Xinjie He, Amit Sahai
An \emph{-divisor set} is a finite set of positive integers containing a multiple of every integer from through . Umans and Wang proposed, as the arithmetic-progression v…
List Recovery for Random Low-Rate Linear Codes
Isaac M Hair, Amit Sahai
We prove a list recovery guarantee for random low-rate linear codes over sufficiently large prime fields. For fixed dimension , error fraction , and accuracy parameter $\var…
Public Key Encryption from High-Corruption Constraint Satisfaction Problems
Isaac M Hair, Amit Sahai
We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs), both of whi…
Deterministic Hardness of Approximation For SVP in all Finite Norms
Isaac M Hair, Amit Sahai
We show that, assuming NP DTIME, the shortest vector problem for lattices of rank in any finite norm is hard to…
Quantum Advantage via Solving Multivariate Polynomials
Pierre Briaud, Itai Dinur, Riddhi Ghosal +3
In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case search problem of finding a solution t…
Quantum Advantage via Solving Multivariate Quadratics
Pierre Briaud, Riddhi Ghosal, Aayush Jain +2
In this work, we propose a new way to (non-interactively, verifiably) demonstrate Quantum Advantage by solving the average-case search problem of finding a solution t…