Theoretical Possibilities and Limits of Efficient Corruption Detection in Multi-Agents

This work initiates a theoretical study of the query and communication complexity of detecting a corrupted matrix via queries in the form of linear probes. This is inspired by corruption detection in multi-agents, since reliable multi-agent systems need to detect changes in worker behavior without exchanging complete models or exhaustive output tables. We establish matching upper and lower bounds for query and total communication bits using deterministic and private randomized protocols, both for verifying a single worker and for identifying a corrupted worker in a complete network. These results confirm the possibility of detection with efficient query and communication. In particular, we show that randomization can yield an exponential improvement over deterministic ones and thus achieve efficient query bounds. Our results provide a theoretical foundation for verification mechanisms in multi-agent systems.