Pith Number

pith:FM64FITE

pith:2026:FM64FITEC2PM2CZHJ2754QXYIP

not attested not anchored not stored refs resolved

Statistical two-round search for one excellent element

Jong Sung Kim, Nagananda K G

When finding one excellent element is feasible, two-round search requires only a logarithmic number of tests in the population size.

arxiv:2605.15612 v1 · 2026-05-15 · cs.IT · math.IT · stat.AP

Open paper page JSON Open Graph Bundle Merged state What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{FM64FITEC2PM2CZHJ2754QXYIP}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

When the target success probability is feasible, we prove that the optimal expected number of tests grows logarithmically with the population size. The upper bound is obtained by combining an initial existence test with a second-round separating design; the lower bound follows from an information-counting argument.

C2weakest assumption

The excellence indicators are independent Bernoulli random variables with success probability λ/n, enabling the Poisson regime and the feasibility condition α ≥ e^{-λ}. This modeling choice is introduced in the problem formulation.

C3one line summary

In the sparse Poisson regime, the optimal expected number of two-round tests to identify one excellent element with probability at least 1-α grows logarithmically with n provided α ≥ e^{-λ}.

References

13 extracted · 13 resolved · 0 Pith anchors

[1] Ahlswede, R. and Wegener, I. (1987),Search Problems, John Wiley 1987

[2] (1988),Combinatorial Search, John Wiley and Teubner 1988

[3] (1995),Probability and Measure, 3 edn, Wiley, New York 1995

[4] (2019), ‘Combinatorial search in two and more rounds’,Theoretical Computer Sci- ence780, 1–11 2019

[5] Du, D. and Hwang, F. K. (2000),Combinatorial Group Testing and Its Applications, 2 edn, World Scientific 2000

Receipt and verification

First computed	2026-05-20T00:01:08.151650Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

2b3dc2a264169ecd0b274ebfde42f843ce79d8e15468e8b3177aee2a02cec477

Aliases

arxiv: 2605.15612 · arxiv_version: 2605.15612v1 · doi: 10.48550/arxiv.2605.15612 · pith_short_12: FM64FITEC2PM · pith_short_16: FM64FITEC2PM2CZH · pith_short_8: FM64FITE

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/FM64FITEC2PM2CZHJ2754QXYIP \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 2b3dc2a264169ecd0b274ebfde42f843ce79d8e15468e8b3177aee2a02cec477

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "b1ec7c0b7ffcc698e865411dfd6e9467f9ac457c3a1872f7c0b651aebd001cf9",
    "cross_cats_sorted": [
      "math.IT",
      "stat.AP"
    ],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "primary_cat": "cs.IT",
    "submitted_at": "2026-05-15T04:50:05Z",
    "title_canon_sha256": "f51ec413e49a258d91917acce99fc428442c35cc1451a942ba06b1ff2d0560e5"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.15612",
    "kind": "arxiv",
    "version": 1
  }
}