Ao construir cuidadosamente um gráfico multidimensional e bem conectado, uma equipe de pesquisadores finalmente criou um código testável localmente há muito procurado que pode revelar imediatamente se ele foi corrompido.
Suponha que você esteja tentando transmitir uma mensagem. Converta cada caractere em bits e cada bit em um sinal. Em seguida, envie-o por cobre, fibra ou ar. Por mais que você tente ser o mais cuidadoso possível, o que é recebido do outro lado não será igual ao que você começou. O ruído nunca falha em corromper.
Na década de 1940, os cientistas da computação enfrentaram pela primeira vez o problema inevitável do ruído. Cinco décadas depois, eles criaram uma abordagem elegante para contorná-la: e se você pudesse codificar uma mensagem de forma que fosse óbvia se ela tivesse sido distorcida antes mesmo de seu destinatário lê-la? Um livro não pode ser julgado pela capa, mas esta mensagem sim.
Eles chamaram essa propriedade de testabilidade local, porque tal mensagem pode ser testada super-rápido em apenas alguns pontos para verificar sua exatidão. Nos 30 anos seguintes, os pesquisadores fizeram progressos substanciais para criar esse teste, mas seus esforços sempre foram insuficientes. Muitos pensaram que a testabilidade local nunca seria alcançada em sua forma ideal.
Agora, em um preprint lançado em 8 de novembro, o cientista da computação Irit Dinur do Instituto de Ciência Weizmann e quatro matemáticos, Shai Evra, Ron Livne, Alex Lubotzky e Shahar Mozes, todos da Universidade Hebraica de Jerusalém, o encontraram.
“É um dos fenômenos mais notáveis que conheço na matemática ou na ciência da computação”, disse Tom Gur, da Universidade de Warwick. “Tem sido o Santo Graal de um campo inteiro.”
Sua nova técnica transforma uma mensagem em um super-canário, um objeto que atesta sua saúde melhor do que qualquer outra mensagem conhecida. Qualquer corrupção significativa que esteja enterrada em qualquer parte de sua superestrutura torna-se aparente a partir de testes simples em alguns pontos.
“Isso não é algo que parece plausível”, disse Madhu Sudan, da Universidade de Harvard. “Este resultado de repente diz que você pode fazer isso.”
A maioria dos métodos anteriores para codificação de dados dependia da aleatoriedade de alguma forma. Mas para testabilidade local, a aleatoriedade não pode ajudar. Em vez disso, os pesquisadores tiveram que conceber uma estrutura gráfica altamente não aleatória, inteiramente nova para a matemática, na qual basearam seu novo método. É tanto uma curiosidade teórica quanto um avanço prático para tornar a informação o mais resiliente possível.
Codificação 101
O ruído é onipresente na comunicação. Para analisá-lo sistematicamente, os pesquisadores primeiro representam as informações como uma sequência de bits, 1s e 0s. Podemos então pensar no ruído como uma influência aleatória que inverte certos bits.
Existem muitos métodos para lidar com esse ruído. Considere uma informação, uma mensagem tão curta e simples como 01. Modifique-a repetindo cada parte dela – cada bit – três vezes, para obter 000111. Então, mesmo se o ruído corromper, digamos, o segundo e o sexto bits – alterar a mensagem para 010110 – um receptor ainda pode corrigir os erros obtendo votos da maioria, duas vezes (uma para os 0s, uma vez para os 1s).
Esse método de modificar uma mensagem é chamado de código. Nesse caso, como o código também vem com um procedimento de correção de erros, é denominado código de correção de erros. Os códigos são como dicionários, cada um definindo um determinado conjunto de palavras-código, como 000111.
Para funcionar bem, um código deve ter várias propriedades. Em primeiro lugar, as palavras-código nele não devem ser muito semelhantes: se um código contivesse as palavras-código 0000 e 0001, seria necessário apenas um bit-flip de ruído para confundir as duas palavras. Em segundo lugar, as palavras-código não devem ser muito longas. A repetição de bits pode tornar a mensagem mais durável, mas também pode demorar mais para ser enviada.
Essas duas propriedades são chamadas de distância e taxa. Um bom código deve ter uma grande distância (entre palavras-código distintas) e uma alta taxa (de transmissão de informações reais). Mas como você pode obter as duas propriedades ao mesmo tempo? Em 1948, Claude Shannon mostrou que qualquer código cujas palavras-código fossem simplesmente escolhidas ao acaso teria um compromisso quase ideal entre as duas propriedades. No entanto, escolher palavras-código completamente aleatórias tornaria um dicionário imprevisível e excessivamente difícil de classificar. Em outras palavras, Shannon mostrou que existem bons códigos, mas seu método para fazê-los não funcionou bem.
“Foi um resultado existencial”, disse Henry Yuen, da Universidade de Columbia.
Nos 40 anos seguintes, os cientistas da computação trabalharam para descobrir receitas não aleatórias para organizar bits que se aproximassem do ideal aleatório. No final da década de 1980, seus códigos eram usados em tudo, desde CDs a transmissões por satélite.
Em 1990, os pesquisadores formularam a ideia de testabilidade local. Mas essa propriedade era diferente. Se você escolher um código aleatoriamente, como aconselhou Shannon, não há como ele ser um código testável localmente. Essas eram as borboletas albinas no universo dos códigos aleatórios – lindas, se é que existiam.
“Você realmente tem que trabalhar muito mais para mostrar que eles existem”, disse Yuen. “Não se preocupe em dar um exemplo explícito.”
Gráficos como códigos
Para entender por que a testabilidade é tão difícil de obter, precisamos pensar em uma mensagem não apenas como uma sequência de bits, mas como um gráfico matemático: uma coleção de vértices (pontos) conectados por arestas (linhas). Essa equivalência tem sido fundamental para a compreensão dos códigos desde que os primeiros códigos inteligentes foram criados por Richard Hamming, dois anos após o resultado de Shannon. (A perspectiva gráfica tornou-se particularmente influente após um artigo de R. Michael Tanner em 1981).
O trabalho de Hamming preparou o terreno para os códigos de correção de erros onipresentes da década de 1980. Ele propôs uma regra que determina que cada mensagem deve ser emparelhada com um conjunto de recibos, que mantém um registro de seus bits. Mais especificamente, cada recebimento é a soma de um subconjunto cuidadosamente escolhido de bits da mensagem. Quando esta soma tem valor par, o recibo é marcado 0, e quando tem valor ímpar, o recibo é marcado 1. Cada recibo é representado por um único bit, ou seja, que os pesquisadores chamam de cheque de paridade ou bit de paridade .
Hamming especificou um procedimento para anexar os recibos a uma mensagem. Um destinatário poderia então detectar erros ao tentar reproduzir os recibos, calculando as somas por si mesmo. Esses códigos de Hamming funcionam muito bem e são o ponto de partida para ver os códigos como gráficos e os gráficos como códigos.
“Para nós, pensar em um gráfico e em um código é a mesma coisa”, disse Dana Moshkovitz, da Universidade do Texas, Austin.
Para fazer um gráfico a partir de um código, comece com uma palavra-código. Para cada bit de informação, desenhe um vértice (ou nó), chamado de nó de dígito. Em seguida, desenhe um nó para cada um dos bits de paridade; estes são chamados de nós de paridade. Finalmente, desenhe linhas de cada nó de paridade até os nós de dígitos que devem se somar para formar seu valor de paridade. Você acabou de criar um gráfico a partir de um código.
Ver códigos e gráficos como equivalentes tornou-se parte integrante da arte de fazer códigos. Em 1996, Michael Sipser e Daniel Spielman usaram o método para criar um código inovador a partir de um tipo de gráfico denominado gráfico expansor. Seu código ainda não podia fornecer testabilidade local, mas provou ser ideal de outras maneiras e acabou servindo como base para os novos resultados.
Expandindo as possibilidades
Os gráficos expansores são diferenciados por duas propriedades que podem parecer contraditórias. Primeiro, eles são esparsos: cada nó está conectado a relativamente poucos outros nós. Em segundo lugar, eles têm uma propriedade chamada expansibilidade – a razão de seu nome – o que significa que nenhum conjunto de nós pode ser gargalos pelos quais poucas arestas passam. Cada nó está bem conectado a outros nós, em outras palavras – apesar da escassez de conexões que possui.
“Por que tal objeto deveria existir?” disse Evra. “Não é tão rebuscado pensar que, se você é esparso, não está tão conectado.”
Mas os gráficos de expansão são surpreendentemente fáceis de criar. Se você construir um gráfico de forma aleatória, escolhendo conexões aleatoriamente entre os nós, um gráfico expansor resultará inevitavelmente. Eles são como uma fonte de aleatoriedade pura e não refinada, tornando-os blocos de construção naturais para os códigos bons que Shannon apontou.
Sipser e Spielman descobriram como transformar um gráfico expansor em um código. As palavras-código que eles criaram foram criadas a partir de muitas palavras muito mais curtas produzidas por um código de Hamming, que eles chamaram de código pequeno. Os bits de suas palavras-código foram representados como as bordas do gráfico do expansor. E todas as receitas para o pequeno código foram representadas em cada nó.
Com efeito, Sipser e Spielman mostraram que se você definir os pequenos códigos em cada nó com boas propriedades, então, como o gráfico está tão bem conectado, essas propriedades se propagam para o código global. Essa propagação deu a eles uma maneira de criar um bom código.
“Expansão, expansão e novamente expansão”, disse Evra. “Esse é o segredo do sucesso.”
No entanto, a testabilidade local não foi possível. Suponha que você tenha uma palavra-código válida de um código de expansão e tenha removido um recibo, ou bit de paridade, de um único nó. Isso constituiria um novo código, que teria muito mais palavras-código válidas do que o primeiro código, uma vez que haveria um recibo a menos que eles precisariam satisfazer. Para alguém trabalhando com o código original, essas novas palavras-código satisfariam os recibos na maioria dos nós – todos eles, exceto aquele em que o recibo foi apagado. E ainda, como os dois códigos têm uma grande distância, a nova palavra-código que parece correta estaria extremamente longe do conjunto original de palavras-código. A testabilidade local era simplesmente incompatível com os códigos de expansão.
Para obter a testabilidade, os pesquisadores teriam que descobrir como trabalhar contra a aleatoriedade que antes havia sido tão útil. No final, os pesquisadores foram onde a aleatoriedade não conseguiu: para dimensões superiores.
O oposto de aleatório
Nem sempre estava claro que eles conseguiriam. A testabilidade local foi alcançada em 2007, mas apenas às custas de outros parâmetros, como taxa e distância. Em particular, esses parâmetros seriam degradados conforme uma palavra-código se tornasse grande. Em um mundo que busca constantemente enviar e armazenar mensagens maiores, esses retornos decrescentes eram uma grande falha. (Embora na prática, mesmo os códigos existentes testáveis localmente já eram mais poderosos do que a maioria dos engenheiros precisava usar.)
A hipótese de que um código poderia ser encontrado com taxa, distância e testabilidade local ideais – que permaneceram constantes mesmo quando as mensagens foram aumentadas – veio a ser conhecida como conjectura c3. Os resultados anteriores fizeram com que alguns pesquisadores pensassem que a solução era inevitável. Mas o progresso começou a diminuir e outros resultados sugeriram que a conjectura pode ser falsa.
“Muitos na comunidade pensaram que era um sonho bom demais para ser verdade”, disse Gur. “As coisas pareciam bastante sombrias.”
Mas em 2017, uma nova fonte de ideias surgiu. Dinur e Lubotzky começaram a trabalhar juntos enquanto participavam de um programa de pesquisa de um ano no Instituto de Estudos Avançados de Israel. Eles chegaram a acreditar que um resultado de 1973 do matemático Howard Garland poderia conter exatamente o que os cientistas da computação procuravam. Considerando que os gráficos expansores comuns são estruturas essencialmente unidimensionais, com cada borda se estendendo em apenas uma direção, Garland criou um objeto matemático que poderia ser interpretado como um gráfico expansor que abrangia dimensões superiores, com, por exemplo, as bordas do gráfico redefinidas como quadrados ou cubos.
Os gráficos de expansão de alta dimensão de Garland tinham propriedades que pareciam ideais para testabilidade local. Eles devem ser construídos deliberadamente do zero, tornando-os uma antítese natural da aleatoriedade. E seus nós estão tão interconectados que suas características locais se tornam virtualmente indistinguíveis de como são globalmente.
“Para mim, os gráficos de expansão de alta dimensão são uma maravilha”, disse Gur. “Você faz um pequeno ajuste em uma parte do objeto e tudo muda.”
Lubotzky e Dinur começaram a tentar criar um código baseado no trabalho de Garland que pudesse resolver a conjectura c3. Evra, Livne e Mozes logo se juntaram à equipe, cada um deles especialista em diferentes aspectos dos expansores de alta dimensão.
Logo eles estavam apresentando seu trabalho em seminários e palestras, mas nem todos estavam convencidos de que a teoria dos expansores de alta dimensão abriria o caminho a seguir. Para compreendê-lo, era necessário subir uma curva de aprendizado íngreme.
“Na época, parecia tecnologia da era espacial, ferramentas matemáticas sofisticadas e exóticas nunca vistas antes na ciência da computação”, disse Gur. “Parecia um exagero.”
Em 2020, os pesquisadores pararam, até que perceberam que poderiam sobreviver sem depender das novas ferramentas mais complicadas. A inspiração que eles ganharam com os expansores de alta dimensão foi o suficiente.
Erros de propagação
Em seu novo trabalho, os autores descobriram como montar gráficos expansores para criar um novo gráfico que conduza à forma ideal de código testável localmente. Eles chamam seu gráfico de complexo de Cayley esquerda-direita.
Como no trabalho de Garland, os blocos de construção de seu gráfico não são mais arestas unidimensionais, mas quadrados bidimensionais. Cada bit de informação de uma palavra-código é atribuído a um quadrado, e bits de paridade (ou recibos) são atribuídos a arestas e cantos (que são nós). Cada nó, portanto, define os valores dos bits (ou quadrados) que podem ser conectados a ele.
Para ter uma ideia de como é o gráfico, imagine observá-lo de dentro, em uma única aresta. Eles constroem seu gráfico de forma que cada aresta tenha um número fixo de quadrados anexados. Portanto, do seu ponto de vista, você se sentiria como se estivesse olhando pela lombada de um livreto. No entanto, dos outros três lados das páginas do livreto, você veria as lombadas de novos livretos se ramificando a partir deles também. Os livretos continuariam se ramificando a partir de cada borda ad infinitum.
“É impossível visualizar. Esse é o ponto principal “, disse Lubotzky. “É por isso que é tão sofisticado.”
Crucialmente, o gráfico complicado também compartilha as propriedades de um gráfico expansor, como dispersão e conexão, mas com uma estrutura local muito mais rica. Por exemplo, um observador sentado em um vértice de um expansor de alta dimensão poderia usar essa estrutura para inferir diretamente que todo o gráfico está fortemente conectado.
“Qual é o oposto de aleatoriedade? É estrutura “, disse Evra. “A chave para a testabilidade local é a estrutura.”
Para ver como esse gráfico leva a um código testável localmente, considere que em um código expansor, se um bit (que é uma aresta) estiver com erro, esse erro só pode ser detectado verificando os recebimentos em seus nós imediatamente vizinhos. Mas em um complexo de Cayley esquerda-direita, se um bit (um quadrado) estiver errado, esse erro será visível em vários nós diferentes, incluindo alguns que nem mesmo estão conectados uns aos outros por uma aresta.
Dessa forma, um teste em um nó pode revelar informações sobre erros de nós distantes. Ao fazer uso de dimensões superiores, o gráfico é, em última análise, conectado de maneiras que vão além do que normalmente chamamos de conexões.
Além da testabilidade, o novo código mantém a taxa, distância e outras propriedades desejadas, até mesmo como escala de palavras-código, provando a conjectura c3 verdadeira. Ele estabelece um novo estado da arte para códigos de correção de erros e também marca a primeira recompensa substancial de trazer a matemática de expansores de alta dimensão para lidar com códigos.
“É uma forma completamente nova de olhar para esses objetos”, disse Dinur.
Aplicações práticas e teóricas devem seguir-se em breve. Diferentes formas de códigos testáveis localmente estão agora sendo usadas em finanças descentralizadas, e uma versão ideal permitirá ferramentas descentralizadas ainda melhores. Além disso, existem construtos teóricos totalmente diferentes na ciência da computação, chamados de provas verificáveis probabilisticamente, que apresentam certas semelhanças com códigos testáveis localmente. Agora que encontramos a forma ideal do último, parece provável que surjam versões recordes do primeiro.
Em última análise, o novo código marca um marco conceitual, o maior passo além dos limites para códigos definidos por aleatoriedade. A única questão que resta é se há limites verdadeiros para o quão bem as informações podem ser forjadas.
Publicado em 25/11/2021 11h39
Artigo original:
Estudo original: