87 papers
Dit paper introduceert een generiek schema voor het schatten van -momenten in een stream van -dimensionale data door indexen te hashen naar Lévy-processen, waarbij het Lévy-Khintchine-representatiestelling de ruimte van schatbare functies volledig karakteriseert en bestaande technieken verenigt.
Deze paper introduceert een nieuwe definitie van subgradienten voor Hadamard-ruimten, gebaseerd op Busemann-functies, waarmee stochastische en incrementele subgradiëntmethoden met gegarandeerde complexiteitsgrenzen kunnen worden toegepast op convex optimalisatieproblemen zoals het berekenen van medians in BHV-boomruimten.
Dit paper stelt dat klassieke benchmarkinstanties voor het Traveling Salesman Problem met tijdvensters niet langer representatief zijn voor evaluatie, omdat een nieuwe exacte methode deze binnen enkele seconden oplost en hun structuur dusdanig exploiteerbaar is dat resultaten misleidend goed lijken.
Dit artikel introduceert het Elastic Time Warping-algoritme, dat met een kubische computatiecomplexiteit tijdsreeksen in een willekeurige metrische ruimte matcht door gebruik te maken van een Hellinger-kern als rekstraf.
Dit artikel introduceert bsort, een niet-comparatief sorteeralgoritme voor gehele getallen en floating-point waarden dat via een benadering afgeleid van binaire quicksort een asymptotische looptijd van en een extra ruimtecomplexiteit van bereikt, met prestaties die concurreren met geoptimaliseerde hybride algoritmen voor gegevens met kleine woordgroottes.
Dit artikel presenteert een een-pass streamingalgoritme dat in het willekeurig bestelde model een verwachte benaderingsfactor van 0,7401 bereikt voor het selecteren van een maximale verzameling disjuncte eenheidsintervallen met lineaire ruimte, wat een verbetering is op de eerdere adversarische limiet van 2/3.
Dit artikel presenteert een polynomiale tijdsschema voor een benadering (PTAS) dat voor het gewogen driehoekvrije 2-matching-probleem een oplossing binnen een factor van het optimum garandeert, gebaseerd op een lokaal zoekalgoritme.
Deze paper presenteert een nieuwe, schaalbare differentieel-private algoritme voor het vinden van frequente substrings dat de near-optimale foutgaranties van eerdere werken behoudt maar de reken- en geheugencomplexiteit drastisch verlaagt door een verfijnde kandidaatgeneratiestrategie en zoekruimte-pruning.
Dit artikel presenteert een verbeterd protocol voor het gedistribueerde experts-probleem dat de spijt minimaliseert met een efficiëntere communicatiekost dan eerdere werken.
Deze paper onderzoekt het online gewogen niet-kruisende matchingprobleem in het Euclidische vlak, waarbij wordt aangetoond dat deterministische algoritmen geen niet-triviale competitieve ratio garanderen maar randomisatie een constante ratio mogelijk maakt, en worden bovendien varianten met herroepbaarheid en collineaire punten geanalyseerd.
Dit paper introduceert een correct en exhaustief algoritme voor het automatisch enumereren van kritieke paren in stringdiagram-rewriting-systemen binnen symmetrische monoidale categorieën zonder Frobenius-structuur, door middel van concrete manipulatie van hypergrafieken.
Dit paper verbetert de looptijd voor -benaderingsalgoritmen voor -median en -means clustering in laagdimensionale Euclidische ruimtes en bewijst een bij benadering overeenkomende ondergrens onder de Gap Exponentiële Tijd Hypothese.
Deze paper toont aan dat er altijd een kritieke en relaxed-stabiele matching bestaat in het veel-naar-veel koppelingsprobleem met voorkeuren, gelijke rangen en quota's, en biedt een polynomiaal algoritme dat een 2/3-benadering levert voor het maximaliseren van de grootte van zo'n matching, hoewel het exacte probleem NP-moeilijk is.
Deze studie toont aan dat er een bewezen scheiding bestaat tussen efficiënte kwantumalgoritmen en klassieke Gaussische benaderingen voor het vinden van de grondtoestand van het verdunde Sachdev-Ye-Kitaev-model, zolang de verdunningsparameter groter is dan .
Deze paper presenteert een nieuw schema voor differentieel privé schatten van zwarte-bok statistieken dat een afweging biedt tussen statistische en orakel-efficiëntie, vergezeld van ondergrenzen die de near-optimale aard van het schema aantonen.
Dit artikel introduceert Exploration Space Theory, een formeel raamwerk dat Kennisruimte-theorie vertaalt naar locatiegebaseerde aanbevelingssystemen om via een distributieve roosterstructuur en Birkhoff's representatiestelling wiskundig gegarandeerde, logisch onderbouwde en verklaarbare routes voor bezoekers te genereren.
Dit artikel introduceert het eerste formele kader voor cooperatief multi-agent reinforcement learning met submodulaire beloningen, waarbij algoritmen worden ontwikkeld die wiskundige garanties bieden op sample-efficiëntie en spijt, inclusief een polynoom-complexiteit benadering voor bekende dynamica en een UCB-gebaseerde leeralgoritme voor onbekende dynamica.
Deze paper introduceert de nieuwe klasse van -snijbare ongewortelde fylogenetische netwerken, die, in tegenstelling tot boom-kind-oriënteerbare netwerken, in polynomiale tijd herkenbaar zijn en het NP-moeilijke probleem van boom-bevatteling polynomiaal oplosbaar maken voor .
Dit paper introduceert een nieuwe methode die backtracking en substitutie combineert om aan te tonen dat de bilineaire complexiteit van het vermenigvuldigen van $3 \times 3\mathbb{F}_2$ minimaal 20 is, waarmee een langdurig lagergrensrecord van 19 wordt verbeterd.
Deze paper introduceert de eerste methode om willekeurige tensornetwerkcontracties, inclusief cyclische netwerken, te benaderen met sketches, en presenteert bovendien een nieuwe methode voor acyclische netwerken die een polynomiale complexiteit bereikt in plaats van de exponentiële complexiteit van bestaande technieken.