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

74

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?

Derrick Stolee
fonte
Wiki da comunidade.
Dave Clarke
O wiki da comunidade está agora em vigor.
Derrick Stolee 04/10/10
Surpreendente quantos exemplos existem sobre topologia e geometria. Estamos apenas mais surpresos com esses dois tópicos?
Suresh Venkat
7
Uma vez que são fornecidos exemplos suficientes da Área X, isso faz com que a Área X não seja mais "não relacionada"?
András Salamon

Respostas:

38

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.

Warren Schudy
fonte
1
Este é um excelente exemplo!
Ryan Williams
25

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

Dana Moshkovitz
fonte
25

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.

Jeffε
fonte
1
O tipo de resultado "em retrospecto, é óbvio" é o melhor tipo de aplicação. A retrospectiva é 20/20.
Derrick Stolee
25

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 .

Suresh Venkat
fonte
+1. O uso de argumentos topológicos para provar declarações combinatórias é verdadeiramente épico. Os leitores interessados ​​podem encontrar mais informações aqui: en.wikipedia.org/wiki/Topological_combinatorics
Robin Kothari
1
@Robin: Ou que tal argumentos geométricos? O principal teorema do clássico artigo da Bayer-Diaconis sobre embaralhamento em cauda de andorinha foi descoberto pensando no embaralhamento como uma transformação de preservação de volume (o mapa do padeiro: duplo e dobra (mod 1) ao longo de cada eixo) do cubo 52. Infelizmente, eles removeram a maioria dos traços da intuição geométrica do trabalho final, substituindo-o por combinações discretas.
Por Vognsen
@ Per Vognsen: Eu não estou familiarizado com esse trabalho, então obrigado pelo ponteiro. Vou dar uma olhada nisso.
Robin Kothari
2
Você pode querer adicionar " métodos topológicos e teóricos de grupo " para Kahn-Saks-Sturtevant. Afinal, eles usam crucialmente ações de grupo em complexos simples.
Joshua Grochow 5/10/10
2
Fiquei me perguntando se vale a pena "acordar" esse tópico depois de um ano para apontar uma referência .. mas, em seguida, é um ótimo tópico, por que não? O resultado de Lovasz e outros resultados, bem como uma introdução à "topologia algébrica para combinatorialistas" podem ser encontrados na monografia de Matousek: kam.mff.cuni.cz/~matousek/akt.html
Sasho Nikolov
22

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.

Joshua Grochow
fonte
21

IP=PSPACE

Ryan Williams
fonte
7
Também gosto do truque polinomial para encontrar combinações perfeitas em gráficos bipartidos, amostrando aleatoriamente o determinante (obrigado, Lovász).
Derrick Stolee
21

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.

Srikanth
fonte
20

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).

Suresh Venkat
fonte
7
Também a prova de Noam Nisan ao lema do núcleo duro de Russell Impagliazzo (no artigo original de Russell)
Dana Moshkovitz
17

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

nO(logn!)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 .

Sariel Har-Peled
fonte
15

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.

Dana Moshkovitz
fonte
Mas esses usos são realmente "não relacionados"? Pelo menos de um ponto de vista ingênuo, parece-me que a teoria da informação é uma das primeiras áreas que vêm à mente quando se ouve pela primeira vez a definição de, digamos, códigos decodificáveis ​​localmente.
arnab
Concordo que a teoria da informação está relacionada a códigos, por exemplo, e os códigos estão relacionados ao TCS. A repetição paralela é talvez um exemplo mais forte: por que você pensaria em usá-la para amplificação de som para PCPs?
Dana Moshkovitz
Sim, concordo plenamente que a repetição paralela é um exemplo surpreendente.
arnab
14

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.

Marc
fonte
Uhm, isso não é exato. Alon e Naor aproximaram a norma de corte de uma matriz - isso está relacionado ao corte máximo, mas não é o mesmo.
Sasho Nikolov
13

Um bom exemplo é o teorema de Barrington:

fdf4d

S5

Diego de Estrada
fonte
12

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.

Kunal
fonte
Talvez eu reformule a pergunta para resolver isso.
Derrick Stolee
12

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.

Boaz Barak
fonte
6
Outro bom exemplo nesse sentido é a recente utilização da densidade Hales-Jewitt conjectura para provar a não-linear limite inferior na rede epsilon para um espaço gama de dimensão VC 2.
Suresh Venkat
11

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.

zotachidil
fonte
7

o(k2)

k2

Álgebra linear usada para sparsify gráficos:

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

Jelani Nelson
fonte
6

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.

Dominic Mulligan
fonte
4

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.

Sasho Nikolov
fonte
3

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

Antonio Valério Miceli-Barone
fonte
0

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

user3493
fonte
2
Gauss discordaria.
Jeffε