Réunion d'hiver SMC 2020
Ottawa, 7 - 11 juin 2021
- BENOIT CORSINI, McGill University
Local minimum spanning tree optimization [PDF]
-
Consider the following procedure on the complete weighted graph. Start with an initial spanning subgraph $H_0$ and, at each step, replace a connected subgraph of $H_i$ with its corresponding minimum-weight spanning tree to obtain $H_{i+1}$. By repeating this procedure, the weight of the graphs $H_0,H_1,\ldots$ decreases and, under the assumption that we do not always choose the same subgraphs, it eventually reaches the global minimum-weight spanning tree on the complete graph.
Given an instance of this procedure, say that its weight is the maximal weight of any connected subgraph we replaced at any step. In a sense, the weight of a procedure describes how ``local'' the changes are, where locality is measured with respect to the current graph at each step. We pose the question: what is the smallest achievable weight, optimized over all possible replacement sequences which terminate at the minimum-weight spanning tree?
We show that, for iid $\mathrm{Uniform}([0,1])$ edge weights on the complete graph $K_n$, this optimal weight converges to $1$ as $n\rightarrow\infty$, no matter what the initial graph $H_0$ is. Our proof reduces the general problem to three important special cases: when the initial graph $H_0$ is a complete graph, a star graph, or a Hamiltonian path.
Based on joint work with Louigi Addario-Berry and Jordan Barrett.
- SINA MOHAMMAD-TAHERI, Concordia University
LASSO-inspired variants of weighted orthogonal matching pursuit with applications to sparse high-dimensional approximation [PDF]
-
Motivated by recent developments in sparse high-dimensional approximation from Monte-Carlo sampling, we propose a new weighted variant of the Orthogonal Matching Pursuit (OMP) algorithm. The associated greedy selection criterion is inspired by the square-root LASSO, and further extends the previous work based on the LASSO. We show the efficacy of the proposed algorithm in the context of high-dimensional polynomial approximation and numerically assess its robustness by analyzing the sensitivity of its tuning parameter with respect to noise.
- GAVIN OROK
- TIAN WANG, University of Illinois at Chicago
On the Effective Version of Serre's Open Image Theorem [PDF]
- TIAN WANG, University of Illinois at Chicago
-
Let $E/\mathbb{Q}$ be an elliptic curve without complex multiplication. By Serre's open image theorem, the mod $\ell$ Galois representation of $E$ is surjective for each prime number $\ell$ that is sufficiently large. Under GRH, we obtain the best explicit upper bound on the largest non-surjective prime in terms of the conductor of $E$. This makes effective a bound of the same asymptotic quality due to Larson and Vaintrob. We also illustrate the efficiency of the bound using an elliptic curve with large conductor in LMFDB. This is a joint work with Jacob Mayle.