1
vote
3answers
186 views

Complete sets of functions

A (finite) set $S$ of boolean functions is called functionally complete if every boolean function can be presented as a finite composition of functions from $S$. For example, $\{ \neg,\wedge \}$ is ...
0
votes
1answer
191 views

Low degree approximation of the polynomial extension of the logical-or function

Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$). Consider ...