Worst--Case to Average--Case Reductions for SIS over integers

• URL: http://arxiv.org/abs/2603.07274v1
• Date: Sat, 07 Mar 2026 16:30:15 GMT
• Title: Worst--Case to Average--Case Reductions for SIS over integers
• Abstract summary: We show that an algorithm that solves random instances of this problem with non-negligible probability yields a worst case for any $n-dimensional integer lattice.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In the present paper we study a non-modular variant of the Short Integer Solution problem over the integers. Given a random matrix $A \in \mathbb{Z}^{n\times m}$ with entries $a_{ij}$ such that $0\le a_{ij}< Q,$ for some $Q>0,$ the goal is to find a nonzero vector ${\bf x}\in\mathbb{Z}^m$ such that $A{\bf x}={\bf 0}$ and $\|{\bf x}\|_\infty \le β,$ for a given bound $β.$ We show that an algorithm that solves random instances of this problem with non-negligible probability yields a polynomial-time algorithm for approximating $\mathrm{SIVP}$ within a factor $\widetilde{O}(n^{3/2})$ (with $\ell_2$ norm) in the worst case for any $n-$dimensional integer lattice.

Related papers

• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
  This paper considers the task of linear regression with shuffled labels. $mathbf Y in mathbb Rntimes m, mathbf Pi in mathbb Rntimes p, mathbf B in mathbb Rptimes m$, and $mathbf Win mathbb Rntimes m$, respectively.
  arXiv  Detail & Related papers  (2023-10-02T16:44:47Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Perturbation Analysis of Randomized SVD and its Applications to Statistics [8.731676546744353]
  RSVD is a class of computationally efficient algorithms for computing the truncated SVD of large data matrices.<n>In this paper we derive upper bounds for the $ell$ and $ell_2,infty$ distances between the exact left singular vectors $widehatmathbfU$ of $widehatmathbfM$.<n>We apply our theoretical results to settings where $widehatmathbfM$ is an additive perturbation of some unobserved signal matrix $mathbfM$.
  arXiv  Detail & Related papers  (2022-03-19T07:26:45Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
  arXiv  Detail & Related papers  (2021-09-21T13:19:04Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
  We show that there are no better-than-brute-force algorithms for the problem. We also show the impossibility of better-than-brute-force algorithms when the prediction error is measured.
  arXiv  Detail & Related papers  (2021-06-06T14:19:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.