87 artigos
Este trabalho apresenta um esquema genérico e unificador para a estimação de momentos em modelos de fluxo de dados multidimensionais, utilizando o teorema de representação de Lévy-Khintchine e o mapeamento de índices para processos de Lévy para caracterizar e estimar uma ampla classe de funções, incluindo aquelas previamente não classificadas.
Este artigo introduz um novo tipo de subgradiente baseado em funções de Busemann para espaços de Hadamard, permitindo a generalização de métodos estocásticos e incrementais de subgradiente com limites de complexidade garantidos para problemas de otimização convexa, como o cálculo de médias e medianas em espaços de árvores BHV.
O artigo demonstra que um método exato simples resolve a maioria das instâncias clássicas de benchmark do Problema do Caixeiro Viajante com Janelas de Tempo em menos de dez segundos, concluindo que essas instâncias não são mais representativas para avaliação de desempenho e exigem cautela no desenho de conjuntos de treinamento para algoritmos de aprendizado de máquina.
O artigo apresenta o algoritmo de Warping Temporal Elástico, que resolve problemas de correspondência de séries temporais em espaços métricos arbitrários utilizando uma penalidade baseada no kernel de Hellinger, com complexidade computacional cúbica.
O artigo apresenta o algoritmo bsort, uma abordagem não baseada em comparações para ordenação de inteiros e números de ponto flutuante que unifica esses casos com complexidade temporal e espaço auxiliar , demonstrando desempenho competitivo com algoritmos híbridos otimizados para dados de pequeno tamanho de palavra.
Este trabalho apresenta um algoritmo de fluxo de dados de uma passagem que, sob ordem aleatória de entrada, alcança um fator de aproximação esperado de 0,7401 para o problema de seleção de intervalos unitários usando espaço linear no tamanho da solução ótima, superando o limite de 2/3 estabelecido para fluxos adversariais e estabelecendo limites inferiores de espaço para aproximações ainda melhores.
Este artigo apresenta um Esquema de Aproximação em Tempo Polinomial (PTAS) para o Problema de 2-Matching Ponderado Livre de Triângulos, utilizando um algoritmo de busca local com análise não trivial para superar a melhor aproximação anterior de 2/3.
Este trabalho apresenta um novo algoritmo de mineração de substrings frequentes com privacidade diferencial que mantém garantias de erro quase ótimas enquanto reduz drasticamente a complexidade de tempo e espaço em comparação com abordagens anteriores, tornando o processo escalável.
Este artigo apresenta um protocolo aprimorado para o problema de especialistas distribuídos que minimiza o arrependimento e a comunicação ao calcular perdas baseadas na norma sobre múltiplos servidores.
Este artigo investiga o problema de emparelhamento não cruzado online ponderado no plano euclidiano, demonstrando que algoritmos determinísticos não garantem uma razão competitiva não trivial, enquanto algoritmos aleatorizados alcançam uma razão constante, além de estabelecer limites para variantes com revocabilidade, pontos colineares e complexidade de aconselhamento.
Este artigo apresenta um algoritmo corretivo e exaustivo para enumerar todos os pares críticos em sistemas de reescrita de diagramas de string em categorias monoidais simétricas (sem estrutura de Frobenius), permitindo a automatização da análise de conflitualidade através da manipulação concreta de hipergrafos.
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 demonstra que, embora encontrar o maior emparelhamento crítico e relaxadamente estável em cenários muitos-para-muitos com empates e cotas seja NP-difícil, é possível obter uma aproximação de 2/3 para esse problema em tempo polinomial.
Este artigo demonstra que, para o modelo SYK esparsificado, existe uma separação comprovada entre algoritmos quânticos eficientes e algoritmos clássicos baseados em estados gaussianos na aproximação do estado fundamental, desde que a probabilidade de esparsificação seja suficientemente alta ().
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.
O artigo apresenta a Teoria do Espaço de Exploração (EST), uma estrutura formal baseada em reticulados que adapta a Teoria do Espaço de Conhecimento para sistemas de recomendação de localização, garantindo matematicamente que as sugestões respeitem dependências de pré-requisitos entre pontos de interesse e ofereçam explicações estruturais válidas.
Este artigo apresenta o primeiro quadro formal e algoritmos com garantias teóricas para aprendizado por reforço multiagente cooperativo com recompensas submodulares, superando a maldição da dimensionalidade e oferecendo limites de aproximação e regret para cenários de dinâmica conhecida e desconhecida.
Este artigo propõe as novas classes de redes filogenéticas não enraizadas chamadas redes -cortáveis, demonstrando que, ao contrário das redes orientáveis para árvore-filho (cujo reconhecimento é NP-difícil), elas são reconhecíveis em tempo polinomial e permitem resolver o problema de contenção de árvores em tempo polinomial para .
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 o primeiro método capaz de aproximar contrações de redes tensoriais arbitrárias, incluindo as cíclicas, e introduz uma segunda técnica para redes acíclicas que reduz a complexidade computacional de exponencial para polinomial em relação ao número de contrações.