91 papers
Deze paper presenteert een volledig dynamische datastructuur die een spectrale sparsificator van een geometrisch graaf met een kernelfunctie onderhoudt bij puntupdates met een updatetijd van , en bovendien toont dat de bijbehorende Laplace-matrices een randomiseerde schets toelaten voor efficiënte matrix-vectorvermenigvuldiging.
Dit artikel introduceert een symmetrische, objectieve verbeteringsaanpak voor het oplossen van afgekwarteerde spelletjes met uitbetalingen, die een nieuw constraint-systeem gebruikt om co-optimale strategieën te vinden door de som van fouten te minimaliseren en zo de traditionele dichotomie tussen strategieverbetering en waarde-iteratie uitdaagt.
Dit artikel bepaalt de drempel voor detectie van correlatie in een paar gecorreleerde stochastische blokmodellen met lage graad-polynomen, waarbij wordt aangetoond dat detectie mogelijk is dan en slechts dan als de subsampling-kans de minimumwaarde van de wortel van de constante van Otter en de Kesten-Stigum-drempel overschrijdt.
Deze paper introduceert een versoepelde definitie van snelwegdimensie die ook natuurlijke ruimten zoals roosters en het Euclidische vlak omvat, en hiermee een PTAS voor het TSP-probleem biedt evenals fundamentele meetkundige hulpmiddelen zoals ingekaderde decomposities en boomdekkingen.
Dit artikel introduceert twee efficiënte algoritmen voor het berekenen van de modulaire inverse voor willekeurige gehele getallen , waarbij het eerste algoritme gebaseerd is op -adische expansies en het tweede een generalisatie vormt van bestaande Hensel-lifting-methoden voor machten van de vorm .
Dit artikel presenteert versnelde algoritmen voor lineaire algebra-taken met kernelmatrices door gebruik te maken van dichtheidsschatting, waardoor de afhankelijkheid van het aantal datapunten en de foutmarge aanzienlijk wordt verbeterd ten opzichte van eerdere methoden.
Dit artikel introduceert het eerste deterministische iteratieve algoritme voor het construeren van een -coreset dat een -subruimte-inbedding garandeert voor elke , waarbij logaritmische factoren in de grootte van de coreset worden verwijderd om een optimale en deterministische oplossing te bieden voor -regressieproblemen.
Deze paper presenteert het eerste multiplicatieve verbetering ten opzichte van de natuurlijke greedy-algoritme voor het maximaliseren van een niet-negatieve monotoon submodulaire functie onder de doorsnede van willekeurige matroiden, door een hybride greedy-locale zoekstrategie te ontwikkelen die een benaderingsratio van ongeveer $0,819k$ bereikt.
Deze paper toont aan dat de noodzakelijke polynomiale additieve fout voor differentieel privé continu release van het aantal unieke items in een turnstile-stroom kan worden omzeild door algoritmen toe te staan zowel multiplicatieve als additieve fouten van polylogaritmische grootte te gebruiken, terwijl ze bovendien polynoomruimte vereisen.
Dit paper introduceert een efficiëntere methode voor het beperken van de gemiddelde querytijd van move structuren in RLBWT-permutaties via lengte-capping, wat leidt tot snellere constructie, een kleinere ruimtebehoefte en optimale querytijden voor BWT-inversie en suffix-array enumeratie.
Dit paper introduceert DRESS, een deterministisch en parameterloos raamwerk dat door iteratieve verfijning van structurele gelijkenis een isomorfisme-invariante vingerafdruk genereert die bewezen minstens zo expressief is als de 2-WL-test, maar met aanzienlijk lagere rekentijd, en presenteert uitgebreide varianten zoals -DRESS die de expressiviteit verder verhogen tot het CFI-trapje.