Pith. sign in

REVIEW 2 major objections 3 minor 38 references

New Statistical and Computational Results for Learning Junta Distributions

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

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

Pith's one-line read Learning junta distributions is computationally equivalent to learning noisy parities, and the paper gives a nearly sample-optimal learner.

desk verdict The LJD/LPN equivalence is new and likely correct, but the paper's sample-optimality proof has a real gap in the adaptive reuse of samples for LearnFourier. read the letter →

arxiv 2505.05819 v3 pith:TAC55D6H submitted 2025-05-09 cs.LG cs.DS

Lorenzo Beretta This is my paper · ORCID
classification cs.LGcs.DS MSC 68Q3268T05
keywords juntadistributionslearningparitieswithnoiseLPNFourieranalysisofBooleanfunctionsdistributionsamplecomplexitytolerantidentitytestingcomputationalequivalence
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 studies distributions on the Boolean cube whose probability mass depends on at most $k$ of the $n$ coordinates. It proves that learning such $k$-junta distributions from independent samples is computationally equivalent, up to factors polynomial in $2^k$ and $n$, to learning $k$-parity functions under the uniform distribution with noise rate $\eta = 1/2 - 2^{-O(k)}$, the well-known LPN problem. It also designs a learner using $O(k\varepsilon^{-2}(2^k+\log n))$ samples and running in $O(\min(2^n,n^k)\cdot k\varepsilon^{-2}(2^k+\log n))$ time, which matches the known statistical lower bound up to polylogarithmic factors. Together these results mean the new algorithm cannot be substantially improved, in samples or runtime, unless there is a breakthrough for noisy parity learning.

What carries the argument

The argument runs through the Fourier transform on $\{\pm1\}^n$: for a junta distribution, the probability mass function is itself a junta function, so its Fourier coefficients are supported on subsets of the $k$ relevant variables. The load-bearing identity is the noise-injection formula $D_A(x) = \mathbb{E}_{p}[D(x \oplus Ap)]$, which, for a random matrix $A$, survives with probability about $2^{-k}$ as a noisy parity distribution with exactly one non-empty Fourier coefficient alive. On the algorithmic side, the key mechanism is a tolerant identity tester that estimates $\ell_1$ distance by the empirical histogram's $\ell_1$ deviation from the candidate distribution and, via a Bernstein-form bounded-differences inequality, pays only an additive $\log(1/\delta)$ samples for high confidence; this lets the learner reuse one batch of samples across $k n^k$ tester calls without a multiplicative $\log n$ penalty.

What would settle it

Simulate Algorithm 2 on the uniform distribution over $\{\pm1\}^{100}$ with $k=2$ and $\varepsilon=0.1$, using the prescribed $m = O(k\varepsilon^{-2}(2^k+\log n))$ samples; because the true distribution is uniform, the tester should return 'close' for every size-$k$ marginal, and the analysis allows total failure probability $o(1)$. If the maximum over the $k n^k$ tester calls of the empirical $\ell_1$ distance to the uniform marginal exceeds the 'far' threshold with probability noticeably larger than the union-bound value, then reusing one sample batch across adaptively chosen tests is the cause and Lemma 4.6's coverage of the algorithm is incomplete.

Watch

Extended reading notes

Core claim

The central discovery is that learning $k$-junta distributions with sample access has exactly the same computational difficulty, up to $\mathrm{poly}(2^k,n)$ factors, as learning $k$-parities with noise rate $\eta = 1/2 - 2^{-O(k)}$. The proof supplies explicit reductions in both directions: accepting only samples with label $+1$ converts noisy parity samples into a junta distribution whose Fourier coefficients reveal the parity, while a random linear noise-injection operator $D_A(x) = \mathbb{E}_{p}[D(x \oplus Ap)]$ collapses all but one non-zero Fourier coefficient of a junta distribution, producing a noisy parity distribution that a parity learner can handle. A coupon-collector loop then recovers all heavy Fourier coefficients. The second result is an algorithm that improves the sample bound from $2^k\log n$ to $2^k+\log n$ while keeping $n^k$-type time, using a high-confidence tolerant identity tester whose sample cost scales additively rather than multiplicatively in $\log(1/\delta)$.

Load-bearing premise

