Events

Title: Generalized Modular String Averaged Procedure and Its Applications to Iterative Methods

Abstract: A modular string averaging procedure (MSA, for short) for a finite number of operators  was first introduced by Reich and Zalas in 2016. The MSA concept provides a flexible  algorithmic framework for solving various feasibility problems such as common fixed point and convex feasibility problems.

Title: Breaking the Supersingular Isogeny Diffie-Hellman protocol

Abstract: Finding an explicit isogeny between two given isogenous elliptic curves over a finite field is considered a hard problem, even for quantum computers.

Title: Eigenvalues for stochastic matrices with a prescribed stationary distribution

Abstract: A square nonnegative matrix T is called stochastic if all of its row sums are equal to 1. Under mild conditions, it turns out that there is a positive row vector w^T (called the stationary distribution for T) whose entries sum to 1 such that the powers of T converge to the outer product of w^T with the all-ones vector. Further, the nature of that convergence is governed by the eigenvalues of T.

In this talk we explore how the stationary distribution for a stochastic matrix exerts an influence on the corresponding eigenvalues.

Title: Bounding the extended complexity of the stable set polytope on perfect graphs

Abstract: This week we will study the extension complexity of the stable set polytope for perfect graphs. More than 40 years ago, Grötschel et al. gave an algorithm to find maximal weight stable sets on perfect graphs based on a compact semidefinite extension. However, whether there is a compact linear extension is still an open problem.

Title: Excluded-minor characteristics

Abstract: We review the excluded-minor characterizations for matroids over small fields and discuss the obstacles towards finding such a characterization for GF(5)-representability.

Title: On the complexity of quantum partition functions

Abstract: Quantum complexity theory has been intertwined with the study of quantum many-body systems ever since Kitaev's insight that computing their ground energies is an intractable quantum constraint satisfaction problem that is complete for a quantum generalization of NP.

Title: Quantum walk state transfer on a hypercube

Abstract: We investigate state transfer on a hypercube by means of a quantum walk where the sender and the receiver vertices are marked by weighted loops.

Title: Extended Formulations for the Colonel Blotto Game

Abstract: Suppose you want to replace Doug Ford as premier. To beat him, you need to win as many seats as possible. You have some finite amount of resources to allocate across all seats - if you spend more on a seat than Ford does, you will win that seat. How should you allocate your resources to maximize your expected number of seats?

Title: Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse

Abstract: I will present the online algorithms for unrelated-machine load balancing problem with recourse.  First, we shall present a (2+\epsilon)-competitive algorithm for the problem with O_\epsilon(\log n) amortized recourse per job.

Title: L-systems and the Lovasz number

Abstract: For positive integers n and k, an L-system is a collection of k-uniform subsets of a set of size n whose pairwise intersection sizes all lie in in the set L. The maximum size of an L-system is equal to the independence number of a certain union of graphs in the Johnson scheme. The Lovasz number is a semidefinite programming approximation of the independence number of a graph. In this talk, we survey the relationship between the maximum size of an L-system and the Lovasz number, illustrating examples both where the Lovasz number is a good approximation and where it is a bad approximation.