AND testing and robust judgement aggregation
© 2020 ACM. A function fg¶{0,1}n→ {0,1} is called an approximate AND-homomorphism if choosing x,ygn uniformly at random, we have that f(xg§ y) = f(x)g§ f(y) with probability at least 1-ϵ, where xg§ y = (x1g§ y1,...,xng§ yn). We prove that if fg¶ {0,1}n → {0,1} is an approximate AND-homomorphism, the...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
ACM
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137503 |
| _version_ | 1811078490008584192 |
|---|---|
| author | Filmus, Yuval Lifshitz, Noam Minzer, Dor Mossel, Elchanan |
| author_facet | Filmus, Yuval Lifshitz, Noam Minzer, Dor Mossel, Elchanan |
| author_sort | Filmus, Yuval |
| collection | MIT |
| description | © 2020 ACM. A function fg¶{0,1}n→ {0,1} is called an approximate AND-homomorphism if choosing x,ygn uniformly at random, we have that f(xg§ y) = f(x)g§ f(y) with probability at least 1-ϵ, where xg§ y = (x1g§ y1,...,xng§ yn). We prove that if fg¶ {0,1}n → {0,1} is an approximate AND-homomorphism, then f is -close to either a constant function or an AND function, where (ϵ) → 0 as ϵ→ 0. This improves on a result of Nehama, who proved a similar statement in which δdepends on n. Our theorem implies a strong result on judgement aggregation in computational social choice. In the language of social choice, our result shows that if f is ϵ-close to satisfying judgement aggregation, then it is (ϵ)-close to an oligarchy (the name for the AND function in social choice theory). This improves on Nehama's result, in which δdecays polynomially with n. Our result follows from a more general one, in which we characterize approximate solutions to the eigenvalue equation f = λ g, where is the downwards noise operator f(x) = y[f(x g§ y)], f is [0,1]-valued, and g is {0,1}-valued. We identify all exact solutions to this equation, and show that any approximate solution in which f and λ g are close is close to an exact solution. |
| first_indexed | 2024-09-23T11:00:47Z |
| format | Article |
| id | mit-1721.1/137503 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:00:47Z |
| publishDate | 2021 |
| publisher | ACM |
| record_format | dspace |
| spelling | mit-1721.1/1375032022-09-27T16:30:08Z AND testing and robust judgement aggregation Filmus, Yuval Lifshitz, Noam Minzer, Dor Mossel, Elchanan © 2020 ACM. A function fg¶{0,1}n→ {0,1} is called an approximate AND-homomorphism if choosing x,ygn uniformly at random, we have that f(xg§ y) = f(x)g§ f(y) with probability at least 1-ϵ, where xg§ y = (x1g§ y1,...,xng§ yn). We prove that if fg¶ {0,1}n → {0,1} is an approximate AND-homomorphism, then f is -close to either a constant function or an AND function, where (ϵ) → 0 as ϵ→ 0. This improves on a result of Nehama, who proved a similar statement in which δdepends on n. Our theorem implies a strong result on judgement aggregation in computational social choice. In the language of social choice, our result shows that if f is ϵ-close to satisfying judgement aggregation, then it is (ϵ)-close to an oligarchy (the name for the AND function in social choice theory). This improves on Nehama's result, in which δdecays polynomially with n. Our result follows from a more general one, in which we characterize approximate solutions to the eigenvalue equation f = λ g, where is the downwards noise operator f(x) = y[f(x g§ y)], f is [0,1]-valued, and g is {0,1}-valued. We identify all exact solutions to this equation, and show that any approximate solution in which f and λ g are close is close to an exact solution. 2021-11-05T15:04:00Z 2021-11-05T15:04:00Z 2020 2021-05-25T12:26:19Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137503 Filmus, Yuval, Lifshitz, Noam, Minzer, Dor and Mossel, Elchanan. 2020. "AND testing and robust judgement aggregation." Proceedings of the Annual ACM Symposium on Theory of Computing. en 10.1145/3357713.3384254 Proceedings of the Annual ACM Symposium on Theory of Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf ACM arXiv |
| spellingShingle | Filmus, Yuval Lifshitz, Noam Minzer, Dor Mossel, Elchanan AND testing and robust judgement aggregation |
| title | AND testing and robust judgement aggregation |
| title_full | AND testing and robust judgement aggregation |
| title_fullStr | AND testing and robust judgement aggregation |
| title_full_unstemmed | AND testing and robust judgement aggregation |
| title_short | AND testing and robust judgement aggregation |
| title_sort | and testing and robust judgement aggregation |
| url | https://hdl.handle.net/1721.1/137503 |
| work_keys_str_mv | AT filmusyuval andtestingandrobustjudgementaggregation AT lifshitznoam andtestingandrobustjudgementaggregation AT minzerdor andtestingandrobustjudgementaggregation AT mosselelchanan andtestingandrobustjudgementaggregation |