### 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

Bilge Acun, Benjamin Lee, Fiodar Kazhamiaka, Kiwan Maeng, Manoj Chakkaravarthy, Udit Gupta, David Brooks, Carole-Jean Wu

Ilkan Esiyok, Pascal Berrang, Katriel Cohn-Gordon, Robert Künnemann