11 papers
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…
SVP is Deterministically NP-Hard for all , Even to Approximate Within a Factor of
Isaac M. Hair, Amit Sahai
We prove that SVP is NP-hard to approximate within a factor of , for all constants and , under standard deterministic Kar…
A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation
Timothy M. Chan, Isaac M. Hair
Given two convex polygons and with and edges, the maximum overlap problem is to find a translation of that maximizes the area of its intersection with . We g…
Convex Polygon Containment: Improving Quadratic to Near Linear Time
Timothy M. Chan, Isaac M. Hair
We revisit a standard polygon containment problem: given a convex -gon and a convex -gon in the plane, find a placement of inside under translation and rotati…