¿Pruebas de propiedad en otras métricas?

20

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 0,1}norteR

  1. es miembro de alguna clase de funciones CFC

  2. es ε -lejos de cada función en la clase C .FεC

El rango de la función es a veces booleano: R = { 0 , 1 } , pero no siempre.RR={0 0,1}

Aquí, -lejos se toma generalmente para significar Hamming distancia: la fracción de puntos de f que tendrían que ser cambiado con el fin de lugar f en la clase C . Esta es una métrica natural si f tiene un rango booleano, pero parece menos natural si el rango tiene un valor real.εFFCF

Mi pregunta: ¿existe un hilo de la literatura de pruebas de propiedad que prueba la cercanía a alguna clase con respecto a otras métricas?C

Aaron Roth
fuente

Respuestas:

19

¡Sí hay! Daré tres ejemplos:

  1. Dado un conjunto S y una "tabla de multiplicación" sobre S x S, considere el problema de determinar si la entrada describe un grupo abeliano o si está lejos de ser uno. Friedl, Ivanyos y Santha en STOC '05 mostraron que hay un probador de propiedades con polylog de complejidad de consulta (| S |) cuando la medida de distancia es con respecto a la distancia de edición de tablas de multiplicación que permite la adición y eliminación de filas y columnas de la tabla de multiplicar El mismo problema también fue considerado en el modelo de distancia de Hamming por Ergun, Kannan, Kumar, Rubinfeld y Viswanathan (JCSS '00) donde mostraron complejidad de consulta de O ~ (| S | ^ {3/2}).

  2. Hay una gran cantidad de trabajo realizado para probar las propiedades del gráfico donde los gráficos se representan mediante listas de adyacencia y hay un límite en el grado de cada vértice. En este caso, el modelo de distancia no es exactamente la distancia de Hamming, sino cuántos bordes se pueden agregar o eliminar mientras se conserva el límite de grado.

  3. En el estudio estrechamente relacionado de las propiedades de prueba de las distribuciones, se han estudiado varias nociones de distancia entre distribuciones. En este modelo, la entrada es una distribución de probabilidad sobre un conjunto y el algoritmo accede a ella mediante el muestreo del conjunto de acuerdo con la distribución desconocida. Luego se requiere el algoritmo para determinar si la distribución satisface alguna propiedad o está "lejos" de ella. Aquí se han estudiado varias nociones de distancia, como L_1, L_2, movimiento de tierras. Las distribuciones de probabilidad sobre dominios infinitos también se han estudiado aquí ( Adamaszek-Czumaj-Sohler, SODA '10 ).

arnab
fuente
44
Para profundizar en el n. ° 1, un problema aún más natural (en mi humilde opinión) es probar la monotonicidad, donde la distancia es el # de posiciones que se detectarán en una permutación para que sea monótono. Esto ha sido estudiado en el documento JCSS'00 mencionado anteriormente (que conduce al documento FOCS'10 más reciente de Comandur-Saks).
Alex Andoni
Si no es demasiado problema, ¿podría vincular a los documentos a los que se hace referencia? idealmente la versión doi / acm.
Suresh Venkat
7

Por lo general, no se llama prueba de propiedad (y realmente no lo es), pero hay una gran cantidad de trabajo para decidir las propiedades de una matriz al observar un pequeño inducido menor. Esto es muy similar al objetivo en las pruebas de propiedad. Ver, por ejemplo, el artículo de Rudelson y Vershynin:

http://portal.acm.org/citation.cfm?id=1255449

Hay documentos anteriores de Frieze-Kannan. El punto es que, por lo general, la métrica que usan es alguna norma de matriz, como la norma espectral, la norma frobenius o la norma de corte. Si lo desea, puede pensar en algunos de estos resultados como algoritmos de prueba de propiedades en una métrica que no sea la distancia de Hamming.

Moritz
fuente
4

F:[norte]reRLpagpag1Lpag

Lpag

L1L1L1norte1


Lpag

k

Clemente C.
fuente