Thesis Defenses Seminar
Friday, December 2, 2022, 11:00am, LSRC D243
William He
Symmetric Formulas for Products of Permutations
Abstract:- We will discuss the computational complexity of multiplying a sequence of permutation matrices. This computational problem exhibits natural symmetries, and the smallest known Boolean formulas for this problem also exhibit these symmetries. In recent work we have proved that with this symmetry constraint, these smallest known formulas are optimal, and in this talk we will give an overview of the proof.
Generated at 2:19pm Tuesday, April 23, 2024 by Mcal. Top
* Reload
* Login