pith. sign in

arxiv: 2401.16540 · v2 · submitted 2024-01-29 · 💻 cs.IT · math.IT

Improved Probabilistic Lower Bounds for Separable Matrices

Daniil Goshkoder , Nikita Polyanskii , Ilya Vorobyev This is my paper

Pith reviewed 2026-05-24 04:40 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords separable matriceslist-decoding separable matricescombinatorial group testingnon-adaptive identificationprobabilistic methodrate lower boundsd defectivesdisjunctive matrices
0
0 comments X

The pith

New probabilistic lower bounds improve achievable rates for separable matrices identifying up to d defectives.

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

The paper derives improved lower bounds on the rates of d-separable matrices, bar-d separable matrices, and their list-decoding variants with list size n to the power 1/d. These bounds apply for any number of defectives d at least 3 and cover both cases where d is known in advance and where it is not. The bounds are obtained via the probabilistic method, establishing the existence of matrices that allow non-adaptive identification of defectives with linear decoding complexity using fewer tests relative to the number of elements than previously shown.

Core claim

By applying the probabilistic method to randomly chosen matrices and using union bounds or concentration, the authors establish new lower bounds on the rates of d-SM, bar d-SM, (d, n^{1/d})-LDSM, and (bar d, n^{1/d})-LDSM for d >= 3.

What carries the argument

The probabilistic method applied to random matrix selection to prove existence of matrices meeting the separability or list-decodability conditions.

If this is right

  • d-SM achieve higher rates than prior lower bounds when the number of defectives is known.
  • bar d-SM achieve improved rates when the exact number of defectives up to d is unknown.
  • (d, n^{1/d})-LDSM allow linear-time decoding with better rates when d is known.
  • (bar d, n^{1/d})-LDSM provide improved rates for list-decoding when d is unknown.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The improved bounds may help narrow the gap to information-theoretic upper bounds on matrix rates in group testing.
  • Similar probabilistic techniques could extend to threshold testing or other matrix-based identification problems.
  • Explicit constructions based on these existence results might be developed for practical use.

Load-bearing premise

The assumption that the probabilistic method applied to random matrices yields a positive probability of satisfying the matrix properties for the claimed rates.

What would settle it

An explicit upper bound on the rate of d-SM or (d, n^{1/d})-LDSM that is strictly smaller than the new lower bound for some fixed d >= 3 and sufficiently large n would disprove the claim.

read the original abstract

This work focuses on non-adaptive combinatorial group testing, with a primary goal of efficiently identifying a set of at most $d$ defective elements among a given set of $n$ elements using the fewest possible tests. Non-adaptive combinatorial group testing often employs disjunctive matrices (DM) and separable matrices (SM). This paper discusses separable matrices and recently introduced list-decoding separable matrices (LDSM) with list size $n^{1/d}$, which allow for non-adaptive identification of defectives with the decoding complexity linear in the number of tests and the number of elements. In our study, we distinguish two subclasses of these matrices: matrices which can be used when the number of defectives $d$ is a priori known ($d$-SM and $(d, n^{1/d})$-LDSM), and matrices which can be used for any subset of at most $d$ defectives ($\bar{d}$-SM and $(\bar{d}, n^{1/d})$-LDSM). Our contribution lies in deriving new lower bounds on the rates of $d$-SM, $\bar{d}$-SM, $(d, n^{1/d})$-LDSM and $(\bar{d}, n^{1/d})$-LDSM for an arbitrary number $d \ge 3$ of defectives.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper derives new lower bounds via the probabilistic method on the achievable rates of d-SM and bar d-SM (separable matrices for known and unknown numbers of defectives) as well as the corresponding (d, n^{1/d})-LDSM and (bar d, n^{1/d})-LDSM variants, for arbitrary d >= 3, in the setting of non-adaptive combinatorial group testing.

Significance. If the claimed improvements hold, the results would tighten existence guarantees for these matrix families, supporting more efficient non-adaptive identification schemes with linear decoding complexity. The probabilistic-method approach is standard for such existence statements, and explicit rate improvements for both known-d and unknown-d cases would be a useful addition to the group-testing literature.

minor comments (2)
  1. [Abstract] Abstract: a short quantitative comparison (e.g., the multiplicative improvement factor over the best prior bound) would help readers immediately gauge the contribution.
  2. [Introduction] Notation for the four matrix classes should be introduced with a single consolidated definition table or paragraph early in the introduction to avoid scattered references.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review and recommendation to accept the manuscript. No major comments were raised, so no changes are required.

Circularity Check

0 steps flagged

No significant circularity; probabilistic existence proofs are self-contained

full rationale

