Kevin Pratt

collaborators

3 papers

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

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 $ε > 0$ there exists a $(3/ 2^{2/3} + ε)^{n}$ -time algorithm for set cover…

math.CO2023

On generalized corners and matrix multiplication

Kevin Pratt

Suppose that $S \subseteq [n]^{2}$ contains no three points of the form $(x, y), (x, y + δ), (x + δ, y^{'})$ , where $δ \neq = 0$ . How big can $S$ be? Trivially, $n \leq ∣ S ∣ \leq n^{2}$ . Slight improv…