BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Kevin Pratt

Kevin Pratt contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and Algorithmsmath.GRComputational ComplexityDiscrete Mathematicsmath.CO

Trust snapshot

Quick read

Trust 15 - UnverifiedVerification L1Unclaimed author
3works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

3 published item(s)

preprint2022arXiv

High-Dimensional Expanders from Chevalley Groups

Let $Φ$ be an irreducible root system (other than $G_2$) of rank at least $2$, let $\mathbb{F}$ be a finite field with $p = \operatorname{char} \mathbb{F} > 3$, and let $\mathrm{G}(Φ,\mathbb{F})$ be the corresponding Chevalley group. We describe a strongly explicit high-dimensional expander (HDX) family of dimension $\mathrm{rank}(Φ)$, where $\mathrm{G}(Φ,\mathbb{F})$ acts simply transitively on the top-dimensional faces; these are $λ$-spectral HDXs with $λ\to 0$ as $p \to \infty$. 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 $\ge 2$, and four exceptional constructions of dimension $4$, $6$, $7$, and $8$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Matrix multiplication via matrix groups

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An Algorithmic Method of Partial Derivatives

We study the following problem and its applications: given a homogeneous degree-$d$ polynomial $g$ as an arithmetic circuit, and a $d \times d$ matrix $X$ whose entries are homogeneous linear polynomials, compute $g(\partial/\partial x_1, \ldots, \partial/\partial x_n) \det X$. By considering special cases of this problem we obtain faster parameterized algorithms for several problems, including the matroid $k$-parity and $k$-matroid intersection problems, faster \emph{deterministic} algorithms for testing if a linear space of matrices contains an invertible matrix (Edmonds's problem) and detecting $k$-internal outbranchings, and more. We also match the runtime of the fastest known deterministic algorithm for detecting subgraphs of bounded pathwidth, while using a new approach. Our approach raises questions in algebraic complexity related to Waring rank and the exponent of matrix multiplication $ω$. In particular, we study a new complexity measure on the space of homogeneous polynomials, namely the bilinear complexity of a polynomial's apolar algebra. Our algorithmic improvements are reflective of the fact that for the degree-$n$ determinant polynomial this quantity is at most $O(n 2^{ωn})$, whereas all known upper bounds on the Waring rank of this polynomial exceed $n!$.

0 citations0 reviewsNo code linkedOpen access