Pith. sign in

REVIEW 2 major objections 4 minor 48 references

Feature Selection and Junta Testing are Statistically Equivalent

T0 review · 2 major / 4 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 Testing whether a boolean function depends on only k variables and finding those k variables are statistically equivalent: both have sample complexity $\Theta\left(\frac{1}{\varepsilon}\left(\sqrt{2^k \log \binom{n}{k}} + \log…

desk verdict The upper-bound side is clean, but the uniform lower bound rests on a false negative-association claim in Proposition 3.19(3), so the main theorem is not proven as written. read the letter →

arxiv 2505.04604 v2 pith:YCSBN7WJ submitted 2025-05-07 cs.LG cs.CCcs.DSstat.ML

Lorenzo Beretta , Nathaniel Harms , Caleb Koch This is my paper · ORCID
classification cs.LGcs.CCcs.DSstat.ML MSC 68Q3268W20
keywords juntatestingfeatureselectionsample-baseddistribution-freesamplecomplexitypropertybalancedfunctionsnegativeassociation
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 proves that, in the distribution-free sample-based setting, the testing question—does an unknown boolean function depend on only $k$ of its $n$ inputs?—and the search question—if it does, which $k$ inputs?—are statistically equivalent. The same simple algorithm, which draws samples and keeps any set of $k$ variables that no sample contradicts, is sample-optimal for both tasks, with sample size $\Theta\left(\frac{1}{\varepsilon}\left(\sqrt{2^k \log \binom{n}{k}} + \log \binom{n}{k}\right)\right)$. This is the first tight bound for any natural class of boolean functions in this model, and it improves the previous lower bound of $\Omega\left(\sqrt{2^k} + \log \binom{n}{k}\right)$. The proof works by reducing both tasks to a distribution-testing problem called SOPP (supported on one per pair) and by a balls-and-bins argument showing that random balanced juntas are indistinguishable from random functions below that sample size.

What carries the argument

The central object is the SOPP testing problem: a distribution $p$ over $[2N]$ is SOPP if each pair of coordinates $(2i, 2i-1)$ contains at most one support point, and testing SOPP with $N = 2^k$ reduces to both junta testing and feature selection. Conditioning each candidate $k$-variable set $S$ gives a distribution over the $(k+1)$-bit strings $(x_S, f(x))$, and SOPP captures exactly whether $f$ is a junta on $S$; the SOPP tester (reject only if a sample hits both members of some pair) is proved sample-optimal. The lower bound is driven by a balls-and-bins lemma: if $M$ random 'balls' (balanced $k$-juntas) thrown into $2^m$ bins have uniform collisions and unlikely collisions, their labels become nearly uniform and hence indistinguishable from random functions. The hard part is verifying the unlikely-collision condition for the family of all balanced $k$-juntas, using negative-association concentration for sub-gaussian and sub-exponential variables.

What would settle it

Compute the empirical tail $P[\langle F,G\rangle > D\lambda/2]$ for uniformly random balanced functions $f,g$ at several $(k,\Delta)$ pairs: Lemma 3.20 predicts decay $\exp(-c(K^2/D)\lambda^2)$, but the true sub-gaussian norm of $F_z$ gives the slower rate $\exp(-c(K/D)\lambda)$; observing which rate holds settles whether the proof's concentration step is valid.

Watch

Extended reading notes

Core claim

Testing $k$-juntas and $k$-feature selection require the same number of random samples: $m = \Theta\left(\frac{1}{\varepsilon}\left(\sqrt{2^k \log \binom{n}{k}} + \log \binom{n}{k}\right)\right)$. The obvious algorithm—draw $m$ samples, then output Accept (for testing) or a set $T$ (for feature selection) if $T$ is consistent with every sample—achieves this bound, and the paper proves matching lower bounds that hold even for two-sided error testers. For constant $\varepsilon$, the lower bound already holds under the uniform distribution; the $1/\varepsilon$ dependence is forced by a construction over a product distribution with exponentially decaying coordinates. A byproduct is the first tight lower bound (up to constants) for $k$-junta truncation testing.

Load-bearing premise

The lower bound stands on the concentration claim in Lemma 3.20 (Section 3.3.2), which assumes each $F_z$ has sub-gaussian parameter $O(D/K)$ even though $F_z = (D/(2K))\sum_{i=1}^{K/D} X_{z,i}$ is a scaled sum of random $\pm1$ variables whose true sub-gaussian norm is $\Theta(\sqrt{D/K})$; without a corrected parameter the uniform-distribution lower bound is unsupported.

Editorial extensions

If this is right

  • For any distribution-free sample-based $k$-junta tester, no estimator based on correlations between variable sets can beat the trivial consistent-set algorithm; the union-bound analysis is tight up to constant factors.
  • Feature selection provides no statistical advantage over testing: deciding whether a junta exists costs the same as recovering the relevant variables, and the two problems can be solved by the same algorithm.
  • Under the uniform distribution with constant $\varepsilon$, once the sample size falls below the stated bound, random balanced juntas become indistinguishable from random functions, so no tester can succeed below it.
  • When the distance parameter $\varepsilon$ is small (down to $2^{-\tau n}$), the sample bound must grow as $1/\varepsilon$, and achieving that dependence requires a known non-uniform product distribution rather than the uniform one.
  • A tight lower bound for testing $k$-junta truncation follows as a byproduct, improving the previous $\Omega(\log \binom{n}{k})$ lower bound.

Reading between the lines

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

  • A candidate general principle suggested by the equivalence: sample-based testing of a class $H$ via the consistent-hypothesis algorithm is sample-optimal exactly when proof-based one-sided testers cannot be beaten by evidence-based two-sided testers; juntas now join the positive side, while support-size functions are the known negative example.
  • The SOPP reduction is a transferable template: any distribution-free sample-based test of a property expressible as 'each hypothesis is a function on a bounded set of coordinates' could be analyzed by mapping each candidate coordinate set to a two-point-pair distribution, with junta testing as the case where the witness set is exactly a $k$-subset of variables.
  • A direct check of the flagged concentration step: computing the true sub-gaussian norm of $F_z$ in Equation (6) validates whether the lower-bound proof can be repaired, since the paper's claimed $O(D/K)$ parameter is smaller than the variance-derived $\Theta(\sqrt{D/K})$; the main theorem might still hold, but not by the given route.
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 / 4 minor

Summary. The paper studies distribution-free sample-based testing of k-juntas and k-feature selection. It formalizes a "brute-force" algorithm that outputs any set of k variables consistent with the sample, and claims that this algorithm is sample-optimal for both tasks with sample size Θ((1/ε)(√(2^k log C(n,k)) + log C(n,k))). The upper bound is obtained by reducing both tasks to testing a distribution property called "Supported on One-Per-Pair" (SOPP) and giving a tight SOPP tester. The lower bound is built from a balls-and-bins lemma applied to balanced k-juntas: under the uniform distribution, the labels of a random balanced junta are shown to be nearly uniform on m samples for m up to the claimed lower bound, and a product-distribution reduction converts this into the 1/ε dependence. The paper also derives a lower bound for junta truncation. The central lower-bound proof relies on a concentration lemma whose proof uses a false negative-association assertion; the main theorem is therefore not established as written.

Significance. If the main theorem can be repaired, this is a substantial contribution: it gives the first tight sample-complexity bound for distribution-free sample-based junta testing, establishes an equivalence between testing and feature selection, and introduces an elegant connection to the SOPP distribution-testing problem. The upper-bound framework (Lemmas 2.4 and 2.5) is clean and appears correct, and the balls-and-bins strategy is a natural and potentially reusable technique. However, the current proof of the uniform lower bound hinges on Lemma 3.20, whose proof is invalid as written; until this is fixed, the paper's central claim is unverified.

major comments (2)
  1. [§3.3.2, Proposition 3.19(3) and Lemma 3.20] The proof of Lemma 3.20 is not valid as written. Proposition 3.19(3) asserts that the variables {F_z G_z} are negatively associated, but this assertion is false. For distinct z, z', since f and g are independent and all four variables have mean zero, E[F_z G_z F_{z'} G_{z'}] = E[F_z F_{z'}] E[G_z G_{z'}] = Cov(F_z,F_{z'}) Cov(G_z,G_{z'}). Negative associativity of the F's and of the G's gives both covariances ≤ 0, so the product is ≥ 0 and is strictly positive in the nondegenerate case. Negative associativity of {F_z G_z} would require Cov(F_z G_z, F_{z'} G_{z'}) ≤ 0, since the identity functions on two disjoint coordinates are both monotone increasing. Moreover, the proof's claim that F_z G_z is a monotone function of the underlying variables fails because F_z and G_z are signed. Since Theorem 3.18 is invoked in Lemma 3.20 only through the asserted negative associativity, and Lemma 3.20 is the sole concentration input to Proposition 3.13 and Lemma 3.21, the uniform lower bound (Theorem 3.1) and hence the main lower bound (Theorem 1.6) are not established as written. Please either prove a valid concentration inequality for sum_z F_z G_z by another method or restructure the lower-bound argument.
  2. [§3.3.2, Proposition 3.19(1)] The claimed sub-gaussian parameter is inconsistent with Eq. (6). F_z = (D/(2K)) sum_{i=1}^{K/D} X_{z,i}, where the X_{z,i} are conditionally centered {±1} variables, so Var(F_z) = Θ(D/K) and the sub-gaussian norm is Θ(√(D/K)), not O(D/K). The stated bound flows into the stated O(D^2/K^2) sub-exponential parameter for F_z G_z. With the corrected norm, the product norm becomes O(D/K), and the final exponent in Lemma 3.20 appears recoverable; I therefore view this as a correctable technical error rather than a separate obstruction, but it must be stated and proved correctly.
minor comments (4)
  1. [§3.4.1, Proposition 3.24] In the simulation step, the two branches are both described as "if x_{n+i*} = 1". The second branch should read "if x_{n+i*} = 0", since otherwise the simulated distribution is not µ_q.
  2. [§3.3.3, proof of Lemma 3.21] The displayed derivation defining T(∆) and the subsequent ratio T(∆)/T(∆−1) is hard to follow and appears to contain a typo in the exponent on (n choose k). Please re-check the algebra so that the splitting argument can be verified without ambiguity.
  3. [§3.2, Lemma 3.10] The hypothesis states "k = k(n) < n−2", but the reduction is to feature selection on a domain of 2n bits while the junta setup uses n bits. The relationship between k and n should be clarified so that the two domains are not confused.
  4. [Theorem 1.6 vs. Lemmas 3.22 and 3.25] The formal theorem states k < (1−τ)n/e, while Lemmas 3.22 and 3.25 use k ≤ (1−τ)n. These hypotheses should be aligned, or the derivation of the stricter condition should be explained.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's upper and lower bounds are derived from first principles, with no fitted inputs, load-bearing self-citations, or predictions that reduce to their own definitions.

full rationale

The paper is self-contained against external benchmarks. The upper bound is proved by explicitly reducing junta testing and feature selection to the newly defined SOPP distribution-testing problem (Lemma 2.4) and then giving a direct analysis of the natural SOPP tester (Lemma 2.5). The lower bound is built from a balls-and-bins framework (Lemma 3.2), verified collision conditions for balanced junta setups (Propositions 3.11 and 3.12), and a concentration analysis of R = 1/2 + (2/D)<F,G> (Proposition 3.13, Proposition 3.19, Lemma 3.20, Lemma 3.21). No fitted parameter is later called a prediction, and no result is imported solely from the authors' prior work to force the conclusion. The algorithm whose optimality is claimed, Algorithm 1, is analyzed directly, and the lower bound applies to any tester, so there is no step where the target sample complexity is assumed as an input. The skeptic's objection about Proposition 3.19(3) concerns whether the negative-association claim is true and whether the concentration argument is valid as written; that is a correctness or proof-gap concern, not a circularity concern. Similarly, the sub-gaussian parameter issue in Proposition 3.19(1) is a technical estimate issue, not a conceptual reduction of the conclusion to its inputs. None of the paper's central claims are defined in terms of each other, and no self-citation carries the load-bearing argument. Therefore the honest finding is no significant circularity.

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

No free parameters are fitted; all constants are universal and no numeric quantities are chosen to match data. The paper introduces the SOPP distribution-testing problem and the balanced junta setup as analytical devices rather than physical entities. The external ingredients are standard concentration and negative-association results, plus the sample-based model itself.

assumptions (3)
  • standard math Standard concentration inequalities for sums of negatively associated sub-gaussian and sub-exponential random variables.
    Theorems 3.17 and 3.18 are used to prove Lemma 3.20 and the lower-bound concentration; the paper cites Wajc's notes and Vershynin's book rather than proving them.
  • domain assumption Closure properties of negative association, including that a uniformly random balanced function gives negatively associated cell indicators under the global balance condition.
    Used in Proposition 3.19 to treat F_z, G_z, and their products as negatively associated; this is an imported statistical fact about the chosen junta setup.
  • domain assumption The sample-based distribution-free testing model permits only independent random labeled examples and allows the algorithm to know the construction distribution in lower bounds.
    The upper bound works for an unknown distribution, while the lower bound constructs a known product distribution, which only strengthens the lower bound. This is the standard model from Valiant's PAC framework.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Feature Selection and Junta Testing are Statistically Equivalent." pith.science (2026). https://pith.science/paper/YCSBN7WJ

@misc{pith2026250504604,
  author       = {Pith},
  title        = {Pith review of: Feature Selection and Junta Testing are Statistically Equivalent},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YCSBN7WJ}},
  note         = {Machine review of arXiv:2505.04604}
}
abstract

