Aplicações do TCS à matemática clássica?

60

No TCS, geralmente usamos resultados e idéias poderosos da matemática clássica (álgebra, topologia, análise, geometria etc.).

Quais são alguns exemplos de quando foi o contrário?

Aqui estão alguns que eu conheço (e também para dar uma amostra do tipo de resultado que estou perguntando):

  • Espumas cúbicas (Guy Kindler, Ryan O'Donnell, Anup Rao e Avi Wigderson: Cubos Esféricos e Arredondamento em Altas Dimensões, FOCS 2008)
  • O Programa de Teoria da Complexidade Geométrica. (Embora esta seja tecnicamente uma aplicação da geometria algébrica e da teoria da representação ao TCS, eles foram levados a introduzir novos grupos quânticos e novas idéias puramente algebro-geométricas e teóricas da representação em sua busca por P vs NP.)
  • Trabalhe em incorporações métricas inspiradas em algoritmos de aproximação e resultados de inadequação

Em particular, não estou procurando aplicações do TCS na lógica (teoria dos modelos finitos, teoria da prova etc.), a menos que sejam particularmente surpreendentes - o relacionamento entre o TCS e a lógica é muito próximo, padrão e histórico para os propósitos desta questão.

Joshua Grochow
fonte
11
Isso é um pouco complicado de responder. A combinatória cai fora da matemática clássica?
Arnab
2
A combinatória é definitivamente a matemática clássica, mas acho que o mesmo comentário vale para a combinatória e para a lógica. Assim: a conjectura de Kakeya em campo finito é um bom exemplo, enquanto novos projetos combinatórios motivados por PRGs estão mais em jogo.
Joshua Grochow 17/08/10
Você pode encontrar bons exemplos procurando resultados publicados em, por exemplo, Annals of Math pela comunidade TCS.
MCH 24/10

Respostas:

32

Os expansores foram desenvolvidos em grande parte no TCS e possuem conexões e aplicações profundas na matemática.

Gil Kalai
fonte
22

Há a prova de Dvir da conjectura de Kakeya no campo finito.

Dai Le
fonte
3
Isso foi motivado por um problema em extratores / fusões (consulte o artigo posterior de Zeev e Avi Wigderson). Outras melhorias (de Madhu Sudão, Shubhangi Saraf, Swastik Kopparty e Zeev Dvir) usaram mais idéias da ciência da computação teórica, especificamente da decodificação de códigos de lista (o método das multiplicidades).
Dana Moshkovitz 17/10/10
11
Duas observações: O método algébrico usado por Dvir é um dos métodos usados ​​para resolver o problema clássico sobre distâncias para conjuntos planares. terrytao.wordpress.com/2010/11/20/… e gilkalai.wordpress.com/2010/11/20/… .
Gil Kalai
2
Segundo, métodos de incidência e resultados de geometria computacional e discreta tiveram aplicações anteriores ao (real) problema de Kakeya.
Gil Kalai
20

Os princípios de invariância foram motivados pela dureza da aproximação, mas são teoremas analíticos úteis. O princípio: uma função de baixo grau, na qual cada uma das variáveis ​​tem pouca influência, se comporta quase da mesma forma, não importa se as entradas são variáveis ​​aleatórias independentes ou variáveis ​​aleatórias Gaussianas (correspondentes). Essa é uma generalização do teorema do limite central; lá a função é a média das variáveis.

Estabilidade de ruído de funções com baixas influências: invariância e otimização E. Mossel, R. O'Donnell, K. Oleszkiewicz. Annals of Mathematics 171 (1), pp. 295-341 (2010). FOCS '05.

Teoremas de teste de baixo grau foram motivados por aplicativos PCP, mas são teoremas algébricos interessantes. O princípio: uma função variada sobre um campo finito que, em média, sobre as linhas em , está próxima na distância de Hamming a um polinômio de baixo grau na linha , está próxima na distância de Hamming a um polinômio de baixo grau em o inteiro .F F n F nnFFnFn

A proximidade na distância de Hamming a um polinômio de baixo grau em um determinado espaço significa que a função se identifica com um polinômio de baixo grau em alguma fração não desprezível do espaço.

Teste de baixo grau aprimorado e suas aplicações . S. Arora e M. Sudan. Em ACM STOC 1997.

Teste Sub-Constante de Baixo Grau de Probabilidade de Erro e Caracterização Sub-Constante de Probabilidade de Erro de NP , R.Raz, S.Safra, Procedimento da 29ª STOC, 1997, pp. 475-484

Dana Moshkovitz
fonte
19

Embora eu seja tendencioso, acho justo dizer que várias idéias da TCS contribuíram para o progresso na conjectura inversa da norma de Gowers, veja, por exemplo, o artigo de Green e Tao .

Manu
fonte
7
Além disso, é justo dizer que componentes da prova do teorema de Szemeredi através do lema da regularidade do hipergrafo (de Gowers, Tao, Rodl, Schacht e outros) foram influenciados pelo trabalho de Alon, Fischer, Shapira e outros no desenvolvimento de versões mais fortes do lema de regularidade do gráfico para provar a testabilidade das propriedades do gráfico.
Arnab
18

A teoria da computabilidade faz parte do TCS? Nesse caso, a Teoria da Computabilidade e a Geometria Diferencial de Bob Soare, que expõe as aplicações dos resultados que ele obteve com o Csima, é um exemplo.

Não sei por que o link não está aparecendo .... Aqui: http://www.people.cs.uchicago.edu/~soare/res/Geometry/geom.pdf

Aaron Sterling
fonte
2
Independentemente de você contar ou não a computabilidade como parte do TCS, esse é um exemplo que eu simplesmente esqueci de mencionar. É ainda mais legal porque isso pode ser feito usando a complexidade de Kolmogorov :).
Joshua Grochow 17/08/10
17