The paper's central contribution is new lower bounds on rates for d-SM, bar d-SM, (d, n^{1/d})-LDSM and (bar d, n^{1/d})-LDSM derived via the probabilistic method: random selection of matrices followed by union bound or concentration to certify existence for d >= 3. No step reduces by construction to a fitted parameter renamed as prediction, a self-definitional loop, or a load-bearing self-citation chain. The derivation relies on standard probabilistic arguments that are independent of the specific rate values obtained and do not invoke uniqueness theorems or ansatzes from prior author work. This is the normal, non-circular case for existence proofs in combinatorial search theory.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard definitions of separable and list-decoding separable matrices together with the applicability of the probabilistic method to establish existence.

axioms (2)
  • domain assumption Standard definitions of d-SM, bar d-SM, (d, n^{1/d})-LDSM and (bar d, n^{1/d})-LDSM from combinatorial group testing literature.
    Invoked to state the objects whose rates are bounded.
  • domain assumption Probabilistic method yields existence of matrices satisfying the separability properties at the claimed rates.
    Core technique used to obtain the lower bounds.

pith-pipeline@v0.9.0 · 5765 in / 1294 out tokens · 29581 ms · 2026-05-24T04:40:07.060307+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

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

  1. Sharp bounds for uniform union-free hypergraphs

    math.CO 2026-05 unverdicted novelty 8.0

    The extremal function U_t(n,r) has its asymptotic order determined up to lower-order terms for almost all t,r ≥ 3.

  2. Sharp bounds for uniform union-free hypergraphs

    math.CO 2026-05 unverdicted novelty 8.0

    U_t(n,r) is asymptotically determined up to lower-order terms for almost all t,r >=3.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    The detection of defective members of large populations,

    R. Dorfman, “The detection of defective members of large populations,” The Annals of mathematical statistics , vol. 14, no. 4, pp. 436–440, 1943

    work page 1943

  2. [2]

    Pooled testing and its applica tions in the covid-19 pandemic,

    M. Aldridge and D. Ellis, “Pooled testing and its applica tions in the covid-19 pandemic,” Pandemics: Insurance and Social Protection , pp. 217–249, 2022

    work page 2022

  3. [3]

    D. Du, F. K. Hwang, and F. Hwang, Combinatorial group testing and its applications . World Scientific, 2000, vol. 12

    work page 2000

  4. [4]

    Group testing: an information theory perspective,

    M. Aldridge, O. Johnson, J. Scarlett et al. , “Group testing: an information theory perspective,” F oundations and Trends® in Communications and Information Theory , vol. 15, no. 3-4, pp. 196–392, 2019

    work page 2019

  5. [5]

    Lectures on designing screening experim ents, com2mac lect,

    A. D’yachkov, “Lectures on designing screening experim ents, com2mac lect,” Note Ser , vol. 10

    work page

  6. [6]

    Cicalese et al

    F. Cicalese et al. , Fault-Tolerant Search Algorithms. Springer, 2013

    work page 2013

  7. [7]

    Nonrandom binary superimpos ed codes,

    W. Kautz and R. Singleton, “Nonrandom binary superimpos ed codes,” IEEE Transactions on Information Theory , vol. 10, no. 4, pp. 363–377, 1964

    work page 1964

  8. [8]

    Lectures on Designing Screening Experiments

    A. G. D’yachkov, “Lectures on designing screening exper iments,” arXiv preprint arXiv:1401.7505 , 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  9. [9]

    Superimposed di stance codes,

    A. G. Dyachkov, V . Rykov, and A. Rashad, “Superimposed di stance codes,” Problems of Control and Information Theory-problemy Uprav leniya i Teorii Informatsii, vol. 18, no. 4, pp. 237–250, 1989

    work page 1989

  10. [10]

    Bounds on the length of d isjunctive codes,

    A. G. D’yachkov and V . V . Rykov, “Bounds on the length of d isjunctive codes,” Problemy Peredachi Informatsii, vol. 18, no. 3, pp. 7–13, 1982

    work page 1982

  11. [11]

    Strongl y separable matrices for nonadaptive combinatorial group t esting,

    J. Fan, H.-L. Fu, Y . Gu, Y . Miao, and M. Shigeno, “Strongl y separable matrices for nonadaptive combinatorial group t esting,” Discrete Applied Mathematics, vol. 291, pp. 180–187, 2021

    work page 2021

  12. [12]

    Fast decoding of union-free codes,

    I. V orobyev, “Fast decoding of union-free codes,” in 2021 XVII International Symposium" Problems of Redundancy in Information and Control Systems"(REDUNDANCY). IEEE, 2021, pp. 106–109

    work page 2021

  13. [13]

    New bounds for union- free families of sets,

    D. Coppersmith and J. B. Shearer, “New bounds for union- free families of sets,” the electronic journal of combinatorics , vol. 5, no. 1, p. R39, 1998

    work page 1998

  14. [14]

    Effici ent algorithms for noisy group testing,

    S. Cai, M. Jahangoshahi, M. Bakshi, and S. Jaggi, “Effici ent algorithms for noisy group testing,” IEEE Transactions on Information Theory , vol. 63, no. 4, pp. 2113–2136, 2017

    work page 2017

  15. [15]

    On the optimality of the kautz-singleton construction in probabi listic group testing,

    H. A. Inan, P . Kairouz, M. Wootters, and A. Özgür, “On the optimality of the kautz-singleton construction in probabi listic group testing,” IEEE Transactions on Information Theory , vol. 65, no. 9, pp. 5592–5603, 2019

    work page 2019

  16. [16]

    Saffron: A fast, efficient, and robust framework for gr oup testing based on sparse-graph codes,

    K. Lee, K. Chandrasekher, R. Pedarsani, and K. Ramchand ran, “Saffron: A fast, efficient, and robust framework for gr oup testing based on sparse-graph codes,” IEEE Transactions on Signal Processing , vol. 67, no. 17, pp. 4649–4664, 2019

    work page 2019

  17. [17]

    A fast binary splitting appro ach to non-adaptive group testing,

    E. Price and J. Scarlett, “A fast binary splitting appro ach to non-adaptive group testing,” arXiv preprint arXiv:2006.10268 , 2020

    work page arXiv 2006

  18. [18]

    Combinatorial group testi ng and sparse recovery schemes with near-optimal decoding t ime,

    M. Cheraghchi and V . Nakos, “Combinatorial group testi ng and sparse recovery schemes with near-optimal decoding t ime,” in 2020 IEEE 61st Annual Symposium on F oundations of Computer Science (FOCS) . IEEE, 2020, pp. 1203–1213

    work page 2020

  19. [19]

    Optimal group testing,

    A. Coja-Oghlan, O. Gebhard, M. Hahn-Klimroth, and P . Lo ick, “Optimal group testing,” in Conference on Learning Theory . PMLR, 2020, pp. 1374–1388

    work page 2020

  20. [20]

    Sub linear-time non-adaptive group testing with o (k log n) test s via bit-mixing coding,

    S. Bondorf, B. Chen, J. Scarlett, H. Y u, and Y . Zhao, “Sub linear-time non-adaptive group testing with o (k log n) test s via bit-mixing coding,” IEEE Transactions on Information Theory , vol. 67, no. 3, pp. 1559–1570, 2020

    work page 2020

  21. [21]

    Quickly-deco dable group testing with fewer tests: Price–scarlett’s non adaptive splitting with explicit scalars,

    H.-P . Wang, R. Gabrys, and V . Guruswami, “Quickly-deco dable group testing with fewer tests: Price–scarlett’s non adaptive splitting with explicit scalars,” in 2023 IEEE International Symposium on Information Theory (I SIT). IEEE, 2023, pp. 1609–1614

    work page 2023

  22. [22]

    Group test ing algorithms: Bounds and simulations,

    M. Aldridge, L. Baldassini, and O. Johnson, “Group test ing algorithms: Bounds and simulations,” IEEE Transactions on Information Theory , vol. 60, no. 6, pp. 3671–3687, 2014

    work page 2014

  23. [23]

    A survey of superimposed code theory,

    A. G. Dyachkov and V . V . Rykov, “A survey of superimposed code theory,” Problems of Control and Information Theory , vol. 12, no. 4, pp. 1–13, 1983

    work page 1983

  24. [24]

    Families of finite se ts in which no set is covered by the union of two others,

    P . Erdös, P . Frankl, and Z. Füredi, “Families of finite se ts in which no set is covered by the union of two others,” Journal of Combinatorial Theory, Series A , vol. 33, no. 2, pp. 158–166, 1982

    work page 1982

  25. [25]

    Almost disjunctive list-decoding codes,

    A. G. D’yachkov, I. V . V orob’ev, N. Polyansky, and V . Y . S hchukin, “Almost disjunctive list-decoding codes,” Problems of Information Transmission , vol. 51, pp. 110–131, 2015

    work page 2015

  26. [26]

    Bounds on constant weight binary superimpos ed codes

    A. Quang, “Bounds on constant weight binary superimpos ed codes.” Problems Control Inf. Theory. , vol. 17, no. 4, pp. 223–230, 1988

    work page 1988

  27. [27]

    On the upper bound of the size of the r-cove r-free families,

    M. Ruszinkó, “On the upper bound of the size of the r-cove r-free families,” Journal of Combinatorial Theory, Series A , vol. 66, no. 2, pp. 302–310, 1994

    work page 1994

  28. [28]

    On r-cover-free families,

    Z. Füredi, “On r-cover-free families,” Journal of Combinatorial Theory, Series A , vol. 73, no. 1, pp. 172–173, 1996

    work page 1996