Kevin Pratt

activity

20232026

most citedFast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

1 citations · 1 across the 7 of their papers we have counts for

collaborators

Showing 2026Show all

3 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.DS2026

Breaking the $2^{n}$ barrier for graph $k$ -coloring

Kevin Pratt

We show that for all $k$ , there exists $ε_{k} > 0$ such that graph $k$ -coloring can be solved by a randomized algorithm with one-sided error in time $O((2-\varepsilon_k)^n)…

cs.CC2026

The edge of the asymptotic spectrum of tensors

Josh Alman, Baitian Li, Kevin Pratt

Strassen founded the theory of the asymptotic spectrum of tensors to study the complexity of matrix multiplication. A central challenge in this theory is to explicitly construct ne…

An algorithm for k-set cover

Breaking the 2n barrier for graph k-coloring

The edge of the asymptotic spectrum of tensors

An algorithm for $k$ -set cover

Breaking the $2^{n}$ barrier for graph $k$ -coloring