87 papers
Dit artikel introduceert de Huffman-Bucket Sketch, een eenvoudige en samenvoegbare datastructuur die HyperLogLog-sketches verliesvrij comprimeert tot bits door registers in buckets te partitioneren en met een Huffman-code te coderen, terwijl het tegelijkertijd constante update-tijden behoudt en de frequentie van het herbouwen van de Huffman-boom beperkt tot keer.
Dit artikel presenteert een studie naar minimale onvoldoende deelverzamelingen (MUSs) van 2-CNF-formules, waaronder een lineaire tijdprocedure voor het herkennen van 2-MUs, polynomiale algoritmen voor het vinden van MUSs met een of twee eenheidsclausules, en een incrementeel polynoomalgoritme voor een specifieke categorie MUSs, terwijl het ook de NP-compleetheid van het bestaan van een deficiëntie-1 MUS bevestigt.
Dit artikel introduceert de Block Sparse Tensor Train (BSTT) schets, een gestructureerde willekeurige projectie die de lineaire schaling garandeert met betrekking tot de tensororde en subspace-dimensie, waardoor exponentiële complexiteit wordt vermeden en quasi-optimale foutgrenzen worden bereikt voor TT-gerelateerde factorisaties.
Dit papier lost een open vraag op door een expliciet voorbeeld te presenteren dat aantoont dat er een fundamenteel verschil bestaat tussen de oblivious en adaptieve settings van differentieel privacy onder continue observatie, waarbij het oblivious model aanzienlijk beter presteert dan het adaptieve model.
Dit artikel introduceert IsalGraph, een methode die de structuur van eindige grafen comprimeert tot een compacte string van negen karakters die door een virtuele machine kan worden gedecodeerd, waarbij elke string een geldige graaf oplevert en de sequenties sterk correleren met grafische bewerkingen voor toepassingen in vergelijkingszoekopdrachten en generatieve modellen.
Dit artikel toont aan dat de grafcontainermethode kan worden gebruikt om bijna optimale steekproefcomplexiteitsgrenzen te bewijzen voor het testen van de -clique-eigenschap en -kleurbaarheid in het dichte grafmodel.
Dit artikel introduceert een 8-competitieve online algoritme voor het plannen van taken met een uniforme lengte op heterogene machines met het doel de totale kosten te minimaliseren, en levert tevens een ondergrens van 2 voor de competitieve ratio.
Dit artikel presenteert een vast-parameter-tractabele (FPT) algoritme dat het Gallai-Milgram-theorema uitbreidt door te bepalen of een graaf met minder dan paden kan worden bedekt, en levert bovendien de eerste polynomiale tijd-algoritmen voor het bepalen van Hamiltoniciteit in grafen met een onafhankelijkheidsgetal van maximaal drie.
Dit paper introduceert -Motif, een GPU-versnelde subgraaf-isomorfisme-algoritme dat het probleem omzet in schaalbare database-operaties op tabellen, waardoor het tot 595 keer sneller is dan traditionele methoden en toepasbaar is op complexe domeinen zoals kwantumcircuitoptimalisatie.
Dit paper presenteert en evalueert verschillende B-boomvarianten die specifiek zijn geoptimaliseerd voor geheugenbeperkte flash-embedded apparaten, waarmee efficiënte indexering mogelijk wordt gemaakt op kleine IoT-apparaten voor landbouw- en industriële monitoring.
Dit paper introduceert de eerste strikt in-place, op vergelijkingen gebaseerde sorteeralgoritmen die een optimale looptijd van O(n(1 + H(A))) bereiken door eenvoudige, stack-gebaseerde natuurlijke mergesort-paradigma's toe te passen, wat vooral relevant is voor geheugenbeperkte ingebouwde systemen zoals die in koelkasten.
Dit artikel verbetert de bestaande analyse voor agnostisch leren onder Gaussische marginals door aan te tonen dat een polynoomgraad van voldoende is voor een -benadering, wat leidt tot (bijna) optimale complexiteitsgrenzen voor het leren van polynoomdrempelfuncties.
Dit artikel presenteert de eerste vooruitgang in het open probleem van het minimaliseren van de maximale doorlooptijd bij het online doorsturen van pakketten in een lijnnetwerk, door te bewijzen dat een specifieke greedy-algoritme een competitieve ratio van $2-2^{1-k}4/3$ wordt vastgesteld.
Dit artikel introduceert een sneller algoritme voor het bepalen en enumereren van transversale rangen in hypergrafieken door een 'look-ahead'-methode te gebruiken, en toont aan dat verdere optimalisatie van de looptijd afhankelijk is van doorbraken in het herkennen van conformiteit en het enumereren van hypercliques.
Dit artikel bewijst een verzwakte versie van een conjectuur over bomenontbindingen in grafen die en het rooster als geïnduceerde minor uitsluiten, door te tonen dat dergelijke grafen een bomenontbinding toelaten waarbij de zakken een beperkte onafhankelijkheidsgetal hebben op basis van specifieke afstandsparameters.
Deze paper introduceert een sequentiële methode voor het genereren, tellen en steekproeven van bipartiete, gerichte en ongerichte grafen met voorgeschreven graadsequenties, waarbij een noodzakelijke en voldoende intervalvoorwaarde wordt vastgesteld om globale haalbaarheid te garanderen en de schaalbaarheid naar grote instanties wordt verbeterd.
Dit artikel onderzoekt de complexiteit van het herschikingsprobleem voor afstand- dominante verzamelingen, waarbij het een interessante dichotomie aantoont door aan te tonen dat het probleem op splitgrafen voor in ligt, terwijl het op andere graafklassen zoals planaire en bipartiete grafen -volledig blijft.
Dit artikel presenteert een nieuwe, efficiënte methode voor gewogen reservoirsampling met vervanging van datastromen die in één doorloop een representatieve steekproef genereert zonder post-processing, waarvan de correctheid formeel is bewezen en de prestaties experimenteel zijn gevalideerd.
Dit artikel introduceert een nieuwe methode met gekaskadeerde accumulatoren om tijdsindex-gemachtigde gewogen sommen efficiënt te berekenen door de vermenigvuldigingskosten te reduceren tot slechts constante vermenigvuldigingen, waardoor opslag van volledige datablokken wordt vermeden en real-time verwerking mogelijk wordt.
Dit artikel onderzoekt de parameteriseringscomplexiteit van het kortste-padprobleem met positieve disjunctieve constraints en levert kerningresultaten met of vertices voor de oplossingsgrootte , evenals vast-parameter-tractabiliteitsresultaten voor structurele parameters van de dwanggraaf.