Pith. sign in

REVIEW 2 major objections 3 minor 43 references

A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions

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

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

Pith's one-line read The paper claims that learning conjunctions and testing juntas share one mechanism, giving $2^{\widetilde O(n^{1/3})}$-time learning, $2^{\widetilde O(k^{1/3})}$-query testing, and the first super-polynomial adaptive/non-adaptive…

desk verdict A promising pair of algorithms for agnostic conjunction learning and tolerant junta testing, but the classical tester as written contains a wrong density factor in the normalized-influence estimator that breaks the proof; it looks repairable. read the letter →

arxiv 2504.16065 v1 pith:GGULVQBY submitted 2025-04-22 cs.DS

Xi Chen , Shyamal Patel , Rocco A. Servedio This is my paper · ORCID
classification cs.DS MSC 68Q3268Q17
keywords agnosticlearningconjunctionstolerantjuntatestingadaptivequerycomplexitynon-adaptivelowerboundsFourieranalysisofBooleanfunctionslocalestimatorsnormalizedinfluences
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper's goal is to establish that two seemingly unrelated noisy-data problems—agnostically learning conjunctions and tolerantly testing juntas—are the same problem in disguise, and to exploit that hidden identity. It claims that a shared 'ball distribution' idea yields a distribution-free agnostic learner for conjunctions running in time $2^{\widetilde O(n^{1/3})}\operatorname{poly}(n,1/\varepsilon)$, an adaptive classical tolerant junta tester making $2^{\widetilde O(k^{1/3})}$ queries, and a matching-query quantum warm-up tester. If these claims are right, adaptive tolerant junta testing provably beats non-adaptive tolerant junta testing, because non-adaptive testers are known to need $2^{\widetilde\Omega(\sqrt{k})}$ queries. A reader should care because this is a first super-polynomial adaptive-vs-non-adaptive separation for a natural tolerant Boolean property, and because the learner improves the long-standing $2^{\widetilde O(\sqrt{n})}$ bound for a basic distribution-free learning problem.

What carries the argument

The load-bearing mechanism is the ball distribution produced by a small random sample of coordinates, together with the SharpNoise operator that enforces it on the Fourier side. In learning, drawing $m=n^{1/3}$ positive examples defines the event $E_{\vec a}$: strings within Hamming distance $n^{2/3}$ of the first example over the coordinates where all examples agree; on $E_{\vec a}$ the optimal conjunction has approximate degree $O(n^{1/3}\log(1/\varepsilon))$, so the low-degree $L^1$ regression theorem learns it. In testing, the analogous object is $f^C=\mathrm{SharpNoise}^C_{\ell,\kappa,\Delta}f$, which sharply attenuates all Fourier coefficients whose support has more than $\ell$ coordinates outside $C$ while nearly preserving the rest; local estimators then compute junta correlations for exponentially many candidate sets $U$ by reusing one set of sample bundles. The classical tester adds a normalized-influence filtering loop, Refine-Coordinates, that pares each candidate coordinate set down to one with half as many irrelevant variables, guaranteeing that a pure set of relevant coordinates is found within $2^{\widetilde O(k^{1/3})}$ total candidates.

What would settle it

Exhibit a single family of Boolean functions for which every poly(k,1/ε)-coordinate reduction satisfying the stated oracle properties moves dist(f,J_k) by more than ε; then Algorithm 7's guarantee fails at its first step. More locally, a concrete counterexample to Claim 47 or Lemma 60—e.g., a junta whose high-level Fourier mass is concentrated on sets that evade every sampled C—would pinpoint exactly where the refinement argument breaks.

Watch

Extended reading notes

Core claim

At its core, the paper claims that the optimal conjunction in agnostic learning and the optimal $k$-junta in tolerant testing are both 'coverage' problems: each wants a small set of variables that captures as much weight as possible of an underlying distribution—the spectral sample in testing, the labeled-example marginal in learning. The paper formalizes this by placing a ball distribution on the sampled coordinates (in learning, inputs within Hamming distance $n^{2/3}$ of the first positive example; in testing, sets whose Fourier support barely escapes the sampled coordinate set $C$), on which the target has approximate degree $O(k^{1/3}\operatorname{polylog} k)$, then using low-degree regression or local estimators on that ball. Theorem 3 states that Algorithm 7 $\pm\varepsilon$-accurately estimates $\operatorname{dist}(f,\mathcal{J}_k)$ for every $f:\{\pm1\}^n\to\{\pm1\}$ using $2^{\widetilde O(k^{1/3})}$ classical queries; Theorem 1 states that Algorithm 1 agnostically learns conjunctions to excess error $\varepsilon$ in time $2^{n^{1/3}\operatorname{polylog}(n,1/\varepsilon)}$; Theorem 2 gives the quantum analogue of the tester. The paper's own conclusion is that adaptive tolerant junta testing provably outperforms non-adaptive, since the known non-adaptive lower bound is $2^{\widetilde\Omega(\sqrt{k})}$.

