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 2026 · cs.DSShow all

2 papers · 2 filters

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)…

An algorithm for k-set cover

Breaking the 2n barrier for graph k-coloring

An algorithm for $k$ -set cover

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