Skip to Main Content

Colloquium Series

xujunliu.jpgPacking edge colorings of subcubic graphs

Thursday, April 4, 2024 from 3:00-3:50 pm in BAC 219

Xujun Liu, Xi'an Jiaotong-Liverpool University, China

Title: Packing edge colorings of subcubic graphs

Abstract: The notion of packing coloring was inspired by a frequency assignment problem: each broadcast station will be assigned a frequency; stations assigned the same frequency are required to be at least a certain distance apart and each frequency requires a different smallest distance; what is the minimum number of frequencies needed for such an assignment?

A matching (induced matching) is a set of edges E such that each pair of edges in E has distance at least two (three). A (1^j,2^k)-packing edge-coloring of a graph G is a partition of its edge set into j matchings and k induced matchings. Gastineau and Togni showed there are subcubic graphs that are not (1,2,2,2,2,2,2)-packing (abbreviated to (1,2^6)-packing) edge-colorable and not (1^2,2^3)-packing edge-colorable. They also asked the question “whether every subcubic graph is (1,2^7)-packing edge-colorable?”. Very recently, Hocquard, Lajou, and Luzar showed that every subcubic graph is (1,2^8)-packing edge-colorable and (1^2,2^5)-packing edge-colorable. They also conjectured that every subcubic graph is (1,2^7)-packing edge-colorable. Furthermore, Gastineau and Togni, as well as Hocquard, Lajou, and Luzar, have conjectured that every subcubic graph is (1^2,2^4)-packing edge-colorable.

We confirm both conjectures. This is based on a joint work with Santana and Short and a joint work with Gexin Yu. 

2023-2024 Colloquium Series

May 9, 2024: Xingting Wang

Speaker/Affiliation: Xingting Wang, Louisiana State University

Title: TBA

Abstract: TBA

 

Date/Time/Location: 
Thursday, May 9, 2024
 from 3:00-3:50 pm in BAC 219

May 2, 2024: Monroe Eskew

Speaker/Affiliation: Monroe Eskew, Kurt Gödel Research Center

Title: TBA

Abstract: TBA

 

Date/Time/Location: 
Thursday, May 2, 2024
 from 3:00-3:50 pm in BAC 219

April 25, 2024: Josh Fitzgerald

Speaker/Affiliation: Josh Fitzgerald, Lagrange Labs

Title: Zero Knowledge Proofs from Pairings on Elliptic Curves

Abstract: TBA

 

Date/Time/Location: 
Thursday, April 25, 2024
 from 3:00-3:50 pm in BAC 219

 

April 4, 2024: Xujun Liu

Speaker/Affiliation: Xujun Liu, Xi'an Jiaotong-Liverpool University, China

Title: Packing edge colorings of subcubic graphs

Abstract: The notion of packing coloring was inspired by a frequency assignment problem: each broadcast station will be assigned a frequency; stations assigned the same frequency are required to be at least a certain distance apart and each frequency requires a different smallest distance; what is the minimum number of frequencies needed for such an assignment?

A matching (induced matching) is a set of edges E such that each pair of edges in E has distance at least two (three). A (1^j,2^k)-packing edge-coloring of a graph G is a partition of its edge set into j matchings and k induced matchings. Gastineau and Togni showed there are subcubic graphs that are not (1,2,2,2,2,2,2)-packing (abbreviated to (1,2^6)-packing) edge-colorable and not (1^2,2^3)-packing edge-colorable. They also asked the question “whether every subcubic graph is (1,2^7)-packing edge-colorable?”. Very recently, Hocquard, Lajou, and Luzar showed that every subcubic graph is (1,2^8)-packing edge-colorable and (1^2,2^5)-packing edge-colorable. They also conjectured that every subcubic graph is (1,2^7)-packing edge-colorable. Furthermore, Gastineau and Togni, as well as Hocquard, Lajou, and Luzar, have conjectured that every subcubic graph is (1^2,2^4)-packing edge-colorable.

We confirm both conjectures. This is based on a joint work with Santana and Short and a joint work with Gexin Yu. 

 

Date/Time/Location: 
Thursday, April 4, 2024
 from 3:00-3:50 pm in BAC 219

 

Mar 14, 2024: Matt Menickelly

Speaker/Affiliation: 
Matt Menickelly, Argonne National Laboratory

Title: Stochastic Noisy Black-Box Optimization for Near-Term Quantum Computing

Abstract:

