He preguntado este problema en MathOverflow , sin ninguna respuesta satisfactoria. Considere el siguiente juego de dos jugadores, que es una simplificación del juego de cartas llamado Winner . (La siguiente formulación fue tomada de un comentario de Guillaume Brunerie sobre MathOverflow). Hay dos...
Estoy buscando un algoritmo para dibujar un gráfico mixto de circunscripción / dependencia (para una aplicación lingüística). Tal gráfico tendría dos tipos diferentes de vértices (tokens, nodos) y dos tipos diferentes de bordes (jerárquico, no jerárquico). Soy nuevo en teoría de gráficos y...
He estado luchando con los detalles técnicos de una prueba sobre la teoría de subastas en este documento: http://users.eecs.northwestern.edu/~hartline/omd.pdf Específicamente, Teorema 2.5: Las condiciones necesarias y suficientes para un mecanismo veraz. Incluso más específicamente, la dirección...
Estoy trabajando en el campo de la ingeniería estructural y me gustaría encontrar un algoritmo eficiente para construir una aproximación (en la métrica de Hausdorff) de un cuerpo convexo por el casco convexo de elipsoides, para algunos fijos . Actualmente solo estoy trabajando en las dimensiones 2...
Background––––––––––––––Background_\underline{\bf Background} En 2005, Regev [1] introdujo el problema de Aprendizaje con errores (LWE), una generalización del problema de Paridad de aprendizaje con error. La suposición de la dureza de este problema para ciertas opciones de parámetros ahora...
Mi pregunta es acerca de la teoría del modelo finito / complejidad descriptiva, por lo que significará "primer orden sobre palabras binarias finitas, usando predicados Rs y un predicado unario P verdadero en la posición del 1 en la palabra".FO(R)FO(R)FO(R) Me gustaría saber, ¿hay alguna...
Esta es una pregunta suave dirigida a establecer lo que la gente piensa que es la mejor práctica profesional para enviar trabajos no originales en el arXiv. Hay un borrador de un artículo [1] de Robert Szelepcsényi, en su espacio web en la Universidad de Chicago, aparentemente escrito hace más de...
Sé que el tiempo de ejecución esperado en el peor de los casos del algoritmo de triangulación incremental aleatorio delaunay (como se da en Computational Geometry ) es . Hay un ejercicio que implica que el peor tiempo de ejecución es . He tratado de construir un ejemplo donde este sea realmente el...
Supongamos que XXX es una variable aleatoria que toma valores en ΣnorteΣn\Sigma^n (para un alfabeto grande ΣΣ\Sigma ), que tiene una entropía muy alta, por ejemplo, H( X) ≥ ( n - δ) ⋅ logEl | Σ |H(X)≥(n−δ)⋅log|Σ|H(X) \ge (n- \delta)\cdot\log|\Sigma|para una constante arbitrariamente pequeña...
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,...
Deje ser un gráfico. Dejeser un número entero Sea el número de inducidas por aristas de tienen vértices y un número impar de aristas. Sea el número de inducidas por aristas de tienen vértices y un número par de aristas. Deje . El problema ODD EVEN DELTA consiste en calcular , dados y .G = ( V,...
Hasta donde sé, una función de Haskell con restricciones de clases de tipo se compila internamente en una función con argumentos adicionales que reciben diccionarios con las implementaciones necesarias de cada clase de tipo en particular. ¿Hay alguna otra posibilidad de cómo compilar clases de...
Los functores construidos a partir de productos finitos y sumas tienen cierre ordinal , que se detalla muy bien en este manuscrito de Francois Metayer. es decir, podemos alcanzar el tipo inductivo iterando el functor , que alcanza su punto fijo después de las iteraciones
El libro de Arora y Barak contiene notas de capítulos sobre PCP Observamos que la estrategia general de Dinur recuerda en cierta medida la construcción en zig-zag de los gráficos de expansión y el algoritmo determinista de espacio de registro de Reingold para la conectividad no dirigida que se...
puntos distintos se seleccionan aleatoriamente de unacuadrícula p × q . (Obviamente, k ≤ p × q y es un número constante dado.) Se construye un gráfico ponderado completo a partir de estos k puntos de modo que el peso del borde entre el vértice i y el vértice j sea igual a la distancia de Manhattan...
Supongamos que Alice tiene una distribución sobre un dominio finito (pero posiblemente muy grande), de modo que la entropía (Shannon) de μ está limitada por una constante arbitrariamente pequeña ε . Alice extrae un valor x de μ , y luego le pide a Bob (quién sabe μ ) que adivine x...
Hace poco comencé a involucrarme con la Optimización matemática y me encanta. Parece que muchos problemas de optimización se pueden expresar y resolver fácilmente como programas lineales (por ejemplo, flujos de red, cobertura de borde / vértice, vendedor ambulante, etc.) Sé que algunos de ellos son...
Estoy tratando de entender el documento sobre p-Optimal Proof Systems and Logic para PTIME . Hay una noción llamada sistemas de prueba en el documento y no entiendo: Σ={0,1}Σ={0 0,1}\Sigma = \{0,1\} ... Identificamos problemas con subconjuntos deQQQ enΣ∗Σ∗\Sigma^* . Creo que la intuición es...
Si tiene dos funciones que implementan un algoritmo de clasificación diferente, ¿es posible inferir por código fuente que ambas tienen las mismas propiedades externas? ¿Significa que ambos tendrán una posible secuencia sin clasificar como entrada y tendrán una secuencia ordenada como salida? ¿De...
Para comprender mejor un artículo, estoy tratando de obtener una breve comprensión de la lógica de punto menos fijo. Hay algunos puntos donde estoy atrapado. Si G = ( V, E)sol=(V,mi)G = (V,E) es un gráfico y Φ ( P) = { ( a , b ) ∣ G ⊨ E( a , b ) ∨ P( a , b ) ∨ ∃ z( E( a ,...