The algorithm reuses the same $m$ samples for all closeness tests and Fourier estimates, while the tester's failure bound is proven for a fixed candidate distribution; the paper does not supply a uniform-convergence or net argument covering the candidate distributions $Q$ that the algorithm constructs adaptively from those same samples.

Editorial extensions

If this is right

  • Any junta-distribution learner running in time substantially below $n^k$ would translate, through the reductions, into a new algorithm for very noisy parity learning; Theorem 1 therefore transfers the conjectured hardness of LPN to LJD.
  • The sample complexity $O(k\varepsilon^{-2}(2^k+\log n))$ meets the known lower bound $\Omega(\varepsilon^{-2}(2^k+\log(n/k)))$ up to polylogarithmic factors, essentially closing the statistical question for junta distributions.
  • For $k = \log\log n$, the improvement from $2^k\log n$ to $2^k+\log n$ samples is a quadratic reduction in sample complexity.
  • The mutual reductions connect distribution learning to the LPN literature: future progress on sparse LPN algorithms transfers to junta-distribution learning, and hardness evidence against LPN applies to LJD as well.

Reading between the lines

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

  • The noise-injection reduction uses only the bound $2^k$ on the number of non-zero Fourier coefficients, so it should extend to any class of distributions over $\{\pm1\}^n$ whose probability mass functions have at most $2^k$ non-zero Fourier coefficients, not just junta PMFs.
  • A natural extension would be to learn junta distributions with respect to a non-uniform base distribution; the Fourier basis changes to the characters of that base distribution, but the noise-injection identity and the additive-log tester appear to survive.
  • The computational equivalence suggests that other structured-distribution learning problems, such as testing junta truncations or low-degree truncations, could be reduced to LJD and thereby inherit LPN hardness, offering a new route to conditional lower bounds in distribution testing.
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

2 major / 3 minor

Summary. The paper studies learning k-junta distributions over {±1}^n from i.i.d. samples. It claims two main results. First, the computational complexity of learning k-junta distributions is equal, up to poly(2^k,n) factors, to that of learning k-parities with noise at rate 1/2 - 2^{-O(k)}; the proof proceeds by reducing LPN to LJD via a filtering construction and LJD to LPN through an intermediate class of noisy parity distributions. Second, it presents an algorithm that properly learns k-junta distributions to TV error ε using O(k ε^{-2}(2^k + log n)) samples and O(min(2^n,n^k) · k ε^{-2}(2^k + log n)) time, based on a high-confidence tolerant identity tester that pays additively in log(1/δ) and on a Fourier-coefficient learning subroutine applied to marginals. The sample complexity is claimed to be optimal up to polylogarithmic factors, matching the lower bound of Chen et al. [15].

Significance. If the proofs are completed, Theorem 1 is a significant conceptual contribution: it ties the complexity of junta distribution learning to LPN, a central computational learning assumption, and strengthens the earlier one-way reduction of [1] into a two-way equivalence. The algorithmic result would improve the sample complexity of [19] by replacing the multiplicative k log n term with k + log n, and the additive-log high-confidence tester is an elegant and potentially reusable ingredient. The paper is careful in setting up the evaluator model and the reductions are genuine two-way reductions with no circularity. However, as written, the proof of Theorem 2 has a load-bearing gap concerning the reuse of samples for adaptively chosen Fourier-learning calls, and Lemma 3.12 contains incorrect formulas. These issues need to be resolved before the results are fully established.

