7 Search Results for "Pratt, Kevin"


Document
Quantum Merlin-Arthur and Proofs Without Relative Phase

Authors: Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha

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


Abstract
We study a variant of QMA where quantum proofs have no relative phase (i.e. non-negative amplitudes, up to a global phase). If only completeness is modified, this class is equal to QMA [Grilo et al., 2014]; but if both completeness and soundness are modified, the class (named QMA+ by Jeronimo and Wu [Jeronimo and Wu, 2023]) can be much more powerful. We show that QMA+ with some constant gap is equal to NEXP, yet QMA+ with some other constant gap is equal to QMA. One interpretation is that Merlin’s ability to "deceive" originates from relative phase at least as much as from entanglement, since QMA(2) ⊆ NEXP.

Cite as

Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha. Quantum Merlin-Arthur and Proofs Without Relative Phase. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{bassirian_et_al:LIPIcs.ITCS.2024.9,
  author =	{Bassirian, Roozbeh and Fefferman, Bill and Marwaha, Kunal},
  title =	{{Quantum Merlin-Arthur and Proofs Without Relative Phase}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{9:1--9:19},
  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.9},
  URN =		{urn:nbn:de:0030-drops-195370},
  doi =		{10.4230/LIPIcs.ITCS.2024.9},
  annote =	{Keywords: quantum complexity, QMA(2), PCPs}
}
Document
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
An Improved Trickle down Theorem for Partite Complexes

Authors: Dorna Abdolazimi and Shayan Oveis Gharan

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)


Abstract
We prove a strengthening of the trickle down theorem for partite complexes. Given a (d+1)-partite d-dimensional simplicial complex, we show that if "on average" the links of faces of co-dimension 2 are (1-δ)/d-(one-sided) spectral expanders, then the link of any face of co-dimension k is an O((1-δ)/(kδ))-(one-sided) spectral expander, for all 3 ≤ k ≤ d+1. For an application, using our theorem as a black-box, we show that links of faces of co-dimension k in recent constructions of bounded degree high dimensional expanders have spectral expansion at most O(1/k) fraction of the spectral expansion of the links of the worst faces of co-dimension 2.

Cite as

Dorna Abdolazimi and Shayan Oveis Gharan. An Improved Trickle down Theorem for Partite Complexes. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{abdolazimi_et_al:LIPIcs.CCC.2023.10,
  author =	{Abdolazimi, Dorna and Oveis Gharan, Shayan},
  title =	{{An Improved Trickle down Theorem for Partite Complexes}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.10},
  URN =		{urn:nbn:de:0030-drops-182807},
  doi =		{10.4230/LIPIcs.CCC.2023.10},
  annote =	{Keywords: Simplicial complexes, High dimensional expanders, Trickle down theorem, Bounded degree high dimensional expanders, Locally testable codes, Random walks}
}
Document
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
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
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
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}
}
  • Refine by Author
  • 5 Pratt, Kevin
  • 1 Abdolazimi, Dorna
  • 1 Bassirian, Roozbeh
  • 1 Blasiak, Jonah
  • 1 Brand, Cornelius
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Algebraic complexity theory
  • 1 Theory of computation → Error-correcting codes
  • 1 Theory of computation → Expander graphs and randomness extractors
  • 1 Theory of computation → Quantum complexity theory
  • Show More...

  • Refine by Keyword
  • 1 Algebraic Algorithms
  • 1 Algebraic computation
  • 1 Bounded degree high dimensional expanders
  • 1 Computational Geometry
  • 1 Fast matrix multiplication
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 2 2023
  • 2 2024
  • 1 2016
  • 1 2021
  • 1 2022

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