Kevin Pratt

works on

algorithmic complexity 1 combinatorial optimization 1 exact exponential algorithms 1 graph coloring 1 randomized algorithms 1

From the 1 of 5 linked papers with an AI index.

activity

20242026

collaborators

5 papers

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

The paper presents a randomized one‑sided error algorithm that solves graph k‑coloring in O((2‑ε_k)^n) time for any k, thus breaking the long‑standing 2^n time barrier.

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…

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 [Pr…

An algorithm for k-set cover

Breaking the 2n barrier for graph k-coloring

The edge of the asymptotic spectrum of tensors

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