Reading March

Christian Engels April 27, 2023 [TCS, Communication Complexity]

Paper 1

$u$ defines the unknown state.
A resolution of a string in ${0,1,u}^*$ is a setting of the undefined values to an arbitrary value in ${0,1}$.
We can define $\bar f(\alpha)$ to be $0$ or $1$ if the value for all resolutions is zero or one. Otherwise it is defined as $u$.
A circuit is called hazard free if $C(\alpha)=\bar f(\alpha)$ for all $\alpha \in {0,1,u}^n$.
Define $MUX_n(s_1,\dots,s_n, x_{0,0,...,0},\dots, x_{1,...,1})=x_{s_1,\dots,s_n}$.
They give an exact bound on the size of the hazard free circuit for MUX$_n$.
$size(MUX_n)=23^n -1$.
They use Karchmer Wigderson game on subcube intersection game for this.
Define $d f(x;y)=1$ if and only if $\bar f(x\oplus u \cdot y)=u$, meaning there is a resolution to one and one to zero.
For any hazard free circuit and any boolean string $a$, we can construct a monotone circuit for $df(a;y)$. Hence, this gives us lower bounds.

Alice has $a$ with $f(a)=1$ and Bob has $b$ with $f(b)=0$. Find a coordinate such that $a_i\neq b_i$.
Their extension: Alice gets $\alpha$, Bob $\beta$ with $\bar f(\alpha)=1$, $\bar f(\beta)=0$. Determine a coordinate such that $\alpha_i\neq \beta_i$ and $\alpha_i\neq u$, $\beta_i\neq u$.
A prime implicant is an $\alpha \in f^{-1}(1)$ such that no value from ${0,1}$ can be replaced by an $u$.
Elements in $f^{-1}(0)$ are called implicates.
It is enough to look at the implicants and implicates as inputs to the game.
- By flipping stable bits, we get the opposite, hence, it is enough for Alice and Bob.
For a monotone function, the complexity between the extension game and the monotone game are the same.
- This is easy to see. Alice flips $u$s up (to 1) and Bob down. Because of monotonicity the value is the still the same.
The Multiplexer function is now an obvious candidate.