Extratores é outro lugar para procurar. Por exemplo, o artigo de Barak-Kindler-Shaltiel-Sudakov-Wigderson'04 fornece (entre outras coisas) construções melhoradas dos gráficos de Ramsey (um problema que estava aberto há algum tempo em matemática discreta).

Moritz
fonte
15

De Wolf e Drucker mencionam em sua pesquisa sobre provas quânticas sobre uma conexão surpreendente entre a complexidade de consultas quânticas e a aproximação de funções simétricas por polinômios.ϵ

ilyaraz
fonte
13

A construção do expansor Zig-Zag foi usada para construir vários exemplos interessantes de grupos com certas propriedades inesperadas, consulte Meshulam-Wigderson , Rozenman-Shalev-Wigderson . A construção em si é muito interessante do ponto de vista matemático, uma vez que usou ferramentas completamente diferentes (motivadas pelo ponto de vista do CS de lidar com entropia) para construir expansores do que as construções anteriores. (No entanto, talvez o aplicativo mais famoso esteja dentro do algoritmo de espaço de log do TCS- Reingold para conectividade não direcionada .)

Boaz Barak
fonte
10

Deixe-me mencionar mais algumas aplicações:

Talvez a contribuição mais importante do TCS para a matemática pura seja a arte das reduções. As reduções da forma usada pelo TCS na complexidade computacional e em outros locais representam um paradigma / ferramenta matemática mais desenvolvido no TCS em comparação com outras áreas da matemática.

A noção de uma prova probabilística: Aqui não me refiro ao método probabilístico (que está enraizado na matemática, mas tem muitas aplicações no CS), mas sim no fato de que uma afirmação matemática como a afirmação que afirma um determinado número é primordial, pode receber uma prova "além de qualquer dúvida razoável". É uma inovação conceitual vinda do CS, embora ainda não tenha muitas aplicações na maneira como a matemática é praticada.

Gil Kalai
fonte
11
Eu não sabia que outras áreas da matemática usaram a idéia de reduções significativamente. Eu realmente aprecio qualquer referência ou indicação que você possa dar a esses trabalhos! Além disso, tive a impressão de que as provas probabilísticas surgiram da pura combinatória, e não da TCS?
21810 Joshua Grochow
3
Expliquei o que quero dizer com "prova probabilística" na versão editada da minha resposta. Em relação às reduções: A complexidade computacional é uma área da matemática enraizada na ciência da computação. Uma característica dessa área é o uso de reduções, que desempenham um papel importante no nível conceitual e técnico. É muito mais desenvolvido do que técnicas semelhantes em outras áreas da matemática. Portanto, a arte das reduções no TCS pode ser considerada uma aplicação importante do TCS na matemática. Eu acho que as reduções do tipo CS também influenciaram os matemáticos em outras áreas, e ainda há mais por vir.
Gil Kalai
Joshua, deixe-me fazer uma analogia. Suponha que alguém se refira ao "cálculo" como uma das maiores aplicações da física na matemática clássica. Também se pode dizer que o cálculo é importante principalmente para atacar problemas provenientes da física que não eram "matemática clássica" antes. Ainda acho que o cálculo é a maior contribuição da física para a matemática. Da mesma forma, as reduções do tipo usado na teoria da complexidade são uma importante contribuição do TCS para a matemática. Ele descreve um grande aparato matemático e idéias matemáticas que têm valor independente (não tão importante como cálculo, no entanto.).
Gil Kalai
G
11
@ JoshuaGrochow, não será difícil encontrar exemplos não triviais de "caso geral para reduções especiais". Por exemplo, a pesquisa da Cassaza que vinculei em minha resposta tem toneladas de reduções não triviais entre problemas equivalentes ao problema de Kadison-Singer, alguns deles muito restritos à primeira vista. Entendo que a geometria aritmética também está cheia dessas coisas, você pode saber mais. Não sei até que ponto o TCS pode reivindicar crédito pela introdução dessa abordagem a problemas intratáveis.
Sasho Nikolov
9

