* Dates within the next 7 days are marked by a star.
Philine Schiewe (Aalto)
An introduction to computational complexity
* Monday 05 May 2025, 14:00, M2 (M233)
When solving optimization problems, we have to consider the resources required for the computation, especially the runtime and the memory requirements. While it is easy to measure the resources needed for a specific implementation, it is often unclear if a more efficient algorithm exists. For example, a shortest path can be computed efficiently (in polynomial time) while finding a longest path is known to be (NP-)hard. In this seminar, we will introduce the basic concepts of computational complexity, to classify (decision) problems according to their (time) complexity. In particular, we will introduce the complexity classes P (polynomial), NP (nondeterministic polynomial) and NPC (NP-complete) and show how polynomial transformations can be used to prove that a specific problem is NP-hard.
SAL Seminar
Sarah Lumpp (Technical University of Munich)
TBA
* Monday 05 May 2025, 17:00, Zoom
Zoom: https://aalto.zoom.us/j/61505481430
Algebraic Statistics and the Study of Multistate Models
Yichao Huang (Beijing Institute of Technology)
Reinforced loop soup revisited
* Tuesday 06 May 2025, 10:15, M3 (M234)
The goal of this talk is to give a glimpse into the connection between some reinforced random processes and the so-called H^{2|2} supersymmetric hyperbolic sigma model. In the first part, we review some basic notions in probability, introduce the vertex reinforced jump process, and review its interpretation as a random walk in random environment. In the second part, we review the connection from the vertex reinforced jump process to the H^{2|2} supersymmetric field, and explain some identities known as BFS-Dynkin isomorphism theorems extended to this context. In particular, we explain the construction of the so-called reinforced loop soup and derive its Dynkin-type isomorphism theorem. Based on joint work with Y. Chang, D.-Z. Liu and X. Zeng.
Aapo Pulkkinen
TBA
Wednesday 07 May 2025, 10:15, M3 (M234)
Seminar on analysis and geometry
Olavi Nevanlinna
Low rank perturbation and Krylov methods
Wednesday 07 May 2025, 14:00, M2 (M233)
We discuss bounds for Krylov methods which are robust in low rank perturbation of the preconditioner.
We first demonstrate using two examples where the spectra are known the different roles of the spectrum and the decay of singular values have in the speed of the iterative processes. Recall that while the spectrum can move dramatically, the singular values do not, and the convergence speed is essentially determine by the decay of singular values.
In the first example a unitary matrix is rank-one perturbation of a nilpotent one and in the second a self-adjoint compact operator is rank-one perturbation of a quasinilpotent one.
Considering the resolvent as a meromorphic function rather than just analytic outside the spectrum it is possible to to show that the behavior seen in those examples is true in general, without assuming anything about how the spectrum moves under the low rank perturbation.
Numerical Analysis seminar
Petteri Kaski
Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
Thursday 15 May 2025, 14:15, M2 (M233)
We show that sufficiently low tensor rank for the balanced tripartitioning tensor $P_d(x,y,z)=\sum_{A,B,C\in\binom{[3d]}{d}:A\cup B\cup C=[3d]}x_Ay_Bz_C$ for a large enough constant $d$ implies uniform arithmetic circuits for the matrix permanent that are exponentially smaller than circuits obtainable from Ryser's formula. We show that the same low-rank assumption implies exponential time improvements over the state of the art for a wide variety of other related counting and decision problems.
As our main methodological contribution, we show that the tensors $P_n$ have a desirable Kronecker scaling property: They can be decomposed efficiently into a small sum of restrictions of Kronecker powers of $P_d$ for constant $d$. We prove this with a new technique relying on Steinitz's lemma, which we hence call Steinitz balancing.
As a consequence of our methods, we show that the mentioned low rank assumption (and hence the improved algorithms) is implied by Strassen's asymptotic rank conjecture [Progr. Math. 120 (1994)], a bold conjecture that has recently seen intriguing progress.
Joint work with Andreas Björklund, Tomohiro Koana, and Jesper Nederlof; cf. https://arxiv.org/abs/2504.05772.
ADM Seminar
Show the events of the past year
Page content by: webmaster-math [at] list [dot] aalto [dot] fi