Os resultados mais influentes de Lipton

Richard J. Lipton foi selecionado como o vencedor do Prêmio Knuth 2014 "por Introdução de Novas Idéias e Técnicas".

Quais são as suas principais idéias e técnicas que Lipton desenvolveu?

Nota. Esta questão se tornará um wiki da comunidade. Coloque uma dessas idéias, técnicas ou resultados por resposta.

O Teorema do Separador Planar afirma que em qualquer grafo plano $n$ vértice $G$ existe um conjunto de vértices cuja remoção deixa o gráfico desconectado em pelo menos dois componentes aproximadamente equilibrados. Além disso, esse conjunto pode ser encontrado em tempo linear. Esse resultado (apertado),comprovado por Lipton e Tarjan(aprimorando um resultado anterior da Ungar), é uma ferramenta poderosa para projetar algoritmos em gráficos planares. Ele fornece muitos algoritmos de tempo subexponenciais exatos para problemas difíceis de NP e algoritmos de aproximação de tempo polinomial aprimorados. Olhar apáginadawikipediaé um bom ponto de partida para explorar as inúmeras aplicações. Umapesquisa inicialcom detalhes de várias aplicações foi escrita por Lipton e Tarjan em 1980.$O(\sqrt{n})$

Karp-Lipton teorema indica que não podem ter de tamanho polinomial circuitos booleanos, a menos que a hierarquia polinomial colapsa para o seu segundo nível.$\mathsf{NP}$

Duas implicações desse teorema para a teoria da complexidade:

• provavelmente não tem de tamanho polinomial booleano circuitos; provar limites mais baixos em tamanhos de circuito é, portanto, uma abordagem possível para separar classes de complexidade.$\mathsf{NP}$
• Vários resultados são baseados nesse teorema para provar separações de classes de complexidade (por exemplo, o Teorema de Kannan).

Auto-redutibilidade aleatória do permanente . Lipton mostrou que, se existe um algoritmo que calcula corretamente a fração permanente de de todos os F n × n , onde F é um campo finito de tamanho de pelo menos 3 n , esse algoritmo pode ser usado como uma caixa preta para calcular a permanente de qualquer matriz com alta probabilidade.$1-1/(3n)$$\mathbb{F}^{n\times n}$$\mathbb{F}$$3n$

A idéia principal é que a permanente seja um polinômio de baixo grau; portanto, sua composição com uma função afim univariada é um polinômio univariado de baixo grau (em x ) e pode ser aprendido exatamente a partir de um pequeno número de valores via interpolação . Você pode escolher um B aleatório para que a composição seja distribuída como permanente de uma matriz aleatória para qualquer x . No x = 0 o polinômio univariada é apenas o permanente A . Detalhes podem ser encontrados no Capítulo 8 de Arora Barak .$A + xB$$x$$B$$x$$x = 0$$A$

Essa abordagem algébrica tem sido extremamente influente na teoria da complexidade. As idéias de Lipton levaram eventualmente à prova do teorema IP = PSPACE, à prova do teorema PCP e a resultados em códigos locais de correção de erros.

Não tenho 100% de certeza se a explicação abaixo é historicamente precisa. Caso contrário, fique à vontade para editar ou remover.

O teste de mutação foi inventado por Lipton. O teste de mutação pode ser visto como uma maneira de medir a qualidade ou eficácia de um conjunto de testes. A idéia principal é injetar falhas no programa a ser testado (ou seja, alterar o programa), preferencialmente os tipos de falhas que um programador humano provavelmente fará, e ver se a suíte de testes encontra as falhas introduzidas. Um exemplo típico do tipo de teste de mutação de falha a introduzir poderia ser substituir x> 0 por x <0 ou substituir x por x + 1 ou x-1. A fração de falhas detectadas pelo conjunto de testes é a "pontuação de adequação de mutação" de um conjunto de testes. Falando muito livremente, pode-se pensar nisso como um método de Monte-Carlo para calcular o escore de adequação da mutação.

Mais abstratamente, pode-se dizer que o teste de mutação traz à tona uma simetria ou dualidade entre um programa e seus conjuntos de testes: não apenas o conjunto de testes pode ser usado para se tornar mais confiante sobre a correção de um programa, mas, inversamente, um programa pode ser usado para ganhar confiança sobre a qualidade de uma suíte de testes.

