BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Chandan Dubey appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
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.
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,\log d)$; assuming Generalized Riemann Hypothesis (GRH).
An $n$-ary integral quadratic form is a formal expression $Q(x_1,..,x_n)=\sum_{1\leq i,j\leq n}a_{ij}x_ix_j$ in $n$-variables $x_1,...,x_n$, where $a_{ij}=a_{ji} \in \mathbb{Z}$. We present a randomized polynomial time algorithm that given a quadratic form $Q(x_1,...,x_n)$, a prime $p$, and a positive integer $k$ outputs a $\mathtt{U} \in \text{GL}_n(\mathbb{Z}/p^k\mathbb{Z})$ such that $\mathtt{U}$ transforms $Q$ to its $p$-adic canonical form.
An $n$-ary integral quadratic form is a formal expression $Q(x_1,...,x_n)=\sum_{1\leq i,j\leq n}a_{ij}x_ix_j$ in $n$-variables $x_1,...,x_n$, where $a_{ij}=a_{ji} \in \mathbb{Z}$. We present a poly$(n,k, \log p, \log t)$ randomized algorithm that given a quadratic form $Q(x_1,...,x_n)$, a prime $p$, a positive integer $k$ and an integer $t$, samples a uniform solution of $Q(x_1,...,x_n)\equiv t \bmod{p^k}$.
We give a polynomial time Turing reduction from the $γ^2\sqrt{n}$-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 $γ^2n^{3/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 $\ell_\infty$ 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}.