---
# System prepended metadata

title: $\ell_p$ norm flow builds

---

# $\ell_p$ norm flow builds

Description of p-norm flow builds and why they work or don't work.

## Build 1: Dynamic $\ell_1$ routing
Use $m^{1+o(1)}$ iterations of an $\ell_1$ oblivious routings to push flows.

*Progress:* seems like we can build a data structure that returns $m^{o(1)}$-quality $\ell_1$ minimizers in $m^{o(1)}$ amortized time using vertex sparsifiers + j-trees + low recourse spanners.

*Issues:* Naively, the returned flow isn't a single cycle -- may be dense. Pushing it and updating when edges changes seems challenging.

Also, if we random sample down to a single cycle, cannot prove that we can sample $O(\log n)$ trees to last us over a long time (oblivious vs adaptive adversary issues).

https://www.overleaf.com/5923724933rwxxrvckrgrb

## Build 2: Adaptive Cycle Toggling
Prove that there is a single low-stretch tree that makes $1/m^{1+o(1)}$-progress against the objective. In fact, exists a cycle on such tree that makes progress.

*Progress:* Exists a cycle on a tree with total stretch at most $m^{1+o(1)}$ wrt some weights that makes $1/m^{1+o(1)}$ progress against the objective.

I believe that fully dynamic low stretch spanning tree against adaptive adversaries should work. In fact can probably even report for each edge an $m^{o(1)}$ overestimate of stretch. Additionally, in total at most $m^{1+o(1)} + q^{1+o(1)}$ edges must change over the course of $q$ queries.

*Issues:* Cannot do a MWU on top of this -- must be in the outside iterative refinement loop.

When done this way, cannot prove that $m^{1+o(1)}$ have their lengths double over the course of the algorithm, so algorithm may be forced to make too many updates.

I can only show existence of an edge -- cannot prove that a random edge sampled wrt stretch makes enough progress.

https://www.overleaf.com/9186267435zpqcqnddbnrj

## Build 3: Precondition with $\ell_4$ routings.
Goal is to get an $m^{5/4+o(1)}$ time algorithm, instead of $m^{1+o(1)}$.
Idea is to consider the problem $\min_{B^\top x = 0} g^\top x + \sum_e r_ex_e^2 + w_e|x_e|^p$ and to precondition it with a norm *between* $2$ and $p$, eg. the 4-norm.

Naively, recover $m^{1+\frac{p-2}{3p-2}+o(1)}$ runtime actually -- can precondition with the $3$-norm. On the $2$-norm side you pay double the norm distortion, so $2|1/2 - 1/3| = 1/3$, and on the $p$-norm side you pay $|1/3-1/p| \le 1/3.$

Idea: do an acceleration on the $2$-norm side using Chebyschev polynomials or something. Essentially, a $4$-norm oblivious routing is a linear operator, so it may be possible to accelerate to get the more natural $1/2 - 1/q = 1/q - 1/p$ type tradeoff.

*Potential Issues:* Can we actually MWU this, or must it be outside the iterative refinement loop? Does acceleration work with approximate minimizers?

## Other Ideas:
Build $\ell_2$-$\ell_p$ oblivious routings or ultra-sparsifiers for the objectives we care about (for some proper definitions).

Here is a note detailing why I don't think such objects exist under the definitions I constructed, but definitely possible that looser definitions are legitimate to use (and not vacuous).

https://www.overleaf.com/2247568984vsdmpyrpnygh
