Stasys Jukna

We consider a general model of monotone circuits, which

we call d-local. In these circuits we allow as gates:

(i) arbitrary monotone Boolean functions whose minterms or

maxterms (or both) have length at most <i>d</i>, and

(ii) arbitrary real-valued non-decreasing functions on ...
more >>>

Dmitry Sokolov

In 1990 Karchmer and Widgerson considered the following communication problem $Bit$: Alice and Bob know a function $f: \{0, 1\}^n \to \{0, 1\}$, Alice receives a point $x \in f^{-1}(1)$, Bob receives $y \in f^{-1}(0)$, and their goal is to find a position $i$ such that $x_i \neq y_i$. Karchmer ... more >>>