BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Mauro Natale (Universidad Nacional del Centro de la Provincia de B
 uenos Aires)
DTSTART:20200605T170000Z
DTEND:20200605T180000Z
DTSTAMP:20260423T004547Z
UID:SemACT/4
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/SemACT/4/">U
 na transformada de Fourier rápida para el grafo de Johnson</a>\nby Mauro 
 Natale (Universidad Nacional del Centro de la Provincia de Buenos Aires) a
 s part of Seminario de álgebra\, combinatoria y teoría de Lie\n\n\nAbstr
 act\nLa Transformada de Fourier para el grafo de Johnson es definida como 
 la matriz cambio de base en el espacio $\\mathcal{F}$ de funciones complej
 as en los vértices del grafo\, de la base delta o canónica a la base de 
 Gelfand-Tsetlin.\n\nLa aplicación directa de esta matriz a un vector gen
 érico requiere $\\binom{n}{k}^2$ operaciones artiméticas. Nosotros demos
 tramos que esta matriz puede ser factorizada como producto de $n-1$ matric
 es ortogonales\, cada una de ellas con a lo sumo dos elementos no nulos en
  cada columna. La factorización está basada en la construcción de bases
  intermedias las cuales son parametrizadas vía el algoritmo de inserción
  de Robinson-Schensted. La factorización nos permite aplicar la Transform
 ada de Fourier a un vector genérico en a lo sumo $2(n-1) \\binom{n}{k}$ o
 peraciones aritméticas. También demostramos que cada una de estas matric
 es esparsas puede ser construída utilizando $O(\\binom{n}{k})$ operacione
 s aritméticas.\n\nComo consecuencia de estos hechos\, podemos computar to
 dos los pesos de las componentes isotípicas de una función $f \\in \\mat
 hcal{F}$ utilizando $O(n \\binom{n}{k})$ operaciones\, lo que mejora los r
 esultados conocidos cuando $k$ domina asintóticamente a $\\sqrt{n}$.\n\nL
 a charla se basa un trabajo conjunto con Rodrigo Iglesias (https://arxiv.o
 rg/abs/1912.09243).\n
LOCATION:https://researchseminars.org/talk/SemACT/4/
END:VEVENT
END:VCALENDAR