major comments (2)
  1. [Section 4.2, Lemma 4.6 and Algorithm 2] Lemma 4.6 does not control the failure probability of LearnFourier in Algorithm 2. The m samples are drawn once, and the set S on which LearnFourier(P|S) is run is selected by Tester from these same samples. Lemma 4.4 guarantees accuracy only for i.i.d. samples from a fixed distribution P|S; conditioned on the event that Tester selected S, the empirical marginal on S is biased, and the conditional failure probability of LearnFourier need not be k^{-2}. The union bound in Lemma 4.6 over the at most k calls actually made does not charge the exponentially many S that could have been selected. Lemmas 4.7-4.10 all invoke this unconditional success event E, so Theorem 2 is not established by the current argument. A valid repair would be either to use fresh samples for every LearnFourier call and include the resulting sample cost, or to prove a uniform-convergence statement over all candidate S; the latter would require a tail exponent roughly m ε^2 2^{-k} exceeding k log n + k, while the stated m = O(k ε^{-2}(2^k + log n)) provides only k + k log n / 2^k, which is insufficient when 2^k is not much larger than log n. The paper should supply one of these arguments explicitly.
  2. [Section 3.3, Lemma 3.12] Lemma 3.12 contains incorrect formulas for the filtered distribution. Conditioning on y=1 in the resampling procedure yields D = (1-2η)P + 2η U_n, not D = (1-2η)/(1+2η) P + 4η/(1+2η) U_n. Consequently the stated Fourier coefficients are also inconsistent: for S nonempty one should have \hat D(H) = 2^{-n} and \hat D(S) = (1-2η)2^{-n}; the bullet '2η, if A=H' is incompatible with \hat D(H)=2^{-n} for any probability distribution. The subsequent rounding argument uses the correct PMF values, so the error is repairable, but the lemma as written is internally inconsistent and should be corrected before the proof of Theorem 1 is accepted.
minor comments (3)
  1. [Section 4.1, Lemma 4.3] In the proof of Lemma 4.3, the sentence explaining Equation (3) says the concave function D ↦ Σ_i sqrt(D_i) is minimized at the uniform distribution; it is actually maximized there. The needed bound follows from Cauchy-Schwarz. Also, the bounded-differences constant is 2/m, not 1/m, since changing one sample can move one unit of mass between two histogram bins. These corrections do not change the stated sample complexity, but the proof should be fixed.
  2. [Section 4.2, Lemma 4.4] The statement of Lemma 4.4 promises sample complexity O(ε^{-2}(k + log δ^{-1})), but the proof takes m = O(ε^{-2} 2^k (k + log δ^{-1})). The displayed m is looser than necessary; the stated bound is achievable by applying Hoeffding to the average of χ_J with error ε and union-bounding over the 2^k coefficients. The proof should be aligned with the statement, since Algorithm 2 relies on the stated bound.
  3. [Algorithm 1 and Section 4.2] There are several small notational and typographical issues. In Algorithm 1, the comment that A is 'PAC if its input has noise of rate 1 - O(2^{-k/2})' should presumably read '1/2 - O(2^{-k/2})'. In Lemma 4.4's proof, 'for each J⊆{±1}^k' should be 'for each J⊆[k]'. In the time-complexity discussion of Algorithm 2, the per-call running time of Tester and of the enumeration over all S is not specified; the time bound in Theorem 2 should state these costs explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: both directions of the LJD/LPN equivalence are genuine reductions, and the sample-optimal algorithm is analyzed against external lower bounds and prior-work techniques without defining its target in terms of its inputs.

full rationale

The paper's two main claims are (1) computational equivalence between learning k-junta distributions and learning noisy k-parities, and (2) a sample-optimal algorithm for learning junta distributions. I traced each reduction and algorithm step for definitional or fitted-input circularity. The reduction LPN to LJD (Lemma 3.12) constructs a junta distribution D whose relevant variables are exactly the parity's support S, then uses a junta-distribution learner only as an oracle and recovers S by querying the evaluator; nothing about S is fed into the construction. The reverse reduction (Sections 3.1 and 3.2) first defines noisy parity distributions by their Fourier support (Definition 3.1), then distills a general junta distribution into a noisy parity distribution using the exogenous noise-injection identity of Feldman et al. (Lemma 3.6, cited to [21]) and coupon-collector repetition over heavy Fourier coefficients. The LPN oracle is used on the distilled distribution, and the target junta is reconstructed from estimated coefficients by triangle inequality and rounding; no estimated coefficient is defined in terms of the final hypothesis. The algorithm of Section 4 uses a high-confidence tolerant identity tester (Lemma 4.3) whose analysis is self-contained via McDiarmid, and a Fourier-estimation subroutine (Lemma 4.4) with a union bound over the 2^k coefficients. The skeptical concern about reusing the same m samples across adaptive calls is a real statistical-concentration question, but it is not a circularity: Lemma 4.6's union bound, even if later shown to be insufficient, does not make any derived quantity equal to an input by construction, nor does it rename a fitted parameter as a prediction. The paper also does not rely on load-bearing self-citations: the sole author's own prior work is not invoked, and the central external anchors ([1], [15], [21], [31]) are independent prior results (algorithmic lower bounds, the low-degree algorithm, and Fourier-noise techniques) rather than author-authored uniqueness theorems. The claimed optimality is conditional on LPN hardness, a standard external assumption, not on a conclusion of this paper. Overall I find no step in which a 'prediction' or 'first-principles result' reduces to its own inputs.

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

