Copertina

Dynamic Construction of the Lovász Local Lemma

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Haeupler, Bernhard, Mitrović, Slobodan, Ramachandran, Srikkanth, Sheu, Wen-Horng, Tarjan, Robert
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
di: Łącki, Jakub, et al.
Pubblicazione: (2025)

A framework for boosting matching approximation: parallel, distributed, and dynamic
di: Mitrović, Slobodan, et al.
Pubblicazione: (2025)

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
di: Mitrović, Slobodan, et al.
Pubblicazione: (2026)

Faster Semi-streaming Matchings via Alternating Trees
di: Mitrović, Slobodan, et al.
Pubblicazione: (2024)

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
di: Dalirrooyfard, Mina, et al.
Pubblicazione: (2024)

On the Locality of the Lovász Local Lemma
di: Davies-Peck, Peter
Pubblicazione: (2025)

A new notion of commutativity for the algorithmic Lovász Local Lemma
di: Harris, David G., et al.
Pubblicazione: (2020)

A Sampling Lovász Local Lemma for Large Domain Sizes
di: Wang, Chunyang, et al.
Pubblicazione: (2023)

Locally computing edge orientations
di: Mitrović, Slobodan, et al.
Pubblicazione: (2025)

Maintaining Random Assignments under Adversarial Dynamics
di: Haeupler, Bernhard, et al.
Pubblicazione: (2026)

SPARSE-PIVOT: Dynamic correlation clustering for node insertions
di: Dalirrooyfard, Mina, et al.
Pubblicazione: (2025)

Reducing Shortcut and Hopset Constructions to Shallow Graphs
di: Haeupler, Bernhard, et al.
Pubblicazione: (2025)

Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness
di: Haeupler, Bernhard, et al.
Pubblicazione: (2026)

Distributed Lovász Local Lemma under Bandwidth Limitations
di: Halldórsson, Magnús M., et al.
Pubblicazione: (2024)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
di: Haeupler, Bernhard, et al.
Pubblicazione: (2024)

A Simple Average-case Analysis of Recursive Randomized Greedy MIS
di: Dalirrooyfard, Mina, et al.
Pubblicazione: (2026)

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
di: Fischer, Manuela, et al.
Pubblicazione: (2021)

Dynamic PageRank: Algorithms and Lower Bounds
di: Jayaram, Rajesh, et al.
Pubblicazione: (2024)

Approximate counting of permutation patterns
di: Ben-Eliezer, Omri, et al.
Pubblicazione: (2024)

Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
di: Haeupler, Bernhard, et al.
Pubblicazione: (2023)

Bidirectional Dijkstra's Algorithm is Instance-Optimal
di: Haeupler, Bernhard, et al.
Pubblicazione: (2024)

DAG Projections: Reducing Distance and Flow Problems to DAGs
di: Haeupler, Bernhard, et al.
Pubblicazione: (2026)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
di: Haeupler, Bernhard, et al.
Pubblicazione: (2025)

Fast and Simple Sorting Using Partial Information
di: Haeupler, Bernhard, et al.
Pubblicazione: (2024)

New Parallel and Streaming Algorithms for Directed Densest Subgraph
di: Mitrović, Slobodan, et al.
Pubblicazione: (2025)

New Structures and Algorithms for Length-Constrained Expander Decompositions
di: Haeupler, Bernhard, et al.
Pubblicazione: (2024)

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
di: Haeupler, Bernhard, et al.
Pubblicazione: (2026)

Near-Optimal Directed Low-Diameter Decompositions
di: Bringmann, Karl, et al.
Pubblicazione: (2025)

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
di: Haeupler, Bernhard, et al.
Pubblicazione: (2025)

Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
di: Haeupler, Bernhard, et al.
Pubblicazione: (2025)

Simple Length-Constrained Expander Decompositions
di: Bodwin, Greg, et al.
Pubblicazione: (2025)

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
di: Haeupler, Bernhard, et al.
Pubblicazione: (2025)

Efficiency of Self-Adjusting Heaps
di: Sinnamon, Corwin, et al.
Pubblicazione: (2023)

Low-Step Multi-Commodity Flow Emulators
di: Haeupler, Bernhard, et al.
Pubblicazione: (2024)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
di: Fischer, Nick, et al.
Pubblicazione: (2024)

Faster All-Pairs Optimal Electric Car Routing
di: Dorfman, Dani, et al.
Pubblicazione: (2025)

Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent
di: Gila, Ofek, et al.
Pubblicazione: (2023)

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
di: Aamand, Anders, et al.
Pubblicazione: (2025)

Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling
di: Dhulipala, Laxman, et al.
Pubblicazione: (2024)

Maintaining Routing Structures under Deletions via Self-Pruning
di: Haeupler, Bernhard, et al.
Pubblicazione: (2025)