A symmetric recursive algorithm for mean-payoff games
De auteurs presenteren een nieuwe deterministische, symmetrische recursieve algoritme voor het oplossen van gemiddelde-betalingsspellen.
💻 Category
cs.DS
87 papers
Succinct QUBO formulations for permutation problems by sorting networks
Deze paper introduceert een compacte en uniforme QUBO-formulering voor permutaties op basis van sorteernetwerken, die aanzienlijk minder variabelen vereist dan de standaardmatrixbenadering en tevens ondersteuning biedt voor complexe operaties en beperkingen.
Structured Gossip: A Partition-Resilient DNS for Internet-Scale Dynamic Networks
Dit artikel introduceert Structured Gossip DNS, een partition-resilient naamoplossingssysteem voor internet-schaalnetwerken dat via passieve stabilisatie en commutatieve operaties de berichtcomplexiteit verlaagt en eventual consistency garandeert zonder globale coördinatie.
The Theory and Practice of Computing the Bus-Factor
Dit artikel introduceert een unificerend, domein-onafhankelijk raamwerk voor het berekenen van de bus-factor door projecten als bipartiete grafen te modelleren, bewijst dat zowel de exacte berekening als de geïntroduceerde robuustheidsgebaseerde maatstaf NP-moeilijk zijn, en presenteert efficiënte lineaire benaderingsalgoritmen die projectrisico's informatiever en stabieler inschatten dan bestaande methoden.
The Li-Chao Tree: Algorithm Specification and Analysis
Dit artikel biedt de eerste formele specificatie van de Li-Chao-boom, inclusief volledige algoritmische beschrijvingen, correctheidswijzen, theoretische complexiteitsanalyse en empirische prestatiekenmerken, waarmee het een definitieve referentie wordt voor deze datastructuur die tot nu toe vooral bekend was uit de competitieve programmering.
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
Dit artikel introduceert permutatie-matchpuzzels op roosters, karakteriseert de oplosbaarheid ervan via een acyclische voorwaarde, levert een tellende formule voor oplossingen, biedt een lineaire algoritme voor het repareren van onoplosbare gevallen, en toont aan dat de veralgemening met willekeurige permutaties NP-compleet is.
Sampling Colorings with Fixed Color Class Sizes
Deze paper presenteert een polynomiale tijd-algoritme om bijna-uniforme steekproeven te trekken uit equitabele kleuringen met een vast aantal kleuren , waarbij de bewijstechniek gebaseerd is op de meetkunde van polynomen en leidt tot een lokaal centrale limietstelling voor de grootte van kleurklassen.
Bayesian inference of planted matchings: Local posterior approximation and infinite-volume limit
Dit artikel toont aan dat bij Bayesiaanse inferentie van aangeplante matchings tussen gecorreleerde puntsets in één dimensie de posteriorverdeling benaderbaar is door lokale algoritmen voor partiële matchings, terwijl voor exacte matchings globale sortering en een specifieke indexering nodig zijn om de statistische limiet te definiëren.
A note on approximating the average degree of bounded arboricity graphs
Dit artikel presenteert een volledige analyse van een sublineair algoritme dat de gemiddelde graad van een graf met begrensd arboriciteit benadert met een querycomplexiteit van , waardoor de logaritmische verliezen en de complexiteit van de oorspronkelijke beschrijving worden vermeden.
Faster shortest-path algorithms using the acyclic-connected tree
Dit paper introduceert de lineaire-tijd 'acyclisch-geconnecteerde' (A-C) boom als een decompositiemethode die het mogelijk maakt om willekeurige single-source-shortest-path-algoritmen te versnellen door gebruik te maken van de modulaire structuur van een graaf, wat leidt tot verbeterde tijdscomplexiteiten afhankelijk van de 'nesting width' van de graaf.
Computational Complexity in Property Testing
Dit artikel initieert een systematische studie naar de computationele complexiteit van eigenschapstesten door hiërarchiestellingen te bewijzen en een fijnmazige ondergrens voor de tijdcomplexiteit van het benaderen van halfruimten af te leiden, waarmee een fundamenteel verschil tussen query- en tijdcomplexiteit wordt aangetoond.
Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing
Dit paper toont aan dat hallucinaties in grote taalmodellen een onvermijdelijk gevolg zijn van optimale geheugenefficiëntie bij het testen van lidmaatschap, waarbij beperkte capaciteit het model dwingt om met hoge zekerheid onjuiste feiten te genereren als onderdeel van een verliesbeperkende compressiestrategie.
DRESS and the WL Hierarchy: Climbing One Deletion at a Time
Dit artikel biedt de theoretische onderbouwing voor het -DRESS-raamwerk, dat door middel van een onvoorwaardelijk bewijs en een conditioneel bewijs aantoont dat het de CFI-paren onderscheidt en minstens zo krachtig is als de -WL-hiërarchie.
Transposition is Nearly Optimal for IID List Update
Dit paper bewijst dat de transpositieregel in het lijstupdate-probleem bij onafhankelijke en identiek verdeelde (i.i.d.) verzoeken een stationaire verwachte toegangskost heeft die maximaal 1 hoger is dan de optimale kost, waarmee een 50 jaar oude conjectuur van Rivest wordt bevestigd.
Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
Dit artikel presenteert een deterministisch algoritme dat ongewogen, verbonden grafen met een begrensde graad en begrensde boomlengte reconstrueert met kortste-padenafstandsvragen, wat een verbetering is op eerdere methoden en overeenkomt met de bekende ondergrens voor deze grafklasse.
Density-Dependent Graph Orientation and Coloring in Scalable MPC
Dit artikel introduceert een schaalbaar MPC-algoritme dat in rondes een graaf oriënteert en kleurt met een complexiteit die afhankelijk is van de subgraafdichtheid , waarmee de eerder bekende -barrière wordt doorbroken.
Intermittent Cauchy walks enable optimal 3D search across target shapes and sizes
Dit wiskundig onderbouwde artikel toont aan dat de Cauchy-wandeling (met een Lévy-exponent van 2) in drie dimensies de enige strategie is die een schaal-invariante, bijna optimale detectie van doelen realiseert, ongeacht hun vorm of grootte, en hiermee de Lévy-flight-vooraginghypothese voor 3D-systemen bevestigt.
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
Dit artikel presenteert een polynomiale grootte-encodering en een efficiënt constructie-algoritme voor de familie van alle snijpunten met een kleine waarde in geheelwaardige symmetrische submodulaire functies, wat een veralgemening is van bestaande structurele stellingen en leidt tot polynomiale algoritmen voor het vinden van dergelijke snijpunten met specifieke kardinaliteitsbeperkingen.
Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements
Dit artikel bewijst dat programmable matter, bestaande uit amoebots op een driehoekig rooster, met behulp van gezamenlijke bewegingen in sublineaire tijd () kan worden gereconfigureerd naar een canonieke lijnstructuur, zonder aanvullende aannames zoals metamodules.
Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
Dit artikel introduceert een efficiënt Sample-and-Search-algoritme voor het leren-versterkte k-mediane clusterprobleem in hoge dimensies, dat de computationele complexiteit en de afhankelijkheid van de dimensie aanzienlijk vermindert ten opzichte van bestaande methoden.