Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations

Guy Bresler; Kiril Bangachev; Stefan Tiegel; Vinod Vaikuntanathan

REVIEW 2 major objections 3 minor 1 cited by

Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations

T0 review · 2 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper presents a polynomial-time reduction that transfers dense LPN/LWE hardness to k-sparse noisy linear equations, preserving sample count up to a 1-o(1) factor and yielding sparse lower bounds that nearly match the trivial…

desk verdict The paper's main reduction hangs on a false uniformity lemma; the idea is fresh and the application is real, but the core distributional claim does not hold as written. read the letter →

arxiv 2411.12512 v1 pith:I4LCLGHG submitted 2024-11-19 cs.CC cs.CRcs.DMmath.STstat.TH

Kiril Bangachev , Guy Bresler , Stefan Tiegel , Vinod Vaikuntanathan This is my paper · ORCID

classification cs.CCcs.CRcs.DMmath.STstat.TH MSC 68Q1768Q2594A60

keywords noisylinearequationslearningparitywithnoiseerrorssparseaverage-casehardnesstensorcompletiongadgetmatrixrandomwalkmixing

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that hardness of the standard, dense versions of LPN and LWE transfers to their $k$-sparse variants with almost no loss, closing a gap that has stood since sparse LPN was introduced. The main reduction maps a dense equation in dimension $\ell = k\log n/\mathsf{poly}(\log k,\log q,\log\log n)$ to a uniformly random $k$-sparse equation in dimension $n$, preserving the number of samples up to a $1-o(1)$ factor and the noise distribution. Assuming dense LWE takes $2^{\Omega(\ell)}$ time, $k$-sparse LWE takes $n^{\Omega(k/(\log k(\log k+\log\log n)))}$ time; assuming dense LPN takes $2^{\Omega(\ell/\log\ell)}$ time, $k$-sparse LPN takes $n^{\Omega(k/(\log k(\log k+\log\log n)^2))}$ time. Both exponents nearly match the brute-force $n^{O(k)}$ algorithms. A corollary gives the first worst-case-lattice-based lower bound for noisy tensor completion, via a direct map from sparse LWE samples to random entries of a noisy low-rank tensor.

What carries the argument

The load-bearing object is the word gadget $G$, whose rows are all vectors $c\,e_i$ for $i\in[h]$ and $c\in\mathbb{Z}/q\mathbb{Z}$, and the sentence gadget $A$ whose rows are all $s$-long concatenations of rows of $G$. A dense vector is split into $s$ words; each word is decoded by sampling uniformly from its preimage under $G$ (a $k$-tuple of rows summing to the word), and the $k$ columns of the resulting $s\times k$ array become the support positions of a $k$-sparse row. Three primitives make this exact: efficient uniform preimage sampling, dynamic-programming computation of preimage sizes, and a pointwise random-walk bound showing all words have nearly equal preimage counts once $k\ge 4h(\log h+\log q+\log(1/\eta))$. The near-equal preimage counts are what guarantee decoded rows are distributed as uniformly random $k$-sparse rows, and full rank of $A$ is what lets the search reduction recover the original secret.

What would settle it

Run the paper's dynamic program for the binary word gadget at small parameters, say $h=10$, $q=2$, $k=60$, and compare $|\mathrm{Preimage}(0)|$ with $|\mathrm{Preimage}(e_1)|$; if the ratio falls outside the promised $1\pm\eta$ interval, the uniformity lemma that carries the reduction is false.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central claim is a reduction: any solver for $k$-sparse noisy linear equations over $\mathbb{Z}/q\mathbb{Z}$ in dimension $n$ yields a solver for the standard dense problem in dimension $\ell = k\log n/\mathsf{poly}(\log q,\log k,\log\log n)$, with the number of samples shrunk only by a $1-o(1)$ factor and the error distribution untouched. The reduction works for decision, search, and strong refutation, for any distribution on the support values, and for moduli from $q=2$ (LPN) up to super-polynomial size. Under the standard conjectures that dense LWE takes $2^{\Omega(\ell)}$ and dense LPN takes $2^{\Omega(\ell/\log\ell)}$, the derived sparse lower bounds are within logarithmic factors of the trivial $n^{O(k)}$ algorithms. In the tensor-completion application, composing the reduction with a sparse-LWE-to-tensor map gives a lower bound for order-$k$, rank-$2^{k-1}$ noisy tensor completion from worst-case lattice hardness.

