Novos artigos mais importantes em complexidade computacional

Frequentemente ouvimos falar de pesquisas e publicações clássicas no campo da complexidade computacional (Turing, Cook, Karp, Hartmanis, Razborov etc.). Fiquei me perguntando se existem trabalhos publicados recentemente considerados seminais e uma leitura obrigatória. Por recente eu quero dizer nos últimos 5/10 anos.

O artigo recente de László Babai, mostrando que o isomorfismo gráfico está em quase-P, já é um clássico.

Aqui está uma exposição mais acessível do resultado publicado nos procedimentos do ICM 2018.

$O(n \log n)$

A importância está nos olhos de quem vê. No entanto, eu diria que a conjectura de dicotomia Feder – Vardi CSP, comprovada independentemente por A. Bulatov e D. Zhuk , é um resultado seminal.

Limites inferiores do circuito ACC não uniforme de Ryan Williams:

https://people.csail.mit.edu/rrw/acc-lbs.pdf

e verificação clássica de cálculos quânticos por Urmila Mahadev:

http://ieee-focs.org/FOCS-2018-Papers/pdfs/59f259.pdf

parecem bons candidatos

Este novo artigo de Hao Huang [1] (ainda não revisado por pares, tanto quanto eu sei) provavelmente se qualifica ... prova a conjectura de sensibilidade de Nisan e Szegedy, que está aberto há ~ 30 anos.

[1] Subgráficos induzidos de hipercubos e uma prova da conjectura de sensibilidade, Hao Huang. Manuscrito, 2019. https://arxiv.org/abs/1907.00847

O trabalho de Subhash Khot, Dor Minzer e Muli Safra, de 2018, "Conjuntos pseudo-aleatórios no gráfico de Grassmann têm expansão quase perfeita" nos levou a "meio caminho" da Conjectura de jogos exclusivos e é metodologicamente bastante interessante de acordo com pessoas mais conhecedoras que eu. Citando Boaz Barak ,

Isso estabelece, pela primeira vez, a dureza de jogos únicos no regime pelos quais um algoritmo de tempo subexponencial era conhecido e, portanto, (necessariamente) utiliza uma redução com alguma (grande) explosão polinomial. Embora teoricamente ainda seja possível que a conjectura de jogos únicos seja falsa (como eu pessoalmente acreditava que seria o caso até essa última sequência de resultados), o cenário mais provável é agora que o UGC é verdadeiro e a complexidade do UG (s). , c) o problema se parece com o seguinte ...

O artigo fez com que alguns pesquisadores (incluindo Barak) mudassem publicamente sua opinião sobre a verdade da UGC (de falsa para verdadeira).

"Sobre a possibilidade de algoritmos SAT mais rápidos" por Pătraşcu & Williams (SODA 2010). Ele fornece relações estreitas entre a complexidade da solução do CNF-SAT e a complexidade de alguns problemas polinomiais (conjunto dominante em k, soma d, etc.).

Os resultados são duplos: ou podemos melhorar a complexidade da solução de alguns problemas polinomiais e, portanto, o ETH é falso e obtemos um algoritmo melhor para o CNF-SAT. Ou ETH é verdadeiro e, portanto, obtemos limites mais baixos em vários problemas polinomiais.

O artigo é surpreendentemente fácil de ler e entender. Para mim, é o começo real da complexidade refinada.

Está um ano além do limite de 10 anos, mas “Delegar Computação: Provas Interativas para Trouxas”, de Goldwasser, Kalai e Rothblum, tem sido um artigo extremamente influente. O resultado principal é que existe uma prova interativa para qualquer cálculo uniforme do espaço de log em que o provador executa no tempo poly (n) e o verificador no tempo n * polylog (n) com polylog (n) bits de comunicação.

O artigo iniciou a pesquisa sobre provas interativas e a computação verificável para problemas em P tem sido incrivelmente influente na criptografia, onde ela e o trabalho que se seguiu tornaram praticamente interativas as provas interativas do mundo real.

Para obter impacto, alcance o documento de referência da Indyk e da Backurs, fornecendo limites para editar o cálculo à distância. Este artigo mostra limites para a computação, vinculando k-SAT e SETH. Para limitar o cálculo da distância de levenshtein, entre as strings, o artigo mostra limites estreitos para calcular a distância de edição - melhor do que a SETH é violada (a SETH pode ser falsa em primeiro lugar, ou ainda ter limites inferiores mais apertados ). A aplicabilidade do SETH a possíveis problemas em P, para obter limites ou limitar a aplicação de algoritmos (possivelmente computação!) É nova.

Ou este artigo de P. Goldberg e C. Papadimitrou, sobre uma complexidade uniforme para as funções totais. Para uma teoria da complexidade unificada das funções totais .

Não tenho certeza se isso se qualifica - ele tem mais de 10 anos e não é realmente um resultado de complexidade computacional em si - mas acho que o par de {Teorema da estrutura gráfica, Teorema secundário do gráfico} vale a pena notar. Foi concluída em 2004 e estabelece uma equivalência entre "Complexidade topológica limitada" e "Não contém algum conjunto finito de menores". Cada teorema estabelece uma direção da equivalência.

Isso teve um impacto primordial no âmbito da teoria da complexidade parametrizada, onde uma dessas medidas geralmente é limitada, permitindo algoritmos eficientes que aproveitam a outra. Então, eu diria que esses resultados tiveram um impacto substancial na complexidade computacional, mesmo que eles não venham diretamente desse campo.