Compilation complexity
Compilation complexity is the smallest number of bits required to summarize a input to a function, such that the output of the function can be computed correctly. The notion was particulatly studied in voting theory.[1] Often, a group has to accept a decision, but some of the voters have not arrived yet. It is desired to take the votes of the present voters and summarize them such that, when the other voters arrive, we can determine the winner. The compilation complexity of a voting-rule is the smallest number of bits required for the summary.
References
See also
- ^ https://dl.acm.org/doi/abs/10.5555/1661445.1661462
- ^ Xia, Lirong; Conitzer, Vincent (2010-07-04). "Compilation Complexity of Common Voting Rules". Proceedings of the AAAI Conference on Artificial Intelligence. 24 (1): 915–920. doi:10.1609/aaai.v24i1.7627. ISSN 2374-3468.
- ^ Karia, Neel; Lang, Jérôme (2021-05-18). "Compilation Complexity of Multi-Winner Voting Rules (Student Abstract)". Proceedings of the AAAI Conference on Artificial Intelligence. 35 (18): 15809–15810. doi:10.1609/aaai.v35i18.17901. ISSN 2374-3468.