Load-bearing premise

The reduction outputs truly uniform random $k$-sparse rows only if every possible word has nearly the same number of $k$-tuples that decode to it, a property the paper proves with a pointwise random-walk bound; if the true pointwise mixing time were $O(h^2)$ rather than $O(h\log h)$, the achievable dense dimension would shrink and the near-optimal trade-off would collapse.

Editorial extensions

If this is right

If dense LWE is exponentially hard, $k$-sparse LWE in dimension $n$ requires $n^{\Omega(k/(\log k(\log k+\log\log n)))}$ time for decision, search, and strong refutation; the analogous LPN bound is $n^{\Omega(k/(\log k(\log k+\log\log n)^2))}$ under $2^{\Omega(\ell/\log\ell)}$ dense hardness.
The reduction keeps all but a $1-o(1)$ fraction of samples and leaves the noise distribution unchanged, so the lower bounds hold even when the attacker has arbitrarily many samples, and they extend verbatim to learning with rounding.
Hardness transfers for every support-value distribution and for varying support sizes, so the results cover both standard $k$-LPN and the binary $k$-LWE variant used in the tensor-completion reduction.
Composing with the paper's sparse-LWE-to-tensor map yields a worst-case lattice lower bound for noisy tensor completion: order-$k$, rank-$2^{k-1}$ completion requires $n^{\Omega(k/(\log k(\log k+\log\log n)))}$ time under exponential worst-case lattice hardness.
Applications previously based on $k$-sparse LPN, including DNF learning, agnostic halfspace learning, and linear-stretch pseudorandom generators, can be re-derived from standard dense LPN assumptions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Going beyond the paper, the entropy calculation suggests per-equation gadget decoding has a ceiling of $\ell\le k\log n$; reaching a full $n^{\Omega(k)}$ bound would likely require coordinating the decoding across all samples rather than decoding each equation separately.
In the few-sample regime (below roughly $n^{k/2}$ samples), this reduction still applies, but matching the known refutation algorithms and proof-system lower bounds would need a noise-aware variant that the paper does not construct.
The tensor-completion construction ties the relative noise level to the expected circular distance of the LWE error, so varying the modulus and error distribution should trade tensor rank against tolerable noise—a curve the paper states only implicitly.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: this is an important paper with a broken central lemma. The dense-to-sparse reduction for LWE/LPN is exactly the kind of result the community wants, and the tensor completion application is a genuine new consequence. But the proof of Lemma 2.1 does not survive contact with a concrete example, and everything downstream of it (Theorem 4.2, and hence the main theorem) is unsupported as written.

The word/sentence decomposition is clever, and the pointwise random-walk bound in Lemma 5.6 is plausibly the right technique for the preimage-size uniformity. The paper is honest about what it proves, and the parameter choices are careful. Credit where due: if the sampling lemma were true, the trade-offs would be near-optimal and the applications to DNF learning and homomorphic encryption would follow cleanly.

The problem: Algorithm 2 does not sample uniformly from Preimage_G(F). Claim 5.2 only establishes that each output corresponds to a unique realization of the algorithm's randomness; it never shows all realizations have equal probability. They do not. In Algorithm 2, case 2 samples uniformly from a set of size h + |S_t|(q-1), while case 3 samples from hq; these differ, so different paths receive different weights.

Concretely, take h=2, q=2, k=5, F=(1,1). Let Z1,Z2 be the zero rows and X=(1,0), Y=(0,1). Then O1=(X,Z1,Y,Z2,Z1) is output with probability (1/4)^4*(1/2) = 1/512, while O3=(Z1,Z2,X,Y,Z1), a permutation of the same multiset, is output with probability (1/4)^3*(1/3)*(1/2) = 1/384. Both lie in Preimage_G(F), so a uniform sampler must give equal probabilities. It does not.

