A weight-preserving reduction from undirected 2-FRP to SSRP establishes their computational equivalence and yields matching improved algorithms for 2-FRP.
hub
URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs
16 Pith papers cite this work. Polarity classification is still indexing.
16
Pith papers citing it
hub tools
years
2026 16representative citing papers
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.
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.
Rational-weight ReLU neural networks and certain polynomial rings with ReLU are characterized as formulas in Rational Pavelka Logic and fragments of LΠ1/2.
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.
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.
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.
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.
Linearizable atomic register implementations in asynchronous message-passing systems require extensive message chains among operations of all types.
First experimental study of dynamic greedy set cover algorithms reveals practical tradeoffs in quality and efficiency across real instances.
citing papers explorer
-
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.
-
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.
-
Neural networks as fuzzy logic formulas
Rational-weight ReLU neural networks and certain polynomial rings with ReLU are characterized as formulas in Rational Pavelka Logic and fragments of LΠ1/2.
-
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.
-
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.