Preguntas sobre las funciones booleanas y su análisis.
A lo largo de los años, me he acostumbrado a ver muchos teoremas de TCS probados mediante análisis discreto de Fourier. La transformación de Walsh-Fourier (Hadamard) es útil en prácticamente todos los subcampos de TCS, incluidas las pruebas de propiedad, pseudoaleatoriedad, complejidad de...
Hace unos años, Joel Friedman realizó algunos trabajos relacionados con los límites del circuito inferior a la cohomología de Grothendieck (ver documentos: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024 ) ¿Esta línea de pensamiento ha aportado nuevas ideas sobre la complejidad...
Sea fff una función booleana y pensemos en f como una función desde {−1,1}n{−1,1}n\{-1,1\}^n hasta . En este lenguaje, la expansión de Fourier de f es simplemente la expansión de f en términos de monomios libres cuadrados. (Estos monomios forman una base para el espacio de funciones reales en . La...
Una máquina PHPHPH tiene acceso oracle a una función booleana aleatoria f:{0,1}n→{−1,1}f:{0,1}n→{−1,1}f:\{0,1\}^n \to \{ -1,1 \} y dos espectros de Fourier ggg y hhh . El espectro de Fourier de una función fff se define como F:{0,1}n→RF:{0,1}n→RF:\{0,1\}^n \to R
La prueba reciente e increíblemente hábil de la conjetura de la sensibilidad se basa en la construcción explícita * de una matriz , definida recursivamente de la siguiente manera: y, para , En particular, es fácil ver que para todo .An∈{−1,0,1}2n×2nAn∈{−1,0,1}2n×2nA_n\in\{-1,0,1\}^{2^n\times...
Los últimos meses comencé a darme conferencias sobre la elección social, el teorema de la flecha y los resultados relacionados. Después de leer sobre los resultados seminales, me pregunté qué sucede con las preferencias de orden parcial, la respuesta está en el documento de Pini et al. : Agregando...
El estado de nuestro conocimiento sobre los circuitos aritméticos generales parece ser similar al estado de nuestro conocimiento sobre los circuitos booleanos, es decir, no tenemos buenos límites inferiores. Por otro lado, tenemos límites inferiores de tamaño exponencial para circuitos booleanos...
¿Hay una manera (razonable) de muestrear una función booleana uniformemente aleatoria cuyo grado como polinomio real es como máximo ?df:{0,1}n→{0,1}f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\}ddd EDITAR: Nisan y Szegedy han demostrado que una función de grado depende a lo sumo de las coordenadas , por lo...
Una propiedad básica de los espacios vectoriales es que un espacio vectorial de dimensión n - d puede caracterizarse por d restricciones lineales linealmente independientes, es decir, existen d vectores linealmente independientes w 1 , ... , w d ∈ F n 2 que son ortogonales a V .V⊆Fn2V⊆F2nV...
¿Todas las funciones cuyo peso de Fourier se concentra en los conjuntos de tamaño pequeño (o términos con bajo grado) se calculan mediante circuitos
¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational? Supongo que no es posible, y que esto está relacionado de alguna manera con el...
XORification es la técnica para hacer que una función o fórmula booleana sea más difícil al reemplazar cada variable por el XOR de k ≥ 2 variables distintas x 1 ⊕ ... ⊕ x k . xxxk≥2k≥2k\geq 2x1⊕…⊕xkx1⊕…⊕xkx_1 \oplus \ldots \oplus x_k Soy consciente de los usos de esta técnica en la complejidad de...
Parte del trabajo sobre la sensibilidad frente a la sensibilidad del bloque se ha dirigido a examinar funciones con un espacio lo más amplio posible entre y para resolver la conjetura de que solo es polinomialmente más grande que . ¿Qué pasa con la dirección opuesta? ¿Qué se sabe sobre las...
Decimos que una función booleana f : { 0 , 1 } n → { 0 , 1 }f:{0,1}n→{0,1}f: \{0,1\}^n \to \{0,1\} es una kkk -junta si fff tiene como máximo kkk variables de influencia. Sea f : { 0 , 1 } n → { 0 , 1 }f:{0,1}n→{0,1}f: \{0,1\}^n \to \{0,1\} ser un 2 k2k2k -junta. Denote las variables de fff por x...
En un problema en el que estoy trabajando actualmente, surge una extensión del operador de ruido de forma natural, y tenía curiosidad por saber si ha habido trabajo previo. Primero permítanme revisar el operador de ruido básico en funciones booleanas de valor real. Dada una función y , st , ,...
Estoy tratando de entender la complejidad de las funciones que se expresan a través de las puertas de umbral y esto me llevó a . En particular, estoy interesado en lo que se sabe actualmente sobre el aprendizaje dentro de T C 0 , ya que no soy un experto en el
¿Es el siguiente problema en PTIME o coNP-hard: Dadas dos expresiones booleanas y e 2 en variables x 1 , ... , x n , sin negación (es decir, las expresiones se construyen completamente a través de ∧ y ∨ ). Decida si e 1 ≡ e 2 , es decir, tienen el mismo valor para todas las asignaciones a las...
Introduciré mi problema con un ejemplo. Supongamos que está diseñando un examen, que consiste en un cierto conjunto de preguntas independientes (que los candidatos pueden obtener bien o mal) Desea decidir sobre un puntaje para dar a cada una de las preguntas, con la regla de que los candidatos con...
Los solucionadores SAT ofrecen una forma poderosa de verificar la validez de una fórmula booleana con un cuantificador. Por ejemplo, para verificar la validez de , podemos usar un solucionador SAT para determinar si φ ( x ) es satisfactoria. Para verificar la validez de ∀ x . φ ( x ) , podemos...
En el documento de Pruebas naturales de Razborov-Rudich , página 6, en la parte que discuten que hay "fuertes pruebas de límites inferiores contra modelos de circuito monótono " y cómo encajan en la imagen, están las siguientes oraciones: Aquí el problema no es la constructividad, las...