45 artigos
Este artigo demonstra que o problema de decisão de raio de cobertura aproximado em reticulados na norma é NP-difícil para uma função explícita de fator de aproximação quando , estabelecendo a primeira prova de dureza para esse problema em normas explícitas.
Este artigo fecha a lacuna de complexidade deixada por trabalhos anteriores ao provar, sob a hipótese ETH, que a dependência duplamente exponencial no número de variáveis existenciais é ótima para QBFs em CNF de aridade limitada, enquanto demonstra que o caso restrito de dois blocos de quantificadores (-QBF) admite um algoritmo quase ótimo com complexidade significativamente reduzida.
O artigo apresenta o AlphaEvolve, um agente de mutação de código baseado em LLM que, atuando como um único meta-algoritmo, estabeleceu novos limites inferiores para cinco números de Ramsey clássicos e recuperou com sucesso os limites conhecidos para todos os casos exatos.
Este artigo estabelece explicitamente que o tamanho ótimo de um circuito varia no máximo em sob perturbações na tabela verdade, estendendo esse limite para distâncias de Hamming gerais e confirmando sua otimalidade para através de uma verificação exaustiva baseada em SAT.
Este artigo propõe um quadro unificador para os teoremas de dicotomia de complexidade em redes de tensores booleanos, classificando os problemas não resolvidos em nove casos baseados em grupos finitos de matrizes complexas e apresentando avanços significativos na resolução de casos cíclicos de ordem superior.
Este trabalho melhora o tempo de execução para o algoritmo de aproximação dos problemas de -média e -means em espaços euclidianos de baixa dimensão e estabelece um limite inferior quase correspondente, demonstrando que tal complexidade é essencial sob a Hipótese do Tempo Exponencial com Lacuna.
Este artigo argumenta que a vantagem quântica já foi alcançada, apesar da falta de consenso, e propõe os próximos passos teóricos e experimentais para o campo.
Este artigo demonstra que o problema de determinar a viabilidade de limpar ou sobreviver no Tetris com uma única peça tetromino (exceto a peça O) é NP-difícil sob o sistema de rotação padrão, refutando uma conjectura antiga, enquanto estabelece que o problema se torna polinomial para peças do tipo dominó e para peças $1 \times k$ em condições específicas de tabuleiro.
O artigo demonstra que, sob a suposição de segurança do problema Learning with Errors (LWE), nenhum algoritmo quântico pode automatizar fracamente a busca de provas no sistema -Frege, estabelecendo assim o primeiro resultado de dificuldade contra a automação quântica de prova proposicional.
Este trabalho apresenta um esquema que permite a estimativa diferenciadamente privada de funções de caixa-preta arbitrárias, equilibrando a eficiência estatística e a eficiência de oráculo, enquanto estabelece limites inferiores que demonstram a quase otimalidade da abordagem proposta.
Este artigo apresenta um teste de isomorfismo em tempo polinomial para extensões de grupos abelianos por grupos gerados por um número limitado de elementos, generalizando resultados anteriores e introduzindo um algoritmo eficiente para calcular o grupo de unidades de um anel finito.
Este artigo compara três semânticas de satisfatibilidade para lógica quântica em dimensões fixas, demonstrando que a semântica padrão é estritamente mais expressiva que as semânticas de projetores comutantes globais e booleanos parciais locais, ao apresentar uma fórmula explícita que é satisfatível apenas na primeira.
Este artigo estabelece uma estrutura de mudança de base que permite estender resultados sobre funções de tensores para corpos gerais, demonstrando que a rank de fatia de tensores 3D é linearmente limitada pela rank geométrica e é quase supermultiplicativa, garantindo assim a existência da rank de fatia assintótica.
Este artigo apresenta um novo método combinando substituição e busca por retrocesso para provar que a complexidade bilinear da multiplicação de matrizes $3 \times 3\mathbb{F}_2$ é de pelo menos 20, superando o limite inferior anterior de 19.
Este artigo apresenta algoritmos determinísticos e limites estruturais para a fatoração de polinômios esparsos com grau individual limitado, incluindo a recuperação de fatores a partir de acesso de caixa-preta e a eliminação de restrições de característica dos corpos.
Este artigo propõe um novo framework unificado e agnóstico a domínios para calcular o "bus-factor" como um problema de otimização combinatória, introduzindo uma medida baseada em robustez de rede que captura tanto a perda de cobertura quanto a fragmentação do projeto, e apresentando algoritmos de aproximação eficientes que demonstram superioridade em estabilidade e informatividade em comparação com abordagens existentes.
Este artigo apresenta uma proposta alternativa para demonstrar vantagem em informação quântica baseada em desigualdades de Bell e jogos CHSH repetidos em paralelo, oferecendo um verificador eficiente e um provador quântico robusto a ruídos que supera a abordagem experimental recente de Kretschmer et al. ao utilizar uma medida de memória fundamentada em informação em vez da contagem de qubits.
O artigo demonstra que a diferença entre o tamanho mínimo de um circuito booleano e o de uma fórmula sobre a base AIG é sempre 0 ou 1, estabelecendo teoremas que definem quando o compartilhamento de portas é necessário e como essa lacuna unitária surge exclusivamente de um único gate com fan-out 2.
Este artigo caracteriza a solvabilidade de um novo tipo de quebra-cabeça de ordenação em grades, fornecendo uma fórmula para contar soluções válidas, um algoritmo linear para corrigir configurações insolúveis e demonstrando que a generalização do problema para permutações arbitrárias é NP-completa.
O artigo demonstra que certos problemas de decisão polinomiais, que exigem a execução causal de um token através de uma sequência de passos, possuem uma limitação intrínseca de tempo causal linear () que impede qualquer aceleração assintótica por paralelismo, provando que nenhuma família de circuitos clássicos em pode implementá-los quando a profundidade do circuito é interpretada como tempo paralelo realizável.