BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Given a non-empty genus in n dimensions with determinant d, we give a randomized algorithm that outputs a quadratic form from this genus. The time complexity of the algorithm is poly(n,logd); assuming Generalized Riemann Hypothesis (GRH).
An n-ary integral quadratic form is a formal expression Q(x1,..,xn)=∑1≤i,j≤naijxixj in n-variables x1,...,xn, where aij=aji∈Z. We present a randomized polynomial time algorithm that given a quadratic form Q(x1,...,xn), a prime p, and a positive integer k outputs a U∈GLn(Z/pkZ) such that U transforms Q to its p-adic canonical form.
An n-ary integral quadratic form is a formal expression Q(x1,...,xn)=∑1≤i,j≤naijxixj in n-variables x1,...,xn, where aij=aji∈Z. We present a poly(n,k,logp,logt) randomized algorithm that given a quadratic form Q(x1,...,xn), a prime p, a positive integer k and an integer t, samples a uniform solution of Q(x1,...,xn)≡tmodpk.
We give a polynomial time Turing reduction from the γ2n-approximate closest vector problem on a lattice of dimension n to a γ-approximate oracle for the shortest vector problem. This is an improvement over a reduction by Kannan, which achieved γ2n3/2.
We give several improvements on the known hardness of the unique shortest vector problem. - We give a deterministic reduction from the shortest vector problem to the unique shortest vector problem. As a byproduct, we get deterministic NP-hardness for unique shortest vector problem in the ℓ∞ norm. - We give a randomized reduction from SAT to uSVP_{1+1/poly(n)}. This shows that uSVP_{1+1/poly(n)} is NP-hard under randomized reductions. - We show that if GapSVP_γ\in coNP (or coAM) then uSVP_{\sqrtγ} \in coNP (coAM respectively). This simplifies previously known uSVP_{n^{1/4}} \in coAM proof by Cai \cite{Cai98} to uSVP_{(n/\log n)^{1/4}} \in coAM, and additionally generalizes it to uSVP_{n^{1/4}} \in coNP. - We give a deterministic reduction from search-uSVP_γto the decision-uSVP_{γ/2}. We also show that the decision-uSVP is {\bf NP}-hard for randomized reductions, which does not follow from Kumar-Sivakumar \cite{KS01}.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.