Subadditivity in t for all-symbol PIR and batch codes

Let ASP(k,t,q)ASP(k,t,q) and ASB(k,t,q)ASB(k,t,q) denote the minimum lengths of, respectively, all-symbol PIR and all-symbol batch codes with parameters k,t,qk,t,q. For all k,qk,q and t1,t21t_1,t_2\geq 1, Subadditivity in tt.

ASP(k,t1+t2,q)ASP(k,t1,q)+ASP(k,t2,q),ASP(k,t_1+t_2,q)\leq ASP(k,t_1,q)+ASP(k,t_2,q), ASB(k,t1+t2,q)ASB(k,t1,q)+ASB(k,t2,q).ASB(k,t_1+t_2,q)\leq ASB(k,t_1,q)+ASB(k,t_2,q).

The claim extends the known subadditivity results for functional PIR and batch codes; the paper notes that the corresponding general statement for all-symbol parameters remains open.

Sources & referencesView supporting material

Primary source

Avital Boruchovsky, Anina Gruica, Jonathan Niemann and Eitan Yaakobi, “Serving Every Symbol: All-Symbol PIR and Batch Codes”, arXiv:2601.04041 (2026).

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.