Maximizing Truth Learning in a Social Network is NP-hard

This paper is a continuation of my work at REU 2024.

We look at the problem of truth learning with unreliable information in a social network. We analyze the complexity of deciding how well a given network can learn. We reach the conclusion that this problem is in fact NP-hard. For more information, see the REU website.

This paper was written by me and Amanda Wang with equal contribution, and by Jie Gao. It was accepted to the 24th International Conference on Autonomous Agents and Multi-Agent Systems in Detroit, United States.

This paper is currently available as a preprint at arXiv.