Randomized LOCAL algorithm computes 2-ruling sets in O(log log n) rounds w.h.p. on graphs with arboricity O(log log n), nearly matching lower bounds and exponentially improving prior combinations of results.
hub Mixed citations
In 32nd European Conference on Object-Oriented Programming (ECOOP 2018)
Mixed citation behavior. Most common role is background (40%).
54
Pith papers citing it
Background
40% of classified citations
hub tools
citation-role summary
background 2
method 2
other 1
citation-polarity summary
representative citing papers
A weight-preserving reduction from undirected 2-FRP to SSRP establishes their computational equivalence and yields matching improved algorithms for 2-FRP.
Pointer machines support working-set heaps with O(1) amortized Push and inverse-Ackermann DecreaseKey, making Dijkstra near-universally optimal with only O(m α(m)) additive overhead.
A bidirectional reduction between suffix random access and function inversion enables improved asymmetric streaming algorithms for exact/approximate pattern matching and relative Lempel-Ziv compression.
Tight single-pass linear-space lower bounds for approximating arbitrary Max-CSP(F) whenever the basic LP admits a (γ,β)-integrality gap.
A cut-preserving sparsifier constructed from approximate max-flow enables faster all-pairs minimum-cut algorithms in unweighted graphs across cut-query, dynamic, and streaming models.
O(n log n) algorithm and matching Omega(n log n) lower bound for partitioning a simple polygon's boundary into the minimum number of contiguous visible segments.
The work defines separated low-diameter decompositions for directed graphs and proves the first sub-logarithmic diameter guarantees via small modifications to two prior algorithms.
Regularity in hypergraphs is fine-grained equivalent to the general case for clique detection, enabling a complete classification of k-sparse Boolean CSP optimization complexity by constraint degree: linear for d≤1, clique-equivalent for d=2, and exhaustive-search for d≥3 under 3-uniform hyperclique
Dynamic LCS maintained under edits in amortized O(log^7 n) time whp, with Omega(log n / log log n) lower bound.
Settles deterministic competitive ratio (up to constants) for MPMD-Size via reduction to metrical task systems on 2^{n-1} points and gives O(1)-competitive deterministic algorithm for polynomial convex delays with f'(0)>0 on uniform metrics.
First sub-trivial algorithms for All-Edges Sparse Triangle, Sparse Monochromatic Triangle, Exact Triangle, and 4-cycle detection using AC0 word operations.
Develops a Stone-Cech compact collecting semantics for residual process behaviour in CCS that distinguishes stable divergence, recurrent divergence, mixed recurrence with escape, and unbounded escape.
The ω(log n)–n^{o(1)} and ω(n^{1/(k+1)})–o(n^{1/k}) complexity gaps (with decidability) for LCL problems on trees extend to LPMSO problems on unbounded-degree rooted trees.
The paper shows fine-grained hardness for approximating reachability diameter in directed graphs, gives additive approximations for unweighted cases, and constant-factor approximations for bounded treewidth and width-bounded DAGs.
For matrix multiplication ⟨d,n,d⟩ the round complexity is Õ(d^{4/3}); for ⟨n,d,n⟩ it is Θ(d √n) when d ≤ √n and O(d^{2/3} n^{2/3}) when d ≥ √n.
Monotone erasure codes are constructed from any monotone Boolean formula access structure, with efficient linear versions for partitioned structures, enabling a generalized AVID primitive.
Introduces De Simone laws over Kleisli categories that guarantee compositionality of coalgebraic trace equivalence and recovers the classical De Simone format while adding a probabilistic variant.
Termination of one-variable linear-constraint loops over integers is decidable in polynomial time if the generalized Collatz conjecture holds, with any such procedure also settling specific instances of the conjecture.
Exponential lower bounds for cutting planes and Res(⊕) on binary clique formulas for random dense graphs, with polynomial randomized communication complexity for falsified clause finding.
A 2D Voronoi-diagram data structure answers smallest-enclosing-disk rectangle queries in O(log^4 n) deterministic time after O(n log^2 n) preprocessing.
A complete formalization of the HoTT Cauchy reals in Cubical Agda that type-checks without postulates or holes.
Persistent iterators snapshot container versions at creation to deliver value semantics and invalidation safety while preserving iterator-based programming in C++.
A probabilistic runtime extension to typestates adds mutable state, mixed input/output sessions, and monitoring of expected action ratios to model concurrent and quantitative aspects of distributed protocols.
citing papers explorer
-
Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
Exponential lower bounds for cutting planes and Res(⊕) on binary clique formulas for random dense graphs, with polynomial randomized communication complexity for falsified clause finding.
-
Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations
The paper develops a general incremental maintenance technique for arbitrary join queries that achieves update times bounded by an optimizable maintenance width using heavy-light partitioning.