Pith. sign in

REVIEW 1 major objections 4 minor 3 cited by

Symmetric Perceptrons, Number Partitioning and Lattices

T0 review · 1 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read This paper proves that, assuming worst-case lattice problems are hard, the symmetric binary perceptron and random number partitioning have no polynomial-time algorithms at the conjectured parameter ranges.

desk verdict The main SBP and NPP hardness theorems are credible and mostly check out, but the near-optimal SBP claim in Remark 1 has a real parameter bug that makes its proof fail as written; it needs a fix before the paper is accepted. read the letter →

arxiv 2501.16517 v2 pith:5VRBQ7PT submitted 2025-01-27 math.ST cs.CCmath-phmath.MPmath.PRstat.TH

Neekon Vafa , Vinod Vaikuntanathan This is my paper · ORCID
classification math.STcs.CCmath-phmath.MPmath.PRstat.TH MSC 68Q1711H0668Q25
keywords symmetricbinaryperceptronnumberpartitioningaverage-casehardnessworst-casetoreductionslatticeproblemsGaussiansmoothingChineseremaindertheoremKarmarkar–Karpalgorithm
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

This paper tries to prove that two average-case search problems—the symmetric binary perceptron (find a $\{\pm1\}$ vector whose product with a random Gaussian matrix has small $\ell_\infty$ norm) and random number partitioning (split random numbers into two groups with sums as close as possible)—are computationally hard, conditional on the worst-case hardness of standard lattice problems. If the paper is right, it confirms up to lower-order terms the conjecture that the best known polynomial-time perceptron guarantee, $\kappa(x)=\Theta(1/\sqrt{x})$, cannot be pushed substantially further, and it shows that the classical Karmarkar–Karp differencing algorithm for number partitioning is nearly optimal. The proof works by smoothing: Gaussian noise turns a worst-case lattice basis into a nearly uniform random instance, and any solver for the random instance is then lifted back to a short lattice vector. The relevance is that these problems exhibit a wide statistical-computational gap, and this gives a worst-case-to-average-case explanation of that gap.

What carries the argument

The carrying mechanism is Gaussian smoothing: for an $n$-dimensional lattice $\Lambda$, if a Gaussian's width exceeds the smoothing parameter $\eta_\varepsilon(\Lambda)$, its reduction modulo $\Lambda$ is statistically close to uniform. The reductions sample $\mathbf{U}$ from a Gaussian of width $\sigma_1 = r/(4m)$, add uniform lattice vectors $\mathbf{V}$, and form $\tilde{\mathbf{A}} = \mathbf{S}^{-1}(\mathbf{V}+\mathbf{U}) \bmod \mathbb{Z}^n$, which is nearly uniform on $[0,1)^{n\times m}$ while encoding the worst-case basis. A solution $\mathbf{A}\mathbf{x}+\mathbf{e}=\mathbf{0}$ with $\|\mathbf{e}\|_\infty \le \kappa(m/n)\sqrt{m}$ is scaled up and lifted to $\mathbf{s}=x_1(\mathbf{U}\mathbf{x}+\mathbf{S}\mathbf{e}')\in \Lambda(\mathbf{B})$ with $\|\mathbf{s}-\mathbf{t}\|_2 \le r + \|\mathbf{S}\|/8$, exactly the IncGDD guarantee. For number partitioning, a normalized Chinese-remainder isomorphism $\tilde\varphi:\bigoplus_i (1/p_i)\mathbb{Z}/p_i\mathbb{Z}\to (1/q)\mathbb{Z}/q\mathbb{Z}$ with $q=\prod_i p_i$ converts the vector congruence into a scalar inner product $\mathbf{a}^\top\mathbf{x}$; choosing $p_i\ge 32nm$ and bounding the accumulated error by $2m/q$ prevents wraparound when inverting $\tilde\varphi$.

What would settle it

