A menudo, cuando participamos en conferencias de TCS, notamos algunos pequeños detalles que desearíamos que los organizadores de la conferencia hubieran tenido en cuenta. Y cuando organizamos conferencias, ya lo hemos olvidado. De ahí la pregunta: ¿Qué pequeños pasos podríamos tomar fácilmente...
Mi pregunta hoy es (como siempre) un poco tonta; pero le pediría que lo considere amablemente. Quería saber sobre la génesis y / o motivación detrás del concepto de ancho de árbol. Estoy seguro de que entiendo que se usa en algoritmos FPT, pero no creo que esa sea la razón por la que se definió...
En TCS a menudo utilizamos resultados e ideas poderosas de las matemáticas clásicas (álgebra, topología, análisis, geometría, etc.). ¿Cuáles son algunos ejemplos de cuándo ha sido al revés? Aquí hay algunos que conozco (y también para dar una idea del tipo de resultados que estoy...
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...
Estoy buscando ejemplos de problemas parametrizados por un número , donde la dureza del problema no es monotónica en k . La mayoría de los problemas (en mi experiencia) tienen una transición de fase única, por ejemplo, k -SAT tiene una transición de fase única de k ∈ { 1 , 2 } (donde el problema...
¿Conoce algoritmos sensibles que se ejecutan en tiempo polinómico en (Longitud de entrada + longitud de salida), pero cuyo tiempo de ejecución asintótico en la misma medida tiene un exponente / constante realmente enorme (al menos, donde el límite superior probado en el tiempo de ejecución está en...
Se conjetura ampliamente que , el exponente óptimo para la multiplicación de matrices, es de hecho igual a 2. Mi pregunta es simple:ωω\omega ¿Qué razones tenemos para creer que ?ω = 2ω=2\omega = 2 Conozco algoritmos rápidos como Coppersmith-Winograd, pero no sé por qué estos podrían...
Soy nuevo en el sitio. En Mathoverflow, esto sería wiki comunitario, pero no veo cómo configurarlo aquí. No es una pregunta de investigación, pero espero sea de interés para los científicos teóricos profesionales en informática. Soy un estudiante graduado de segundo año en teoría, y me preguntaba...
Después de estudiar autómatas deterministas de estado finito (DFA) en pregrado, sentí que se los comprende muy bien. Mi pregunta es si hay algo que todavía no entendemos acerca de ellos. No me refiero a generalizaciones de DFA, sino a los DFA originales no modificados que estudiamos en...
antecedentes Hace varios años, cuando era estudiante universitario, nos dieron una tarea de análisis amortizado. No pude resolver uno de los problemas. Lo había pedido en teoría teórica , pero no se obtuvieron resultados satisfactorios. Recuerdo que el curso TA insistió en algo que no pudo probar,...
¿Cuáles son las pautas generales para verificar sus pruebas? Creo que esto es importante para los estudiantes graduados como yo. Ya sé lo que tenemos que hacer para probar algo, pero siempre debes verificar todo antes de enviarlo. Incluso a tu propio asesor. Desarrollé algunas estrategias por...
Esta pregunta es algo que me he preguntado por un tiempo. Cuando las personas describen el problema P vs. NP, a menudo comparan la clase NP con la creatividad. Señalan que componer una sinfonía de calidad de Mozart (análoga a una tarea de NP) parece mucho más difícil que verificar que una sinfonía...
Con el advenimiento de internet (y el sentido común) hay una demanda cada vez mayor de investigación de acceso abierto. Varios investigadores (incluyéndome a mí) encuentran frustrante que los artículos de investigación publicados revisados por expertos estén detrás de los muros de pago. Estoy...
Al diseñar un algoritmo para un nuevo problema, si no puedo encontrar un algoritmo de tiempo polinómico después de un tiempo, podría intentar probar que es NP-hard en su lugar. Si tengo éxito, he explicado por qué no pude encontrar el algoritmo de tiempo polinómico. No es que sepa con certeza que...
En el hilo ¿ Principales problemas no resueltos en informática teórica? , Iddo Tzameret hizo el siguiente excelente comentario: Creo que deberíamos distinguir entre los principales problemas abiertos que se consideran problemas fundamentales, como P≠NPP≠NP P\neq NP , y los principales problemas...
Recientemente, cuando hablé con un físico, afirmé que, en mi experiencia, cuando un problema que ingenuamente parece que debería llevar un tiempo exponencial resulta no trivial en P o BPP, generalmente se puede identificar una "razón general" por la que ocurre la reducción. --- y casi siempre, esa...
Los algoritmos genéticos no tienen mucha tracción en el mundo de la teoría, pero son un método metaheurístico razonablemente bien utilizado (por metaheurístico me refiero a una técnica que se aplica genéricamente a muchos problemas, como el recocido, el descenso de gradiente y similares). De hecho,...
¿Qué herramientas utilizas para escribir artículos? Por la poca experiencia que tengo, los teóricos pasan una gran cantidad de tiempo escribiendo y refinando artículos, además de ser creativos. Es decir, comunicar su trabajo a otras personas. Tal vez los documentos no son la forma correcta de...
Me he encontrado con el algoritmo polinómico que resuelve 2SAT. Me ha parecido sorprendente que 2SAT esté en P, donde todas (o muchas otras) de las instancias de SAT son NP-Complete. ¿Qué hace que este problema sea diferente? ¿Qué lo hace tan fácil (NL-Complete, incluso más fácil que...
El propósito de esta pregunta es recopilar ejemplos de la informática teórica donde el uso sistemático de las computadoras fue útil. al construir una conjetura que conduzca a un teorema, falsificar un enfoque de conjetura o prueba, construir / verificar (partes de) una prueba. Si tiene un...