En las pruebas de propiedades de gráficos, un algoritmo consulta un gráfico de destino para detectar la presencia o ausencia de aristas y necesita determinar si el objetivo tiene una determinada propiedad o está ϵϵ\epsilon lejos de tener la propiedad. (Se puede pedir que un algoritmo tenga éxito...
Existe una gran literatura sobre "pruebas de propiedad": el problema de realizar una pequeña cantidad de consultas de recuadro negro a una función para distinguir entre dos casos:F: { 0 , 1 }norte→ RF:{0 0,1}norte→Rf\colon\{0,1\}^n \to R es miembro de alguna clase de funciones CFFfCC\mathcal{C}...
El método negativo del adversario ( ) es un SDP que caracteriza la complejidad de la consulta cuántica. Es una generalización del método adversario ampliamente utilizado ( A D V ) y supera las dos barreras que obstaculizaron el método adversario:ADV±ADV±ADV^\pmADVADVADV La barrera de la prueba de...
En [1], Turan muestra que la sensibilidad (llamada "complejidad crítica" en el documento) de una propiedad gráfica es estrictamente mayor que dondemes el número de vértices en el gráfico. Continúa conjeturando que cualquier propiedad de gráfico no trivial tiene sensibilidad≥m-1. Menciona que esto...
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...
Alice y Bob tienen cadenas de n bits, y quieren averiguar si son iguales mientras hacen poca comunicación. La solución aleatoria estándar es tratar las cadenas de n bits como polinomios de grado luego evaluar los polinomios sobre algunos elementos elegidos al azar de un campo de tamaño mayor que n...
Un algoritmo de prueba de distribución para una propiedad de distribución P (que es solo un subconjunto de todas las distribuciones sobre [n]) puede acceder a las muestras de acuerdo con alguna distribución D, y se requiere que decida (whp) si D∈PD∈PD\in P o d(D,P)>ϵd(D,P)>ϵd(D,P)>\epsilon (...
Me gustaría saber (en relación con esta otra pregunta ) si se conocen límites inferiores para el siguiente problema de prueba: a uno se le da acceso de consulta a una secuencia de números no negativos y ε ∈ ( 0 , 1 ) , con la promesa de que ∑ n k = 1 a k = 1 o ∑ n k = 1 a k ≤ 1 - ε .unanorte≥ ⋯ ≥...
Supongamos que tenemos una gráfica y parámetros k , ϵ . ¿Hay rangos de valores para k (o es factible para todo k ) para el que es posible comprobar si G es ε -lejos de tener un conjunto independiente de tamaño al menos k en el tiempo O ( n + poli ( 1 / ε ) ) ?solGGk ,
Deje que sea un gráfico aleatorio en bordes. Con una probabilidad muy alta, tiene muchos ciclos. Nuestro objetivo es producir cualquiera de estos ciclos lo más rápido posible.G∼G(n,n−1/2)G∼G(n,n−1/2)G \sim G(n, n^{-1/2})≈n3/2≈n3/2\approx n^{3/2}GGG444444 Suponiendo que tenemos acceso a en forma...