Exemplos de matemática "não relacionada" desempenhando um papel fundamental no TCS?

Por favor, liste exemplos em que um teorema da matemática que normalmente não era considerado aplicável à ciência da computação foi usado pela primeira vez para provar um resultado na ciência da computação. Os melhores exemplos são aqueles em que a conexão não era óbvia, mas uma vez descoberta, é claramente o "caminho certo" para fazer isso.

Esta é a direção oposta da pergunta Aplicações do TCS à matemática clássica?

Por exemplo, consulte "Teorema de Green e isolamento em gráficos planares" , em que um teorema de isolamento (que já era conhecido usando uma prova técnica) é re-provado usando o Teorema de Green a partir de cálculo multivariado.

Que outros exemplos existem?

Maurice Herlihy, Michael Saks, Nir Shavit e Fotios Zaharoglou receberam o prêmio Godel em 2004 pelo uso da topologia algébrica no estudo de alguns problemas na computação distribuída.

Eu tenho um exemplo de um trabalho que eu co-escrevi com Noga Alon e Muli Safra há alguns anos:

Noga usou teoremas de ponto fixo de topologia algébrica para provar o "Teorema de divisão de colar": se você tem um colar com contas de tipos t e deseja dividir partes dele entre b pessoas, para que cada uma receba o mesmo número de contas de cada tipo ( suponha que b divide t), você sempre pode fazer isso cortando o colar em no máximo (b-1) t lugares.

Usamos esse teorema para construir um objeto combinatório que usamos para provar a dureza da aproximação de Set-Cover.

Mais algumas informações estão aqui: http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest.html

Em retrospecto, isso pode ser óbvio, mas sempre gostei da aplicação de Steele, Yao e Ben-Or do teorema de Oleinik-Petrovsky / Milnor / Thom (limitando o número de Betti de conjuntos semi-algébricos reais) limites na árvore de decisão algébrica e nos modelos de árvore de computação algébrica.

Um dos meus resultados favoritos é o uso de argumentos topológicos na prova de Lovasz da conjectura de Kneser e o uso de métodos topológicos ( e teóricos de grupos ) no ataque de Kahn-Saks-Sturtevant à forte conjectura de Aandera-Rosenberg-Karp sobre evasão .

A teoria da representação de grupos finitos é usada na abordagem de Cohn-Kleinberg-Szegedy-Umans para multiplicação de matrizes . Eles mostram que, se existem famílias de produtos de grinalda de abelianos com grupos simétricos que satisfazem certas condições, existem algoritmos de multiplicação de matrizes de complexidade quadrática.

A teoria da representação (de grupos algébricos) também aparece na abordagem da teoria da complexidade geométrica de Mulmuley e Sohoni para limites inferiores. Ainda não está claro se isso conta como um aplicativo, uma vez que ainda não foram comprovados novos resultados de complexidade com essa abordagem, mas pelo menos uma conexão interessante foi feita entre duas áreas que, à primeira vista, parecem totalmente independentes.

$IP = PSPACE$

A teoria da aproximação (que lida com a aproximação de funções de valor real possivelmente complicadas ou não naturais por funções simples, como polinômios de baixo grau) teve muitos usos na complexidade do circuito, complexidade da consulta quântica, pseudo-aleatoriedade etc.

Acho que uma das aplicações mais legais das ferramentas desta área vem deste artigo de Beigel, Reingold e Spielman, onde eles mostraram que a classe de complexidade PP é fechada sob interseção usando o fato de que a função de sinal pode ser aproximada por um baixo função racional grau.

Nisan e Szegedy e Paturi mostraram limites mais baixos para aproximar funções simétricas por polinômios de baixo grau. Esse método é frequentemente usado para provar os limites inferiores da complexidade da consulta Quantum. Veja as notas da aula de Scott Aaronson , por exemplo.

Outra idéia bonita: a idéia de Yao de usar princípios minimax e a prova de que jogos mistos têm um equilíbrio (dualidade de programação essencialmente linear) para mostrar limites mais baixos em algoritmos aleatórios (construindo uma distribuição sobre entradas para um algoritmo determinístico).

Teoremas de ponto fixo estão por todo o lado ...

$n$$O(\log n!)$comparações, duh). A prova desse fato passa pela geometria dos pólipos de alta dimensão. Especificamente, a prova usa a desigualdade de Brunn-Minkowski. Uma boa apresentação disso está no livro de Matousek sobre Palestras sobre geometria discreta (Seção 12.3). A prova original é de Kahn e Linial, daqui .