À luz dessa dualidade, o teste de mutação também é conceitualmente próximo à injeção de falha . Ambos são tecnicamente semelhantes, mas têm finalidades diferentes. O teste de mutação procura medir a qualidade do conjunto de testes, enquanto a injeção de falha procura estabelecer a qualidade do programa, geralmente a qualidade de seu tratamento de erros.

Recentemente, idéias do teste de mutação foram usadas para testar (formalizações de) teorias lógicas. Parafraseando o resumo de (4): Ao desenvolver formalizações não triviais em um provador de teoremas, uma quantidade considerável de tempo é dedicada à “depuração” de especificações e teoremas. Normalmente, especificações ou teoremas incorretos são descobertos durante tentativas de prova com falha. Essa é uma forma cara de depuração. Portanto, muitas vezes é útil testar conjecturas antes de embarcar em uma prova. Uma maneira possível de fazer isso é atribuir valores aleatórios às variáveis ​​livres da conjectura e depois avaliá-la. (4) usa mutações para testar a qualidade dos geradores de casos de teste usados.

História . De (1): A história do teste de mutação pode ser rastreada até 1971 em um artigo de Richard Richardton [...] O nascimento do campo também pode ser identificado em outros trabalhos publicados no final da década de 1970 por Lipton et al. (2) bem como Hamlet (3).

1. Repositório do Teste de Mutação: Teoria do Teste de Mutação .

2. RA DeMillo, RJ Lipton, FG Sayward, Dicas sobre Seleção de Dados de Teste: Ajuda para o Programador Praticante .

3. RG Hamlet, testando programas com a ajuda de um compilador .

4. S. Berghofer, T. Nipkow, Teste aleatório em Isabelle / HOL. .

Schwartz - Zippel - DeMillo-Lipton O lema é uma ferramenta fundamental na complexidade aritmética: basicamente, afirma que se você deseja saber se um circuito aritmético representa o polinômio zero, basta avaliar o circuito em uma entrada. Você obterá um valor diferente de zero com boa probabilidade se o circuito não representar o polinômio zero.

Esse é um lema particularmente importante, pois nenhum algoritmo determinístico em tempo polinomial é conhecido para esse problema.

O lema é geralmente conhecido como Schwartz-Zippel Lemma . Uma história desse lema pode ser encontrada no blog de Lipton .

A cobertura em sistemas de adição de vetores é difícil para o EXPSPACE : em RJ Lipton, O problema de alcançabilidade requer espaço exponencial , Relatório de pesquisa 63, Universidade de Yale, 1976.

$d$$\langle v_0,A\rangle$$v_0$$\mathbb{N}^d$$A$$\mathbb{Z}^d$$\mathbb{N}^d$$v\to v'$$u$$A$$v'=v+u$$v'$$v$$\mathbb{N}^d$$v_0\to v_1\to\cdots\to v_n$$v_n\geq v$$\mathbb{N}^d$$v_n(i)\geq v(i)$$1\leq i\leq d$. Combinado com um limite superior do EXPSPACE comprovado por C. Rackoff em 1978 , o resultado de Lipton mostra a integridade do EXPSPACE.

$v_n=v$

A complexidade da comunicação multipartidária e o modelo Número na testa foram introduzidos por Ashok K. Chandra , Merrick L. Furst e Richard J. Lipton em protocolos multipartidários , STOC 1983, doi: 10.1145 / 800061.808737 .

O modelo multipartidário é uma extensão natural do modelo de complexidade de comunicação de duas partes de Yao , onde Alice e Bob têm metades não sobrepostas dos bits de entrada e desejam se comunicar para calcular uma função predeterminada de toda a entrada. No entanto, estender a partição dos bits de entrada para mais partes geralmente não é muito interessante (para limites inferiores, geralmente é possível considerar apenas as duas primeiras partes).

$k$$k$$n$

$n$

$N$$k$$N$$k=3$$N$$O(\sqrt{\log N})$$N \le k(2^n-1)$$O(\sqrt{n})$

$^0$

$N$