The central claims rest on standard mathematical tools. The only domain assumption is the evaluator model. No new physical or mathematical entities are introduced.

assumptions (4)
  • standard math Standard Fourier-analytic facts over the Boolean cube, including orthonormality of characters and Parseval's identity.
    Used throughout Sections 2 to 4 to express distributions and analyze low-degree approximations.
  • standard math Standard concentration inequalities, including Hoeffding and the Bernstein form of McDiarmid's inequality.
    Used for sample bounds in Lemmas 3.3, 3.10, 4.3, and 4.4.
  • domain assumption The learning model requires the learner to output an evaluator for the PMF, not just a sampler.
    Stated in Section 2; the LPN-to-LJD reduction uses query access to the learned PMF in Lemma 3.12.
  • domain assumption The lower bound of [15] is valid in the standard sample-access model.
    Used to claim near-optimality of the sample complexity in Theorem 2, though the paper's bound carries an extra factor k.

how reviews work

0 comments
Cite this review

Pith. "Pith review of New Statistical and Computational Results for Learning Junta Distributions." pith.science (2026). https://pith.science/paper/TAC55D6H

@misc{pith2026250505819,
  author       = {Pith},
  title        = {Pith review of: New Statistical and Computational Results for Learning Junta Distributions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TAC55D6H}},
  note         = {Machine review of arXiv:2505.05819}
}
abstract

We study the problem of learning junta distributions on $\{0, 1\}^n$, where a distribution is a $k$-junta if its probability mass function depends on a subset of at most $k$ variables. We make two main contributions: - We show that learning $k$-junta distributions is \emph{computationally} equivalent to learning $k$-parity functions with noise (LPN), a landmark problem in computational learning theory. - We design an algorithm for learning junta distributions whose statistical complexity is optimal, up to polylogarithmic factors. Computationally, our algorithm matches the complexity of previous (non-sample-optimal) algorithms. Combined, our two contributions imply that our algorithm cannot be significantly improved, statistically or computationally, barring a breakthrough for LPN.

Figures

Figures reproduced from arXiv: 2505.05819 by the authors.

