BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Chandan Dubey contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph 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}.