Preguntas etiquetadas con boolean-functions

11
Dado

Aquí hay un problema con un sabor similar al de las juntas de aprendizaje: Entrada: Una función f:{0,1}n→{−1,1}f:{0,1}n→{−1,1}f: \{0,1\}^n \rightarrow \{-1,1\} , representada por un oráculo de membresía, es decir, un oráculo que dado xxx , devuelve f(x)f(x)f(x) . Objetivo: encontrar un subcubo...

10
Representando la función booleana por un polinomio

Supongamos que tenemos una función booleana de . Está claro que un polinomio multivariado real p ( x ) tal que f ( x ) = p ( x ) en x ∈ { 0 , 1 } n puede ser multilineal. ¿Cuáles son algunas clases interesantes de funciones booleanas para las cuales el grado mínimo de p ( x )F: { 0 , 1 }norte→ { 0...

9
La entropía de una distribución ruidosa.

Digamos que tenemos una función tal que ∀ x ∈ Z n 2f:Zn2→Rf:Z2n→Rf:\mathbb{Z}_2^n \to \mathbb{R} yfes una distribución, es decir,Σx∈Z n 2 f(x)=1.∀x∈Zn2f(x)∈{12n,22n,…,2n2n},∀x∈Z2nf(x)∈{12n,22n,…,2n2n},\forall x\in \mathbb{Z}_2^n \quad f(x) \in \left\{\frac{1}{2^n}, \frac{2}{2^n}, \ldots,...