The reduction is constructive, so a direct test is possible: take a family of worst-case lattice bases with known geometry, run the smoothing construction to produce random SBP or NPP instances, and apply a candidate polynomial-time solver. If the solver succeeds with non-negligible probability on instances generated from every basis, the reconstruction step outputs a lattice point within distance $r+\|\mathbf{S}\|/8$ of the target, solving IncGDD$_\gamma$ and hence SIVP/GapCRP/GDD; exhibiting such a solver on the constructed distribution would refute Assumptions 1 and 2. A simpler falsifier is a polynomial-time algorithm achieving $\kappa(m)=2^{-\omega(\log^2 m)}$ on random number-partitioning instances, which would improve on Karmarkar–Karp and contradict the NPP corollary.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes two conditional average-case hardness theorems. Theorem 3 reduces the worst-case lattice problem IncGDD (incremental guaranteed distance decoding: given a lattice basis, $n$ short independent lattice vectors, a target, and a radius, find a lattice point within $r+\|\mathbf{S}\|/8$ of the target) with approximation factor $\gamma(n)=n^{O(1/\varepsilon)}$ to SBP with $\kappa(x)=1/x^{1/2+\varepsilon}$. Since the worst-case problems GDD (guaranteed distance decoding), SIVP (shortest independent vectors), and GapCRP (gap covering radius) all reduce to IncGDD, Corollary 2 follows: under Assumption 1 (polynomial hardness of those problems), no polynomial-time algorithm solves average-case SBP at that $\kappa$; under the stronger subexponential Assumption 2, a variant yields hardness for $\kappa(x)=1/(\sqrt{x}\,\log^c x)$ for a sufficiently large constant $c$. Theorem 4 performs the same reduction in dimension $n=\Omega((\log m)^{1+\varepsilon})$ to NPP at $\kappa(m)=2^{-\log^{2+\varepsilon} m}$, and composing with Assumption 2 gives Corollary 3: no polynomial-time algorithm solves NPP at $\kappa(m)=2^{-\log^{3+\varepsilon} m}$. The paper therefore claims to prove the GKPX22 conjecture up to lower-order terms and to show that the Karmarkar–Karp differencing algorithm is nearly tight, all conditional on worst-case lattice hardness.

Load-bearing premise

The load-bearing premise is that approximate worst-case lattice problems (SIVP, GapCRP, GDD) are genuinely hard—in the strong versions, require $2^{\omega(n^{1/2-\varepsilon})}$ time even with approximation factor $2^{n^{1/2-\varepsilon}}$—so any future improvement in lattice reduction beyond the known time-versus-approximation tradeoff would weaken or invalidate the hardness conclusions.

Editorial extensions

If this is right

  • If any of the worst-case lattice problems SIVP, GapCRP, or GDD with $\gamma(n)=n^{O(1/\varepsilon)}$ requires super-polynomial time, then no polynomial-time algorithm solves average-case SBP with $\kappa(x)=1/x^{1/2+\varepsilon}$, even with inverse-polynomial success probability.
  • If Assumption 2 holds, then no polynomial-time algorithm solves SBP with $\kappa(x)=1/(\sqrt{x}\log^c x)$ for a sufficiently large constant $c$, and none solves NPP with $\kappa(m)=2^{-\log^{3+\varepsilon} m}$.
  • The Karmarkar–Karp guarantee $2^{-O(\log^2 m)}$ for number partitioning is optimal up to one logarithmic factor in the exponent, and the GKPX22 conjecture for the perceptron is confirmed up to lower-order terms.
  • The hardness statement is robust: it survives under uniform $[0,1]$ input distributions, under weaker solution requirements $\mathbf{x}\in\{-1,0,1\}^m\setminus\{\mathbf{0}\}$, and when the solver need only succeed with non-negligible probability.

Reading between the lines

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

  • Beyond the paper: if the requirement $m\gg n^{\Theta(1/\varepsilon)}$ could be relaxed to $m=\Theta(n)$, the proof would directly abut the statistical threshold $\kappa_{\mathrm{stat}}(x)=2^{-\Theta(x)}$ and would determine whether the computational-statistical gap persists at constant aspect ratio; the current reduction breaks in that regime.
  • Beyond the paper: the smoothing-to-average-case template may transfer to the asymmetric binary perceptron, since the difficulty there is again finding a sign vector with small linear image; the authors explicitly leave this as an open question.
  • Beyond the paper: the CRT embedding suggests that other scalar-output average-case problems, such as random subset-sum or one-dimensional SIS with a composite modulus, could inherit near-tight worst-case lattice hardness from the same no-wraparound argument.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 4 minor