For a function $f \colon \{0,1\}^n \to \{0,1\}$, the junta testing problem asks whether $f$ depends on only $k$ variables. If $f$ depends on only $k$ variables, the feature selection problem asks to find those variables. We prove that these two tasks are statistically equivalent. Specifically, we show that the ``brute-force'' algorithm, which checks for any set of $k$ variables consistent with the sample, is simultaneously sample-optimal for both problems, and the optimal sample size is \[ \Theta\left(\frac 1 \varepsilon \left( \sqrt{2^k \log {n \choose k}} + \log {n \choose k}\right)\right). \]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

48 extracted references · 22 canonical work pages

  1. [1]

    Learning and testing junta distributions

    Maryam Aliakbarpour, Eric Blais, and Ronitt Rubinfeld. Learning and testing junta distributions. In , pages 19--46. PMLR, 2016

    work page 2016

  2. [2]

    Efficient quantum algorithms for (gapped) group testing and junta testing

    Andris Ambainis, Aleksandrs Belovs, Oded Regev, and Ronald de Wolf. Efficient quantum algorithms for (gapped) group testing and junta testing. In , pages 903--922. SIAM, 2016. https://doi.org/10.1137/1.9781611974331.ch65 doi:10.1137/1.9781611974331.ch65

    doi:10.1137/1.9781611974331.ch65 2016

  3. [3]

    Quantum algorithms for learning and testing juntas

    Alp At c and Rocco A Servedio. Quantum algorithms for learning and testing juntas. Quantum Information Processing , 6(5):323--348, 2007. https://doi.org/10.1007/s11128-007-0061-6 doi:10.1007/s11128-007-0061-6

    doi:10.1007/s11128-007-0061-6 2007

  4. [4]

    Local correction of juntas

    Noga Alon and Amit Weinstein. Local correction of juntas. Information Processing Letters , 112(6):223--226, 2012. https://doi.org/10.1016/j.ipl.2011.12.005 doi:10.1016/j.ipl.2011.12.005

    work page doi:10.1016/j.ipl.2011.12.005 2012

  5. [5]

    Tolerant junta testing and the connection to submodular optimization and function isomorphism

    Eric Blais, Cl \'e ment Canonne, Talya Eden, Amit Levi, and Dana Ron. Tolerant junta testing and the connection to submodular optimization and function isomorphism. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2113--2132, 2018. https://doi.org/10.1137/1.9781611975031.138 doi:10.1137/1.9781611975031.138

    work page doi:10.1137/1.9781611975031.138 2018

  6. [6]

    Distribution testing lower bounds via reductions from communication complexity

    Eric Blais, Cl \'e ment L Canonne, and Tom Gur. Distribution testing lower bounds via reductions from communication complexity. ACM Transactions on Computation Theory (TOCT) , 11(2):1--37, 2019. https://doi.org/10.1145/3305270 doi:10.1145/3305270

    work page doi:10.1145/3305270 2019

  7. [7]

    Quantum algorithm for distribution-free junta testing

    Aleksandrs Belovs. Quantum algorithm for distribution-free junta testing. In Proceedings of the 14th International Computer Science Symposium in Russia (CSR) , pages 50--59. Springer, 2019. https://doi.org/10.1007/978-3-030-19955-5_5 doi:10.1007/978-3-030-19955-5_5

    work page doi:10.1007/978-3-030-19955-5_5 2019

  8. [8]

    VC dimension and distribution-free sample-based testing

    Eric Blais, Renato Ferreira Pinto Jr , and Nathaniel Harms. VC dimension and distribution-free sample-based testing. In , pages 504--517, 2021. https://doi.org/10.1145/3406325.3451104 doi:10.1145/3406325.3451104

    arXiv 2021