This is not a cosmetic gap. Algorithm 4 relies on Lemma 2.1 for its "uniform output" claim, and Algorithm 5 builds on that to produce randomsupport(n,k,D). Without uniform preimage sampling, the sparse instances produced by the reduction are not distributed as the standard sparse LWE/LPN distribution, so the decision/search/refutation reductions do not map one distribution to the other. Theorem 4.2 and the main theorem are therefore unsupported.

Is this repairable? Possibly. One could replace the ad-hoc sampler with a proper conditional sampler using the DP of Algorithm 3, or add a rejection step that reweights by the path probability. But as submitted, the paper needs real work, not copy-editing.

Bottom line: the paper deserves a serious referee because the high-level idea and the application are valuable, and the flaw might be fixable, but I would not accept it in this form.

Referee Report

2 major / 3 minor

Summary. The paper presents a polynomial-time reduction from standard dense noisy linear equations over Z/qZ in dimension ℓ = k log n / poly(log k, log q, log log n) to k-sparse noisy linear equations in dimension n, with the number of samples preserved up to a 1-o(1) factor and the noise distribution preserved. From this it derives near-optimal hardness lower bounds for k-sparse LPN and k-sparse LWE under standard dense hardness assumptions, and it gives a reduction from k-sparse LWE to noisy tensor completion. The proof is built around a gadget matrix and a word/sentence decoding procedure, with Lemmas 2.1–2.3 as the key sampling primitives.

Significance. If correct, this would be a significant and clean result: it nearly closes the gap between dense and sparse noisy linear equations, transfers hardness to applications in learning theory and cryptography, and gives the first hardness evidence for noisy tensor completion based on worst-case lattice assumptions. The paper is constructive, with explicit algorithms and detailed parameter instantiations, and it is unusually versatile (decision/search/refutation, arbitrary support distributions, variable support sizes). The main caveat is that the distributional core of the proof currently rests on a false lemma.

major comments (2)

[§5.2, Lemma 5.8 and Theorem 4.2] Lemma 2.1 is false as stated. Algorithm 2 samples from sets of different sizes in cases 2 and 3, so different preimage tuples receive different probabilities. Claim 5.2 only proves that each output corresponds to a unique random tape, not that the corresponding random outcomes are equally likely. Concretely, take h=2, q=2, k=5, and F=(1,1). The rows of G are the zero rows 1,2, the row (1,0) at index 3, and the row (0,1) at index 4. The tuples (3,1,4,2,1) and (1,2,3,4,1) are both in Preimage_G(F), but the algorithm outputs the first with probability (1/4)^4·(1/2) = 1/512 and the second with probability (1/4)^3·(1/3)·(1/2) = 1/384. Since both are valid preimages, the output distribution of Algorithm 2 is not uniform.
[§5.2, Lemma 5.8 and Theorem 4.2] Because Algorithm 2 is not a uniform preimage sampler, Lemma 5.8(2) and the distributional statement of Theorem 4.2(2) do not follow. In the proof of Lemma 5.8, the factor 1/|Preimage_G(F)| is cancelled after conditioning on F; this step is valid only if Algorithm 2 samples uniformly from the preimage, which the counterexample above disproves. Consequently the output of Algorithm 5 is not shown to be distributed as randomsupport(n,k,D), and the main reduction (Theorem 4.1 and Corollaries 5.13–5.15) currently lacks a valid distributional analysis. The authors would need to replace Algorithm 2 with a genuinely uniform preimage sampler and re-prove Lemma 5.8.

minor comments (3)

