Palestra - Aplicações da Teoria de Concentração de Medida

Idioma
  • Português
Data e horário
  • Sex, 31 Jul. 14:00 - 15:00 (UTC-3)
Palestrante
  • Cesar Niche - Instituto de Matemática/UFRJ
Local
  • YouTube

Queremos resolver os três problemas seguintes: \[\] 1) Dado um problema cuja solução é binária ("sim" ou "não"), criamos um algoritmo que dá uma solução aleatoriamente, com probabilidade \(p = 1/2 + \delta\), com \(\delta > 0\), de ser correta. Executamos o algoritmo \(n\) vezes e escolhemos como solução "certa" a que aparece com mais frequência. Quanto deve ser \(n\) para que a probabilidade de obter a solução errada seja menor que \(\epsilon\)?; \[\] 2) Temos \(N\) pontos em \( \mathbb{R}^n\), que são o input de um programa que calcula as distâncias entre cada par de pontos e determina a solução de um problema que é função destas. Porém, \(n\) é muito grande (\(10 ^6\), por exemplo), o que impossibilita, do ponto de vista prático, de executar o programa. Existe alguma forma de "diminuir a dimensão" \(n\) sem distorcer muito as distâncias entre os pontos, de maneira que seja possível obter uma solução (aproximada) usando realmente o programa?. \[\] 3) Seja \(x\) um vetor desconhecido em \( \mathbb{R} ^n \) que tem \(s\) ou menos entradas diferentes de zero, i.e. \(x\) é \(s\)-esparso. Sabemos que \(y = Ax\), onde \(y\) está em \(\mathbb{R}^m\) e é dado e \(A\) é uma matriz desconhecida. A priori, poderíamos ter vários \(\hat{x}\) esparsos tais que \(y = A \hat{x}\). Como construir \(A\) para que a distância entre qualquer \(\hat{x}\) e o vetor \(x\), i.e. o erro, seja pequena? \[\] Nesta palestra descreverei as soluções aos problemas 1) a 3), todas elas baseadas na idéia de Concentração de Medida e farei propaganda sobre um curso sobre Teoria de Concentração de Medida e Aplicações que ditarei em 2020/2 (dezembro 2020 - março 2021).