Statements from FPRD Lab papers

Theorems

Search theorem, lemma, proposition, and corollary statements from FPRD Lab publications. Each entry links to the statement in its complete paper.

61 theorems · 18 lemmas · 19 propositions · 9 corollaries

Search statementsKindPublication

3 of 107 statements

theoremTheorem 1

Retuned direct reduction

For every fixed real number $c$ with $0\le c<1/28$ , there is a deterministic polynomial-time mapping that assigns to each $3$ SAT formula $\varphi$ a nonsingular matrix $B\in\mathbb Z^{n\times n}$ , a target $t\in\mathbb Z^n$ , and a radius $r\in\mathbb Q_{>0}$ such that…

Parameter retuning in the direct reduction for the Euclidean closest vector problem: 1/30-hardness and a 1/28 retained-parameter frontierreleased

propositionProposition 2

Retuned binary soundness

Under the exact conditions above, if equation (10) has a solution $x$ satisfying $\operatorname{wt}(x)\le4M^{2c}R,$ then $\varphi$ is satisfiable.

Parameter retuning in the direct reduction for the Euclidean closest vector problem: 1/30-hardness and a 1/28 retained-parameter frontierreleased

corollaryCorollary 3

Binary nearest codeword and binary syndrome decoding are NP-hard to approximate within $n^{1/15}$ under deterministic polynomial-time many-one reductions.

Parameter retuning in the direct reduction for the Euclidean closest vector problem: 1/30-hardness and a 1/28 retained-parameter frontierreleased