Search Results

Documents authored by Pratt, Kevin

Document
DOI: 10.4230/LIPIcs.ITCS.2024.89
On Generalized Corners and Matrix Multiplication

Authors: Kevin Pratt

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Suppose that S ⊆ [n]² contains no three points of the form (x,y), (x,y+δ), (x+δ,y'), where δ ≠ 0. How big can S be? Trivially, n ≤ |S| ≤ n². Slight improvements on these bounds are obtained from Shkredov’s upper bound for the corners problem [Shkredov, 2006], which shows that |S| ≤ O(n²/(log log n)^c) for some small c > 0, and a construction due to Petrov [Fedor Petrov, 2023], which shows that |S| ≥ Ω(n log n/√{log log n}). Could it be that for all ε > 0, |S| ≤ O(n^{1+ε})? We show that if so, this would rule out obtaining ω = 2 using a large family of abelian groups in the group-theoretic framework of [Cohn and Umans, 2003; Cohn et al., 2005] (which is known to capture the best bounds on ω to date), for which no barriers are currently known. Furthermore, an upper bound of O(n^{4/3 - ε}) for any fixed ε > 0 would rule out a conjectured approach to obtain ω = 2 of [Cohn et al., 2005]. Along the way, we encounter several problems that have much stronger constraints and that would already have these implications.
Cite as

Kevin Pratt. On Generalized Corners and Matrix Multiplication. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 89:1-89:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{pratt:LIPIcs.ITCS.2024.89,
  author =	{Pratt, Kevin},
  title =	{{On Generalized Corners and Matrix Multiplication}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{89:1--89:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.89},
  URN =		{urn:nbn:de:0030-drops-196174},
  doi =		{10.4230/LIPIcs.ITCS.2024.89},
  annote =	{Keywords: Algebraic computation, fast matrix multiplication, additive combinatorics}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.19
Matrix Multiplication via Matrix Groups

Authors: Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, and Chris Umans

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
In 2003, Cohn and Umans proposed a group-theoretic approach to bounding the exponent of matrix multiplication. Previous work within this approach ruled out certain families of groups as a route to obtaining ω = 2, while other families of groups remain potentially viable. In this paper we turn our attention to matrix groups, whose usefulness within this framework was relatively unexplored. We first show that groups of Lie type cannot prove ω = 2 within the group-theoretic approach. This is based on a representation-theoretic argument that identifies the second-smallest dimension of an irreducible representation of a group as a key parameter that determines its viability in this framework. Our proof builds on Gowers' result concerning product-free sets in quasirandom groups. We then give another barrier that rules out certain natural matrix group constructions that make use of subgroups that are far from being self-normalizing. Our barrier results leave open several natural paths to obtain ω = 2 via matrix groups. To explore these routes we propose working in the continuous setting of Lie groups, in which we develop an analogous theory. Obtaining the analogue of ω = 2 in this potentially easier setting is a key challenge that represents an intermediate goal short of actually proving ω = 2. We give two constructions in the continuous setting, each of which evades one of our two barriers.
Cite as

Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, and Chris Umans. Matrix Multiplication via Matrix Groups. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{blasiak_et_al:LIPIcs.ITCS.2023.19,
  author =	{Blasiak, Jonah and Cohn, Henry and Grochow, Joshua A. and Pratt, Kevin and Umans, Chris},
  title =	{{Matrix Multiplication via Matrix Groups}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.19},
  URN =		{urn:nbn:de:0030-drops-175226},
  doi =		{10.4230/LIPIcs.ITCS.2023.19},
  annote =	{Keywords: Fast matrix multiplication, representation theory, matrix groups}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.18
High-Dimensional Expanders from Chevalley Groups

Authors: Ryan O'Donnell and Kevin Pratt

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
Let Φ be an irreducible root system (other than G₂) of rank at least 2, let 𝔽 be a finite field with p = char 𝔽 > 3, and let G(Φ,𝔽) be the corresponding Chevalley group. We describe a strongly explicit high-dimensional expander (HDX) family of dimension rank(Φ), where G(Φ,𝔽) acts simply transitively on the top-dimensional faces; these are λ-spectral HDXs with λ → 0 as p → ∞. This generalizes a construction of Kaufman and Oppenheim (STOC 2018), which corresponds to the case Φ = A_d. Our work gives three new families of spectral HDXs of any dimension ≥ 2, and four exceptional constructions of dimension 4, 6, 7, and 8.
Cite as

Ryan O'Donnell and Kevin Pratt. High-Dimensional Expanders from Chevalley Groups. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 18:1-18:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{odonnell_et_al:LIPIcs.CCC.2022.18,
  author =	{O'Donnell, Ryan and Pratt, Kevin},
  title =	{{High-Dimensional Expanders from Chevalley Groups}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{18:1--18:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.18},
  URN =		{urn:nbn:de:0030-drops-165802},
  doi =		{10.4230/LIPIcs.CCC.2022.18},
  annote =	{Keywords: High-dimensional expanders, simplicial complexes, group theory}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.38
Parameterized Applications of Symbolic Differentiation of (Totally) Multilinear Polynomials

Authors: Cornelius Brand and Kevin Pratt

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We study the following problem and its applications: given a homogeneous degree-d polynomial g as an arithmetic circuit C, and a d × d matrix X whose entries are homogeneous linear polynomials, compute g(∂/∂ x₁, …, ∂/∂ x_n) det X. We show that this quantity can be computed using 2^{ω d}|C|poly(n,d) arithmetic operations, where ω is the exponent of matrix multiplication. In the case that C is skew, we improve this to 4^d|C| poly(n,d) operations, and if furthermore X is a Hankel matrix, to φ^{2d}|C| poly(n,d) operations, where φ = (1+√5)/2 is the golden ratio. Using these observations we give faster parameterized algorithms for the matroid k-parity and k-matroid intersection problems for linear matroids, and faster deterministic algorithms for several problems, including the first deterministic polynomial time algorithm for testing if a linear space of matrices of logarithmic dimension contains an invertible matrix. We also match the runtime of the fastest deterministic algorithm for detecting subgraphs of bounded pathwidth with a new and simple approach. Our approach generalizes several previous methods in parameterized algorithms and can be seen as a relaxation of Waring rank based methods [Pratt, FOCS19].
Cite as

Cornelius Brand and Kevin Pratt. Parameterized Applications of Symbolic Differentiation of (Totally) Multilinear Polynomials. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 38:1-38:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{brand_et_al:LIPIcs.ICALP.2021.38,
  author =	{Brand, Cornelius and Pratt, Kevin},
  title =	{{Parameterized Applications of Symbolic Differentiation of (Totally) Multilinear Polynomials}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{38:1--38:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.38},
  URN =		{urn:nbn:de:0030-drops-141079},
  doi =		{10.4230/LIPIcs.ICALP.2021.38},
  annote =	{Keywords: Parameterized Algorithms, Algebraic Algorithms, Longest Cycle, Matroid Parity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.69
Exploring Circle Packing Algorithms

Authors: Kevin Pratt, Connor Riley, and Donald Sheehy

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We present an interactive tool for visualizing and experimenting with different circle packing algorithms.
Cite as

Kevin Pratt, Connor Riley, and Donald Sheehy. Exploring Circle Packing Algorithms. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 69:1-69:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{pratt_et_al:LIPIcs.SoCG.2016.69,
  author =	{Pratt, Kevin and Riley, Connor and Sheehy, Donald},
  title =	{{Exploring Circle Packing Algorithms}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{69:1--69:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.69},
  URN =		{urn:nbn:de:0030-drops-59616},
  doi =		{10.4230/LIPIcs.SoCG.2016.69},
  annote =	{Keywords: Computational Geometry, Processing, Javascript, Visualization, Incremental Algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact