A symmetric recursive algorithm for mean-payoff games
Die Autoren stellen einen neuen deterministischen, symmetrischen rekursiven Algorithmus zur Lösung von Mittelwertspielen vor.
💻 Category
cs.DS
87 Arbeiten
Succinct QUBO formulations for permutation problems by sorting networks
Die Arbeit stellt eine neue QUBO-Formulierung für Permutationsprobleme vor, die auf Sortiernetzwerken basiert und im Vergleich zur herkömmlichen Permutationsmatrix-Kodierung eine signifikante Reduktion der Variablenanzahl auf sowie eine dünnere Interaktionsstruktur ermöglicht.
Structured Gossip: A Partition-Resilient DNS for Internet-Scale Dynamic Networks
Die Arbeit stellt „Structured Gossip DNS" vor, ein partitionstolerantes DNS-System für Internet-Skala, das durch die Nutzung von DHT-Fingertabellen und passiver Stabilisierung die Nachrichtenkomplexität auf reduziert und dabei ohne globale Koordination eine eventual consistency gewährleistet.
The Theory and Practice of Computing the Bus-Factor
Diese Arbeit stellt ein einheitliches, domänenunabhängiges Framework zur Berechnung des Bus-Faktors vor, das das Problem als kombinatorische Optimierung auf bipartiten Graphen modelliert, die NP-Schwere der exakten Berechnung beweist und effiziente Approximationsalgorithmen sowie einen neuartigen, auf Netzwerkrüstigkeit basierenden Maßstab für eine stabilere Risikobewertung entwickelt.
The Li-Chao Tree: Algorithm Specification and Analysis
Diese Arbeit liefert die erste formale Spezifikation und Analyse der Li-Chao-Baum-Datenstruktur, einschließlich vollständiger algorithmischer Beschreibungen, Korrektheitsbeweise, Komplexitätsanalysen und empirischer Leistungscharakterisierungen.
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
Diese Arbeit charakterisiert die Lösbarkeit von Permutations-Match-Puzzles auf -Gittern durch eine acyclische Bedingung, liefert eine Hook-Längen-Formel für die Anzahl der Lösungen und zeigt, dass das Finden minimaler Reparaturen bei einer Verallgemeinerung auf beliebige Permutationen NP-vollständig ist.
Sampling Colorings with Fixed Color Class Sizes
Diese Arbeit stellt einen polynomiellen Algorithmus zur näherungsweisen uniformen Stichprobenziehung äquitabler Graphfärbungen bei vor, wobei der Beweis auf der Geometrie von Polynomen basiert und als Nebenprodukt einen multivariaten lokalen zentralen Grenzwertsatz für die Größen der Farbklassen liefert.
Bayesian inference of planted matchings: Local posterior approximation and infinite-volume limit
Diese Arbeit untersucht die bayessche Inferenz von gepflanzten Matchings zwischen korrelierten Punktmengen in einer Dimension und zeigt, dass die Posterior-Verteilung im Fall partieller Matchings durch lokale Algorithmen approximiert werden kann, während für exakte Matchings eine globale Sortierung und eine spezielle Indexierung erforderlich sind, um ein wohldefiniertes unendliches Volumen-Limit zu erhalten.
A note on approximating the average degree of bounded arboricity graphs
Dieser Artikel stellt einen vereinfachten und optimierten Algorithmus zur -Approximation des durchschnittlichen Grades in Graphen mit beschränkter Arboreszenz vor, der logarithmische Verluste vermeidet und eine Abfragekomplexität von erreicht.
Faster shortest-path algorithms using the acyclic-connected tree
Die vorgestellte Arbeit führt die lineare Zeit-zu-Verfügung stehende "acyclic-connected"-Baum-Zerlegung ein, um beliebige Single-Source-Shortest-Path-Algorithmen durch rekursive Verarbeitung auf dieser Struktur zu verbessern und so Laufzeiten zu erreichen, die vom neu definierten Parameter "Nesting Width" abhängen.
Computational Complexity in Property Testing
Dieses Papier untersucht systematisch die Rechenkomplexität im Property Testing, indem es Hierarchiesätze für die Beziehung zwischen Abfrage- und Zeitkomplexität herleitet und unter fine-grained Annahmen wie der k-SUM-Vermutung eine fundamentale Lücke zwischen diesen beiden Komplexitätsmaßen für die Approximation des Abstands zu Halbräumen aufzeigt.
Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing
Die Arbeit zeigt, dass Halluzinationen in großen Sprachmodellen eine unvermeidbare Konsequenz der informationstheoretisch optimalen Speichereffizienz bei begrenzter Kapazität sind, da der Zwang zur verlustbehafteten Kompression von Fakten dazu führt, dass auch nicht-zutreffende Aussagen mit hoher Wahrscheinlichkeit bewertet werden.
DRESS and the WL Hierarchy: Climbing One Deletion at a Time
Diese Arbeit liefert den theoretischen Nachweis, dass das deterministische Framework -DRESS durch die Anwendung auf -Vertex-deletierte Teilgraphen die Unterscheidungskraft der -Weisfeiler-Leman-Hierarchie erreicht, wobei dies sowohl für CFI-Grafenpaare bedingungslos bewiesen als auch für allgemeine Graphen unter einer strukturellen Vermutung gezeigt wird.
Transposition is Nearly Optimal for IID List Update
Die Arbeit beweist, dass die Transpositionsregel im i.i.d.-Modell für das Listen-Update-Problem eine erwartete Zugriffskosten von höchstens OPT+1 erreicht und damit eine 50 Jahre alte Vermutung von Rivest bis auf eine unvermeidbare additive Konstante bestätigt.
Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
Die vorgestellte Arbeit zeigt, dass beschränkte Graphen mit beschränkter Baumlänge und maximalem Grad durch einen deterministischen Algorithmus mit Abfragen der kürzesten Pfade rekonstruiert werden können, was eine Verbesserung um einen -Faktor gegenüber dem bisherigen Besten darstellt und die bekannte untere Schranke für Graphen mit beschränkter Chordalität erreicht.
Density-Dependent Graph Orientation and Coloring in Scalable MPC
Die Arbeit stellt skalierbare MPC-Algorithmen vor, die in stark sublinearer Speicherkapazität Graphenorientierungen und -färbungen in Abhängigkeit von der Subgraphendichte berechnen und dabei die Rundenzahl von auf senken.
Intermittent Cauchy walks enable optimal 3D search across target shapes and sizes
Diese Arbeit beweist mathematisch, dass intermittierende Cauchy-Walks (mit dem Lévy-Exponenten ) in drei Dimensionen eine einzigartige, skaleninvariante und nahezu optimale Suchstrategie für Ziele unterschiedlicher Größe und Form darstellen, wobei die Zielform im Vergleich zu niedrigeren Dimensionen einen entscheidenden Einfluss auf die Detektierbarkeit hat.
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
Die Arbeit stellt einen polynomiellen Algorithmus vor, der für ganzzahlige symmetrische submodulare Funktionen eine kompakte Darstellung aller Schnitte mit einem vorgegebenen Wert erzeugt und damit die Suche nach solchen Mengen mit zusätzlichen Kardinalitätsbedingungen effizient ermöglicht.
Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements
Die Arbeit beweist, dass im zentralisierten Joint-Movement-Modell programmierbarer Materie jede beliebige Struktur in sublinearer Zeit von Runden in eine kanonische Linienstruktur umkonfiguriert werden kann, wodurch eine offene Frage zur universellen Rekonfiguration ohne zusätzliche Annahmen positiv beantwortet wird.
Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
Die Arbeit stellt einen effizienten Sample-and-Search-Algorithmus für das lernunterstützte k-Median-Clustering in hohen Dimensionen vor, der durch eine Prognose-basierte Vorverarbeitung die Rechenkomplexität deutlich senkt und die Abhängigkeit von der Dimensionalität beseitigt.