The optimal functional 2s12^{s-1}-batch code conjecture

A functional kk-batch code of dimension ss consists of servers storing linear combinations of ss linearly independent information bits, with every multiset of kk linear combinations recoverable from disjoint subsets of servers. Let FB(s,k)FB(s,k) be the minimum number of servers in such a code.

Optimal functional 2s12^{s-1}-batch code conjecture. For any ss,

FB(s,2s1)=2s1.FB(s,2^{s-1})=2^s-1.

This asserts that the minimum number of servers for k=2s1k=2^{s-1} is exactly the number of nonzero vectors in F2s\mathbb{F}_2^s. The source presents it as open; the subsequent pairing result is an approach toward this conjecture.

Sources & referencesView supporting material

Primary source

Lev Yohananov and Isaac Barouch Essayag, “Optimal Functional 2^s-1-Batch Codes: Exploring New Sufficient Conditions”, arXiv:2501.11122 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.