Summary. The paper proves conditional average-case hardness for the symmetric binary perceptron (SBP) and the number partitioning problem (NPP), via worst-case to average-case reductions from lattice problems (IncGDD, and hence SIVP, GapCRP, and GDD) using Gaussian smoothing in the style of Micciancio-Regev. Theorem 3 gives a polynomial-time reduction to SBP with κ(x)=1/x^{1/2+ε} under polynomial lattice hardness assumptions; Theorem 4 gives a poly(m)-time reduction to NPP with κ(m)=2^{-log^{2+ε} m} under subexponential lattice hardness assumptions. The paper also claims, in Remark 1, a near-optimal SBP hardness statement with κ(x)=1/(√x log^{1+c} x) for c>3 under Assumption 2. Corollaries are drawn for the original GKPX22 conjecture and for near-tightness of the Karmarkar-Karp algorithm.

Significance. If the results hold, they resolve (up to lower-order terms) the conjecture of Gamarnik, Kızıldağ, Perkins and Xu that the Bansal-Spencer guarantee κ=Θ(1/√x) is the best achievable by efficient algorithms, and they show that Karmarkar-Karp's 2^{-O(log^2 m)} guarantee is nearly optimal for NPP. The reductions are carefully structured, follow the Micciancio-Regev framework, and are versatile with respect to the input distribution and the solution set. The NPP reduction's use of the Chinese remainder theorem to compress n-dimensional lattice information into a one-dimensional NPP instance is elegant. The main theorems are stated with explicit parameters, and the polynomial-hardness SBP result and the NPP result are essentially sound. The near-optimal SBP claim in Remark 1, however, is not supported by the written proof, as detailed below.

major comments (1)
  1. [§3.1, Remark 1] The near-optimal SBP claim is not established by the written proof. In the proof of Theorem 3, Proposition 1 and the invocation of Lemma 8 give a total statistical distance of O(m e^{-ln^2 n}) between the matrix fed to the SBP oracle and the Gaussian ensemble N(0,1)^{n×m}. This is negligible in the main body of Theorem 3 because there m=n^{Θ(1/ε)} is polynomial in n. Remark 1, however, sets m=2^{O(n^{3/(2c)})}. For any fixed c>3, this m is super-polynomial in n and, since n^{3/(2c)} grows faster than ln^2 n, the product m e^{-ln^2 n}=exp(Θ(n^{3/(2c)})-Θ(ln^2 n)) diverges. Hence the reduction does not produce an input statistically close to the Gaussian distribution on which the SBP solver is assumed to succeed, and the claimed hardness for κ(x)=1/(√x log^{1+c} x) does not follow as written. A likely repair is to base the smoothing parameter and error on m rather than n: set σ2=ln m, γ=4m ln m, and use smoothing error e^{-ln^2 m}; then the total error becomes m e^{-ln^2 m}=negl(m), the approximation factor remains 2^{O(n^{3/(2c)})}, and the norm bound becomes (ln m)^c ≥ 8n^{3/2}, which is consistent with m=2^{O(n^{3/(2c)})}. The authors should either incorporate this parameter change or restrict the near-optimal claim accordingly.
