Baitian Li

activity

20232026

collaborators

Showing cs.DSShow all

4 papers · 1 filter

cs.DS2026

An algorithm for $k$ -set cover

Josh Alman, Baitian Li, Kevin Pratt

We show that set cover on a universe of size $n$ and with sets of size at most $k$ can be solved in time $2^{(1 - 1/ k + O (1/ k^{3/2})) n}$ . This improves on a $2^{(1 - 0.929/ k) n}$ -time alg…

cs.DS2025

Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum

Josh Alman, Baitian Li

We study circuits for computing depth-2 linear transforms defined by Kronecker power matrices. Recent works have improved on decades-old constructions in this area using a new ''re…

cs.DS2025

Faster Convolutions: Yates and Strassen Revisited

Cornelius Brand, Radu Curticapean, Baitian Li +1

Given two vectors $u, v \in Q^{D}$ over a finite domain $D$ and a function $f : D \times D \to D$ , the convolution problem asks to compute the vector $w \in Q^{D}$ whose…

cs.DS2023

Counting perfect matchings and Hamiltonian cycles faster