I. M. Hair

activity

20242026

collaborators

Showing 2025Show all

2 papers · 1 filter

cs.CC2025

SVP $_{p}$ is Deterministically NP-Hard for all $p > 2$ , Even to Approximate Within a Factor of $2^{l o g^{1 - ε} n}$

Isaac M. Hair, Amit Sahai

We prove that SVP $_{p}$ is NP-hard to approximate within a factor of $2^{l o g^{1 - ε} n}$ , for all constants $ε > 0$ and $p > 2$ , under standard deterministic Kar…

cs.CG2025

A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation

Timothy M. Chan, Isaac M. Hair

Given two convex polygons $P$ and $Q$ with $n$ and $m$ edges, the maximum overlap problem is to find a translation of $P$ that maximizes the area of its intersection with $Q$ . We g…

SVPp​ is Deterministically NP-Hard for all p>2, Even to Approximate Within a Factor of 2log1−εn

A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation

SVP $_{p}$ is Deterministically NP-Hard for all $p > 2$ , Even to Approximate Within a Factor of $2^{l o g^{1 - ε} n}$