Universal Hirschberg for Width Bounded Dynamic Programs

• URL: http://arxiv.org/abs/2512.10132v1
• Date: Wed, 10 Dec 2025 22:26:22 GMT
• Title: Universal Hirschberg for Width Bounded Dynamic Programs
• Abstract summary: Hirschberg's algorithm reduces the space complexity for the longest common subsequence problem from $O(N2)$ to $O(N)$ via a midpoint bisection on a grid dynamic program (DP)<n>We show that the underlying idea generalizes to a broad class of dynamic programs with local dependencies on directed acyclic graphs (DP DAGs)<n>We show that an $()$ space term is unavoidable in forward single-pass models and discuss conjectured $sqrtT$-type barriers in streaming settings.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Hirschberg's algorithm (1975) reduces the space complexity for the longest common subsequence problem from $O(N^2)$ to $O(N)$ via recursive midpoint bisection on a grid dynamic program (DP). We show that the underlying idea generalizes to a broad class of dynamic programs with local dependencies on directed acyclic graphs (DP DAGs). Modeling a DP as deterministic time evolution over a topologically ordered DAG with frontier width $ω$ and bounded in-degree, and assuming a max-type semiring with deterministic tie breaking, we prove that in a standard offline random-access model any such DP admits deterministic traceback in space $O(ω\log T + (\log T)^{O(1)})$ cells over a fixed finite alphabet, where $T$ is the number of states. Our construction replaces backward dynamic programs by forward-only recomputation and organizes the time order into a height-compressed recursion tree whose nodes expose small "middle frontiers'' across which every optimal path must pass. The framework yields near-optimal traceback bounds for asymmetric and banded sequence alignment, one-dimensional recurrences, and dynamic-programming formulations on graphs of bounded pathwidth. We also show that an $Ω(ω)$ space term (in bits) is unavoidable in forward single-pass models and discuss conjectured $\sqrt{T}$-type barriers in streaming settings, supporting the view that space-efficient traceback is a structural property of width-bounded DP DAGs rather than a peculiarity of grid-based algorithms.

Related papers

• Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise [55.29259818039367]
  We study online convex optimization (OCO) in non-stationary environments under heavy-tailed noise.<n>We propose textbfHT-PAder, a parameter-free algorithm combining restarted AdaGrad experts over a geometric pool of block lengths.<n>Even in the special case of finite variance ($p=2$), HT-PAder provides the first parameter-free minimax universal dynamic regret guarantee.
  arXiv  Detail & Related papers  (2026-07-29T15:58:18Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• DAGGER: Gradient-Free Construction of Transiently Amplifying Networks under Hard Connectivity Constraints [0.0]
  DAGGER is a gradient-free single-pass algorithm for transient non-normal amplification.<n>It matches or exceeds gradient-based methods at multiset preservation in a single forward pass.<n>We show why DAGGER is structurally different from other amplifying networks.
  arXiv  Detail & Related papers  (2026-05-31T13:20:26Z)
• Coherent Rollout Oracles for Finite-Horizon Sequential Decision Problems [0.0]
  Coherent quantum rollout for sequential decision problems requires a unitary simulator.<n>With branch-dependent valid actions, this mapping is totalized coherent rank-select over an entangled $N-bit mask.<n>We give the first reversible-circuit complexity analysis of this primitive.
  arXiv  Detail & Related papers  (2026-04-28T00:46:37Z)
• Acyclic Graph Pattern Counting under Local Differential Privacy [6.729442409066558]
  We present the first general solution for counting arbitrary acyclic patterns under local differential privacy (LDP)<n>We tackle two fundamental challenges: generalizing pattern construction from distributed data and eliminating node duplication during the construction.<n> Experiments on real-world graph datasets across multiple types of acyclic patterns demonstrate that our mechanisms achieve up to $46$-$2600times$ improvement in utility and $300$-$650times$ reduction in communication cost compared to the baseline methods.
  arXiv  Detail & Related papers  (2026-03-20T06:12:12Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling [2.0607844057825324]
  We study the sublinear space continual release model for edge-differentially private (DP) graph algorithms.<n>Our main result is the first continual release DSG algorithm that matches the additive error of the best static DP algorithms.<n>We introduce graph densification in the graph DP setting, adding edges to trigger earlier subsampling, which removes the extra logarithmic factors in error and space incurred by prior work.
  arXiv  Detail & Related papers  (2025-10-13T17:20:13Z)
• Scalable Graph Generative Modeling via Substructure Sequences [50.32639806800683]
  We introduce Generative Graph Pattern Machine (G$2$PM), a generative Transformer pre-training framework for graphs.<n>G$2$PM represents graph instances (nodes, edges, or entire graphs) as sequences of substructures.<n>It employs generative pre-training over the sequences to learn generalizable and transferable representations.
  arXiv  Detail & Related papers  (2025-05-22T02:16:34Z)
• On the Price of Differential Privacy for Hierarchical Clustering [21.64775530337936]
  We present a novel algorithm in the weight privacy model that shows significantly better approximation than known impossibility results in the edge-level DP setting.<n>Our results show that our algorithm performs well in terms of extra cost and has good scalability to large graphs.
  arXiv  Detail & Related papers  (2025-04-22T04:39:40Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Scalable network reconstruction in subquadratic time [0.0]
  We present a general algorithm applicable to a broad range of reconstruction problems that significantly outperforms this quadratic baseline. Our algorithm relies on a second neighbor search that produces the best edge candidates with high probability. We show that our algorithm achieves a performance that is many orders of magnitude faster than the quadratic baseline.
  arXiv  Detail & Related papers  (2024-01-02T19:00:13Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• Generalization Bounds for Stochastic Gradient Descent via Localized $\varepsilon$-Covers [16.618918548497223]
  We propose a new covering technique localized for the trajectories of SGD. This localization provides an algorithm-specific clustering measured by the bounds number. We derive these results in various contexts and improve the known state-of-the-art label rates.
  arXiv  Detail & Related papers  (2022-09-19T12:11:07Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
  In graph-based binary learning, a subset of known labels $hatx_i$ are used to infer unknown labels. When restricting labels $x_i$ to binary values, the problem is NP-hard. We propose a fast projection-free method by solving a sequence of linear programs (LP) instead.
  arXiv  Detail & Related papers  (2021-06-03T07:22:48Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  We study the noiseless model in the fundamental least-squares setup. We assume that an optimum predictor fits perfectly inputs and outputs $langle theta_*, phi(X) rangle = Y$, where $phi(X)$ stands for a possibly infinite dimensional non-linear feature map.
  arXiv  Detail & Related papers  (2021-02-05T14:02:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.