Tata Institute of Fundamental Research
Approximate Polymorphisms
STCS Student Seminar
Speaker:
Nitin Saurabh (Technion-IIT, Haifa, Israel)
Date:
Friday, 18 Jun 2021, 17:15 to 18:15
Venue:
(Scan to add to calendar)
Abstract:
A Boolean function f on n variables is called a polymorphism of another Boolean function g on m variables if their operations commute. That is, for all {0,1}-matrix Z of dimension (n x m), f(g(row1(Z)), g(row2(Z)), ..., g(rown(Z))) = g(f(col1(Z)), f(col2(Z)), ...,f(colm(Z))). The function f is called an approximate polymorphism if this equality holds with probability close to 1 when Z is sampled uniformly.
The problem of characterizing the structure of exact or approximate polymorphisms appears in several different contexts, namely in understanding the complexity of CSPs, property testing, and social choice theory.
In this talk, we will give a characterization of exact polymorphisms, and also show that approximate polymorphisms must be close to exact polymorphisms. Our results generalize the classical linearity testing result of Blum et al. as well as the recent AND testing result of Filmus et al.
This is based on a joint work with Gilad Chase, Yuval Filmus and Dor Minzer.
Zoom link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09
| Speaker: | Nitin Saurabh (Technion-IIT, Haifa, Israel) |
| Date: | Friday, 18 Jun 2021, 17:15 to 18:15 |
| Venue: |
(Scan to add to calendar)
Abstract:
A Boolean function f on n variables is called a polymorphism of another Boolean function g on m variables if their operations commute. That is, for all {0,1}-matrix Z of dimension (n x m), f(g(row1(Z)), g(row2(Z)), ..., g(rown(Z))) = g(f(col1(Z)), f(col2(Z)), ...,f(colm(Z))). The function f is called an approximate polymorphism if this equality holds with probability close to 1 when Z is sampled uniformly.
The problem of characterizing the structure of exact or approximate polymorphisms appears in several different contexts, namely in understanding the complexity of CSPs, property testing, and social choice theory.
In this talk, we will give a characterization of exact polymorphisms, and also show that approximate polymorphisms must be close to exact polymorphisms. Our results generalize the classical linearity testing result of Blum et al. as well as the recent AND testing result of Filmus et al.
This is based on a joint work with Gilad Chase, Yuval Filmus and Dor Minzer.
Zoom link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09
The problem of characterizing the structure of exact or approximate polymorphisms appears in several different contexts, namely in understanding the complexity of CSPs, property testing, and social choice theory.
In this talk, we will give a characterization of exact polymorphisms, and also show that approximate polymorphisms must be close to exact polymorphisms. Our results generalize the classical linearity testing result of Blum et al. as well as the recent AND testing result of Filmus et al.
This is based on a joint work with Gilad Chase, Yuval Filmus and Dor Minzer.
Zoom link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09