45 artigos
Este trabalho apresenta a linguagem SCORE e demonstra, com auxílio de um assistente de prova, como interpretar suas operações de pilha como bijeções totais, permitindo que todos os termos do modelo computacional sejam vistos como bijeções totais em vez de parciais.
Este trabalho demonstra que qualquer código localmente decodificável relaxado (RLDC) com consultas e erro de sombreamento abaixo de um certo limiar pode ser convertido em um código localmente decodificável (LDC) padrão com parâmetros comparáveis, generalizando resultados anteriores ao remover a exigência de linearidade e estabelecendo limites inferiores aprimorados para RLDCs, RLCCs e PCPPs.
Este livro apresenta um levantamento dos avanços recentes na lista de decodificação de códigos de Reed-Solomon e famílias relacionadas, destacando algoritmos eficientes que alcançam a capacidade teórica com tamanho de lista ótimo e complexidade de tempo quase linear ou sublinear.
Este trabalho apresenta um algoritmo randomizado de tempo polinomial para aprender determinantes lidos uma única vez (RODs) ao conectar o problema à versão de caixa-preta do Problema de Atribuição de Menores Principais (PMAP), demonstrando que ambos são equivalentes e resolvendo o PMAP através da investigação da propriedade de extensão de posto um em matrizes densas.
Este trabalho propõe um algoritmo quântico para teste de isomorfismo aproximado de grafos que utiliza passeios quânticos MNRS sobre o produto dos grafos, alcançando uma complexidade de consulta de O(n^3/2 log n/ε) e estabelecendo uma aceleração polinomial genuína sobre o limite inferior clássico de Ω(n^2).