8 Search Results for "Pratt, Kevin"

Document
DOI: 10.4230/LIPIcs.ECRTS.2024.7
The Omnivisor: A Real-Time Static Partitioning Hypervisor Extension for Heterogeneous Core Virtualization over MPSoCs

Authors: Daniele Ottaviano, Francesco Ciraolo, Renato Mancuso, and Marcello Cinque

Published in: LIPIcs, Volume 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)

Abstract
Following the needs of industrial applications, virtualization has emerged as one of the most effective approaches for the consolidation of mixed-criticality systems while meeting tight constraints in terms of space, weight, power, and cost (SWaP-C). In embedded platforms with homogeneous processors, a wealth of works have proposed designs and techniques to enforce spatio-temporal isolation by leveraging well-understood virtualization support. Unfortunately, achieving the same goal on heterogeneous MultiProcessor Systems-on-Chip (MPSoCs) has been largely overlooked. Modern hypervisors are designed to operate exclusively on main cores, with little or no consideration given to other co-processors within the system, such as small microcontroller-level CPUs or soft-cores deployed on programmable logic (FPGA). Typically, hypervisors consider co-processors as I/O devices allocated to virtual machines that run on primary cores, yielding full control and responsibility over them. Nevertheless, inadequate management of these resources can lead to spatio-temporal isolation issues within the system. In this paper, we propose the Omnivisor model as a paradigm for the holistic management of heterogeneous platforms. The model generalizes the features of real-time static partitioning hypervisors to enable the execution of virtual machines on processors with different Instruction Set Architectures (ISAs) within the same MPSoC. Moreover, the Omnivisor ensures temporal and spatial isolation between virtual machines by integrating and leveraging a variety of hardware and software protection mechanisms. The presented approach not only expands the scope of virtualization in MPSoCs but also enhances the overall system reliability and real-time performance for mixed-criticality applications. A full open-source reference implementation of the Omnivisor based on the Jailhouse hypervisor is provided, targeting ARM real-time processing units and RISC-V soft-cores on FPGA. Experimental results on real hardware show the benefits of the solution, including enabling the seamless launch of virtual machines on different ISAs and extending spatial/temporal isolation to heterogenous cores with enhanced regulation policies.
Cite as

Daniele Ottaviano, Francesco Ciraolo, Renato Mancuso, and Marcello Cinque. The Omnivisor: A Real-Time Static Partitioning Hypervisor Extension for Heterogeneous Core Virtualization over MPSoCs. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 7:1-7:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ottaviano_et_al:LIPIcs.ECRTS.2024.7,
  author =	{Ottaviano, Daniele and Ciraolo, Francesco and Mancuso, Renato and Cinque, Marcello},
  title =	{{The Omnivisor: A Real-Time Static Partitioning Hypervisor Extension for Heterogeneous Core Virtualization over MPSoCs}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{7:1--7:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-324-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{298},
  editor =	{Pellizzoni, Rodolfo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.7},
  URN =		{urn:nbn:de:0030-drops-203107},
  doi =		{10.4230/LIPIcs.ECRTS.2024.7},
  annote =	{Keywords: Mixed-Criticality, Embedded Virtualization, Real-Time Systems, MPSoCs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.9
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
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.CCC.2023.10
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
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}
}
  • 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 Computer systems organization → Real-time system architecture
  • 1 Theory of computation → Algebraic complexity theory
  • 1 Theory of computation → Error-correcting codes
  • 1 Theory of computation → Expander graphs and randomness extractors
  • Show More...

  • Refine by Keyword
  • 1 Algebraic Algorithms
  • 1 Algebraic computation
  • 1 Bounded degree high dimensional expanders
  • 1 Computational Geometry
  • 1 Embedded Virtualization
  • Show More...

  • Refine by Type
  • 8 document

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

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact