8 papers · 1 filter
Shaving Two Logs for Discrete and Continuous Fréchet Distance
Timothy M Chan, Isaac M Hair
We revisit the classical computational geometry problem of computing the exact (discrete or continuous) Fréchet distance between two given polygonal curves with vertices in a c…
Witness Encryption via Prime-Order Generic Groups
Isaac M Hair, Amit Sahai
For every constant , we unconditionally construct witness encryption for NP in the classical generic cyclic group model with the following properties. For SAT instances of s…
Polynomial-Factor Deterministic NP-Hardness for SVP in Every lp Norm with p > 2
Isaac M Hair, Amit Sahai
For every constant and every constant \[ 0<\varepsilon< \min\left\{\frac{p-2}{4p},\frac18\right\}, \] we show that the -shortest vector problem for lattices of…
Bellman-Ford in Almost-Linear Time
Isaac M. Hair, George Z. Li, Jason Li +1
We consider the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights and solve this problem in time.
Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths
Isaac M. Hair, George Z. Li, Jason Li +1
We revisit the single-source shortest paths (SSSP) problem on directed graphs with nonnegative real weights and give a deterministic parallel algorithm with $O(n^{1+o(1)}t^2 + m^{1…
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 $\vare…
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 ap…