Figure 1
Figure 1. An arrow from A to B means that problem B reduces to problem A (i.e., A is harder than B). The blue arrows were proven in previous work, the red arrow was proven in [1] and the black arrows are proven in this work. Theorem 2. There exists an algorithm that properly learns k-junta distributions up to TV distance ε using Op k ε 2 p2 k ` log nqq samples and Opminp2 n, nk q ¨ k ε 2 p2 k ` log nqq running time. Algorithm… view at source ↗
Figure 2
Figure 2. An arrow from A to B means that we reduce problem B to problem A. Definition 3.1 (Noisy parity distribution). We say that a distribution D over t˘1u n is a noisy parity distribution with relevant variables J Ď rns with noise rate η ă 1{2 if DppSq “ 1 2 n ¨ $ ’& ’% 1 if S “ H ˘p1 ´ 2ηq if S “ J 0 otherwise. (1) Observation 1. A noisy parity distribution with noise rate η “ 0 corresponds to the uniform distribution tr… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 37 canonical work pages

  1. [15]

    Learning and testing junta distributions with sub cube conditioning

    Xi Chen et al. “Learning and testing junta distributions with sub cube conditioning”. In: Conference on Learning Theory. PMLR. 2021, pp. 1060–1113

    work page 2021

  2. [1]

    Learning and testing junta distri- butions

    Maryam Aliakbarpour, Eric Blais, and Ronitt Rubinfeld. “Learning and testing junta distri- butions”. In: Conference on Learning Theory. PMLR. 2016, pp. 19–46

    work page 2016

  3. [19]

    Learning junta distributions and quantum junta states, and QAC 0 circuits

    Francisco Escudero-Guti´ errez. “Learning junta distributions and quantum junta states, and QAC 0 circuits”. In: arXiv preprint arXiv:2410.15822 (2024)

    arXiv 2024

  4. [2]

    An Illuminating Algorithm for the Light Bulb Problem

    Josh Alman. “An illuminating algorithm for the light bulb problem”. In: arXiv preprint arXiv:1810.06740 (2018)

    work page Pith review arXiv 2018

  5. [3]

    Learning juntas in the presence of noise

    Jan Arpe and R¨ udiger Reischuk. “Learning juntas in the presence of noise”. In: Theoretical computer science 384.1 (2007), pp. 2–21

    work page 2007

  6. [4]

    Parameterized learnability of juntas

    Vikraman Arvind, Johannes K¨ obler, and Wolfgang Lindner. “Parameterized learnability of juntas”. In: Theoretical computer science 410.47-49 (2009), pp. 4928–4936

    work page 2009

  7. [5]

    On Testing and Learning Quantum Junta Channels

    Zongbo Bao and Penghui Yao. “On Testing and Learning Quantum Junta Channels”. In: The Thirty Sixth Annual Conference on Learning Theory . PMLR. 2023, pp. 1064–1094

    work page 2023

  8. [6]

    Hidden progress in deep learning: Sgd learns parities near the computa- tional limit

    Boaz Barak et al. “Hidden progress in deep learning: Sgd learns parities near the computa- tional limit”. In: Advances in Neural Information Processing Systems 35 (2022), pp. 21750– 21764

    work page 2022

Show all 38 references
  1. [7]

    Improved bounds for testing juntas

    Eric Blais. “Improved bounds for testing juntas”. In: International Workshop on Approxima- tion Algorithms for Combinatorial Optimization . Springer. 2008, pp. 317–330

    2008

  2. [8]

    Open problems-learning a function of r relevant variables

    Avrim Blum. “Open problems-learning a function of r relevant variables”. In: Lecture Notes in Computer Science 2777 (2003), pp. 731–733

    2003

  3. [9]

    Relevant examples and relevant features: Thoughts from computational learn- ing theory

    Avrim Blum. “Relevant examples and relevant features: Thoughts from computational learn- ing theory”. In: AAAI Fall Symposium on ‘Relevance . Vol. 5. 1994, p. 1

    1994

  4. [10]

    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”. In: Journal of the ACM (JACM) 50.4 (2003), pp. 506–519

    2003

  5. [11]

    Selection of relevant features and examples in machine learning

    Avrim L Blum and Pat Langley. “Selection of relevant features and examples in machine learning”. In: Artificial intelligence 97.1-2 (1997), pp. 245–271

    1997

  6. [12]

    Exact learning of juntas from membership queries

    Nader H Bshouty and Areej Costa. “Exact learning of juntas from membership queries”. In: Theoretical Computer Science 742 (2018), pp. 82–97

    2018

  7. [13]

    A survey on feature selection methods

    Girish Chandrashekar and Ferat Sahin. “A survey on feature selection methods”. In: Com- puters & electrical engineering 40.1 (2014), pp. 16–28

    2014

  8. [14]

    Testing and learning quantum juntas nearly optimally

    Thomas Chen, Shivam Nadimpalli, and Henry Yuen. “Testing and learning quantum juntas nearly optimally”. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2023, pp. 1163–1185

    2023

  9. [16]

    Detecting Low-Degree Truncation

    Anindya De et al. “Detecting Low-Degree Truncation”. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing . 2024, pp. 1027–1038. 22

    2024

  10. [17]

    Learning Structured Distributions

    Ilias Diakonikolas. “Learning Structured Distributions.” In: Handbook of Big Data 267 (2016), pp. 10–1201

    2016

  11. [18]

    Sample-optimal identity testing with high probability

    Ilias Diakonikolas et al. “Sample-optimal identity testing with high probability”. In: 45th In- ternational Colloquium on Automata, Languages, and Programming (ICALP 2018) . Schloss- Dagstuhl-Leibniz Zentrum f¨ ur Informatik. 2018

    2018

  12. [20]

    Representation, approximation and learning of submodular functions using low-rank decision trees

    Vitaly Feldman, Pravesh Kothari, and Jan Vondr´ ak. “Representation, approximation and learning of submodular functions using low-rank decision trees”. In: Conference on Learning Theory. PMLR. 2013, pp. 711–740

    2013

  13. [21]

    New results for learning noisy parities and halfspaces

    Vitaly Feldman et al. “New results for learning noisy parities and halfspaces”. In: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06) . IEEE. 2006, pp. 563–574

    2006

  14. [22]

    On agnostic learning of parities, monomials, and halfspaces

    Vitaly Feldman et al. “On agnostic learning of parities, monomials, and halfspaces”. In: SIAM Journal on Computing 39.2 (2009), pp. 606–645

    2009

  15. [23]

    Time/accuracy tradeoffs for learning a relu with respect to gaussian marginals

    Surbhi Goel, Sushrut Karmalkar, and Adam Klivans. “Time/accuracy tradeoffs for learning a relu with respect to gaussian marginals”. In: Advances in neural information processing systems 32 (2019)

    2019

  16. [24]

    Testing junta truncation

    William He and Shivam Nadimpalli. “Testing junta truncation”. In: arXiv preprint arXiv:2308.13992 (2023)

    2023 arXiv

  17. [25]

    Agnostically learning halfspaces

    Adam Tauman Kalai et al. “Agnostically learning halfspaces”. In: SIAM Journal on Com- puting 37.6 (2008), pp. 1777–1805

    2008

  18. [26]

    Efficient noise-tolerant learning from statistical queries

    Michael Kearns. “Efficient noise-tolerant learning from statistical queries”. In: Journal of the ACM (JACM) 45.6 (1998), pp. 983–1006

    1998

  19. [27]

    On the learnability of discrete distributions

    Michael Kearns et al. “On the learnability of discrete distributions”. In: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing . 1994, pp. 273–282

    1994

  20. [28]

    Efficient authentication from hard learning problems

    Eike Kiltz et al. “Efficient authentication from hard learning problems”. In: Journal of Cryp- tology 30.4 (2017), pp. 1238–1275

    2017

  21. [29]

    Embedding hard learning problems into gaussian space

    Adam Klivans and Pravesh Kothari. “Embedding hard learning problems into gaussian space”. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Tech- niques (APPROX/RANDOM 2014). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. 2014

    2014

  22. [30]

    Superpolynomial lower bounds for decision tree learning and testing

    Caleb Koch, Carmen Strassle, and Li-Yang Tan. “Superpolynomial lower bounds for decision tree learning and testing”. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2023, pp. 1962–1994

    2023

  23. [31]

    Constant depth circuits, Fourier trans- form, and learnability

    Nathan Linial, Yishay Mansour, and Noam Nisan. “Constant depth circuits, Fourier trans- form, and learnability”. In: Journal of the ACM (JACM) 40.3 (1993), pp. 607–620

    1993

  24. [32]

    Learning functions of k relevant variables

    Elchanan Mossel, Ryan O’Donnell, and Rocco A Servedio. “Learning functions of k relevant variables”. In: Journal of Computer and System Sciences 69.3 (2004), pp. 421–434

    2004

  25. [33]

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

    Oded Regev. “On lattices, learning with errors, random linear codes, and cryptography”. In: Journal of the ACM (JACM) 56.6 (2009), pp. 1–40. 23

    2009

  26. [34]

    Near log-convexity of measured heat in (discrete) time and consequences

    Mert Sa˘ glam. “Near log-convexity of measured heat in (discrete) time and consequences”. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) . IEEE. 2018, pp. 967–978

    2018

  27. [35]

    Adaptivity helps for testing juntas

    Rocco A Servedio, Li-Yang Tan, and John Wright. “Adaptivity helps for testing juntas”. In: 30th Conference on Computational Complexity (CCC 2015) . Schloss Dagstuhl-Leibniz- Zentrum fuer Informatik. 2015

    2015

  28. [36]

    Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem

    Gregory Valiant. “Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem”. In: Journal of the ACM (JACM) 62.2 (2015), pp. 1– 45

    2015

  29. [37]

    Estimating the unseen: improved estimators for entropy and other properties

    Gregory Valiant and Paul Valiant. “Estimating the unseen: improved estimators for entropy and other properties”. In: Journal of the ACM (JACM) 64.6 (2017), pp. 1–41

    2017

  30. [38]

    McDiarmid’s inequalities of Bernstein and Bennett forms

    Yiming Ying. “McDiarmid’s inequalities of Bernstein and Bennett forms”. In: City University of Hong Kong (2004), p. 318. 24

    2004

Pith tools

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