Show all 48 references
  1. [9]

    The non-adaptive query complexity of testing k-parities

    Harry Buhrman, David Garc a-Soriano, Arie Matsliah, and Ronald de Wolf. The non-adaptive query complexity of testing k-parities. Chicago Journal of Theoretical Computer Science , 6:1--11, 2013

    2013

  2. [10]

    A strong composition theorem for junta complexity and the boosting of property testers

    Guy Blanc, Caleb Koch, Carmen Strassle, and Li-Yang Tan. A strong composition theorem for junta complexity and the boosting of property testers. In , pages 1757--1777. IEEE, 2023. https://doi.org/10.1109/FOCS57990.2023.00107 doi:10.1109/FOCS57990.2023.00107

    2023

  3. [11]

    Improved bounds for testing juntas

    Eric Blais. Improved bounds for testing juntas. In , pages 317--330, 2008. https://doi.org/10.1007/978-3-540-85363-3_26 doi:10.1007/978-3-540-85363-3_26

    2008 doi

  4. [12]

    Testing juntas nearly optimally

    Eric Blais. Testing juntas nearly optimally. In , pages 151--158, 2009. https://doi.org/10.1145/1536414.1536437 doi:10.1145/1536414.1536437

    2009

  5. [13]

    Relevant examples and relevant features: Thoughts from computational learning theory

    Avrim Blum. Relevant examples and relevant features: Thoughts from computational learning theory. In AAAI Fall Symposium on Relevance , volume 5, page 1, 1994

    1994

  6. [14]

    Measure theory , volume 1

    Vladimir Igorevich Bogachev and Maria Aparecida Soares Ruas. Measure theory , volume 1. Springer, 2007. https://doi.org/10.1007/978-3-540-34514-5 doi:10.1007/978-3-540-34514-5

    2007 doi

  7. [15]

    Almost optimal distribution-free junta testing

    Nader H Bshouty. Almost optimal distribution-free junta testing. In , pages 1--13, 2019. https://doi.org/10.4230/LIPIcs.CCC.2019.2 doi:10.4230/LIPIcs.CCC.2019.2

    2019 doi

  8. [16]

    A survey on distribution testing: Your data is big

    Cl \'e ment Canonne. A survey on distribution testing: Your data is big. but is it blue? Theory of Computing , pages 1--100, 2020. https://doi.org/10.4086/toc.gs.2020.009 doi:10.4086/toc.gs.2020.009

    2020 doi

  9. [17]

    Exploring the gap between tolerant and non-tolerant distribution testing

    Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen. Exploring the gap between tolerant and non-tolerant distribution testing. IEEE Transactions on Information Theory , 71(2):1153--1170, 2025. https://doi.org/10.1109/TIT.2024.3483995 doi:10.1109/...

    2025

  10. [18]

    A lower bound for testing juntas

    Hana Chockler and Dan Gutfreund. A lower bound for testing juntas. Information Processing Letters , 90(6):301--305, 2004. https://doi.org/10.1016/j.ipl.2004.01.023 doi:10.1016/j.ipl.2004.01.023

    2004 doi

  11. [19]

    Efficient sample extractors for juntas with applications

    Sourav Chakraborty, David Garc \' a-Soriano, and Arie Matsliah. Efficient sample extractors for juntas with applications. In , pages 545--556. Springer, 2011. https://doi.org/10.1007/978-3-642-22006-7_46 doi:10.1007/978-3-642-22006-7_46

    2011 doi

  12. [20]

    Learning and testing junta distributions with sub cube conditioning

    Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. Learning and testing junta distributions with sub cube conditioning. In , pages 1060--1113. PMLR, 2021

    2021

  13. [21]

    Testing and learning quantum juntas nearly optimally

    Thomas Chen, Shivam Nadimpalli, and Henry Yuen. Testing and learning quantum juntas nearly optimally. In , pages 1163--1185, 2023. https://doi.org/10.1137/1.9781611977554.ch43 doi:10.1137/1.9781611977554.ch43

    2023 doi

  14. [22]

    Settling the query complexity of non-adaptive junta testing

    Xi Chen, Rocco A Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie. Settling the query complexity of non-adaptive junta testing. Journal of the ACM (JACM) , 65(6):1--18, 2018. https://doi.org/10.1145/3213772 doi:10.1145/3213772

    2018 doi

  15. [24]

    Junta correlation is testable

    Anindya De, Elchanan Mossel, and Joe Neeman. Junta correlation is testable. In , pages 1549--1563. IEEE, 2019. https://doi.org/10.1109/FOCS.2019.00090 doi:10.1109/FOCS.2019.00090

    2019

  16. [25]

    Testing convex truncation

    Anindya De, Shivam Nadimpalli, and Rocco A Servedio. Testing convex truncation. In , pages 4050--4082. SIAM, 2023. https://doi.org/10.1137/1.9781611977554.ch155 doi:10.1137/1.9781611977554.ch155

    2023 doi

  17. [26]

    Distribution testing under the parity trace, 2023

    Renato Ferreira Pinto Jr and Nathaniel Harms. Distribution testing under the parity trace, 2023. https://doi.org/10.48550/ARXIV.2304.01374 doi:10.48550/ARXIV.2304.01374

    2023 doi arXiv

  18. [27]

    Testing support size more efficiently than learning histograms

    Renato Ferreira Pinto Jr and Nathaniel Harms. Testing support size more efficiently than learning histograms. In , 2025. https://doi.org/10.48550/ARXIV.2410.18915 doi:10.48550/ARXIV.2410.18915

    2025 doi arXiv

  19. [28]

    Testing juntas

    Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. Testing juntas. Journal of Computer and System Sciences , 68(4):753--787, 2004. https://doi.org/10.1016/j.jcss.2003.11.004 doi:10.1016/j.jcss.2003.11.004

    2004 doi

  20. [29]

    Distribution-free testing of linear functions on R ^n

    Noah Fleming and Yuichi Yoshida. Distribution-free testing of linear functions on R ^n . In , pages 22--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2020. https://doi.org/10.4230/LIPIcs.ITCS.2020.22 doi:10.4230/LIPIcs.ITCS.2020.22

    2020 doi

  21. [30]

    Property testing and its connection to learning and approximation

    Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM) , 45(4):653--750, 1998. https://doi.org/10.1145/290179.290180 doi:10.1145/290179.290180

    1998

  22. [31]

    On sample-based testers

    Oded Goldreich and Dana Ron. On sample-based testers. ACM Transactions on Computation Theory (TOCT) , 8(2):1--54, 2016. https://doi.org/10.1145/2898355 doi:10.1145/2898355

    2016 doi

  23. [32]

    The optimal sample complexity of pac learning

    Steve Hanneke. The optimal sample complexity of pac learning. Journal of Machine Learning Research , 17(38):1--15, 2016

    2016

  24. [33]

    Distribution-free property-testing

    Shirley Halevy and Eyal Kushilevitz. Distribution-free property-testing. SIAM Journal on Computing , 37(4):1107--1138, 2007. https://doi.org/10.1137/050645804 doi:10.1137/050645804

    2007 doi

  25. [34]

    Testing junta truncation

    William He and Shivam Nadimpalli. Testing junta truncation. arXiv preprint arXiv:2308.13992 , 2023. https://doi.org/10.48550/ARXIV.2308.13992 doi:10.48550/ARXIV.2308.13992

    2023 doi arXiv

  26. [35]

    Junta distance approximation with sub-exponential queries

    Vishnu Iyer, Avishay Tal, and Michael Whitmeyer. Junta distance approximation with sub-exponential queries. In , pages 24--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2021. https://doi.org/10.4230/LIPIcs.CCC.2021.24 doi:10.4230/LIPIcs.CCC.2021.24

    2021 doi

  27. [36]

    Bagging is an optimal pac learner

    Kasper Green Larsen. Bagging is an optimal pac learner. In , pages 450--468. PMLR, 2023

    2023

  28. [37]

    Distribution-free junta testing

    Zhengyang Liu, Xi Chen, Rocco A Servedio, Ying Sheng, and Jinyu Xie. Distribution-free junta testing. ACM Transactions on Algorithms (TALG) , 15(1):1--23, 2018. https://doi.org/10.1145/3264434 doi:10.1145/3264434

    2018 doi

  29. [38]

    Lower bounds for tolerant junta and unateness testing via rejection sampling of graphs

    Amit Levi and Erik Waingarten. Lower bounds for tolerant junta and unateness testing via rejection sampling of graphs. In , 2019. https://doi.org/10.4230/LIPIcs.ITCS.2019.52 doi:10.4230/LIPIcs.ITCS.2019.52

    2019 doi

  30. [39]

    Optimal non-adaptive tolerant junta testing via local estimators

    Shivam Nadimpalli and Shyamal Patel. Optimal non-adaptive tolerant junta testing via local estimators. In , pages 1039--1050, 2024. https://doi.org/10.1145/3618260.3649687 doi:10.1145/3618260.3649687

    2024

  31. [40]

    Proclaiming dictators and juntas or testing boolean formulae

    Michal Parnas, Dana Ron, and Alex Samorodnitsky. Proclaiming dictators and juntas or testing boolean formulae. In , pages 273--285. Springer, 2001. https://doi.org/10.1007/3-540-44666-4_30 doi:10.1007/3-540-44666-4_30

    2001 doi

  32. [41]

    Optimal distribution-free sample-based testing of subsequence-freeness with one-sided error

    Dana Ron and Asaf Rosin. Optimal distribution-free sample-based testing of subsequence-freeness with one-sided error. ACM Transactions on Computation Theory (TOCT) , 14(1):1--31, 2022. https://doi.org/10.1145/3512750 doi:10.1145/3512750

    2022 doi

  33. [42]

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

    Mert Sa g lam. Near log-convexity of measured heat in (discrete) time and consequences. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages 967--978. IEEE, 2018. https://doi.org/10.1109/FOCS.2018.00095 doi:10.1109/FOCS.2018.00095

    2018

  34. [43]

    Understanding machine learning: From theory to algorithms

    Shai Shalev-Shwartz and Shai Ben-David . Understanding machine learning: From theory to algorithms . Cambridge university press, 2014. https://doi.org/10.1017/CBO9781107298019 doi:10.1017/CBO9781107298019

    2014 doi

  35. [44]

    S., Bundit Laekhanukit, and Pasin Manurangsi

    Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi. On the parameterized complexity of approximating dominating set. J. ACM , 66(5), August 2019. https://doi.org/10.1145/3325116 doi:10.1145/3325116

    2019 doi

  36. [45]

    Servedio, Li-Yang Tan, and John Wright

    Rocco A. Servedio, Li-Yang Tan, and John Wright. Adaptivity helps for testing juntas. In Proceedings of the 30th Conference on Computational Complexity , page 264–279, Dagstuhl, DEU, 2015. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.CCC.20...

    2015 doi

  37. [46]

    L. G. Valiant. A theory of the learnable. Commun. ACM , 27(11):1134–1142, November 1984. https://doi.org/10.1145/1968.1972 doi:10.1145/1968.1972

    1984

  38. [47]

    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. Journal of the ACM (JACM) , 62(2):1--45, 2015. https://doi.org/10.1145/2728167 doi:10.1145/2728167

    2015 doi

  39. [48]

    High-dimensional probability: An introduction with applications in data science , volume 47

    Roman Vershynin. High-dimensional probability: An introduction with applications in data science , volume 47. Cambridge university press, 2018. https://doi.org/10.1017/9781108231596 doi:10.1017/9781108231596

    2018 doi

  40. [49]

    Negative association - definition, properties, and applications

    David Wajc. Negative association - definition, properties, and applications. https://www.cs.cmu.edu/ dwajc/notes/Negative 2017. Accessed 2025-03-13

    2017

Pith tools

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