Fast Convolutions for Near-Convex Sequences

Cornelius Brand, Alexandra LassotaISAAC 2023 · OpenReview

TL;DR

This paper introduces novel measures for quantifying the "near-convexity" of sequences. They leverage these measures to develop algorithms for (min, +)-convolution and related problems that bridge the gap between highly efficient algorithms for perfectly convex sequences and the conjectured quadratic lower bound for general sequences.

What Problem Does This Paper Address?

The paper tackles the problem of computing the (min, +)-convolution of two sequences, a fundamental operation in areas like tropical algebra and computational geometry. While perfectly convex sequences can be convolved in near-linear time, general sequences are conjectured to require quadratic time. This leaves a significant gap where the complexity of "almost convex" or "near-convex" sequences remains poorly understood. The authors aim to quantify this "near-convexity" and develop algorithms that smoothly interpolate between the two extremes, providing better performance than the general quadratic approach for inputs that exhibit some degree of convexity.

Methods

The core of the paper lies in introducing two new measures of convexity: the convex sequence number and the convex rank.

  • Convex Sequence Number ($s_t$): This measures the minimum number of "cuts" needed to partition a sequence into convex subsequences. The authors provide a linear-time greedy algorithm to compute this.
  • Convex Rank ($r_t$): This is a more refined measure, defined as the minimum number of convex sequences whose pointwise minimum forms the original sequence. Computing the exact convex rank is hard, so the authors develop an $O(\log n)$-approximation algorithm using a greedy approach combined with dynamic programming.

These convexity measures are then used to design faster algorithms for:

  • (min, +)-CONVOLUTION: Algorithms with running times like $O(s_a \cdot n)$ or $O(r_a \cdot n)$ are presented, where $s_a$ and $r_a$ are the convex sequence number and convex rank of one of the input sequences, respectively.
  • SUPER ADDITIVITY TESTING: This problem is reduced to (min, +)-convolution with $a=b$, leading to similar complexity bounds.
  • CONVOLUTION 3-SUM: An algorithm with $O(s_a \cdot n)$ complexity is developed.
  • MINIMUM CONSECUTIVE SUBSUMS: Algorithms with $O(s_t \cdot n)$ and $O(r_t \cdot n)$ complexities are presented.

The algorithms often leverage existing techniques like the SMAWK algorithm for efficiently processing convex structures.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and complexity, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Quantifying "Near-Convexity" is Key: The paper demonstrates that the degree of convexity can be precisely measured, and this measurement directly translates into algorithmic improvements.
  • Convex Sequence Number vs. Convex Rank: The distinction between these two measures is crucial. The convex sequence number is easy to compute but can be large for "entangled" convex sequences. The convex rank is a more accurate measure of underlying structure but harder to compute exactly.
  • Interpolation is Possible: The work successfully bridges the gap between the $O(n)$ complexity for fully convex sequences and the conjectured $O(n^2)$ for general sequences, providing a spectrum of algorithms based on the input's convexity.
  • Greedy Algorithms with DP for Approximation: The $O(\log n)$-approximation for convex rank highlights the power of combining greedy strategies with dynamic programming for complex structural problems.

Key Results

  • Convex Sequence Number Computation: A linear-time algorithm to compute the minimum number of cuts to partition a sequence into convex subsequences.
  • Convex Rank Approximation: An $O(\log n)$-approximation algorithm for the convex rank, running in $O(r_t \cdot n^4 \log n)$ time.
  • Improved Convolution Algorithms:
  • (min, +)-CONVOLUTION: $O(s_a \cdot n)$ and $O(r_a \cdot n)$ algorithms are presented.
  • MINIMUM CONSECUTIVE SUBSUMS: $O(s_t \cdot n)$ and $O(r_t \cdot n)$ algorithms.
  • SUPER ADDITIVITY TESTING: $O(r_a \cdot n)$ algorithm.
  • CONVOLUTION 3-SUM: $O(s_a \cdot n)$ algorithm.
  • Theoretical Significance: The results provide a fine-grained understanding of convolution complexity based on input structure and offer algorithms that are optimal under certain assumptions (like the min-plus conjecture).

Limitations and Future Work

  • Exact Convex Rank Computation: The paper notes that computing the convex rank exactly is a challenging open question, potentially NP-hard.
  • CONVOLUTION 3-SUM with Convex Rank: An efficient $O(r_t \cdot n)$ algorithm for CONVOLUTION 3-SUM remains an open problem.
  • Tightness of Bounds: While the algorithms are efficient based on the new measures, the paper acknowledges that some bounds might not be tight, especially concerning the dependence on the convex rank.
  • Further Research Directions: The authors suggest exploring whether tighter bounds can be achieved, particularly for avoiding quadratic dependencies on the convex rank, and investigating the exact complexity of computing the convex rank.

Summary updated

Abstract

We develop algorithms for (min,+)-Convolution and related convolution problems such as Super Additivity Testing, Convolution 3-Sum and Minimum Consecutive Subsums which use the degree of convexity of the instance as a parameter. Assuming the min-plus conjecture (Künnemann-Paturi-Schneider, ICALP'17 and Cygan et al., ICALP'17), our results interpolate in an optimal manner between fully convex instances, which can be solved in near-linear time using Legendre transformations, and general non-convex sequences, where the trivial quadratic-time algorithm is conjectured to be best possible, up to subpolynomial factors.
BibTeX
@inproceedings{brand2023fast,
  author = {Cornelius Brand and Alexandra Lassota},
  title = {{Fast Convolutions for Near-Convex Sequences}},
  booktitle = {ISAAC},
  year = {2023},
  url = {https://openreview.net/forum?id=cfGAc7SgyC},
}
Figure