minor comments (4)
  1. [§3.1, Theorem 3 proof] The displayed statistical closeness bound for W states Δ(W, N(0, σ2^2/2)^{n×m}) ≤ ..., but Lemma 8 gives variance σ^2 for D_{Z^n+v, σ√(2π)}, so the correct covariance is σ2^2 I_n per column, not σ2^2/2. With the printed covariance, A=W/σ2 would be close to N(0,1/2), not N(0,1). This is a typo, but it should be corrected since the subsequent scaling argument relies on the σ2^2 variance.
  2. [§4, Theorem 4 proof] The sentence 'By closure, we know e'' ∈ 1/q·Z/qZ' is imprecise, because f is sampled continuously from [0,1/q)^m, so e''=f^T x+e' is not automatically in the discrete set 1/q·Z/qZ. The intended argument is that e'' is small and satisfies e'' ≡ -φ(⌊A⌋_p x) (mod 1), which forces equality with the unique small representative in 1/q·Z/qZ. This should be stated explicitly.
  3. [§4, Corollary 3] The passage from hardness for κ(m)=2^{-log^{2+ε} m} to hardness for κ(m)=2^{-log^{3+ε} m} for arbitrary ε>0 requires instantiating Theorem 4 with parameter 1+ε rather than with the same ε. With the same ε and ε<1, the resulting lattice algorithm runs in time 2^{O(n^{1/(1+ε)})}, which is not ruled out by Assumption 2. The text should spell out this parameter shift.
  4. [§4, proof of Lemma 14] The lower bound on the number of primes in [N,10N] is derived as π(10N)-π(N) > 4N/ln N - 2N/ln N = 2N/ln N, which is indeed at least N/ln N. The text says only that π(10N)>4N/ln N and then 'by taking the difference'; adding the explicit subtraction would avoid confusion.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the central worst-case-to-average-case reductions rest on external lattice machinery; self-citations appear only in supporting or alternative arguments.

full rationale

The paper's main theorems (Theorems 3 and 4) reduce worst-case IncGDD instances to average-case SBP and NPP by Gaussian smoothing, following the external framework of Micciancio and Regev [MR07]. The load-bearing ingredients in the proof are: Corollary 1 and Lemmas 6-7 from [MR07] (smoothing and statistical closeness), Lemma 8 whose proof invokes [MR07, Lemma 4.4] alongside [GVV22, Lemma 17], the spectral and chi-square tail bounds of [RV10] and [LM00], uniform lattice-vector sampling from [Mic04], and the prime number theorem in Lemma 14. None of these assume the hardness of SBP or NPP. The self-citations [GVV22] (in the proof sketch of Lemma 8) and [BV15] (in the alternative 1D-SIS discussion in Section 1.1.3) are supporting technical references rather than premises that define the target result; the main reduction does not reduce to a self-citation chain. There is no fitting of parameters to data, no quantity defined in terms of the quantity it is claimed to predict, and no uniqueness theorem imported from the authors' prior work to force the chosen reduction. The near-optimal SBP parameterization in Remark 1 may have a non-negligible statistical-closeness issue when m=2^{O(n^{3/(2c)})}, since Proposition 1's bound m e^{-ln^2 n} is not negligible for that m; however, that is a potential correctness or parameterization gap in the written proof, not a circularity, because the claimed hardness would still not be equivalent by construction to the assumption. Overall, the derivation chain is self-contained against independent prior work, so the circularity score is low.

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

The reductions are self-contained except for standard lattice-technical lemmas and the explicitly stated worst-case lattice hardness assumptions. No data are fitted and no new entities are postulated.

