Combinatorial Bounds for List Recovery via Discrete Brascamp-Lieb Inequalities

Proceedings of the 58th Annual ACM Symposium on Theory of Computing 2026 Open access

Read full text
Authors: Joshua Brakensiek, Yeyuan Chen, Manik Dhar, Zihan Zhang
DOI: 10.1145/3798129.3800756
Cited by: 0
References: 65

Abstract

In coding theory, the problem of list recovery asks one to find all codewords c of a given code C which such that at least 1−ρ fraction of the symbols of c lie in some predetermined set of ℓ symbols for each coordinate of the code. A key question is bounding the maximum possible list size L of such codewords for the given code C.

Fields of Study & Subjects

Bayesian Modeling and Causal Inference Data Management and Algorithms Multi-Criteria Decision Making

Publication details

Journal / source
Proceedings of the 58th Annual ACM Symposium on Theory of Computing
Publisher
ACM
Pages
365–376
Publication date
9 June 2026