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%).
52
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.
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.
GPLC is a gradual source probabilistic lambda calculus formalized with probabilistic couplings for static relations, elaborated to a distribution-based target language TPLC, and proven type-safe with conservative extension and gradual guarantee properties.
citing papers explorer
-
Near-Optimal Distributed 2-Ruling Sets on Graphs with Low Arboricity
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.
-
Undirected Replacement Paths: Dual Fault Reduces to Single Source
A weight-preserving reduction from undirected 2-FRP to SSRP establishes their computational equivalence and yields matching improved algorithms for 2-FRP.
-
Near-Optimal Heaps and Dijkstra on Pointer Machines
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.
-
Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms
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.
-
Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
Tight single-pass linear-space lower bounds for approximating arbitrary Max-CSP(F) whenever the basic LP admits a (γ,β)-integrality gap.
-
Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
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.
-
The Contiguous Art Gallery Problem is in {\Theta}(n log n)
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.
-
Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
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.
-
The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
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 Longest Common Substring in Polylogarithmic Time
Dynamic LCS maintained under edits in amortized O(log^7 n) time whp, with Omega(log n / log log n) lower bound.
-
Beating Trivial Time for Tricky Triangle Tasks
First sub-trivial algorithms for All-Edges Sparse Triangle, Sparse Monochromatic Triangle, Exact Triangle, and 4-cycle detection using AC0 word operations.
-
A Stone-Cech Collecting Semantics for Residual Process Behaviour
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.
-
Generalizing LCL Complexity Gaps to Unbounded Degree via Monadic Second-Order Properties
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.
-
Revisiting Diameter in Directed Graphs
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.
-
Rectangular Matrix Multiplication in the Low-Bandwidth Model
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
Monotone erasure codes are constructed from any monotone Boolean formula access structure, with efficient linear versions for partitioned structures, enabling a generalized AVID primitive.
-
Compositionality in Coalgebraic Trace Semantics
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.
-
Loop Termination and Generalized Collatz Sequences
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.
-
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.
-
Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams
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.
-
Formalizing the Real Numbers in Homotopy Type Theory with Cubical Agda
A complete formalization of the HoTT Cauchy reals in Cubical Agda that type-checks without postulates or holes.
-
Persistent Iterators with Value Semantics
Persistent iterators snapshot container versions at creation to deliver value semantics and invalidation safety while preserving iterator-based programming in C++.
-
Modelling Distributed Applications with Mixed-Choice Stateful Typestates
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.
-
A Gradual Probabilistic Lambda Calculus
GPLC is a gradual source probabilistic lambda calculus formalized with probabilistic couplings for static relations, elaborated to a distribution-based target language TPLC, and proven type-safe with conservative extension and gradual guarantee properties.
-
On the Duality of Coverings in Hilbert Geometry
Hilbert-geometry covering numbers satisfy polarity duality: N^H_K(G, α) is bounded above and below by c^{±d} times N^H_{G°}(K°, α) for an absolute constant c.
-
All ascents exponential from valued constraint graphs of pathwidth three
A controlled doubling construction yields a pathwidth-three VCSP in which every ascent in the fitness landscape is exponentially long.
-
A Myhill-Nerode Characterization and Active Learning for One-Clock Timed Automata
A Myhill-Nerode characterization for one-clock deterministic timed automata enables L*-style active learning of the canonical automaton.
-
Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
A two-pass sublinear-space streaming algorithm achieves (1/2-ε)-approximation for Max-DICUT on unbounded-degree graphs.
-
Typing Fallback Functions: A Semantic Approach to Type Safe Smart Contracts
Semantic typing via coinductively defined interpretations on a typed operational semantics ensures information flow control and non-interference for TinySol contracts that use fallback functions.
-
Learned Static Function Data Structures
Learned static functions combine per-key ML-predicted prefix codes with classic static function storage to compress static key-value mappings beyond zero-order entropy limits.
-
AgentBound: Securing Execution Boundaries of AI Agents
AgentBound is the first declarative access control framework for Model Context Protocol servers that generates policies from source code at 80.9% accuracy and blocks most threats in malicious servers with negligible overhead.
-
PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
Establishes PLS-completeness for lexicographic local search in 4-CNF and 3-CNF (double flips), and for Abelian permutation orbit minimization even when groups are cyclic or consist of involutions, with applications to bounded congestion games.
-
Temporal Graph Reconfiguration for Always-Connected Graphs
Defines LCR problem on always-connected temporal graphs, gives DP algorithm, proves APX-hardness of shortest reconfiguration, and establishes equivalence to STSR.
-
One-Sided Local Crossing Minimization
One-sided local crossing minimization is NP-hard for forests of high-degree stars (with tight ETH lower bound), solvable in quadratic time for degree-2 stars, and admits a 3-approximation via median heuristic with tie-breaking.
-
Homomorphism Indistinguishability Relations induced by Quantum Groups
Generalizes homomorphism indistinguishability equivalences induced by orthogonal easy quantum groups, including a classification of (0,0)-intertwiners for graph-theoretic versions.
-
Guarded Negation Transitive Closure Logic
GNTC satisfiability is 2ExpTime-complete and model checking is P^NP[O(log² n)]-complete via polynomial and exponential reductions to UNTC and 2-way alternating parity tree automata.
-
Fast Byzantine Total Order Broadcast
Flutter achieves 2Δ + ε good-case latency for Byzantine Total Order Broadcast via a new binary consensus called Blink, under partial synchrony with 5f+1 servers.
-
Executable formal semantics for the POSIX shell
Smoosh is an executable semantics for the POSIX shell judged most conformant to the standard among seven other shells via multiple test suites.
-
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.
-
Average-Tree Phylogenetic Diversity Parameterized by Scanwidth and Invisibility
Maximum APD subset selection is polynomial-time for scanwidth at most 2, NP-hard for scanwidth 3, with an O(2^sw n) FPT algorithm and linear-time results when the induced network is reticulation-visible or has bounded invisible reticulations per biconnected component.
-
Incremental Strongly Connected Components with Predictions
A prediction-augmented data structure for incremental SCC maintenance achieves near-optimal update times with accurate edge-order predictions and degrades smoothly with prediction error.
-
Communication Requirements for Linearizable Registers
Linearizable atomic register implementations in asynchronous message-passing systems require extensive message chains among operations of all types.
-
Engineering Algorithms for Dynamic Greedy Set Cover
First experimental study of dynamic greedy set cover algorithms reveals practical tradeoffs in quality and efficiency across real instances.
-
Voter Model Meets Rumour Spreading: an FPRAS for Consensus Probabilities on Voter Models with Agnostic Nodes
Develops an FPRAS for consensus probabilities in voter models with agnostic nodes by combining martingale analysis with rumour-spreading bounds and MCMC estimation.
-
On the enumeration of Tarski fixed points
Derives query lower bounds matching lattice width for Tarski fixed point enumeration of isotone maps and gives poly-space algorithms for increasing/decreasing cases on lattices including binary relations.
-
On Complexity Bounds and Confluence of Parallel Term Rewriting
Automatic techniques derive upper and lower bounds on parallel complexity of term rewriting by reusing sequential methods, with sufficient criteria for confluence of the parallel-innermost relation, shown via AProVE extension and benchmarks.
-
Maximum Centre-Disjoint Mergeable Disks
Proves NP-hardness of selecting a maximum centre-disjoint subset of disks with merging of the rest and gives ILP plus linear-time algorithm for collinear centers.
-
Optimal Spectral Design with Prior Information
Convex reformulation and polynomial-time algorithm for spectral design problems that update a prior information matrix by rank-one updates under Euclidean-norm bounds on the design vectors.
-
CycleTrajectory: An End-to-End Pipeline for Enriching and Analyzing GPS Trajectories to Understand Cycling Behavior and Environment
CycleTrajectory is a pipeline that filters, resamples, map-matches via OSRM, enriches with OSM road data, and derives cycling metrics from action-camera GPS trajectories, reporting 5.64% map-matching error.
-
String Covering: A Survey
A survey of string covering techniques including covers and seeds, with proposals for future research directions in combinatorial string algorithms.