One-sided linearity testing
Yuval Filmus ( Technion - Israel Institute of Technology )
- 14:00 27th September 2019 ( week -2, Michaelmas Term 2019 )Lecture Theatre B, Wolfson Building
A classical property testing result states that if a Boolean function f satisfies f(x XOR y) = f(x) XOR f(y) for most inputs x,y, then f is close to an XOR. Prompted by an application to approximate judgment aggregation, we discuss what happens when replacing XOR with AND. The solution involves a one-sided analog of the familiar noise operator of Boolean Function Analysis.
Joint work with Noam Lifshitz, Dor Minzer, and Elchanan Mossel.
Share this:
