### Avatars Grow Legs: Generating Smooth Human Motion from Sparse Tracking Inputs with Diffusion Model

Yuming Du, Robin Kips, Albert Pumarola, Sebastian Starke, Ali Thabet, Artsiom Sanakoyeu

International Symposium on Algorithms and Computation (ISAAC)

We study a graph reordering problem motivated by compressing massive graphs such as social networks and inverted indexes. Given a graph, *G *= (*V*, *E*), the *Minimum Logarithmic Arrangement* problem is to find a permutation, π, of the vertices that minimizes

∑ (1 + ⌊lg |π(u) − π(v)|⌋). (u,v)∈E

This objective has been shown to be a good measure of how many bits are needed to encode the graph if the adjacency list of each vertex is encoded using relative positions of two consecutive neighbors under the *π* order in the list rather than using absolute indices or node identifiers, which requires at least lg *n* bits per edge. We show the first non-trivial approximation factor for this problem by giving a polynomial time *O*(log *k*)-approximation algorithm for graphs with treewidth *k*.

Yuming Du, Robin Kips, Albert Pumarola, Sebastian Starke, Ali Thabet, Artsiom Sanakoyeu

Lisa Rivalin, Andrew Grier, Tobias Tiecke, Chi Zhou, Doris Gao, Prakriti Choudhury, John Fabian

Nadia Alshahwan, Mark Harman, Alexandru Marginean