A symmetric recursive algorithm for mean-payoff games
O artigo propõe um novo algoritmo recursivo simétrico e determinístico para resolver jogos de pagamento médio.
💻 Category
cs.DS
87 artigos
Succinct QUBO formulations for permutation problems by sorting networks
O artigo apresenta uma nova formulação QUBO para problemas de permutação baseada em redes de ordenação, que utiliza apenas variáveis binárias — uma melhoria significativa em relação à codificação padrão de matriz de permutação — permitindo amostragem imparcial, a imposição de restrições adicionais e a execução de operações algébricas sobre permutações de forma mais eficiente e esparsa.
Structured Gossip: A Partition-Resilient DNS for Internet-Scale Dynamic Networks
O artigo apresenta o "Structured Gossip DNS", um sistema de resolução de nomes escalável e resiliente a partições para redes dinâmicas em larga escala, que utiliza tabelas de dedos de DHT e estabilização passiva para reduzir a complexidade de mensagens e garantir consistência eventual sem coordenação global.
The Theory and Practice of Computing the Bus-Factor
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.
The Li-Chao Tree: Algorithm Specification and Analysis
Este artigo apresenta a primeira especificação formal e análise completa da Árvore Li-Chao, uma estrutura de dados amplamente utilizada na programação competitiva para manutenção dinâmica de envoltórias inferiores, incluindo provas de correção, análise de complexidade e caracterizações de desempenho.
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
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.
Sampling Colorings with Fixed Color Class Sizes
Este artigo apresenta um algoritmo de amostragem em tempo polinomial para colorações equitativas de grafos com cores, utilizando a geometria de polinômios multivariados para estabelecer um Teorema do Limite Central local multivariado para os tamanhos das classes de cor.
Bayesian inference of planted matchings: Local posterior approximation and infinite-volume limit
Este artigo investiga a inferência bayesiana de emparelhamentos ocultos em conjuntos de pontos correlacionados unidimensionais, demonstrando que, no modelo de emparelhamento parcial, a distribuição posterior pode ser aproximada localmente e possui um limite bem definido, enquanto no modelo exato essa aproximação requer uma ordenação global e uma indexação cuidadosa baseada em fluxo para estabelecer o limite de volume infinito.
A note on approximating the average degree of bounded arboricity graphs
Este artigo apresenta uma descrição completa e otimizada de um algoritmo que estima o grau médio de grafos com arboricidade limitada, eliminando fatores logarítmicos desnecessários e alcançando uma complexidade de consulta de .
Faster shortest-path algorithms using the acyclic-connected tree
Este artigo apresenta um método de pré-processamento linear que utiliza a nova decomposição de árvores acíclico-conectadas (A-C) para transformar algoritmos de caminho mais curto de fonte única, obtendo complexidades de tempo além do pior caso que dependem da largura de aninhamento do grafo.
Computational Complexity in Property Testing
Este artigo inicia um estudo sistemático da complexidade computacional no teste de propriedades, estabelecendo teoremas de hierarquia entre consultas e tempo de execução e provando limites inferiores finos para a aproximação de distância a semiespaços, revelando assim uma separação fundamental entre a complexidade de consultas e a de tempo.
Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing
Este artigo demonstra teoricamente e valida empiricamente que as alucinações em modelos de linguagem são uma consequência inevitável da otimização de memória sob capacidade limitada, onde a estratégia informacionalmente ótima para testes de associação em dados esparsos exige a atribuição de alta confiança a alguns fatos incorretos como resultado da compressão com perdas.
DRESS and the WL Hierarchy: Climbing One Deletion at a Time
Este artigo fornece a justificativa teórica para o framework -DRESS, provando incondicionalmente que ele distingue pares CFI específicos e demonstrando condicionalmente que sua capacidade de distinção é pelo menos equivalente à hierarquia -WL para todos os grafos.
Transposition is Nearly Optimal for IID List Update
Este artigo prova que a regra de transposição no problema de atualização de listas, sob um modelo de solicitações independentes e identicamente distribuídas (i.i.d.), atinge um custo esperado de acesso no máximo OPT+1, confirmando uma conjectura de 50 anos de Rivest e oferecendo um procedimento puramente sem memória para ordenar probabilidades aproximadamente.
Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
O artigo apresenta um algoritmo determinístico que reconstrói grafos conexos com grau limitado e comprimento de árvore limitado usando consultas de distância, melhorando o estado da arte em um fator logarítmico e igualando o limite inferior conhecido para grafos de cordalidade limitada.
Density-Dependent Graph Orientation and Coloring in Scalable MPC
Este artigo apresenta algoritmos de computação massivamente paralela (MPC) escaláveis que orientam e colorem grafos em rodadas, dependendo da densidade do subgrafo mais denso (), superando a barreira de complexidade de rodadas de estabelecida por trabalhos anteriores.
Intermittent Cauchy walks enable optimal 3D search across target shapes and sizes
Este artigo demonstra matematicamente que, em buscas tridimensionais, a estratégia de caminhada de Lévy com expoente (caminhada de Cauchy) é única e otimamente eficiente para detectar alvos de diversos tamanhos e formas, revelando uma sensibilidade à geometria do alvo que não existe em dimensões inferiores.
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
O artigo demonstra que a família de todos os conjuntos com valor em uma função submodular simétrica de valor inteiro pode ser representada de forma polinomial e fornece um algoritmo eficiente para sua construção, generalizando resultados anteriores sobre funções de corte-rank em grafos e permitindo a resolução de problemas de cardinalidade prescrita em tempo polinomial para fixo.
Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements
Este artigo demonstra que, no modelo de matéria programável com movimentos conjuntos, é possível reconfigurar qualquer estrutura amoebot em um segmento de linha canônico em tempo sublinear de , resolvendo positivamente uma questão em aberto sobre a viabilidade de algoritmos universais sem suposições auxiliares.
Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
Este artigo apresenta o algoritmo "Sample-and-Search", uma abordagem de aprendizado aumentado para o problema de agrupamento -médias em altas dimensões que utiliza amostragem e pré-processamento com preditores para reduzir significativamente a complexidade computacional e o custo de agrupamento em comparação com métodos existentes.