Impacto do programa de Grothendieck no TCS

27

Grothendieck faleceu . Ele teve um impacto maciço na matemática do século XX, continuando no século XXI. Esta pergunta é feita de alguma forma no estilo / espírito, por exemplo, de Contribuições de Alan Turing para Ciência da Computação .

Quais são as principais influências de Grothendieck na ciência da computação teórica?

vzn
fonte
obituário em inglês / ABCNews
vzn 14/11
Talvez isso seja relevante: Grothendieck é um computador?
babou
6
Espero que alguém da teoria B escreva sobre teoria das categorias e topologias de Grothendieck (ou o trabalho dele não é relevante para a ciência da computação?).
Sasho Nikolov
1
fyi algum esboço / esboço de uma resposta do reddit / "frobenius"
vzn 14/11/14
2
Talvez @AndrejBauer possa ajudar.
Sasho Nikolov

Respostas:

28

A desigualdade de Grothendieck , desde seus dias em análise funcional, provou inicialmente relacionar normas fundamentais em espaços de produtos tensores. Grothendieck chamou a desigualdade de "o teorema fundamental da teoria métrica dos espaços de produto tensorial" e a publicou em um artigo agora famoso em 1958, em francês, em uma revista brasileira de circulação limitada. O artigo foi amplamente ignorado por 15 anos, até ser redescoberto por Lindenstrauss e Pelczynski (depois que Grothendieck deixou a análise funcional). Eles deram muitas reformulações dos principais resultados do artigo, relacionaram-no a pesquisas sobre operadores absolutamente somadores e normas de fatoração e observaram que Grothendieck havia resolvido problemas "abertos" que haviam sido levantados apóso artigo foi publicado. Pisier faz um relato muito detalhado da desigualdade, suas variantes e sua tremenda influência na análise funcional em sua pesquisa .

A desigualdade de Grothendieck é muito naturalmente expressa na linguagem de otimização combinatória e algoritmos de aproximação. Ele diz que o problema de otimização não-convexo e difícil de NP é aproximado até uma constante fixa por seu semidefinido relaxamento máximo { Σ i , j um i ju i ,

max{xTAy:x{1,1}m,y{1,1}n}
onde S n + m - 1 é a unidade de esfera em R n + m
max{Eu,jumaEujvocêEu,vj:você1,...,vocêm,v1,...,vnSn+m-1},
Sn+m-1Rn+m. As provas da desigualdade fornecem "algoritmos de arredondamento" e, de fato, o arredondamento aleatório de hiperplano de Goemans-Williamson faz o trabalho (mas fornece uma constante subótima). No entanto, a desigualdade de Grothendieck é interessante porque a análise do algoritmo de arredondamento deve ser "global", isto é, examinar todos os termos da função objetivo juntos.

Dito isto, não deve surpreender que a desigualdade de Grothendiecks tenha encontrado uma segunda (terceira? Quarta?) Vida em ciência da computação. Khot e Naor pesquisam suas múltiplas aplicações e conexões para otimização combinatória.

A história não acaba aí. A desigualdade está relacionada às violações da desigualdade de Bell na mecânica quântica (consulte o artigo de Pisier), foi usada por Linial e Shraibman no trabalho sobre complexidade da comunicação e até se mostrou útil no trabalho de análise de dados privados (plug descarado).

Sasho Nikolov
fonte
1
Aqui está outro texto sobre a desigualdade de Grothendieck e CS. Mas não estou qualificado para comentar.
babou
Uma palestra de Giles Pisier no IHES também pode ser interessante: dailymotion.com/video/… (infelizmente é interrompida por anúncios irritantes).
amigos estão dizendo sobre Sasho Nikolov
17

XX{simple, dependent, polymorphic, higher-order}

Dave Clarke
fonte
1
12

p

Estou supondo que a visão de Mulmuley de generalização da hipótese de Riemann sobre campos finitos provenientes das conjecturas de Weil possa ser pensada como fazendo perguntas que originalmente tiveram resultados frutíferos da co-homologia ética de Grothendieck.

T ....
fonte
1
Essas aplicações são teóricas em ciência da computação? Tudo parece matemática para mim - ou provavelmente esse outro pedaço do TCS.
Dave Clarke
7
VNPVP