[§3.1] The distribution randomsupport(n,k,D) is used in Section 1 but only defined in Section 3.1; please move the definition earlier or add a forward reference at first use.
[§5.1.1, Algorithm 2] The phrase 'indexing one of the zero rows' is ambiguous when q>2, since every block b=0 gives h zero rows; a short comment explaining the index convention (index = b·h + j) would make the algorithm easier to read.
[§4.3] The folklore decision algorithm states a runtime of roughly 2^{O(sqrt(q)·(q n)^{k/2})}, but the exact dependence on q through the number of groups is not made explicit; please state the constant/exponent precisely.

Circularity Check

0 steps flagged · score 0.0 of 10

No load-bearing circularity: the dense-to-sparse reduction is a constructive gadget mapping under external hardness assumptions.

full rationale

The paper's derivation chain is self-contained in the relevant sense. The central reduction is a constructive gadget decoding: a dense vector f is mapped to a k-sparse row e with e^T A = f^T, and Theorem 4.2's correctness is proved from the word-decoding Lemmas 2.1-2.3 and Lemma 5.8, not assumed. The hardness conclusions are explicitly conditional on the external dense LWE/LPN hypotheses (LWE A1-A3, LPN A1-A3), which are not derived inside the paper; the entropy limitation in Section 4.3 is presented as a limitation of the gadget approach, not as an input to the reduction. No parameter is fitted to the target quantity and then renamed a prediction: the preservation of the number of samples and of the noise distribution is argued from the linear algebra of the gadget and from the random-walk preimage-size bound. Author self-citations appear only in background and downstream application sections and are not load-bearing for the main reduction. A caveat outside the circularity criterion: the proof of Lemma 2.1 (Claim 5.2) only establishes uniqueness of the random realization, which does not by itself establish uniformity, and this may be a genuine correctness bug; but a false lemma is not a circular derivation, so it does not affect the circularity score.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The reduction has no fitted parameters: the choices of h (word length), t (number of words), and the rejection probability η=(ht)^{-2} are set analytically to satisfy the stated constraints (Parameter Relation 1), not tuned to any data or to force the target lower bound. The constants are explicit in Observation 6.1 and Section 5.2. The axioms are the external hardness conjectures and standard algorithmic/lattice facts the paper relies on.

assumptions (4)

domain assumption Exponential hardness of standard dense LWE (LWE A1) and near-exponential hardness of standard LPN (LPN A1): no 2^{Ω(ℓ)}-time (LWE) or 2^{Ω(ℓ/log ℓ)}-time (LPN) algorithm exists for decision/search/refutation.
These explicit conjectures, stated in Sections 3.3.1 and 3.4.1, are the external hypotheses from which the sparse lower bounds in Corollaries 6.2 to 6.5 are derived.
standard math Known algorithmic upper bounds: the BKW algorithm solves dense LPN in 2^{O(ℓ/log ℓ)} time, and the fastest known algorithms for dense LWE with polynomial modulus run in 2^{Ω(ℓ)} time.
Used in Sections 3.3.1 and 3.4.1 to calibrate the hardness assumptions and in Section 4.3 to argue the near-tightness of the trade-off.
standard math The Regev (and Peikert) worst-case to average-case reductions from lattice problems such as gapSVP to dense LWE.
Invoked in Sections 3.4.1 and 7.3 to convert LWE hardness into worst-case lattice hardness for the tensor completion lower bound (Theorem 1.2).
standard math Entropy counting bound: a k-sparse vector in n dimensions carries at most log C(n,k) ≤ k log n bits of entropy.
Used in Section 4.3 to show that per-equation decoding can transfer at most k log n bits, placing a fundamental limit on the dense dimension ℓ within this approach.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations." pith.science (2026). https://pith.science/paper/I4LCLGHG

@misc{pith2026241112512,
  author       = {Pith},
  title        = {Pith review of: Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I4LCLGHG}},
  note         = {Machine review of arXiv:2411.12512}
}

abstract

