Aug 2026· 3 citations· ⚡ 1 influential· 38 references
Computer ScienceMathematics
Abstract
We prove that, for every constant $\rho>1$, the Euclidean shortest vector problem is NP-hard to approximate within any constant factor $\rho$ under a deterministic polynomial-time many-one reduction. This extends our previous deterministic NP-hardness result from $\rho<\sqrt 2$ to arbitrary constants and gives a deterministic version of Khot's randomized arbitrary-constant theorem.
The usefulness of one-sided-error randomized reductions is demonstrated by showing that they can be conditionally derandomized when the target problem has an OR function, and a general theorem formalizing this derandomization is proved.
For every constant $2<p<\infty$ and every constant \[ 0<\varepsilon<\min\left\{\frac{p-2}{4p},\frac18\right\}, \] we show that the $\ell_p$-shortest vector problem for lattices of rank $M$ is NP hard to approximate within a factor of $M^\varepsilon$, via a deterministic reduction. For $p=\infty$, the same holds for eve...
We prove that exact Euclidean SVP is NP-hard under deterministic polynomial-time many-one reductions for full-rank cyclic integer lattices, equivalently full-rank ideals of $R_N:=\mathbb{Z}[X]/(X^N-1)$ in the coefficient norm. Hardness holds with $N=q-1$ for a varying odd prime $q$. As an application, we prove the same...
We show that approximately counting the vertices of a bounded 0/1 polytope, presented as a system of rational linear inequalities, is, informally speaking, NP-hard. In particular, there is no FPRAS for this problem unless RP=NP. The proof is by a reduction from approximately counting homomorphisms from a given graph to...
We show that Integer Quadratic Programming is W[1]-hard parameterized by the number of variables. Thus, under standard complexity assumptions, Integer Quadratic Programming cannot be solved in f(n)|I|^{O(1)} time for any computable function f where |I| is the size of the encoding and n is the number of variables.
We give the first deterministic polynomial time algorithm that approximates the permanent of arbitrary nonnegative rational matrices within a subexponential factor. For a matrix of order $n$, the approximation factor is \[ \exp\!\left(O\!\left(\frac{n(\log\log n)^2}{\log n}\right)\right)=\exp(o(n)). \] All previously k...
S. Kudria, Jason Luo, Mahbod Majid· 2 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
