| Alex Kodess, Farmingdale State College | Alex Kodess, Farmingdale State College | EWG 336 | Title: Algebraically Defined Directed Graphs<br><br>
Abstract:To view the abstract <a href="https://www.mathsci.udel.edu/content-sub-site/Documents/kodess_talk_nov_18_2019_abstract.pdf">click here</a> | 11/18/2019 7:30:00 PM | 11/18/2019 8:30:00 PM | False | |
| Daniel Katz, California State University at Northridge | Daniel Katz, California State University at Northridge | EWG 336 | Title: Rudin-Shapiro-Like Polynomials with Low Correlation<br><br>
Description: The Rudin-Shapiro polynomials are a sequence of polynomials with coefficients in {+1,-1} arising from an elegant recursive construction that gives them interesting analytic and combinatorial properties. They are known to be very flat on the complex unit circle: if f is a Rudin-Shapiro polynomial and we let z range over the unit circle, then the ratio of the maximum value of |f(z)| to the root mean square value is never larger than the square root of 2. When we identify a polynomial with the sequence of its coefficients, we find that a typical Rudin-Shapiro polynomial has very low autocorrelation: the inner products of the sequence of coefficients with nontrivial translates of itself have considerably smaller mean square magnitude than what one would obtain with a typical random sequence with entries from {+1,-1}.
The fact that the inner product is only large when the sequences are perfectly aligned makes such sequences very useful for synchronization in communications networks. For multi-user networks, we want to avoid confusing one user's sequence with another's, so we demand pairs of sequences that also have low cross-correlation (inner product with each
other) at all shifts. We investigate pairs of Rudin-Shapiro-Like polynomials, a generalization of Shapiro's original recursive construction, and derive a general formula for their mean square cross-correlation. Borwein and Mossinghoff had shown that there are Rudin-Shapiro-like polynomials with low autocorrelation, and now we have found pairs of polynomials such that both have low autocorrelation and the pair has low mutual cross-correlation. There are bounds on how small these quantities can be, and we have found infinite families that achieve the bounds. This is joint work with Sangman Lee, Eli Moore, and Stanislav A. Trunov. | 11/11/2019 7:30:00 PM | 11/11/2019 8:30:00 PM | False | |
| Krystal Guo from Universite de Montreal, Canada | Krystal Guo from Universite de Montreal, Canada | EWG 336 |
Title: Distinguishing graphs with Weisfeiler-Lehman refinement and
cellular algebras
</br></br>
Abstract:
Cellular algebras were first studied by Weisfeiler and Lehman; in the
course of analyzing their algorithm for Graph Isomorphism, they define
matrix algebras which are graph invariants. Evdokimov and Ponomarenko
show that the kth dimensional Weisfeiler-Lehman algorithm fails to
distinguish two graph if the result matrix algebras are weakly
isomorphic. In this talk, we will explore the Weisfeiler-Lehman
algorithm, which still plays a large part in recent Graph Isomorphim
algorithms. We will define the matrix algebras associated with
WL-dimension and discuss the algebraic explanation of how graphs can
fail to be distinguished by the algorithm. | 10/29/2019 3:30:00 PM | 10/29/2019 4:30:00 PM | False | |
| Krystal Guo, Universite de Montreal, Canada | Krystal Guo, Universite de Montreal, Canada | EWG 336 | Title: Algebraic graph theory and quantum walks<br><br>
Description: A system of interacting quantum qubits can be modelled by a
graph. The evolution of the quantum system can be completely encoded
as a quantum walk in a graph, which can be seen, in some sense, as a
quantum analogue of random walk. This gives rise to a rich connection
between algebraic graph theory, linear algebra and quantum computing.
In this talk, I will present recent results on the average mixing
matrix of a graph; a quantum walk has a transition matrix which is a
unitary matrix with complex values and thus will not converge, but we
may speak of an average distribution over time, which is modelled by
the average mixing matrix. This rank of matrix is somewhat
surprisingly related to strongly cospectral vertices in a graph; two
vertices are strongly cospectral if and only if the corresponding rows
of the average mixing matrix are equal. This talk will not assume any
prior knowledge of quantum computing or physics.
| 10/28/2019 5:30:00 PM | 10/28/2019 6:30:00 PM | False | |
This Page Last Modified On:
<a target='_blank' href='/Lists/CalendarDiscreteMathematics/calendar.aspx' class='ms-promotedActionButton'> <span style='font-size:16px;margin-right:5px;position:relative;top:2px;' class='fa fa-pencil-square-o'></span><span class='ms-promotedActionButton-text'>EDIT CALENDAR</span> </a>
WebPartEditorsOnly