We present a polynomial-time reduction from solving noisy linear equations over $\mathbb{Z}/q\mathbb{Z}$ in dimension $\Theta(k\log n/\mathsf{poly}(\log k,\log q,\log\log n))$ with a uniformly random coefficient matrix to noisy linear equations over $\mathbb{Z}/q\mathbb{Z}$ in dimension $n$ where each row of the coefficient matrix has uniformly random support of size $k$. This allows us to deduce the hardness of sparse problems from their dense counterparts. In particular, we derive hardness results in the following canonical settings. 1) Assuming the $\ell$-dimensional (dense) LWE over a polynomial-size field takes time $2^{\Omega(\ell)}$, $k$-sparse LWE in dimension $n$ takes time $n^{\Omega({k}/{(\log k \cdot (\log k + \log \log n))})}.$ 2) Assuming the $\ell$-dimensional (dense) LPN over $\mathbb{F}_2$ takes time $2^{\Omega(\ell/\log \ell)}$, $k$-sparse LPN in dimension $n$ takes time $n^{\Omega(k/(\log k \cdot (\log k + \log \log n)^2))}~.$ These running time lower bounds are nearly tight as both sparse problems can be solved in time $n^{O(k)},$ given sufficiently many samples. We further give a reduction from $k$-sparse LWE to noisy tensor completion. Concretely, composing the two reductions implies that order-$k$ rank-$2^{k-1}$ noisy tensor completion in $\mathbb{R}^{n^{\otimes k}}$ takes time $n^{\Omega(k/ \log k \cdot (\log k + \log \log n))}$, assuming the exponential hardness of standard worst-case lattice problems.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
math.ST 2025-06 accept novelty 2.0 of 10

A survey of the low-degree polynomial framework for predicting statistical-computational gaps, covering definitions, evidence, connections to other methods, and open problems.

Reference graph

Works this paper leans on

10 extracted references · 3 canonical work pages · cited by 1 Pith paper

[342]

Cryptography from Learning Pa rity with Noise

/i.sc/s.sc/b.sc/n.sc: 9781605585062. /d.sc/o.sc/i.sc: 10.1145/1536414.1536461 (cit. on pp. 5, 18, 20). [Pei16] Chris Peikert. A Decade of La/t_tice Cryptography. 2016. /d.sc/o.sc/i.sc: 10.1561/0400000074 (cit. on pp. 17, 18). [Pie12] Krzysztof Pietrzak. “Cryptography from Learning Pa rity with Noise”. In: SOFSEM 2012: /T_he- ory and Practice of Computer S...

arXiv 2016
[1002]

Continuous LWE is as Hard as LWE and Applications to Learning Gaussian Mixtures

/i.sc/s.sc/b.sc/n.sc: 9781450355599. /d.sc/o.sc/i.sc: 10.1145/3188745.3188962 (cit. on p. 22). [GVV22] Aparna Gupte, Neekon Vafa, and Vinod Vaikuntanatha n. “Continuous LWE is as Hard as LWE and Applications to Learning Gaussian Mixtures”. In:2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). 2022, pp. 1162–1173./d.sc/o.sc/i.sc: 10...

arXiv 2008
[1075]

A Time-Space Lower Bound for a Large Class of Lea rning Problems

/d.sc/o.sc/i.sc: 10.5555/1873601.1873687 (cit. on p. 9). [Raz17] Ran Raz. “A Time-Space Lower Bound for a Large Class of Lea rning Problems”. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FO CS). 2017, pp. 732–742. /d.sc/o.sc/i.sc: 10.1109/FOCS.2017.73 (cit. on p. 22). [Reg09] Oded Regev. “On la/t_tices, learning with errors, ran...

work page arXiv 1987
[1566]

Hardness of SIS a nd LWE with Small Parameters

/u.sc/r.sc/l.sc: https://proceedings.mlr.press/v65/moshkovitz17a.html (cit. on p. 22). [MP13] Daniele Micciancio and Chris Peikert. “Hardness of SIS a nd LWE with Small Parameters”. In: Advances in Cryptology – CRYPTO 2013 . Ed. by Ran Cane/t_ti and Juan A. Garay. Berlin, Hei- delberg: Springer Berlin Heidelberg, 2013, pp. 21–39. /i.sc/s.sc/b.sc/n.sc: 978...

arXiv 2006
[2002]

