* Seuraavan viikon tapahtumat merkitty tähdellä
Rolf Stenberg
Variational principles. Pitfalls by integration by parts.
* Wednesday 23 April 2025, 14:00, M2 (M233)
Anna-Mariya Otsetova (Midterm review)
Quantitative asymptotics for stochastic evolution equations
* Friday 25 April 2025, 11:15, M3 (M234)
Eero Virmavirta
Optimizing application placement in private cloud environment under capacity constraints (MSc thesis presentation)
Monday 28 April 2025, 15:00, M2 (M233)
SAL Seminar
Aapo Pulkkinen
TBA
Wednesday 07 May 2025, 10:15, M3 (M234)
Seminar on analysis and geometry
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
Sivusta vastaa: webmaster-math [at] list [dot] aalto [dot] fi