Yao's two-probe implicit membership problem

How large an element universe can be supported in a table of size n using only two probes to decide set membership without storing pointers or auxiliary data?

Sep 23, 2026

Polynomial upper bound for two-probe implicit membership

Model / AI: ChatGPT 5.5 Pro

self-reported (bound improvement)

Songhua He establishes the first quantitative improvement in 45 years to Andrew Yao's 1981 Ramsey-theoretic bounds for implicit data structures, decreasing the two-probe universe threshold from a tower of exponentials to O(n^2 (log n)^2). The author notes that the core proofs were generated by ChatGPT 5.5 Pro without mathematical hints and then validated and edited by the author.

Source read 2026-10-08. Read the arXiv v1 abstract, main theorems, and AI-generation statement. The combinatorial arguments were not re-derived.

Paper — Paper