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 |