1 citations · 1 across the 7 of their papers we have counts for
7 papers
An algorithm for -set cover
Josh Alman, Baitian Li, Kevin Pratt
We show that set cover on a universe of size and with sets of size at most can be solved in time . This improves on a -time alg…
Breaking the barrier for graph -coloring
Kevin Pratt
We show that for all , there exists such that graph -coloring can be solved by a randomized algorithm with one-sided error in time $O((2-\varepsilon_k)^n)…
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…
Faster Convolutions: Yates and Strassen Revisited
Cornelius Brand, Radu Curticapean, Baitian Li +1
Given two vectors over a finite domain and a function , the convolution problem asks to compute the vector whose…
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…
A stronger connection between the asymptotic rank conjecture and the set cover conjecture
Kevin Pratt
We give a short proof that Strassen's asymptotic rank conjecture implies that for every there exists a -time algorithm for set cover…
On generalized corners and matrix multiplication
Kevin Pratt
Suppose that contains no three points of the form , where . How big can be? Trivially, . Slight improv…