Load-bearing premise

The load-bearing premise is that the prior coordinate-oracle theorem is exactly as strong as stated: it must reduce the n input coordinates to a poly(k,1/ε)-size set while preserving distance to the closest k-junta up to ε, and must give error-free access to the reduced dictator coordinates with only poly(log(q/δ)) overhead.

Editorial extensions

If this is right

  • Adaptive tolerant junta testing is provably more powerful than non-adaptive: the $2^{\widetilde O(k^{1/3})}$-query tester beats the known $2^{\widetilde\Omega(\sqrt{k})}$ non-adaptive lower bound, giving the first super-polynomial separation for a natural tolerant Boolean property.
  • Agnostic conjunction learning runs in time $2^{n^{1/3}\operatorname{polylog}(n,1/\varepsilon)}$, and boosting converts this into $2^{n^{1/3}\operatorname{polylog}(n,s)}$-time learning of $s$-term DNF formulas and total-integer-weight LTFs over conjunctions.
  • The quantum warm-up shows the spectral-sample oracle is the only quantum ingredient needed; the same machinery classically simulates it through normalized-influence sampling, suggesting quantum speedup here is not essential once coordinates are reduced.
  • The new arbitrary-accuracy estimator for normalized influences (Algorithm 3) replaces constant-factor approximations and may strengthen other algorithms that use influence information.

Reading between the lines

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

  • If the connection is genuine, it predicts that any further improvement to agnostic conjunction learning (below $2^{n^{1/3}}$) should transfer to tolerant junta testing, and vice versa; the paper leaves this transfer as a challenge.
  • A testable extension is to use the ball-distribution trick on other 'coverage' concept classes, such as decision lists or monotone DNF terms, by checking whether the sampled Hamming ball admits a low-degree approximant; the paper does not explore those cases.
  • The classical tester's dependence on exact coordinate oracles suggests an immediate robustness experiment: replace oracles by approximate versions and measure how the $2^{\widetilde O(k^{1/3})}$ bound degrades; nothing in the paper quantifies this.
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 claims two main results. First, it gives a distribution-free algorithm for agnostically PAC learning conjunctions over {±1}^n that runs in time 2^{O~(n^{1/3})} for constant excess error ε, improving on the previous 2^{O~(n^{1/2})} algorithm of KKMS08. Second, it gives an adaptive classical tolerant k-junta tester that makes 2^{O~(k^{1/3})} queries, improving on the 2^{O~(√k)}-query algorithms of ITW21 and NP24 and thereby yielding the first super-polynomial separation between adaptive and non-adaptive tolerant testing for a natural Boolean property. The paper also presents a quantum 'warm-up' tester with the same query complexity and a new estimator for normalized influences (Algorithm 3). The classical tester relies on coordinate-oracle machinery from ITW21 and on a recursive coordinate-filtering procedure (Refine-Coordinates, Algorithm 4).

Significance. If the correctness issues identified below are resolved, the contribution would be substantial. The claimed agnostic-learning result improves a long-standing bound of Kalai et al., and the claimed tolerant-testing result would give a provable super-polynomial adaptive/non-adaptive separation for a natural Boolean property-testing problem. The paper is ambitious and quite detailed: algorithms and parameters are stated explicitly, several technical ingredients (ball distributions, SharpNoise, local estimators, normalized-influence sampling) are developed at length, and the exposition of the conceptual link between learning conjunctions and junta testing is interesting. The proofs contain enough structure that a local correction to the estimator of Section 6.1 could plausibly repair the main theorem, but as written the classical tester's correctness argument has at least one load-bearing error.