An improved algorithm for learning sparse parities in the presence of noise

Ed. by Moti Yung. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002, pp. 288–304. /i.sc/s.sc/b.sc/n.sc: 978-3-540-45708-4. /d.sc/o.sc/i.sc: 10.1007/3-540-45708-919 (cit. on p. 18). [YYL+21] Di Yan, Yu Yu, Hanlin Liu, Shuoyao Zhao, and Jiang Zhang. “An improved algorithm for learning sparse parities in the presence of noise”. In: /T_heoretical Computer ...

work page doi:10.1007/3-540-45708-919 2021
[2012]

From local pseudorandom gener ators to hardness of learning

Ed. by Xiaoyun Wang and Kazue Sako. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 485–503. /i.sc/s.sc/b.sc/n.sc: 978-3-642-34961-4. /d.sc/o.sc/i.sc: 10.1007/978-3-642-34961-430 (cit. on p. 3). [DMW23] Abhishek Dhawan, Cheng Mao, and Alexander S. Wein. Detection of Dense Subhypergraphs by Low-Degree Polynomials. 2023. arXiv: 2304.08135 [cs.DS] ...

arXiv 2019
[2014]

Public-key cryptosystems from the w orst-case shortest vector problem: ex- tended abstract

/d.sc/o.sc/i.sc: 10.1017/CBO9781139814782 (cit. on p. 63). [Pei09] Chris Peikert. “Public-key cryptosystems from the w orst-case shortest vector problem: ex- tended abstract”. In: Proceedings of the Forty-First Annual ACM Symposium on /T_heoryof Com- puting. STOC ’09. Bethesda, MD, USA: Association for Computing Machinery, 2009, pp. 333–

doi:10.1017/cbo9781139814782
[2020]

Mult i-party Homomorphic Secret Sharing and Sublinear MPC from Sparse LPN

Ed. by Anne Canteaut and Yuval Ishai. Cham: Springer Internati onal Publishing, 2020, pp. 768–797. /i.sc/s.sc/b.sc/n.sc: 978-3-030-45724-2. /d.sc/o.sc/i.sc: 10.1007/978-3-030-45724-226 (cit. on p. 16). [DIJ+23] /Q_uang Dao, Yuval Ishai, Aayush Jain, and Huijia Lin. “Mult i-party Homomorphic Secret Sharing and Sublinear MPC from Sparse LPN”. In: Advances i...

work page arXiv 2022

Show all 10 references

[2021]

Algorithms and certiﬁcates for Boolean CSP refutation: smoothed is no harder than random

/d.sc/o.sc/i.sc: 10.4230/LIPIcs.APPROX/RANDOM.2021.60 (cit. on p. 22). [GKM22] Venkatesan Guruswami, Pravesh K. Kothari, and Pete r Manohar. “Algorithms and certiﬁcates for Boolean CSP refutation: smoothed is no harder than random”. In: Proceedings of the 54th Annual ACM SIGAC...

2001
[2023]

arXiv: 2311.00289 [math.ST] (cit. on p. 64). 60 [ODo14] Ryan O’Donnell. Analysis of Boolean Functions . Cambridge : Cambridge University Press

arXiv

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [342]

Cryptography from Learning Pa rity with Noise

/i.sc/s.sc/b.sc/n.sc: 9781605585062. /d.sc/o.sc/i.sc: 10.1145/1536414.1536461 (cit. on pp. 5, 18, 20). [Pei16] Chris Peikert. A Decade of La/t_tice Cryptography. 2016. /d.sc/o.sc/i.sc: 10.1561/0400000074 (cit. on pp. 17, 18). [Pie12] Krzysztof Pietrzak. “Cryptography from Learning Pa rity with Noise”. In: SOFSEM 2012: /T_he- ory and Practice of Computer S...

arXiv 2016

[2] [1002]

Continuous LWE is as Hard as LWE and Applications to Learning Gaussian Mixtures