A prova construtiva de Moser do lema local de Lovasz usa idéias de ciência da computação, fornece uma nova prova do lema local de Lovasz e resolve um problema que as pessoas pensam há bastante tempo.

Peter Shor
fonte
9

O método da função de barreira de Batson-Spielman-Srivastava teve várias aplicações na geometria e na análise funcional, surgiu na ciência da computação e é uma forma muito original de argumento de função potencial, remanescente do método dos estimadores pessimistas. Além disso, é contrário à sabedoria convencional que a análise do polinômio característico das matrizes aleatórias é intratável, e é melhor observar os momentos da matriz.

O método da função de barreira foi desenvolvido primeiro para provar a existência de (e construir em tempo polinomial determinístico) sparsifiers de gráficos que preservam suas propriedades espectrais. Tais esparsificadores foram motivados por aplicações algorítmicas: essencialmente, qualquer algoritmo que precise calcular aproximadamente os cortes pode ser acelerado ao receber como entrada uma versão esparsa da entrada original.

1n

Avançando para 2013, o método da função de barreira, em esteróides, e aumentado com a maquinaria de polinômios entrelaçados, foi usado por Marcus, Srivastava e Spielman , para resolver um dos problemas mais notórios na análise funcional, o problema de Kadison-Singer . Esse problema surge de questões fundamentais da física matemática, mas vai muito além - é conhecido por ser equivalente a dezenas de problemas em toda a matemática. Sem mencionar que muitos analistas (incluindo Kadison e Singer) nem pensaram que o problema tivesse uma resolução positiva (a pesquisa citada por Cassaza et al. Especula sobre possíveis contra-exemplos).

Sasho Nikolov
fonte
5

Um exemplo que vem à mente é o Teorema de Incorporação de Higman e suas consequências teóricas em grupo.

Teorema da incorporação de Higman: Um grupo G é gerado finitamente com uma apresentação recursiva se G for um subgrupo de um grupo finitamente apresentado.

(Observe que a parte esquerda da equivalência possui um componente computacional enquanto a direita é puramente teórica de grupo).

mike
fonte
11
GHGWord(G)NPG
5

O significado de aleatoriedade , o que é considerado uma "sequência aleatória" e questões relacionadas foram importantes em matemática, teoria das probabilidades e estatística por séculos. A ciência da computação teórica (e a teoria da complexidade) oferece insights profundos e convincentes muito robustos para a compreensão da aleatoriedade.

Enquanto o método probabilístico iniciado na des randomização da matemática, que é um importante conceito matemático, é desenvolvido principalmente no CS.

Isso está relacionado à resposta de Moritz .

Gil Kalai
fonte
5

Teoria de autômatos e algebraicidade

A teoria dos autômatos deu alguns resultados interessantes para caracterizar a algebraicidade. Menciono dois deles, com referências. Não é de forma alguma exaustivo.

Fq(t)

Fq(t)qq=pspsFq[[t]]Fq

Fq(t)Fq(t)

i=0aitiFq(t){ai}i=0p

Fq(t)

iIxiti,
IQFq(t)

iIaitiFq(t){ai}iIp

2. Números transcendentais

Sequências automáticas também são usadas para caracterizar números transcendentais. Por exemplo,

b2xRx={xi}i=0b

  1. xx
  2. xbx
  3. x

Obviamente, o primeiro item é um resultado muito clássico!

Referências.

[1] Gilles Christol. Conjuntos pré-périodiques k-reconnaissables . Em Teoria da Ciência da Computação 9 (1), pp 141-145, 1979.

[2] Kiran S. Kedlaya. Autômatos finitos e extensões algébricas de campos de função . No Journal de thorie des nombres de Bordeaux 18 , pp 379-420, 2006. arXiv: math / 0410375 .

[3] Boris Adamcweski, Yann Bugeaud. Sobre a complexidade dos números algébricos I. Expansões em bases inteiras . In Annals of Mathematics 165 (2), pp 547-565, 2007.

Bruno
fonte
teorema (Adamczewski & Bugeaud [3]) pode estar errado ou ser mal interpretado
XL _At_Here_There
4

Lτ

L

τpτ(1+τ)cc

Bruno
fonte
1

O IMHO TCS é um ramo da matemática e eu diria um pouco mais amplo. Vivemos na era algorítmica, quase todo mundo, em todas as atividades humanas, inventa / reinventa algoritmos, principalmente heurísticos. Mas alguns desses algoritmos são 1. bons; 2. conter (enterrado) respostas para questões matemáticas profundas; 3. Aguarde uma análise / melhoria / atenção matemática profissional. Minha experiência pessoal: um poder impressionante de uma heurística de física / aprendizado de máquina, a Aproximação de Bethe, como uma técnica de prova. O principal problema é que possíveis encontros desse tipo acontecem principalmente no setor, onde ninguém se importa com essas informações / revelações não relacionadas ao produto.

gurvits leonídeos
fonte