assumptions (8)
  • standard math Reductions from SIVP_gamma, GapCRP_gamma, and GDD_gamma to IncGDD_gamma exist (MR07 Lemmas 3-5).
    Invoked in Corollaries 2 and 3; these are prior results not reproven in the paper.
  • standard math Gaussian smoothing lemmas: for scale at least the smoothing parameter, Gaussian mod lattice is close to uniform; smoothing parameter bound in terms of lambda_n (MR07 Lemmas 6-7, Corollary 1).
    Used in Propositions 1 and 2 to turn a worst-case lattice basis into a statistically uniform matrix.
  • standard math Lemma 8: discrete Gaussian sampling from Z^n+v with scale sigma sqrt(2 pi) is close to a continuous Gaussian; proof is sketched via GVV22 Lemma 17 and MR07 Lemma 4.4.
    Load-bearing for converting the uniform matrix into a Gaussian SBP or NPP input; the paper provides only a proof sketch.
  • standard math Efficient uniform sampling from the quotient lattice L(B)/L(S) via [Mic04, Proposition 2.9].
    Used to sample V in Propositions 1 and 2; the paper cites this standard result without proof.
  • domain assumption Assumption 1: polynomial-factor approximate SIVP/GapCRP/GDD require super-polynomial time.
    Section 2.2; basis for the SBP polynomial-hardness result in Corollary 2.
  • domain assumption Assumption 2: subexponential hardness of approximate SIVP/GapCRP/GDD with gamma(n)=2^{n^{1/2-eps}} in time 2^{omega(n^{1/2-eps})}.
    Section 2.2; basis for the near-optimal SBP result and the NPP result in Corollaries 2 and 3.
  • standard math Prime number theorem density bound (Lemma 14) and CRT representation with no wraparound (Lemmas 11-13).
    Used in the NPP reduction to compress matrix rows into a single scalar via CRT.
  • standard math Random matrix spectral norm bound (RV10, Lemma 9) and chi-square tail bound (LM00, Lemma 10).
    Used for norm estimates in both reductions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Symmetric Perceptrons, Number Partitioning and Lattices." pith.science (2026). https://pith.science/paper/5VRBQ7PT

@misc{pith2026250116517,
  author       = {Pith},
  title        = {Pith review of: Symmetric Perceptrons, Number Partitioning and Lattices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5VRBQ7PT}},
  note         = {Machine review of arXiv:2501.16517}
}
abstract

The symmetric binary perceptron ($\mathrm{SBP}_{\kappa}$) problem with parameter $\kappa : \mathbb{R}_{\geq1} \to [0,1]$ is an average-case search problem defined as follows: given a random Gaussian matrix $\mathbf{A} \sim \mathcal{N}(0,1)^{n \times m}$ as input where $m \geq n$, output a vector $\mathbf{x} \in \{-1,1\}^m$ such that $$|| \mathbf{A} \mathbf{x} ||_{\infty} \leq \kappa(m/n) \cdot \sqrt{m}~.$$ The number partitioning problem ($\mathrm{NPP}_{\kappa}$) corresponds to the special case of setting $n=1$. There is considerable evidence that both problems exhibit large computational-statistical gaps. In this work, we show (nearly) tight average-case hardness for these problems, assuming the worst-case hardness of standard approximate shortest vector problems on lattices. For $\mathrm{SBP}$, for large $n$, the best that efficient algorithms have been able to achieve is $\kappa(x) = \Theta(1/\sqrt{x})$ (Bansal and Spencer, Random Structures and Algorithms 2020), which is a far cry from the statistical bound. The problem has been extensively studied in the TCS and statistics communities, and Gamarnik, Kizildag, Perkins and Xu (FOCS 2022) conjecture that Bansal-Spencer is tight: namely, $\kappa(x) = \widetilde{\Theta}(1/\sqrt{x})$ is the optimal value achieved by computationally efficient algorithms. We prove their conjecture assuming the worst-case hardness of approximating the shortest vector problem on lattices. For $\mathrm{NPP}$, Karmarkar and Karp's classical differencing algorithm achieves $\kappa(m) = 2^{-O(\log^2 m)}~.$ We prove that Karmarkar-Karp is nearly tight: namely, no polynomial-time algorithm can achieve $\kappa(m) = 2^{-\Omega(\log^3 m)}$, once again assuming the worst-case subexponential hardness of approximating the shortest vector problem on lattices to within a subexponential factor.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

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

  1. TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability

    cs.CL 2026-08 reject novelty 7.0 of 10

    The paper introduces TCS-Bench, a 300-task proof-generation benchmark from top TCS papers, and reports frontier LLM accuracies from 30% to 68% using an automated verifier.

  2. Strong Low Degree Hardness for the Number Partitioning Problem

    math.ST 2025-05 conditional novelty 7.0 of 10

    Low coordinate degree algorithms with randomized rounding fail to solve random number partitioning near-optimally, giving strong low-degree hardness for this problem.

  3. 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