While the paradigm of quantum computing has attracted much scientific and popular attention, we must contend with the fact that the current state-of-the-art in quantum hardware is noisy to the point of limited use. A modern and predominant solution for developing and testing quantum algorithms and hardware in the near-term lies in variational quantum algorithms (VQAs). These algorithms effectively separate the inherently quantum aspects of an algorithm from tasks that can be performed efficiently on a classical computer. Almost all VQAs entail casting a problem as one of ground state energy minimization for a problem-defined Hamiltonian. From this perspective, a classical optimization algorithm can be implemented on a classical computer, treating measurements of the quantum system described by the problem Hamiltonian as a computational black box.

In this talk, I will provide an introduction to VQAs, assuming no prior knowledge about quantum computing. I intend to assume only a healthy familiarity with linear algebra and multivariable calculus (of course, having taken MTH 432/532/632 is a bonus). I will describe my past and ongoing work in the analysis and development of stochastic (actually, noisy) black-box optimization methods which serve as appropriate classical optimizers in most VQAs. I will also start the talk by describing what the national laboratories are and share my perspective on the various roles that applied mathematicians play within them.

Date/Time/Location: 
Thursday, March 14, 2024
 from 3:00-3:50 pm in BAC 219

 

Nov 16, 2023: Bryan Van Scoy

Speaker/Affiliation: 
Bryan Van Scoy, Miami University, Department of Electrical and Computer Engineering

Title: Systematic analysis of iterative black-box optimization algorithms using control theory

Abstract: Iterative algorithms are used to solve optimization problems throughout control, robotics, statistics and estimation, signal processing, communication, networks, machine learning, and data science. Recent work from both optimization and control communities has developed a systematic methodology to analyze the worst-case performance of a black-box algorithm over a class of problems. In this talk, we first describe this systematic methodology from a controls perspective and then show how it can be used to analyze and design algorithms in various contexts, such as trading off convergence rate and robustness to gradient noise with noisy first-order oracles, consensus optimization for a multi-agent system, and primal-dual algorithms.

Date/Time/Location: 
Thursday, November 16, 2023
 from 3:00-3:50 pm in BAC 219

 

Nov 9, 2023: Bob Krueger

Speaker/Affiliation: 
Bob Krueger, University of Illinois, Urbana-Champaign

Title: Sparse random analogues of classical combinatorial theorems

Abstract: A successful trend in modern extremal/probabilistic combinatorics is the investigation of how well classical theorems, like those of Ramsey, Turán, and Szemerédi, hold in sparse random contexts. Graph and hypergraph container methods have played a big role in improving our knowledge of these sparse structures. I will present an overview of this area, including some joint work with Jozsef Balogh and Haoran Luo on a random version of the Erdős-Ko-Rado Theorem and Sperner's Theorem. If time permits, I will also talk about some recent work on the typical behavior of graph homomorphisms from expanders, including Lipschitz functions on expanders.

Date/Time/Location: 
Thursday, November 9, 2023
 from 3:00-3:50 pm in BAC 219

Sep 28, 2023: Todd Kapitula

Speaker/Affiliation: 
Todd Kapitula, Calvin University

Title: Viewing spectral problems through the lens of the Krein matrix

Abstract: Determining the stability of nonlinear waves usually requires that the spectrum for the appropriate linearized operator be known. In the case of Hamiltonian systems, the spectrum has a great deal of structure. This structure can be exploited to determine things like the number of (potentially) unstable eigenvalues, or when a destabilizing Hamiltonian-Hopf bifurcation can occur. In my talk I will discuss some of the mathematical tools which allow us to address these questions. Applications will also be given.

Date/Time/Location: 
Thursday, September 28, 2023
 from 3:00-3:50 pm in BAC 219

 

Sep 14, 2023: Khodakhast Bibak

Speaker/Affiliation: 
Khodakhast Bibak, Miami University, Department of Computer Science and Software Engineering

Title: Authentication of variable length messages in quantum key distribution using number-theoretic and combinatorial techniques

Abstract: Authentication plays a critical role in the security of quantum key distribution (QKD) protocols. We propose using Polynomial Hash and its variants for authentication of variable length messages in QKD protocols. Since universal hashing is used not only for authentication in QKD but also in other steps in QKD like error correction and privacy amplification, and also in several other areas of quantum cryptography, Polynomial Hash and its variants as the most efficient universal hash function families can be used in these important steps and areas, as well. We introduce and analyze several efficient variants of Polynomial Hash and, using deep results from number theory, prove that each variant gives an $\varepsilon$-almost-\(\Delta\)-universal family of hash functions. We also give a general method for transforming any such family to an $\varepsilon$-almost-strongly universal family of hash functions. The latter families can then, among other applications, be used in the Wegman--Carter MAC construction which has been shown to provide a universally composable authentication method in QKD protocols. As Polynomial Hash has found many applications, our constructions and results are potentially of interest in various areas.

Date/Time/Location: 
Thursday, September 14, 2023
 from 3:00-3:50 pm in BAC 219