We prove that any Steiner triple system $\mathcal{S}$, with $n = v(\mathcal{S})$ sufficiently large, admits a packing by almost spanning paths that covers almost all edges. More formally, for any $\mu > 0$, we obtain a family of $(1-\mu)n/3$ pairwise edge-disjoint paths, with $(1-\mu)n$ vertices each, all contained in $\mathcal{S}$.

The Frieze–Kannan regularity lemma is a powerful tool in combinatorics. It has also found applications in the design of approximation algorithms and recently in the design of fast combinatorial algorithms for boolean matrix multiplication. The algorithmic applications of this lemma require one to efficiently construct a partition satisfying the conditions of the lemma. R. Williams recently asked if one can construct a partition satisfying the conditions of the Frieze–Kannan regularity lemma in deterministic subcubic time. We resolve this problem by designing an $\tilde O(n^{\omega})$ time algorithm for constructing such a partition, where $\omega < 2.376$ is the exponent of fast matrix multiplication. The algorithm relies on a spectral characterization of vertex partitions satisfying the properties of the Frieze–Kannan regularity lemma.

We prove that asymptotically (as $n\to\infty$) almost all graphs with n vertices and $C_dn^{2-\frac{1}{2d}} \log^{\frac{1}{d}} n$ edges are universal with respect to the family of all graphs with maximum degree bounded by d. Moreover, we provide an efficient deterministic embedding algorithm for finding copies of bounded degree graphs in graphs satisfying certain pseudorandom properties. We also prove a counterpart result for random bipartite graphs, where the threshold number of edges is even smaller but the embedding is randomized.

We propose a new algorithm for optimal MAE stack filter design. It is based on three main ingredients. First, we show that the dual of the integer programming formulation of the filter design problem is a minimum cost network flow problem. Next, we present a decomposition principle that can be used to break this dual problem into smaller subproblems. Finally, we propose a specialization of the network Simplex algorithm based on column generation to solve these smaller subproblems. Using our method, we were able to efficiently solve instances of the filter problem with window size up to 25 pixels. To the best of our knowledge, this is the largest dimension for which this problem was ever solved exactly.