Existem muitos usos da teoria da informação na ciência da computação teórica: por exemplo, para provar limites inferiores para códigos localmente decodificáveis ​​(veja Katz e Trevisan), na prova de Raz do teorema da repetição paralela, na complexidade da comunicação (veja, por exemplo, o tópico) do trabalho sobre compressão da comunicação, por exemplo, o trabalho relativamente recente de Barak, Braverman, Chen e Rao, e as referências ali) e muito mais trabalho.

Alon e Naor usaram a desigualdade de Grothendieck para provar um algoritmo de aproximação no problema do corte máximo . Eu acho que existem trabalhos subseqüentes sobre esse tópico, mas eu não sou especialista.

Curiosamente, o mesmo teorema foi usado por Cleve, Hoyer, Toner e Watrous para analisar jogos quânticos de XOR, e Linial e Shraibman o usaram para a complexidade da comunicação quântica. Até onde eu sei, a relação entre a desigualdade de Grothendieck e o fundamento da física quântica foi descoberta por Tsirelson em 85, mas os dois resultados que mencionei abordam especificamente a ciência da computação.

Um bom exemplo é o teorema de Barrington:

$f$$d$$f$$4^d$

$S_5$

Plugue descarado: uso da conjectura isotrópica (e geometria convexa em geral) no projeto de mecanismos diferencialmente privados aproximadamente ótimos para consultas lineares em meu trabalho com Moritz Hardt .

Para responder parcialmente à pergunta de Suresh acima, acho que a pergunta original é um pouco complicada por causa do "normalmente não se aplica à ciência da computação". Algumas dessas técnicas que podem parecer originalmente "não relacionadas" tornam-se "normais" ao longo do tempo. Portanto, as técnicas mais bem-sucedidas (por exemplo, análise de Fourier em Kahn-Kalai-Linial, incorporações métricas em Linial-London-Rabinovich) não são mais respostas válidas.

A combinatória aditiva / teoria dos números foi muito utilizada na literatura sobre extratores. Penso que as primeiras instâncias vêm da observação de que os gráficos de Paley poderiam ser usados ​​como bons extratores, e algumas questões em aberto na teoria dos números aditivos implicariam em melhores. A referência mais antiga que eu conheço é Zuckerman 1990 (veja sua tese ), mas nos últimos anos essa tem sido uma área ativa com interessantes trechos entre TCS e combinatória aditiva. (Um dos destaques é a prova de Dvir da conjetura Kakeya de campo finito, mas essa é obviamente uma contribuição do TCS para a matemática e não o contrário.) A priori, não está claro por que esse tipo de perguntas matemáticas, sobre somas e produtos conjuntos, seria importante para o CS.

Sleator, Tarjan e Thurston provaram a existência de uma família infinita de pares de árvores de busca binária com nvértices e distância de rotação 2n-6usando geometria hiperbólica.

$o(k^2)$

$k^2$

Álgebra linear usada para sparsify gráficos:

Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava: sparsifiers duas vezes. STOC 2009: 255-262.

Isso pode ou não contar, mas recentemente as teorias de conjuntos de Zermelo-Fraenkel com átomos (ZFA) e Fraenkel-Mostowski (FM) foram aplicadas ao estudo da sintaxe abstrata com ligação de nomes. O ZFA foi introduzido no início do século 20 como uma ferramenta para provar a independência da CH e depois esquecido, mas redescoberto no final dos anos 90 por dois cientistas da computação - Gabbay e Pitts - estudando algo completamente desconectado.

Veja este documento de pesquisa, por exemplo.

A aplicação de Kahn e Kim da entropia de grafos na classificação sob informações parciais (http://portal.acm.org/citation.cfm?id=129731). Eles deram o primeiro algoritmo de tempo polinomial que executa as informações teoricamente ótimas (até constantes) número de comparações. O artigo é uma pequena viagem de campo em matemática, usando alguns argumentos combinatórios clássicos, juntamente com geometria convexa, entropia de grafos e programação convexa. Existe um algoritmo mais simples e mais recente, mas ainda sabemos como analisá-lo sem entropia de gráfico.

A teoria dos números foi usada para desenvolver o RSA e outros esquemas criptográficos de chave pública.

A descoberta da multiplicação de Karatsuba foi surpreendente.