/i.sc/s.sc/b.sc/n.sc: 9781450355599. /d.sc/o.sc/i.sc: 10.1145/3188745.3188962 (cit. on p. 22). [GVV22] Aparna Gupte, Neekon Vafa, and Vinod Vaikuntanatha n. “Continuous LWE is as Hard as LWE and Applications to Learning Gaussian Mixtures”. In:2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). 2022, pp. 1162–1173./d.sc/o.sc/i.sc: 10...

arXiv 2008

[3] [1075]

A Time-Space Lower Bound for a Large Class of Lea rning Problems

/d.sc/o.sc/i.sc: 10.5555/1873601.1873687 (cit. on p. 9). [Raz17] Ran Raz. “A Time-Space Lower Bound for a Large Class of Lea rning Problems”. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FO CS). 2017, pp. 732–742. /d.sc/o.sc/i.sc: 10.1109/FOCS.2017.73 (cit. on p. 22). [Reg09] Oded Regev. “On la/t_tices, learning with errors, ran...

work page arXiv 1987

[4] [1566]

Hardness of SIS a nd LWE with Small Parameters

/u.sc/r.sc/l.sc: https://proceedings.mlr.press/v65/moshkovitz17a.html (cit. on p. 22). [MP13] Daniele Micciancio and Chris Peikert. “Hardness of SIS a nd LWE with Small Parameters”. In: Advances in Cryptology – CRYPTO 2013 . Ed. by Ran Cane/t_ti and Juan A. Garay. Berlin, Hei- delberg: Springer Berlin Heidelberg, 2013, pp. 21–39. /i.sc/s.sc/b.sc/n.sc: 978...

arXiv 2006

[5] [2002]

An improved algorithm for learning sparse parities in the presence of noise

Ed. by Moti Yung. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002, pp. 288–304. /i.sc/s.sc/b.sc/n.sc: 978-3-540-45708-4. /d.sc/o.sc/i.sc: 10.1007/3-540-45708-919 (cit. on p. 18). [YYL+21] Di Yan, Yu Yu, Hanlin Liu, Shuoyao Zhao, and Jiang Zhang. “An improved algorithm for learning sparse parities in the presence of noise”. In: /T_heoretical Computer ...

work page doi:10.1007/3-540-45708-919 2021

[6] [2012]

From local pseudorandom gener ators to hardness of learning

Ed. by Xiaoyun Wang and Kazue Sako. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 485–503. /i.sc/s.sc/b.sc/n.sc: 978-3-642-34961-4. /d.sc/o.sc/i.sc: 10.1007/978-3-642-34961-430 (cit. on p. 3). [DMW23] Abhishek Dhawan, Cheng Mao, and Alexander S. Wein. Detection of Dense Subhypergraphs by Low-Degree Polynomials. 2023. arXiv: 2304.08135 [cs.DS] ...

arXiv 2019

[7] [2014]

Public-key cryptosystems from the w orst-case shortest vector problem: ex- tended abstract

/d.sc/o.sc/i.sc: 10.1017/CBO9781139814782 (cit. on p. 63). [Pei09] Chris Peikert. “Public-key cryptosystems from the w orst-case shortest vector problem: ex- tended abstract”. In: Proceedings of the Forty-First Annual ACM Symposium on /T_heoryof Com- puting. STOC ’09. Bethesda, MD, USA: Association for Computing Machinery, 2009, pp. 333–

doi:10.1017/cbo9781139814782

[8] [2020]

Mult i-party Homomorphic Secret Sharing and Sublinear MPC from Sparse LPN

Ed. by Anne Canteaut and Yuval Ishai. Cham: Springer Internati onal Publishing, 2020, pp. 768–797. /i.sc/s.sc/b.sc/n.sc: 978-3-030-45724-2. /d.sc/o.sc/i.sc: 10.1007/978-3-030-45724-226 (cit. on p. 16). [DIJ+23] /Q_uang Dao, Yuval Ishai, Aayush Jain, and Huijia Lin. “Mult i-party Homomorphic Secret Sharing and Sublinear MPC from Sparse LPN”. In: Advances i...

work page arXiv 2022