53 extracted references · 49 canonical work pages · cited by 3 Pith papers

  1. [1]

    Generating hard instances of lattice problems (extended abstract)

    Mikl \' o s Ajtai. Generating hard instances of lattice problems (extended abstract). In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996 , pages 99--108. ACM , 1996

    work page 1996

  2. [2]

    Proof of the contiguity conjecture and lognormal limit for the symmetric perceptron, 2021

    Emmanuel Abbe, Shuangping Li, and Allan Sly. Proof of the contiguity conjecture and lognormal limit for the symmetric perceptron, 2021

    work page 2021

  3. [3]

    Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster

    Emmanuel Abbe, Shuangping Li, and Allan Sly. Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 , pages 860--873. ACM , 2022

    work page 2022

  4. [4]

    Storage capacity in symmetric binary perceptrons

    Benjamin Aubin, Will Perkins, and Lenka Zdeborová. Storage capacity in symmetric binary perceptrons. Journal of Physics A: Mathematical and Theoretical , 52(29):294003, June 2019

    work page 2019

  5. [5]

    On the solution-space geometry of random constraint satisfaction problems

    Dimitris Achlioptas and Federico Ricci - Tersenghi. On the solution-space geometry of random constraint satisfaction problems. In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006 , pages 130--139. ACM , 2006

    work page 2006

  6. [6]

    Constructive algorithms for discrepancy minimization

    Nikhil Bansal. Constructive algorithms for discrepancy minimization. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA , pages 3--10. IEEE Computer Society, 2010

    work page 2010

  7. [7]

    Clustering of solutions in the symmetric binary perceptron

    Carlo Baldassi, Riccardo Della Vecchia, Carlo Lucibello, and Riccardo Zecchina. Clustering of solutions in the symmetric binary perceptron. Journal of Statistical Mechanics: Theory and Experiment , 2020(7):073303, 2020

    work page 2020

  8. [8]

    On the atypical solutions of the symmetric binary perceptron

    Damien Barbier, Ahmed El Alaoui, Florent Krzakala, and Lenka Zdeborová. On the atypical solutions of the symmetric binary perceptron. Journal of Physics A: Mathematical and Theoretical , 57(19):195202, April 2024

    work page 2024

