Joseph Halpern Publishes “Information Acquisition Under Resource Limitations in a Noisy Environment”

01 Feb 2018

CHAI’s Joseph Halpern and his colleague Matvey Soloviev at Cornell University published this paper in Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), 2018. The abstract reads:

We introduce a theoretical model of information acquisition under resource limitations in a noisy environment. An agent must guess the truth value of a given Boolean formula ϕ after performing a bounded number of noisy tests of the truth values of variables in the formula. We observe that, in general, the problem of finding an optimal testing strategy for ϕ is hard, but we suggest a useful heuristic. The techniques we use also give insight into two apparently unrelated, but well-studied problems: (1) rational inattention (the optimal strategy may involve hardly ever testing variables that are clearly relevant to ϕ) and (2) what makes a formula hard to learn/remember.