An Improved Dictatorship Test with Perfect Completeness

Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari

A Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is called a dictator if it depends on exactly one variable i.e $f(x_1,x_2,\dots ,x_n)=x_i$ for some $i\in [n]$. In this wor…