Show all 53 references
  1. [9]

    Noise-tolerant learning, the parity problem, and the statistical query model

    Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM , 50(4):506--519, 2003

    2003

  2. [10]

    Classical hardness of learning with errors

    Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehl \' e . Classical hardness of learning with errors. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 20...

    2013

  3. [11]

    Continuous LWE

    Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang. Continuous LWE . In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , pages 694--707. ACM , 2021

    2021

  4. [12]

    Nikhil Bansal and Joel H. Spencer. On-line balancing of random inputs. Random Struct. Algorithms , 57(4):879--891, 2020

    2020

  5. [13]

    Constrained key-homomorphic prfs from standard lattice assumptions - or: How to secretly embed a circuit in your PRF

    Zvika Brakerski and Vinod Vaikuntanathan. Constrained key-homomorphic prfs from standard lattice assumptions - or: How to secretly embed a circuit in your PRF . In Yevgeniy Dodis and Jesper Buus Nielsen, editors, Theory of Cryptography - 12th Theory of Cryptography Conference,...

    2015

  6. [14]

    Thomas M. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Transactions on Electronic Computers , EC-14(3):326--334, 1965

    1965

  7. [15]

    Cryptographic hardness of learning halfspaces with massart noise

    Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, and Lisheng Ren. Cryptographic hardness of learning halfspaces with massart noise. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: A...

    2022

  8. [16]

    Near-optimal cryptographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals

    Ilias Diakonikolas, Daniel Kane, and Lisheng Ren. Near-optimal cryptographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, ed...

    2023

  9. [17]

    The overlap gap property: A topological barrier to optimizing over random structures

    David Gamarnik. The overlap gap property: A topological barrier to optimizing over random structures. Proceedings of the National Academy of Sciences , 118(41):e2108492118, 2021

    2021

  10. [18]

    M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman, 1979

    1979

  11. [19]

    Kızıldağ

    David Gamarnik and Eren C. Kızıldağ. Algorithmic obstructions in the random number partitioning problem, 2021

    2021

  12. [20]

    Kizildag, Will Perkins, and Changji Xu

    David Gamarnik, Eren C. Kizildag, Will Perkins, and Changji Xu. Algorithms and barriers in the symmetric binary perceptron model. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022 , pages 576--587. IEEE , 2022

    2022

  13. [21]

    Kizildag, Will Perkins, and Changji Xu

    David Gamarnik, Eren C. Kizildag, Will Perkins, and Changji Xu. Geometric barriers for stable and online algorithms for discrepancy minimization. In Gergely Neu and Lorenzo Rosasco, editors, The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Ban...

    2023

  14. [22]

    Kim, Vinod Vaikuntanathan, and Or Zamir

    Shafi Goldwasser, Michael P. Kim, Vinod Vaikuntanathan, and Or Zamir. Planting undetectable backdoors in machine learning models : [extended abstract]. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022 ,...

    2022

  15. [23]

    Finding a large submatrix of a gaussian random matrix

    David Gamarnik and Quan li. Finding a large submatrix of a gaussian random matrix. Annals of Statistics , 46, 02 2016

    2016

  16. [24]

    The complexity of the covering radius problem on lattices and codes

    Venkatesan Guruswami, Daniele Micciancio, and Oded Regev. The complexity of the covering radius problem on lattices and codes. In 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 21-24 June 2004, Amherst, MA, USA , pages 161--173. IEEE Computer Society, 2004

    2004

  17. [25]

    Continuous LWE is as hard as LWE & applications to learning gaussian mixtures

    Aparna Gupte, Neekon Vafa, and Vinod Vaikuntanathan. Continuous LWE is as hard as LWE & applications to learning gaussian mixtures. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022 , pages 1162--1173. I...

    2022

  18. [26]

    Number balancing is as hard as minkowski's theorem and shortest vector

    Rebecca Hoberg, Harishchandra Ramadas, Thomas Rothvoss, and Xin Yang. Number balancing is as hard as minkowski's theorem and shortest vector. In Friedrich Eisenbrand and Jochen K \" o nemann, editors, Integer Programming and Combinatorial Optimization - 19th International Conf...

    2017

  19. [27]

    The number of orthants in n-space intersected by an s-dimensional subspace

    Roger David Joseph and Louise Hay. The number of orthants in n-space intersected by an s-dimensional subspace. 1960

    1960

  20. [28]

    Extensions of lipschitz mappings into a hilbert space

    William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. Contemporary Mathematics , 26:189--206, 1984

    1984

  21. [29]

    Improved algorithms for integer programming and related lattice problems

    Ravi Kannan. Improved algorithms for integer programming and related lattice problems. In David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas, edito...

    1983

  22. [30]

    Minkowski's convex body theorem and integer programming

    Ravi Kannan. Minkowski's convex body theorem and integer programming. Math. Oper. Res. , 12(3):415--440, 1987

    1987

  23. [31]

    Narendra Karmarkar and Richard M. Karp. The differencing method of set partitioning. 1982

    1982

  24. [32]

    Probabilistic analysis of optimum partitioning

    Narendra Karmarkar, Richard M Karp, George S Lueker, and Andrew M Odlyzko. Probabilistic analysis of optimum partitioning. Journal of Applied probability , 23(3):626--645, 1986

    1986

  25. [33]

    Factoring polynomials with rational coefficients

    Arjen K Lenstra, Hendrik Willem Lenstra, and L \'a szl \'o Lov \'a sz. Factoring polynomials with rational coefficients. Mathematische annalen , 261:515--534, 1982

    1982

  26. [34]

    Adaptive estimation of a quadratic functional by model selection

    Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics , pages 1302--1338, 2000

    2000

  27. [35]

    Constructive discrepancy minimization by walking on the edges

    Shachar Lovett and Raghu Meka. Constructive discrepancy minimization by walking on the edges. SIAM J. Comput. , 44(5):1573--1582, 2015

    2015

  28. [36]

    Deterministic discrepancy minimization via the multiplicative weight update method

    Avi Levy, Harishchandra Ramadas, and Thomas Rothvoss. Deterministic discrepancy minimization via the multiplicative weight update method. In Friedrich Eisenbrand and Jochen K \" o nemann, editors, Integer Programming and Combinatorial Optimization - 19th International Conferen...

    2017

  29. [37]

    Almost perfect lattices, the covering radius problem, and applications to ajtai's connection factor

    Daniele Micciancio. Almost perfect lattices, the covering radius problem, and applications to ajtai's connection factor. SIAM J. Comput. , 34(1):118--169, 2004

    2004

  30. [38]

    Mézard, T

    M. Mézard, T. Mora, and R. Zecchina. Clustering of solutions in the random satisfiability problem. Physical Review Letters , 94(19), May 2005

    2005

  31. [39]

    Worst-case to average-case reductions based on gaussian measures

    Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput. , 37(1):267--302, 2007

    2007

  32. [40]

    Frozen 1-rsb structure of the symmetric ising perceptron

    Will Perkins and Changji Xu. Frozen 1-rsb structure of the symmetric ising perceptron. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , pages 1579--1588. ACM , 2021

    2021

  33. [41]

    Lattices in computer science - average-case hardness

    Oded Regev. Lattices in computer science - average-case hardness. Lecture Notes for Class (scribe: Elad Verbin ). https://cims.nyu.edu/ regev/teaching/lattices_fall_2004/ln/averagecase.pdf, 2004

    2004

  34. [42]

    On lattices, learning with errors, random linear codes, and cryptography

    Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM , 56(6):34:1--34:40, 2009

    2009

  35. [43]

    Constructive discrepancy minimization for convex sets

    Thomas Rothvo . Constructive discrepancy minimization for convex sets. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014 , pages 140--145. IEEE Computer Society, 2014

    2014

  36. [44]

    The subspace flatness conjecture and faster integer programming

    Victor Reis and Thomas Rothvoss. The subspace flatness conjecture and faster integer programming. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023 , pages 974--988. IEEE , 2023

    2023

  37. [45]

    Non-asymptotic theory of random matrices: extreme singular values

    Mark Rudelson and Roman Vershynin. Non-asymptotic theory of random matrices: extreme singular values. In Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II--IV: Invited Lectures , pages 15...

    2010

  38. [46]

    A hierarchy of polynomial time lattice basis reduction algorithms

    Claus - Peter Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci. , 53:201--224, 1987

    1987

  39. [47]

    Six standard deviations suffice

    Joel Spencer. Six standard deviations suffice. Transactions of the American Mathematical Society , 289(2):679--706, 1985

    1985

  40. [48]

    On the cryptographic hardness of learning single periodic neurons

    Min Jae Song, Ilias Zadik, and Joan Bruna. On the cryptographic hardness of learning single periodic neurons. In Marc'Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: ...

    2021

  41. [49]

    Hardness of agnostically learning halfspaces from worst-case lattice problems

    Stefan Tiegel. Hardness of agnostically learning halfspaces from worst-case lattice problems. In Gergely Neu and Lorenzo Rosasco, editors, The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India , volume 195 of Proceedings of Machine...

    2023

  42. [50]

    Balancing gaussian vectors in high dimension

    Paxton Turner, Raghu Meka, and Philippe Rigollet. Balancing gaussian vectors in high dimension. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria] , volume 125 of Proceedings of Machine Le...

    2020

  43. [51]

    Robert O. Winder. Single stage threshold logic. In 2nd Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1961) , pages 321--332, 1961

    1961

  44. [52]

    The differencing algorithm ldm for partitioning: A proof of a conjecture of karmarkar and karp

    Benjamin Yakir. The differencing algorithm ldm for partitioning: A proof of a conjecture of karmarkar and karp. Mathematics of Operations Research , 21(1):85--99, 1996

    1996

  45. [53]

    Wein, and Joan Bruna

    Ilias Zadik, Min Jae Song, Alexander S. Wein, and Joan Bruna. Lattice-based methods surpass sum-of-squares in clustering. In Po - Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK , volume 178 of Proceedings of Machine Learning Rese...

    2022

Pith tools

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