major comments (2)
  1. [§6.1, Lemma 50 and Algorithm 3] After sorting iid uniforms r_1,...,r_|U| decreasing as y_1>...>y_|U|, the variable y_|U| is the minimum of |U| iid uniform random variables and has density |U|(1-t)^{|U|-1}; equivalently, the ordered vector has density |U|! on the ordered simplex, not 1/|U|! as assumed in the proof of Lemma 50. Direct computation gives E_y[E_x[(T_{√(y_|U|)} g(x))^2]] = ∑_{S⊇U} fhat(S)^2 / C(|S|,|U|) = NInf_U[f], not NInf_U[f]/(|U|!)^2. Consequently Algorithm 3's final multiplication by (|U|!)^2 makes the estimator return (|U|!)^2 · NInf_U[f] in the limit, so the additive accuracy claim of Lemma 48 does not hold at the true NInf scale. This error is load-bearing: Lemma 65 uses the λ_U values from Estimate-Ninf to argue that the sets T sampled in Algorithm 4 line 2(c)(iv) are within total-variation distance (ε/k')^5·(2^{k^{1/3}polylog})^{-1} of the true normalized-influence distribution, and Lemma 53 and the correctness proof of Algorithm 7 depend on that bound. The fix appears local (drop the (|U|!)^2 multiplier and correct the density in Lemma 50), but it must be propagated through Lemmas 52 and 65.
  2. [§6.2.2, Lemma 65 and the proof of Lemma 53] Lemma 65 conditions on the event E_x[h^2(x)] ≥ ε^2/(2(k')^2) and then invokes Lemma 59 to conclude W_{≥γ}[h] ≥ ε^2/(4(k')^2). However Lemma 59's hypothesis is E_x[h^2(x)] ≥ ε^2/(2k^2), and in the formal setting k' = poly(k,1/ε) is generally much larger than k, so the stated condition does not imply Lemma 59's hypothesis. The same k vs k' mismatch appears in the proof of Lemma 53, where the exit/non-exit thresholds are asserted at ε^2/(2(k')^2) and 2ε^2/(k')^2, whereas Algorithm 4 line 2(c)(iii) and Assumption 54 use ε^2/k^2 and 2ε^2/k^2. These thresholds feed the total-variation argument that justifies the sampling step, so the manuscript must state them consistently at the k^2 scale (or change the algorithm's thresholds accordingly) for the proof of Lemma 53 to go through. If the occurrences of (k')^2 in these two proofs are typos, they still need to be corrected because the submitted text, as written, does not establish the required bound.
minor comments (3)
  1. [§4.3, Lemma 29 and the proof of Lemma 32] The success probability in Lemma 29 is written as 'εm' rather than ε^m, and the same superscript appears lost in the proof of Lemma 32 ('εm·εm'). The intended meaning is clear, but the notation should be fixed throughout Section 4.
  2. [§6.1, Algorithm 3 line 3(a)] The displayed update for g_{S∪{u}} is not readable as written: 'g_{S∪{u}}(x) = g_S(x) − 1/2(g_S(x) + g(x⊕u S))' appears to involve g_S(x⊕u) and should use a precise notation for the set S. Please rewrite this line unambiguously, matching the induction in Lemma 49.
  3. [§6.2, Algorithm 4 line 2(a)] The coordinates i_1,...,i_m are drawn with replacement from C, while I is then treated as a set of m coordinates. If duplicates occur, |I| is smaller than m; the later probability calculations in Lemmas 55 and 56 treat the draws with replacement, which is consistent, but the algorithm should state explicitly that I is the set of distinct drawn coordinates, since the averaging operation f^I_ave is defined for a set.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new algorithms are built on external results (KKMS08, ITW21, NP24), and the paper's own prior results enter only as lower-bound context.

full rationale

The paper's derivation chain is self-contained relative to external prior work. The agnostic conjunction learner (Algorithm 1, Theorem 1) invokes the KKMS08 L1 polynomial-regression theorem (Theorem 10) as a black box, and neither the lemma statements nor the analysis define the target quantity in terms of the algorithm's output. The quantum tolerant junta tester (Algorithm 2, Theorem 2) uses the spectral sample, the SharpNoise operator, and local estimators from NP24; these are external tools with stated assumptions that do not include the theorem being proved. The classical tester (Algorithm 7, Theorem 3) relies on the coordinate-oracle reduction of ITW21 (Theorems 24 and 25) and on NP24 local estimators; while Theorem 3 is conditional on those external results, that conditionality is not circularity. The paper's own prior work appears only as lower-bound context: CP23 and CDL+24 are cited for the known non-adaptive lower bound and for prior adaptive tolerant testing lower bounds, and they are not used to derive the new upper bounds. No fitted parameter is renamed as a prediction, no quantity is defined in terms of the target result, and no load-bearing uniqueness claim is imported from the authors' own prior papers. The skeptical observation in the prompt about Lemma 50 concerns a possible mathematical error in the normalized-influence estimator (an alleged incorrect (|U|!)^2 factor) and its downstream effect on Refine-Coordinates; even if correct, that would be a correctness gap, not a circularity issue, because the estimator is not defined in terms of the junta-distance result it is used to prove. Overall, the claimed improvements are genuine reductions to external results rather than disguised restatements of their own assumptions.

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

The central claims inherit unproved background from prior literature: L1 regression, coordinate oracles, flat polynomials, and Fourier facts. All algorithmic parameters are fixed symbolically for the proofs; none are fitted to data. The new objects, SharpNoise, ball distributions, sample bundles, and normalized influence sampling, are mathematical constructions built from existing definitions, not newly postulated entities with independent physical evidence.

assumptions (6)
  • domain assumption L1 polynomial regression theorem (Theorem 10 of KKMS08): low-degree polynomial approximation with squared error ε^2 implies agnostic learning in time poly(n^d, 1/ε).
    Used in Algorithm 1 step 2(c) to convert the O(n^{1/3} log(1/ε))-degree approximation of c* under D|E_a from Lemma 31 into a hypothesis. This is an external theorem, not proved in the paper.
  • domain assumption Coordinate oracle reduction (Theorem 24, Corollary 4.7 of ITW21): with poly(k, 1/ε) queries one can reduce n to k'=poly(k,1/ε) approximate dictators and simulate f^S_ave with small loss.
    Basis of the classical tester. Theorem 3 carries over only if this reduction preserves dist(f,J_k) up to ε (property 2) and permits exact oracle simulation with poly(log(q/δ)) overhead (property 4).
  • standard math Flat polynomial constructions of KLS96 and Linial-Nisan, including coefficient bounds from NP24 (Lemmas 17, 18, 19, 20).
    Used to design the SharpNoise operator and local estimators. These are cited results, not re-proved in the paper.
  • standard math Fourier analytic facts: Parseval's identity, spectral sample definition, O'Donnell Proposition 3.22, law of total variance, Cauchy-Schwarz, Hoeffding and Chernoff bounds.
    Invoked throughout Sections 3, 5, and 6 without proof as standard background.
  • standard math The spectral sample of a Boolean function can be drawn with one quantum query, and classical draws are impossible in general (O'Donnell, Nielsen-Chuang, Simon).
    Justifies the quantum query model for Theorem 2. The classical tester avoids this assumption by using normalized influences.
  • domain assumption The WLOG assumptions ε >= 2^{-k^{0.001}} and k at least a large constant, with fallback to the DMN19 tester otherwise.
    Used at the start of Section 6 to simplify polylog factors. The authors justify it by comparing polylog(1/ε) with k; if the fallback tester did not have the stated query bound, the classical result would not cover tiny ε.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions." pith.science (2026). https://pith.science/paper/GGULVQBY

@misc{pith2026250416065,
  author       = {Pith},
  title        = {Pith review of: A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GGULVQBY}},
  note         = {Machine review of arXiv:2504.16065}
}
abstract

The main conceptual contribution of this paper is identifying a previously unnoticed connection between two central problems in computational learning theory and property testing: agnostically learning conjunctions and tolerantly testing juntas. Inspired by this connection, the main technical contribution is a pair of improved algorithms for these two problems. In more detail, - We give a distribution-free algorithm for agnostically PAC learning conjunctions over $\{\pm 1\}^n$ that runs in time $2^{\widetilde{O}(n^{1/3})}$, for constant excess error $\varepsilon$. This improves on the fastest previously published algorithm, which runs in time $2^{\widetilde{O}(n^{1/2})}$ [KKMS08]. - Building on the ideas in our agnostic conjunction learner and using significant additional technical ingredients, we give an adaptive tolerant testing algorithm for $k$-juntas that makes $2^{\widetilde{O}(k^{1/3})}$ queries, for constant "gap parameter" $\varepsilon$ between the "near" and "far" cases. This improves on the best previous results, due to [ITW21, NP24], which make $2^{\widetilde{O}(\sqrt{k})}$ queries. Since there is a known $2^{\widetilde{\Omega}(\sqrt{k})}$ lower bound for non-adaptive tolerant junta testers, our result shows that adaptive tolerant junta testing algorithms provably outperform non-adaptive ones.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 34 canonical work pages

  1. [1]

    Canonne, Talya Eden, Amit Levi, and Dana Ron

    Eric Blais, Cl \' e ment L. Canonne, Talya Eden, Amit Levi, and Dana Ron. Tolerant junta testing and the connection to submodular optimization and function isomorphism. ACM Trans. Comput. Theory , 11(4):24:1--24:33, 2019

    work page 2019

  2. [2]

    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. Chic. J. Theor. Comput. Sci. , 2013, 2013

    work page 2013

  3. [3]

    Improved bounds for testing juntas

    Eric Blais. Improved bounds for testing juntas. In Proc. RANDOM , pages 317--330, 2008

    work page 2008

  4. [4]

    Testing juntas nearly optimally

    Eric Blais. Testing juntas nearly optimally. In Proc.\ 41st Annual ACM Symposium on Theory of Computing (STOC) , pages 151--158, 2009

    work page 2009

  5. [5]

    Self-testing/correcting with applications to numerical problems

    Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences , 47:549--595, 1993. Earlier version in STOC'90

    work page 1993

  6. [6]

    A. Blum. Machine learning: a tour through some favorite results, directions, and open problems. FOCS 2003 tutorial slides, available at http://www-2.cs.cmu.edu/ avrim/Talks/FOCS03/tutorial.ppt, 2003

    work page 2003

  7. [7]

    Jon Louis Bentley and James B. Saxe. Generating sorted lists of random numbers. ACM Transactions on Mathematical Software , 6(3):359--364, September 1980

    work page 1980

  8. [8]

    Nader H. Bshouty. Almost optimal distribution-free junta testing. In Amir Shpilka, editor, 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA , volume 137 of LIPIcs , pages 2:1--2:13. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2019

    work page 2019

Show all 43 references
  1. [9]

    Mildly exponential lower bounds on tolerant testers for monotonicity, unateness, and juntas

    Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, and Rocco A Servedio. Mildly exponential lower bounds on tolerant testers for monotonicity, unateness, and juntas. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 4321--4337. SIAM, 2024

    2024

  2. [10]

    Chockler and D

    H. Chockler and D. Gutfreund. A lower bound for testing juntas. Information Processing Letters , 90(6):301--305, 2004

    2004

  3. [11]

    New lower bounds for adaptive tolerant junta testing

    Xi Chen and Shyamal Patel. New lower bounds for adaptive tolerant junta testing. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1778--1786. IEEE, 2023

    2023

  4. [12]

    Servedio, Li - Yang Tan, Erik Waingarten, and Jinyu Xie

    Xi Chen, Rocco A. Servedio, Li - Yang Tan, Erik Waingarten, and Jinyu Xie. Settling the query complexity of non-adaptive junta testing. J. ACM , 65(6):40:1--40:18, 2018

    2018

  5. [13]

    Learning from satisfying assignments

    Anindya De, Ilias Diakonikolas, and Rocco A Servedio. Learning from satisfying assignments. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms , pages 478--497. SIAM, 2014

    2014

  6. [14]

    Kane, and Lisheng Ren

    Ilias Diakonikolas, Daniel M. Kane, and Lisheng Ren. Faster algorithms for agnostically learning disjunctions and their implications. CoRR , abs/2504.15244, 2025

    2025 arXiv

  7. [15]

    Junta correlation is testable

    Anindya De, Elchanan Mossel, and Joe Neeman. Junta correlation is testable. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019 , pages 1549--1563. IEEE Computer Society, 2019

    2019

  8. [16]

    A complete characterization of statistical query learning with applications to evolvability

    Vitaly Feldman. A complete characterization of statistical query learning with applications to evolvability. Journal of Computer and System Sciences , 78(5):1444--1459, 2012

    2012

  9. [17]

    Fischer, G

    E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky. Testing juntas. J. Computer & System Sciences , 68(4):753--787, 2004

    2004

  10. [18]

    Y. Freund. Boosting a weak learning algorithm by majority. Information and Computation , 121(2):256--285, 1995

    1995

  11. [19]

    Aravind Gollakota, Sushrut Karmalkar, and Adam R. Klivans. The polynomial method is universal for distribution-free correlational SQ learning. CoRR , abs/2010.11925, 2020

    2010 arXiv

  12. [20]

    Haussler

    D. Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications . Information and Computation , 100:78--150, 1992

    1992

  13. [21]

    Hajnal, W

    A. Hajnal, W. Maass, P. Pudlak, M. Szegedy, and G. Turan. Threshold circuits of bounded depth. Journal of Computer and System Sciences , 46:129--154, 1993

    1993

  14. [22]

    Junta distance approximation with sub-exponential queries

    Vishnu Iyer, Avishay Tal, and Michael Whitmeyer. Junta distance approximation with sub-exponential queries. In Valentine Kabanets, editor, 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference) , volume 200 of LIPIcs...

    2021

  15. [23]

    M. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM , 45(6):983--1006, 1998

    1998

  16. [24]

    Agnostically learning halfspaces

    Adam Tauman Kalai, Adam R Klivans, Yishay Mansour, and Rocco A Servedio. Agnostically learning halfspaces. SIAM Journal on Computing , 37(6):1777--1805, 2008

    2008

  17. [25]

    Inclusion-exclusion: Exact and approximate

    Jeff Kahn, Nathan Linial, and Alex Samorodnitsky. Inclusion-exclusion: Exact and approximate. Combinatorica , 16:465--477, 1996

    1996

  18. [26]

    Klivans and R

    A. Klivans and R. Servedio. Learning DNF in time 2^ O (n^ 1/3 ) . Journal of Computer & System Sciences , 68(2):303--318, 2004

    2004

  19. [27]

    Klivans and Alexander A

    Adam R. Klivans and Alexander A. Sherstov. A lower bound for agnostically learning disjunctions. In Conference on Learning Theory (COLT'07) , pages 409--423, 2007

    2007

  20. [28]

    M. J. Kearns, R. E. Schapire, and L. Sellie. Toward Efficient Agnostic Learning . Machine Learning , 17(2-3):115--141, 1994

    1994

  21. [29]

    Linial and N

    N. Linial and N. Nisan. Approximate inclusion-exclusion. Combinatorica , 10(4):349--365, 1990

    1990

  22. [30]

    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 Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA , volume 124 of...

    2019

  23. [31]

    The Confidence-Man: His Masquerade

    Herman Melville. The Confidence-Man: His Masquerade . Dix, Edwards & Co., 1857. Available at https://www.gutenberg.org/files/21816/21816-h/21816-h.htm https://www.gutenberg.org/files/21816/21816-h/21816-h.htm

  24. [32]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information (10th Anniversary edition) . Cambridge University Press, 2016

    2016

  25. [33]

    Optimal non-adaptive tolerant junta testing via local estimators

    Shivam Nadimpalli and Shyamal Patel. Optimal non-adaptive tolerant junta testing via local estimators. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1039--1050, 2024

    2024

  26. [34]

    O'Donnell

    R. O'Donnell. Analysis of Boolean Functions . Cambridge University Press, 2014

    2014

  27. [35]

    R. Paturi. On the degree of polynomials that approximate symmetric B oolean functions . In Proceedings of the 24th Symposium on Theory of Computing , pages 468--474, 1992

    1992

  28. [36]

    Tolerant property testing and distance approximation

    Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. J. Comput. Syst. Sci. , 72(6):1012--1042, 2006

    2006

  29. [37]

    Pallavoor, Sofya Raskhodnikova, and Erik Waingarten

    Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Erik Waingarten. Approximating the distance to monotonicity of boolean functions. Random Struct. Algorithms , 60(2):233--260, 2022

    2022

  30. [38]

    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 Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018 , pages 967--978. IEEE Computer Society, 2018

    2018

  31. [39]

    Schapire

    R. Schapire. The strength of weak learnability. Machine Learning , 5(2):197--227, 1990

    1990

  32. [40]

    Testing by implicit learning: A brief survey

    Rocco A Servedio. Testing by implicit learning: A brief survey. Property testing: current research and surveys , pages 197--210, 2010

    2010

  33. [41]

    Daniel R. Simon. On the power of quantum computation. SIAM J. Comput. , 26(5):1474--1483, 1997

    1997

  34. [42]

    Servedio, L.-Y

    R.A. Servedio, L.-Y. Tan, and J. Wright. Adaptivity helps for testing juntas. In Proceedings of the 30th IEEE Conference on Computational Complexity , pages 264--279, 2015

    2015

  35. [43]

    L. Valiant. A theory of the learnable. Communications of the ACM , 27(11):1134--1142, 1984

    1984

Pith tools

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