91 artigos
O artigo apresenta uma estrutura de dados totalmente dinâmica que mantém um esparsificador espectral de grafos geométricos com tempo de atualização quase constante e inicialização quase linear, sendo robusta contra adversários adaptativos e permitindo a manutenção eficiente de sketchs para matrizes Laplacianas sob atualizações esparsas.
Este artigo propõe uma abordagem inovadora e simétrica para resolver jogos de pagamento descontado, minimizando iterativamente um erro definido por um sistema de restrições que utiliza todas as arestas do grafo, desafiando a dicotomia tradicional entre métodos de melhoria de estratégia e iteração de valor.
Este trabalho estabelece o limiar exato para a detecção de correlação em pares de grafos de blocos estocásticos esparsos correlacionados utilizando polinômios de baixo grau, demonstrando que a distinção entre o modelo correlacionado e grafos independentes é possível se e somente se a probabilidade de subamostragem exceder o mínimo entre a constante de Otter e o limiar de Kesten-Stigum.
Este artigo relaxa a definição de dimensão de rodovia para incluir espaços métricos naturais como grades e o plano euclidiano ao exigir o cruzamento apenas de caminhos aproximadamente mais curtos, permitindo assim a construção de um PTAS para o Problema do Caixeiro Viajante e o desenvolvimento de um conjunto básico de ferramentas métricas para espaços com baixa dimensão de rodovia.
Este artigo apresenta dois algoritmos generalizados para o cálculo de inversos modulares: o primeiro calcula para quaisquer inteiros e , aproveitando a aritmética nativa de computadores para maior eficiência, enquanto o segundo estende métodos de elevação de Hensel existentes para modulos da forma .
Este artigo propõe algoritmos mais rápidos para operações de álgebra linear em matrizes de kernel, utilizando estimativa de densidade de kernel (KDE) para reduzir a dependência computacional no número de pontos e no erro de aproximação em comparação com métodos anteriores, ao mesmo tempo que estabelece limites inferiores que indicam a complexidade fundamental desses problemas.
Este artigo apresenta o primeiro algoritmo iterativo determinístico para construir um coreset de tamanho ótimo que garante uma incorporação de subespaço para qualquer , eliminando fatores logarítmicos no tamanho do coreset e permitindo a resolução determinística de problemas de regressão .
Este artigo apresenta o primeiro algoritmo que oferece uma melhoria multiplicativa sobre a razão de aproximação do algoritmo ganancioso para a maximização de funções submodulares sob interseção de matróides, alcançando uma razão de aproximadamente $0,819kk$ e aplicável também a casos não monotônicos e a restrições de paridade.
Este trabalho demonstra que é possível contornar as barreiras de erro aditivo conhecidas para a liberação contínua de dados com privacidade diferencial em fluxos de torniquete, propondo algoritmos que utilizam espaço polilogarítmico para estimar o número de elementos distintos e o momento com erros tanto aditivos quanto multiplicativos polilogarítmicos.
Este artigo propõe uma abordagem de "length capping" para estruturas de movimento em permutações RLBWT que, além de garantir tempo de consulta ótimo e construção linear, reduz significativamente o espaço de representação e melhora o desempenho prático, como demonstrado pela biblioteca RunPerm em coleções genômicas repetitivas.
O artigo apresenta o DRESS, um framework determinístico e sem parâmetros que refina iterativamente a similaridade estrutural de arestas em grafos para gerar uma impressão digital invariante a isomorfismos, superando em expressividade e eficiência o teste 2-WL e oferecendo generalizações como Motif-DRESS e Δ-DRESS para distinguir grafos complexos.