Kevin Pratt

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.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.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.DS2024

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

Andreas Björklund, Radu Curticapean, Thore Husfeldt +2

In this paper we further explore the recently discovered connection by Björklund and Kaski [STOC 2024] and Pratt [STOC 2024] between the asymptotic rank conjecture of Strassen [Pro…

An algorithm for k-set cover

Breaking the 2n barrier for graph k-coloring

Faster Convolutions: Yates and Strassen Revisited

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

An algorithm for $k$ -set cover

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