Author name cluster

Kevin Pratt

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

SODA Conference 2025 Conference Paper

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

Andreas Björklund
Radu Curticapean
Thore Husfeldt
Petteri Kaski
Kevin Pratt

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 [Progr. Math. 1994] and the three-way partitioning problem. We show that under the asymptotic rank conjecture, the chromatic number of an n -vertex graph can be computed deterministically in O (1. 99982 n ) time, thus giving a conditional answer to a question of Zamir [ICALP 2021], and questioning the optimality of the 2 n poly( n ) time algorithm for chromatic number by Björklund, Husfeldt, and Koivisto [SICOMP 2009]. Viewed in the other direction, if chromatic number indeed requires deterministic algorithms to run in close to 2 n time, we obtain a sequence of explicit tensors of superlinear rank, falsifying the asymptotic rank conjecture. Our technique is a combination of earlier algorithms for detecting k -colorings for small k and enumerating k -colorable subgraphs, with an extension and derandomisation of Pratt’s tensor-based algorithm for balanced three-way partitioning to the unbalanced case.

Details

STOC Conference 2024 Conference Paper

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 on a universe of size n with sets of bounded size. This strengthens and simplifies a recent result of Bj'orklund and Kaski that Strassen’s asymptotic rank conjecture implies that the set cover conjecture is false. From another perspective, we show that the set cover conjecture implies that a particular family of tensors T n ∈ ℂ N ⊗ ℂ N ⊗ ℂ N has asymptotic rank greater than N 1.08 . Furthermore, if one could improve a known upper bound of 8 n on the tensor rank of T n to 2/9 · n 8 n for any n , then the set cover conjecture is false.

Details

YNIMG Journal 2021 Journal Article

A 3-axis coil design for multichannel TMS arrays

Lucia I. Navarro de Lara
Mohammad Daneshzand
Anthony Mascarenas
Douglas Paulson
Kevin Pratt
Yoshio Okada
Tommi Raij
Sergey N. Makarov

PURPOSE: Multichannel Transcranial Magnetic Stimulation (mTMS) arrays enable multiple sites to be stimulated simultaneously or sequentially under electronic control without moving the system's stimulation coils. Here, we build and characterize the performance of a novel modular 3-axis TMS coil that can be utilized as a unit element in large-scale multichannel TMS arrays. METHODS: We determined the basic physical characteristics of the 3-axis TMS coil x-, y- and z-elements using a custom 2-channel programmable stimulator prototype. We mapped the temporal rate-of-change of the induced magnetic field (dB/dt) on a 2D plane parallel to the coil surface (including an extended line for full spatial coverage) and compared those values with predictions from magnetic field simulations. Temperature measurements were carried out to assess the incorporated air-cooling method. We measured the mutual and self-inductances of the x/y/z-elements to assess coupling between them. Additionally, we measured and calculated the coupling between z-elements in the array configuration. Finally, we performed electric field simulations to evaluate the stimulation intensity and focality of the coil and compared the results to conventional TMS coils as well as demonstrated suitability of the 3-axis coil for a multichannel array configuration. RESULTS: The experimentally obtained dB/dt values validated the computational model of the 3-axis coil and therefore confirmed that both the coil and stimulator system are operating as intended. The air-cooling system was effective for brief high-frequency pulse trains and extended single- and paired-pulse TMS protocols. The electromagnetic simulations suggested that an array of the 3-axis coils would have comparable stimulation intensity to conventional TMS coils, therefore enabling clearly suprathreshold stimulation of the human brain. The recorded coil coupling between the x/y/z-elements was < 1% and the maximal coupling between z-elements in the array configuration was 1.8% and 3.4% for the measured and calculated values, respectively. CONCLUSION: We presented a 3-axis coil intended for multichannel TMS arrays. The electromagnetic measurements and simulations verified that the coil fabrication met the desired specifications and that the inductive coupling between the elements was negligible. The air-cooled 3-axis TMS coil appears suitable to be used as an element in multichannel TMS arrays.

Details DOI

FOCS Conference 2019 Conference Paper

Waring Rank, Parameterized and Exact Algorithms

Kevin Pratt

We show that the Waring rank (symmetric tensor rank) of a certain family of polynomials has intimate connections to the areas of parameterized and exact algorithms, generalizing some well-known methods and providing a concrete approach to obtain faster approximate counting and deterministic decision algorithms. To illustrate the amenability and utility of this approach, we give an algorithm for approximately counting subgraphs of bounded treewidth, improving on earlier work of Alon, Dao, Hajirasouliha, Hormozdiari, and Sahinalp. Along the way we give an exact answer to an open problem of Koutis and Williams and sharpen a lower bound on the size of perfectly balanced hash families given by Alon and Gutner.

Details