87 artigos
Este artigo apresenta o Huffman-Bucket Sketch (HBS), uma estrutura de dados simples e mesclável que comprime losslessly um esboço HyperLogLog para o espaço ótimo de bits, mantendo atualizações em tempo constante e a capacidade de mesclagem ao utilizar uma codificação Huffman baseada na distribuição concentrada de ranks.
Este artigo apresenta um estudo sobre subconjuntos minimamente insatisfiáveis (MUSs) de fórmulas 2-CNF, incluindo um procedimento de tempo linear para reconhecê-los, a análise da complexidade computacional para encontrar MUSs específicos e um algoritmo incremental polinomial para MUSs que contêm cláusulas unitárias.
O artigo introduz o esboço de Bloco Tensor Train Esparsa (BSTT), uma projeção aleatória estruturada que unifica operadores existentes e garante propriedades de incorporação e injeção de subespaço com complexidade linear na ordem do tensor e na dimensão do subespaço, superando o escalamento exponencial de métodos anteriores e proporcionando limites de erro quase ótimos para fatoração QB e arredondamento TT.
Este trabalho resolve uma questão em aberto demonstrando a primeira separação explícita entre os cenários de privacidade diferencial "oblivious" e "adaptativo" na observação contínua, apresentando um algoritmo preciso para o primeiro caso que falha drasticamente no segundo após apenas um número constante de passos de tempo.
O artigo apresenta o IsalGraph, um método que codifica a estrutura de qualquer grafo finito e simples em uma string compacta de nove caracteres, garantindo decodificação válida, invariância a isomorfismos e forte correlação entre a distância de edição de grafos e a distância de Levenshtein nas strings resultantes.
Este artigo estabelece limites quase ótimos para a complexidade de amostragem na verificação das propriedades de clique e -colorabilidade em grafos densos, demonstrando que o método de contagem de grafos é uma ferramenta poderosa para analisar algoritmos de teste de propriedades.
Este artigo investiga o agendamento online de tempos ocupados em máquinas heterogêneas, propondo um algoritmo 8-competitivo para tarefas de comprimento unitário e estabelecendo um limite inferior de 2 para a razão competitiva, preenchendo uma lacuna teórica crucial para modelos de computação em nuvem.
Os autores apresentam um algoritmo FPT que estende o teorema de Gallai-Milgram, decidindo em tempo polinomial se um grafo pode ser coberto por menos caminhos do que o número de independência, e fornecendo um certificado de independência caso contrário, além de resolver o problema de Hamiltonicidade para grafos com número de independência limitado.
O artigo apresenta o -Motif, um algoritmo acelerado por GPU para isomorfismo de subgrafos que reformula o problema como operações de banco de dados em formato tabular, alcançando acelerações de até 595 vezes em relação a métodos tradicionais e permitindo aplicações escaláveis em áreas como a compilação de circuitos quânticos.
Este trabalho apresenta e avalia experimentalmente variantes de B-trees otimizadas para dispositivos embarcados com restrições de memória, demonstrando que tais otimizações específicas para armazenamento permitem uma indexação eficiente mesmo em equipamentos de borda de pequeno porte.
Este artigo apresenta os primeiros algoritmos de ordenação baseados em comparações que são estritamente in-place (usando apenas O(1) memória adicional) e atingem um tempo de execução ótimo em relação à entropia baseada em sequências, O(n(1 + H(A))), através de duas abordagens simples para implementar a ordenação por mesclagem natural baseada em pilha.
Este artigo melhora os limites conhecidos para a complexidade de aprendizado agnóstico sob marginais gaussianas, demonstrando que um grau polinomial de é suficiente para aproximar classes de conceitos com área de superfície gaussiana , resultando em limites quase ótimos para funções de limiar polinomial no modelo de consultas estatísticas.
Este artigo apresenta o primeiro avanço na questão de existência de um algoritmo -competitivo para o problema de encaminhamento de pacotes em rede linear, demonstrando que uma estratégia gananciosa atinge uma razão competitiva de $2-2^{1-k}4/3$.
Este artigo apresenta um novo algoritmo de "olhar à frente" para reconhecer hipergrafos com posto transversal pelo menos em tempo e enumerar seus conjuntos de interseção mínimos, demonstrando que uma melhoria adicional para tempo polinomial em e é equivalente a avanços fundamentais na enumeração de cliques hipergrafos e no reconhecimento de hipergrafos conformes.
Os autores provam uma versão enfraquecida da conjectura de Chudnovsky et al., demonstrando que grafos que excluem e a grade como menores induzidos admitem uma decomposição em árvore cujos sacos possuem números de independência de distância controlados por funções polilogarítmicas.
Este artigo propõe um método sequencial para geração, enumeração e amostragem de grafos bipartidos, direcionados e não direcionados com sequências de graus prescritas, estabelecendo condições de viabilidade global que garantem escalabilidade para instâncias grandes onde métodos existentes falham.
Este artigo investiga a complexidade computacional do problema de reconfiguração de conjuntos dominantes de distância- sob as regras de deslizamento e salto de tokens, estabelecendo uma dicotomia de complexidade ao demonstrar que o problema é tratável em tempo polinomial para grafos divididos quando , enquanto permanece PSPACE-completo para outras classes de grafos como planares, bipartidos e cordais.
Este trabalho apresenta um novo método de amostragem com reposição para fluxos de dados que, em uma única passagem sobre uma população de tamanho desconhecido, gera uma amostra ponderada representativa e pronta para uso, com correção e eficiência formalmente provadas e validadas experimentalmente.
Esta carta apresenta uma abordagem inovadora que utiliza acumuladores em cascata para calcular eficientemente somas ponderadas com potências de índice temporal em tempo real, eliminando a necessidade de armazenamento de blocos de dados e reduzindo drasticamente o custo computacional de multiplicações.
Este artigo investiga a complexidade parametrizada do problema do caminho mais curto com restrições disjuntivas positivas, estabelecendo resultados de kernelização e tratabilidade parametrizada fixa para diferentes parâmetros, como o tamanho da solução e propriedades estruturais do grafo de forçamento.