Algebra, Number Theory, and Applications Research Group

Aalto Math
Members Research profile and projects ANTA seminar ANTA courses News and links


Oliver W. Gnilke

Oliver W. Gnilke
Marcus Greferath

Marcus Greferath
Camilla Hollanti

Camilla Hollanti
Petter Kaski

Petteri Kaski

Subscribe to the seminar e-mail list here!

Past Talks

11.10. 15:15  Robin Rajamäki: Additive 2D bases – M2 (M233)

Additive bases, i.e. sets of integers whose pairwise sums cover a desired set of integers, have been studied by number theorists since the early 20th century. In particular, the combinatorial problem of minimizing the number of elements required to cover a given set of consecutive integers is often of interest. Such optimal bases find applications in e.g. sparse linear sensor arrays, where the number of sensors is desired to be kept low in order to reduce costs and mitigate non-ideal coupling effects between array elements. Although much of the existing work on additive bases is directly applicable to 1D sparse array design, often 2D arrays are required in practice. However, additive 2D bases have not been studied as extensively as their 1D counterpart in the past. In our talk, we present some recent results on rectangular additive bases, i.e. additive bases whose sumsets cover a rectangular area of consecutive points in the plane. For example, optimal rectangular bases found through exhaustive computer search are shown. Furthermore, different rectangular bases with analytically tractable structure and a low element count are introduced.

5.10. 15:15  Niko Väisänen (Nokia/Aalto): Beamforming -- Enabling Higher Data Rate Wireless Communications – M205

MSc thesis presentation

4.10. 15:15  Negin Karimi: LCD codes – M3 (M234)

Error-correcting codes play an important role in digital communication among all types of codes. Linear codes are studied the most. Because of their algebraic structure, they are easier to describe, encode, and decode than nonlinear codes. A special class of linear codes is linear complementary dual code (LCD code). LCD codes are defined by Massy in 1992. He was shown that asymptotically good codes exist. LCD codes have been widely applied in data storage, communications systems, and cryptography. Also, they are interesting objects in the general framework of algebraic coding. In this talk will be presented some of the properties cyclic codes, quasi-cyclic codes and quasi-twisted codes with complementary dual.

25.8. 15:15  Ville Kujala: Achieving the capacity of coded PIR using arbitrary linear code (BSc presentation) – M3 (M234)

24.8. 14:15  Juuso Korvuo: Hilojen lähimmän vektorin ongelma (kandiesitelmä) – M3 (M234)

24.8. 9:15  Aki Malinen: Algebraic methods in maximum likelihood estimation (BSc presentation) – M3 (M234)

14.8. 14:30  Kaisa Nyberg / Chris Brzuska: Connections between linear and statistical independence of binary random variables / Survey about indistinguishability obfuscation – M2 (M233)

Informal presentations during the visit of our new Cryptology professor Chris Brzuska

2.8. 11:15  Leevi Korkeala: Hyperbolisten ryhmien pinta-aliryhmät (kandiesitelmä) – M3 (M234)

2.8. 10:15  Miio Taarna : Julkisen liikenteen verkostojen tarkastelu verkkoteorian keinoin (kandiesitelmä) – M3 (M234)

20.7. 11:15  Valtteri Lipiäinen: Verkkojen Ollivier-Ricci -kaarevuus (kandiesitelmä) – M3 (M234)

20.7. 10:15  Miika Leinonen: Kvaternioalgebrat ja hyvin pyöristyvät hilat (kandiesitelmä) – M3 (M234)

21.6. 15:00  Prof. Oktay Olmez, Ankara University: Binary three-weight linear codes from partial geometric difference sets – M3 (M234)

Links between linear codes, non-linear functions from cryptography, graphs and combinatorial designs have attracted the attention of many researchers over the last 50 years. Difference set method is a powerful tool to construct designs and explore the links between designs and many other combinatorial objects including codes and nonlinear cryptographic functions. In this talk, we will introduce a generalisation of $(v,k,\lambda)-$difference sets known as partial geometric difference sets. In particular, we will show that existence of a family of partial geometric difference sets is equivalent to existence of a certain family of three-weight linear codes. We also provide a link between binary plateaued functions, three-weight linear codes and partial geometric difference sets.

11.5. 14:00  Amaro Barreal: Doctoral thesis defense: Lattice codes for physical layer communications – M1 (M232)

Opponent Prof. Bharath Sethuraman, custos Camilla Hollanti.

10.5. 16:15  Thomas Westerbäck: Combinatorial coding theory via polymatroids – M3 (M234)

Matroid theory can be used to analyze many interesting properties of linear codes over finite fields. Recent research has proven matroid theory to be a valuable tool in several areas in coding theory, e.g. in distributed storage, index coding and network coding. Polymatroids, a generalization of matroids, can be associated with any finite code. In this talk I will present how polymatroids and codes are closely related via entropy and how polymatroid theory can be used in order to analyze many interesting properties of codes. New coding theoretical results will be given in the setting of polymatroids. These results can therefore also be applied to non-code objects that are associated with polymatroids.

9.5. 15:15  Prof. Bharath Sethuraman (California State University, Northridge): Matrices from Division Algebras and Fast Decodability (NOTE: ON TUESDAY!) – M2 (M233)

We call two matrices A and B in M_n(C) mutually orthogonal if AB* + BA*=0, where A* indicates the conjugate transpose of A. The situation where such matrices arise from the embedding of a division algebra over a number field into M_n(C) is particularly interesting in wireless communications, where the presence of such matrices leads to fast decodability. We describe fundamental limits on the number of families of matrices that are mutually orthogonal across the families, and limits on the number of matrices in each family. The limits are obtained by a mix of techniques from both linear algebra and the theory of Brauer groups of commutative rings.

26.4. 15:15  Dr. David Cushing (Durham): Bakry-Emery curvature functions of graphs – M3 (M234)

Ricci curvature has proven to be a vital notion in many areas of mathematics. There have been various attempts at generalising this notion to graphs. We look at one such notion due to Bakry and Emery. We introduce the Bakry-Emery curvature function and obtain results on Cartesian products of graphs and also on a certain regularity property. I will also demonstrate interactive software that computes curvature.

22.3. 15:15  Matthias Grezet: Rank distribution and generalized weights of Delsarte codes – M3 (M234)

Delsarte codes and, in particular, all rank-metric codes play an important role in network coding to correct errors and secure an adversarial channel. The purpose of this talk is to study the properties inherent to Delsarte codes via algebraic and combinatoric methods. We will first present an analogue of the Singleton bound theorem for this context. Then, we will talk about the rank distribution of a specific code. Finally, we will introduce a new invariant, called the set of generalized weights, and see how it can characterize different type of codes

15.3. 14:15  Taoufiq Damir: The bounded gaps between primes (NOTE unusual time!) – M3 (M234)

The aim of the talk is to present a survey on the main ideas developed by Selberg, Goldston, Pintz, Yildirim, Maynard and Tao in order to prove the bounded gap between primes, namely the existence of infinitely many primes p such that p+M is prime, where M is some positive even integer. The talk will be in two parts. The first part will be mostly dedicated to an introduction to elementary Analytic number theory and Sieve theory, then in the second part we will sketch the proofs of the main results leading to the bounded gaps.

8.3. 15:15  Anna-Lena Horlemann-Trautmann: Symbol Erasures in Random Network Coding – M3 (M234)

In random network coding we want to communicate over a noisy network channel with one sender and several receivers, where all receivers want to get the same information from the sender. We encode the data before sending it through the network, so the receivers can reconstruct the original data from the corrupted data. From a mathematical point of view, classical tools used in this context are projective spaces over finite fields. In this talk we will give an introduction to random network coding and explain how the classical model by Kötter and Kschischang treats erasures during the communication. Then we give an alternative model and show that, depending on the network topology, the classical or the alternative model can be advantageous for erasure correction.

1.3. 17:15  Prof. Petteri Kaski: Arithmetic circuits for multilinear tasks (45min, NOTE unusual time!) – M3 (M234)

This talk will give a brief introduction to the design of arithmetic circuits for solving computational tasks, with a focus on multilinear tasks and designs, such as fast matrix multiplication and fast polynomial multiplication in the bilinear case, and higher-order designs such as determinants, permanents, and our recent design (with Andreas Björklund) for the \binom{6}{2}-linear form, which e.g. captures the task of counting the 6-cliques in a given graph.

22.2. 15:15  Ivo Kubjas: Two-Party Function Computation – M3 (M234)

Assume a distributed system with two users, each user possesses a collection of binary strings. We introduce a new problem termed function computation on the reconciled data, where the users seek to compute a function on the union of their collections. Trivially, the users could just exchange their collections and then compute the value of the function. We see that any deterministic protocol can not perform much better in terms of bits communicated between the users. Namely, we show that any protocol that computes a sum and a product of reconciled sets of non-negative integers has to communicate at least 2^n + n - 1 and 2^n + n - 3 bits in the worst-case scenario, respectively. We also consider other approaches for estimating the communication complexity of the protocols. We establish connections to other problems in computer science, such as set disjointness and finding the intersection, yielding a variety of additional bounds. We present a randomized protocol, which is based on use of a family of hash functions and analyze its characteristics.

16.2. 10:15  Prof. Sihem Mesnager (University of Paris 8): Linear codes from bent functions over finite fields – M2 (M233)

Error correcting codes are widely studied by researchers and employed by engineers. They have long been known to have applications in computer and communication systems, data storage devices (starting from the use of Reed Solomon codes in CDs) and consumer electronics. A lot of progress has been made on the constructions of linear codes with few weights. Such codes have applications in secret sharing authentication codes, association schemes and strongly regular graphs. Certain special types of functions over finite fields are closely related to linear or nonlinear codes. In the past decade, a lot of progress on interplays between special functions and codes has been made. In particular, APN functions, planar functions, Dickson polynomials, and q-polynomials were employed to construct linear codes with optimal or almost optimal parameters. Recently, several new approaches to constructing linear codes with special types of functions were proposed, and a lot of linear codes with excellent parameters were obtained. Bent functions are maximally nonlinear Boolean functions. They were introduced by Rothaus in the 1960's and initially studied by Dillon as early as 1974 in his Thesis. The notion of bent function has been extended in arbitrary characteristic. For their own sake as interesting combinatorial objects, but also for their relations to coding theory (e.g. Reed-Muller codes, Kerdock codes, etc.), combinatorics (e.g. difference sets), design theory, sequence theory, and applications in cryptography (design of stream ciphers and of S-boxes for block ciphers), bent functions have attracted a lot of research for the past four decades. It is well-known that Kerdock codes are constructed from bent functions. Very recently, some authors have highlighted that bent functions lead to the construction of interesting linear codes (in particular, linear codes with few weights). This talk is devoted to linear codes from bent functions in characteristic $p$. We shall present the state of the art as well as our recent contributions in this topic. We will present two generic constructions of linear codes involving special functions and investigate constructions of good linear codes based on the generic constructions involving bent functions over finite fields. More specifically, we shall give more details on our recent results on linear codes with few weights from weakly regular bent functions based on a generic construction.

15.2. 15:15  Piermarco Milione: Quaternion Algebras, Arithmetic, and Applications. – M2 (M233)

Quaternion algebras are a wide generalization of the famous Hamilton's quaternions, and they include matrix algebras as special cases. They are the first examples of non-commutative algebras, and it is precisely the lack of commutativity which makes them appealing for many applications, not only in mathematics. In this talk we give an introduction to the arithmetic theory of quaternion algebras, stressing analogies and differences with the arithmetic of number fields. We take as archetype the order of Hurwitz's quaternions, which is the analog of the ring of Gaussian integers, in this non-commutative context. Finally, we also give a brief overview of some results, joint with L. Amorós, which are obtained in the study of the arithmetic in certain quaternion algebras and the corresponding bad reductions of certain families of Shimura curves.

4.1. 15:15  David Karpuk: Lattices for Reliable and Secure Wireless Communication – Y228a

Wireless communications is ubiquitous in modern life, and the mathematics of communications engineering is fundamental to everything from large cellular networks to small Wi-Fi networks. In wireless communications, data is often represented as a finite subset of R^n called a constellation, and choosing a constellation cleverly can increase reliability of transmission or protect against malicious eavesdroppers. Constellations carved from lattices, that is, discrete subsets of R^n, are especially useful as the underlying algebraic structure of lattices allows for analysis of certain error probabilities. In this talk we will begin with a survey of practical lattice constructions, discuss our recent work concerning lattices from number-theoretic constructions and Hadamard matrices, and discuss future work regarding applications of so-called well-rounded lattices.

16.11. 15:15  Alessandro Neri (University of Zurich): On the Genericity of Maximum Rank Distance and Gabidulin Codes – Y229a

Codes in the rank-metric have been studied for the last four decades. For linear codes a Singleton-type bound can be derived for these codes. In analogy to MDS codes in the Hamming metric, we call rank-metric codes that achieve the Singleton-type bound MRD (maximum rank distance) codes. Since the works of Delsarte and Gabidulin we know that linear MRD codes exist for any set of parameters. The codes they describe are called Gabidulin codes. The question, if there are other general constructions of MRD codes that are not equivalent to Gabidulin codes, has been of large interest recently. Some constructions of non-Gabidulin MRD codes are known, but many of the derived codes are not linear over the underlying field but only linear over some subfield of it. In general, it remains an open question for which parameters non-Gabidulin MRD codes exist, and if so, how many such codes there are. We show that the properties of being MRD and non-Gabidulin are generic. This implies that over a large field extension degree a randomly chosen generator matrix generates an MRD and a non-Gabidulin code with high probability. Moreover, we give an upper bound on the respective probabilities in dependence on the extension degree. Joint work with Anna-Lena Horlemann-Trautmann, Tovohery Randrianarisoa and Joachim Rosenthal.

9.11. 15:15  Dr. Marzieh Arabi Kakavand (Isfahan University of Technology): Simple-extending modules and semisimple-extending modules – Y229a

Let M be an R-module and N be any submodule of M. A submodule C of M is called a complement of N if C is maximal in the collection of submodules Q of M such that Q\cap N=0. A submodule C of M is called complement (in M) if there is a submodule N such that C is complement of N in M. A module M is called extending (or CS) module if every complement submodule of M is a direct summand of M. These modules were introduced by Harada and Muller in 1980 and later were studied quite extensively by many authors. A module M is called simple-extending (semisimple-extending) if every complement of any simple (semisimple) submodule of M is a direct summand. The aim of the talk is to present some recent results concerning simple-extending and semisimple-extending modules. Namely, we will describe rings R such that every R-module M is simple-extending (semisimple-extending).

4.11. 10:00  SITE VISIT TALKS: Kazim Buyukboduk (Koc University, Istanbul): Reciprocity Laws and p-adic analytic construction of rational points (NOTE: starts 10 sharp!) – M2 (M233)

Our goal in this talk is to present a basic overview of reciprocity laws, starting off with that is due to Gauss and reaching all the way up to those predicted as part of Langlands' Program and Wiles' celebrated Modularity Theorem in this vein. The latter result is one of the key inputs in our recent p-adic analytic construction of a rational point of infinite order on an elliptic curve of rank one that has good supersingular reduction at p.

2.11. 15:15  Oliver Gnilke : Semigroup action problems in cryptography – M2 (M233)

With quantum algorithms available to solve the classical discrete logarithm problem a need for different one-way functions arises. We study several alternatives to the DLP based on different semigroups and evaluate their security. A general framework for reducing semigroup action problems to smaller instances, in line with the Pohlig-Hellman attack on classical DLPs, is given.

26.10. 15:15  Petteri Kaski (Aalto University, Department of Computer Science): How proofs are prepared at Camelot – M2 (M233)

We study a design framework for robust, independently verifiable, and workload-balanced distributed algorithms working on a common input. An algorithm based on the framework is essentially a distributed encoding procedure for a Reed--Solomon code (each compute node is tasked to produce one or more symbols of the codeword), which enables (a) robustness against byzantine adversarial failures with intrinsic error-correction and identification of failed nodes, and (b) independent randomized verification to check the entire computation for correctness, which takes essentially no more resources than each node individually contributes to execute the computation. The framework also enables smooth tradeoffs between per-node compute time and the number of nodes used for computation. The framework builds on recent Merlin—Arthur proofs of batch evaluation of Williams [Proc. 31st IEEE Conference on Computational Complexity (CCC'16, May 29--June 1, 2016, Tokyo), 2:1–17] with the basic observation that Merlin's magic is not needed for batch evaluation---mere Knights can prepare the independently verifiable proof, in parallel, and with intrinsic error-correction. [This is joint work with Andreas Björklund (Lund University).] Link:

19.10. 15:15  Matti Karppa (Aalto University, Department of Computer Science): Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time – M2 (M233)

We derandomize G. Valiant's [J. ACM 62 (2015) Art. 13] subquadratic-time algorithm for finding outlier correlations in binary data. Our derandomized algorithm gives deterministic subquadratic scaling essentially for the same parameter range as Valiant's randomized algorithm, but the precise constants we save over quadratic scaling are more modest. Our main technical tool for derandomization is an explicit family of correlation amplifiers built via a family of zigzag-product expanders in Reingold, Vadhan, and Wigderson [Ann. of Math. 155 (2002) 157--187].

5.10. 15:15  Ferdinand Blomqvist: The closest vector problem and quotients – M2 (M233)

Let L be a lattice, i.e., a discrete subgroup of R^n, and K a sublattice of L. We show that, if we can solve the closest vector problem (CVP) for both K and L/K, then we can solve it for L. Furthermore, we show that solving the CVP for L/K is not harder than solving it for L. In addition, we show how to use this result to construct efficient algorithms for certain instances of the CVP. Finally, we note that these results are not limited to lattices, but also hold in a more general setting.

28.9. 15:15  David Karpuk (Aalto University): An Algebraic Approach to Private Information Retrieval – M2 (M233)

21.9. 15:15  Eimear Byrne (University College Dublin): Optimal Transmission Rates in Broadcast with Side Information and the Rank-Metric Covering Radius – M2 (M233)

In the first part of this talk, we introduce the broadcast with side-information is a problem, which arises is a number of network coding contexts, including index coding and coded-caching. Such problems involve efficient delivery of big data files to many users, each of whom already has some data stored locally in its cache via some form of placement, either randomly or by design. In the case of linear coding, the structure of the cached data or side information can be expressed as a rank-metric code. The fundamental limits of transmission in these problems then relate to covering properties of certain classes of matrix codes. We will make this connection explicit and give some bounds using rank-metric covering methods. In the second part of this talk, we will briefly discuss the rank-metric covering problem and describe some bounds on the covering radius of an arbitrary rank-metric code. We will apply these results to maximum rank distance (MRD) codes. We will discuss open problems related to these topics. This talk is based on joint works with M. Calderini (Univ. Trento) and A. Ravagnani (Univ. Neuchatel).

14.9. 15:15  Ragnar Freij-Hollanti: Hierarchical storage systems and connections to matroid theory – M2 (M233)

8.9. 14:00  Maria Montoya (Aalto University): Visible-light and camera-display communications – M2 (M233)

Most of the wireless communications technologies we are currently using employ radio waves. However, they cover only a portion of the available electromagnetic spectrum. Visible-light communications have recently gained momentum due to the availability of suitable hardware and processing capabilities on off-the-shelf devices such as smartphones. This talk will first introduce visible-light communications and present some application scenarios. It will then focus on camera-display communications involving smartphones. Finally, the talk will conclude with some open research questions at the intersection of networking, computer vision, and information theory.

7.9. 15:15  Jukka Kohonen (Aalto University, Department of Computer Science): An improved lower bound for finite additive 2-bases – M2 (M233)

A set of non-negative integers A is an additive 2-basis with range n, if its sumset A + A contains 0,1,...,n but not n + 1. Explicit bases are known with arbitrarily large size |A| = k and n/k^2 ≥ 2/7 > 0.2857. We present a more general construction and improve the lower bound to 85/294 > 0.2891. This is apparently the first advance in this lower bound since 1979. These results are available on the arXiv at

1.9. 11:00  Atte Mäkelä : Kandiesitelmä: Yksityisestä tiedonhausta ja avainsanahausta – M3 (M234)

31.8. 16:15  Prof. Emina Soljanin (Rutgers University): Cloud storage space vs. download time for large files (IEEE COM/IT Finland Chapter Talk) – M2 (M233)

Users of cloud systems demand that their data be reliably stored and quickly accessible. Cloud providers today strive to meet these demands through over-provisioning: keeping processors ready to go at all times and replicating data over multiple servers. Special erasure codes have been designed and adopted in practice as a more storage-efficient way to provide reliability. We will show how coding reduces download time of large files, in addition to providing reliability against disk failures. For the same total storage used, coding exploits the diversity and parallelism in the system better than today's replication schemes, and hence gives faster download. We will introduce a fork-join queuing framework to model multiple users requesting their data simultaneously, and demonstrate the trade-off between the download time and the amount of storage space. At the end, we will mention several problems that arise in distributed systems when the stored data is large, changing, and expanding.

31.8. 15:15  Prof. Emina Soljanin (Rutgers University): Network coding: A theoretical minimum and an open problem (IEEE COM/IT Finland Chapter Talk) – M2 (M233)

Consider a directed acyclic graph (network) where h source-nodes produce elements of some finite field (source symbols). Edges carry linear combinations of their parent node inputs. In turn, this implies that edges throughout the network carry linear combinations of the source symbols. The network coding multicast problem asks: How should nodes in such a network with N receivers combine their inputs to ensure that each h edges observed by a receiver carry independent combinations of the source symbols? Moreover, what is the minimum field size necessary to realize combinations with this property? The field size problem is completely solved in the case of two sources and arbitrarily many receivers, but in no other cases. This talk will show how graph theory and algebraic geometry have been instrumental in proving the two-source case and gaining some further insights.

30.8. 11:00  Juha-Pekka Puska: Kandiesitelmä: Yksityiset menetelmät geneettisessä testauksessa – M3 (M234)

30.8. 10:00  Raine Nieminen: Bsc thesis presentation: Supersingular Elliptic Curve Isogeny Cryptography – M3 (M234)

22.6. 16:15  Prof. N. Asokan: Securing cloud-assisted services – M3 (M234)

All kinds of previously local services are being moved to a cloud setting. While this is justified by the scalability and efficiency benefits of cloud-based services, it also raises new security and privacy challenges. Solving them by naive application of standard security/privacy techniques can conflict with other functional requirements. In this talk, I will outline some cloud-assisted services and the apparent conflicts that arise while trying to secure these services. I will also discuss potential solutions to resolve such conflicts.

21.6. 12:15  Ferdinand Blomqvist: 2-server PIR with subpolynomial complexity – M3 (M234)

Private information retrieval (PIR) allows a user to download items from a database without disclosing the identity of the items. In this talk I will discuss the techniques used in the relatively recent paper '2-server PIR with sub-polynomial complexity' by Dvir and Gopi (

9.6. 15:15  Rawad Bitar: Secure Multi-Party Computation and Secret Sharing (Note the unusual day!) – U3 (U141)

In secure multi-party computation (MPC), a set of parties, each holding a private input, wish to compute a function of their inputs while keeping them private. For example, the employees of a certain company wish to compute the sum of their salaries without revealing any employee’s salary. In the setting of secure MPC, there is no trusted party that can take all inputs and compute the desired function. However, all parties can be involved in the computation process. A secret sharing scheme is a random encoding of a secret into a set of shares. Each share is given to a party, such that a given number of parties can reconstruct the secret while none of the parties can obtain any information about the secret. In this talk, I will do a brief survey on secure MPC and and its connection to secret sharing and their applications. I will give examples of problems asked in the MPC literature and conclude with open problems.

2.6. 15:15  Guillermo Carlo Nunez Ponasso: PIR with Low Storage Overhead: Coding instead of Replication (INTENSIVE COURSE ON CODING THEORY FOR DISTRIBUTED DATA STORAGE) (further info) – U3 (U141)

2.6. 14:00  Antti Pöllänen: One extra bit of download ensures perfectly private information retrieval (INTENSIVE COURSE ON CODING THEORY FOR DISTRIBUTED DATA STORAGE) (further info) – U3 (U141)

2.6. 13:00  Teemu Pudas: Batch codes and their applications (INTENSIVE COURSE ON CODING THEORY FOR DISTRIBUTED DATA STORAGE) (further info) – U3 (U141)

1.6. 15:15  Prof. Lenny Fukshanski, Claremont McKenna Collage: Well-rounded lattices from algebraic constructions – U3 (U141)

Well-rounded lattices are vital in extremal lattice theory, since the classical optimization problems can usually be reduced to them. On the other hand, many of the important constructions of Euclidean lattices with good properties come from different algebraic settings. This prompts a natural question: which of the lattices coming from algebraic constructions are well-rounded? We consider three such constructions: ideal lattices from number fields, lattices from finite abelian groups, and cyclic lattices from quotient polynomial rings. In each of these cases, we provide a partial answer to the above question, as well as discuss some generalizations, applications, and directions for future research.

1.6. 13:00  Ferdinand Blomqvist: Introduction to private information retrieval (PIR) / Breaking the O(n^{1/(2k−1)}) barrier for information-theoretic PIR (INTENSIVE COURSE ON CODING THEORY FOR DISTRIBUTED DATA STORAGE) (further info) – U3 (U141)

1.6. 11:00  Marc Härkönen: New Constructions of SD and MR Codes over Small Finite Fields (INTENSIVE COURSE ON CODING THEORY FOR DISTRIBUTED DATA STORAGE) (further info) – U3 (U141)

31.5. 12:00  Prof. Salim El Rouayheb, Illinois Institute of Technology Chicago: INTENSIVE COURSE ON CODING THEORY FOR DISTRIBUTED DATA STORAGE (3 cr) (further info) – U3 (U141)

30.5. 12:00  Prof. Salim El Rouayheb, Illinois Institute of Technology Chicago: INTENSIVE COURSE ON CODING THEORY FOR DISTRIBUTED DATA STORAGE (3 cr) (further info) – U3 (U141)

Distributed storage systems are becoming a vital infrastructure of today’s society by allowing to store reliably large amounts of data online in the “cloud” and make it accessible anywhere and anytime. In these systems, failure is the norm rather than the exception. And, to protect against data loss data is stored redundantly using codes. This course focuses on the recent state-of-the-art research topics in coding theory for distributed data storage systems. The topics covered by the course include regenerating codes, locally repairable codes, index codes, information theoretic tradeoffs and information theoretic security and privacy. Moreover, the course will also highlight how these theoretical results are currently being applied in real-world systems, such as Microsoft and Facebook data centers. Tentative schedule: Mon 30.5. 12-13, 14-16 (3x45min) Tue 31.5. 12-13, 14-16 (3x45min), Wed 1.6. 11-12, 13-15 (3x45min), Thu 2.6. 13-16 (3x45min), Friday possibly an hour or two, if we still need more time for student presentations. If you want credits, you need to present a paper that you can choose from a given list. Register (preferably) by 15.5. to Camilla:

18.5. 15:15  Serge Kas Hanna, Illinois Institute of Technology Chicago: The Capacity of Private Information Retrieval – M237

In this talk, I will discuss the recent result on the private information retrieval (PIR) capacity by Jafar et al. In PIR a user wants to retrieve a record from a database without revealing the identity of the desired record to the server storing copies of the database. The information theoretic capacity of PIR is the maximum number of bits of the desired record that can be privately retrieved per bit of downloaded information. This talk is based on the following paper:

12.5. 16:00  Colva Roney-Dougal (University of Saint Andrews, United Kingdom): Proving hyperbolicity in polynomial time (Joint with Algorithms Seminar) – T4 (CS building)

The study of finitely-presented groups has been ongoing since the work of Hamilton in the 1850s - almost as long as group theory itself! This talk will be a gentle introduction to finitely-presented groups, with an emphasis on algorithms. One class of finitely presented groups for which the word problem has a straightforward solution is the hyperbolic groups. Gromov showed that with probability 1, a finitely-presented group is either hyperbolic or has order at most two, so in some sense the hyperbolic groups are generic. It is undecidable in general whether a finitely-presented group is hyperbolic, but I will present some new algorithms that run in polynomial time, and can often prove hyperbolicity.

11.5. 15:15  Razane Tajeddine, Illinois Institute of Technology Chicago: Private Information Retrieval with Keyword Search – M237

The talk will be divided into two main parts. In the first part, I will give a brief introduction to information theoretic and computational Private Information Retrieval (PIR) with emphasis on examples and will summarize the main results in this area. In the second part, I will talk about the application of PIR for privacy while searching online using keywords. When a user wants to search for a file by keywords, the server searches all the files in until finding the required keyword in one of the files or knowing that it does not exist in any of them. For PIR schemes in the first part, it is assumed that the user knows the location or name of the needed file, which is not usually the case. Thus, PIR for searching allows the user to privately search keywords to access the files.

20.4. 15:15  Jokke Häsä (University of Helsinki): Zeta functions of multivariate polynomials and representation growth of Lie groups – M237

Representation growth of a group describes the growth of the number of inequivalent irreducible linear representations of the group in terms of the dimension of the representation space. A result of Michael Larsen and Alexander Lubotzky specifies the polynomial growth rate of simple Lie groups in terms of properties of the root system of the group. The proof is based on examining the multivariate polynomial obtained from the Weyl formula for representation dimensions of a complex Lie group. This leads to a study of zeta functions generated by multivariate polynomials. With Alexander Stasinski, we have found the domain of convergence for the zeta functions for a certain class of multivariate polynomials. As a corollary, we are able to recover Larsen and Lubotzky's result, and also pinpoint the exact property of the simple root systems that makes their proof work.

31.3. 15:15  Prof. René Schoof (University of Rome Tor Vergata): Lagrange's theorem for finite algebraic groups (colloquium talk) – M1 (M232)

Lagrange’s Theorem says that every finite group of cardinality $n$ has the property that the $n$-th power of any of its elements is trivial. It is conjectured that a similar statement holds for “finite algebraic groups”. In this lecture we explain what finite algebraic groups are and describe the conjecture. We illustrate everything with several examples.

30.3. 15:15  Prof. René Schoof (University of Rome Tor Vergata): Serre's uniformity conjecture for elliptic curves – M237

In 1972 J.-P. Serre proved an important theorem concerning the Galois action on the torsion points of elliptic curves over number fields. We describe a conjectural uniform version of this theorem and its relation to rational points on modular curves.

16.3. 15:15  Prof. Simo Särkkä (Aalto University): Connections of Bayesian Filtering and Information Theory – M237

Bayesian filtering (or tracking) methods such as particle filters and Kalman filters are routinely used as optimal multi-channel signal processing algorithms in smartphones, automotive applications, aerospace systems, as well as in various positioning systems, among other fields. Information theory is concerned with the optimality and limits of coding systems, noisy channels, and data compression. It is intuitively clear that these disciplines have a lot in common although the connections are rarely addressed in literature. In this talk, the aim is to discuss some of these connections in order to find applications of results between the fields.

9.3. 15:15  Dr. Niko Laaksonen (University College London/University of Copenhagen): Lattice Point Counting in Sectors of Hyperbolic Space – M237

Huber demonstrated how the hyperbolic lattice point problem in conjugacy classes corresponds to counting lattice points in a sector of the hyperbolic plane. This is equivalent to counting geodesic segments according to length. For this problem, Good and Chatzakos--Petridis proved separately an error term analogous to that of Selberg. We show how this generalises to three dimensions and prove a similar strong bound on the error term. We will also apply the work of Chamizo on large sieve inequalities in hyperbolic spaces to our problem in the radial and spatial aspects. In particular, we will discuss why these yield diminishing returns in higher dimensions.

24.2. 15:15  Prof. Valtteri Niemi (University of Helsinki): Garbling and Applications – M237

The history of garbled circuits traces back to Andrew Yao, who introduced the technique in 1980s. The original inspiration is known as the two millionaires' problem. The term "garbled circuit" was introduced by Beaver, Micali and Rogaway for the purpose of performing secure multiparty computation with Yaoís circuit garbling technique. In 2012 Bellare, Hoang and Rogaway elevated garbled circuits from a cryptographic technique to a cryptographic goal by defining several new security notions for garbled circuits. This talk explains these fundamental notions, motivation behind them and how they can be extended. We continue by presenting different classes of garbling schemes, relations between them and other theoretical results. Finally we discuss some application scenarios and efficiency of garbling techniques in cloud computing.

10.2. 16:15  Dr. Relinde Jurrius (University of Neuchatel): On defining q-matroids (NOTE DIFFERENT TIME THAN USUAL!) – M237

The motivation to study q-matroids comes from rank metric codes. There is a link between the weight enumerator of a linear code (in the Hamming metric) and the Tutte polynomial of the associated matroid. Can we do the same in the rank metric case? We will not answer that question here, but focus on the first step: we define a q-matroid, the q-analogue of a matroid. A strong feature of matroids is that they have several cryptomorphic definitions: definitions that are equivalent, but look very different. Best known are the axiom systems for independent sets, bases, and the rank function. These definitions all have a q-analogue, however, these q-analogues are not always equivalent! To solve this problem, we first have to ask ourselves the question: what properties do we want a q-matroid to have? We think a q-matroid should "behave nicely" under deletion, contraction, and duality. Also, we want the duality to coincide with duality in rank metric codes, which are our main examples of q-matroids. In this talk, we will discuss the problems and possible solutions concerned with the different ways to define a q-matroid, illustrated by examples. Joint work with Ruud Pellikaan.

3.2. 15:15  Roope Vehkalahti (University of Turku): Capacity and Geometry of Numbers in Fading Channels – M237

During the last fifteen years multiple-input multiple-output (MIMO) channels have slowly replaced single antenna channels as a main subject of study in information theory. In such channel the message signal is transmitted from multiple antennas unlike in the traditional one-antenna transmission. In addition the system may also contain several receiving antennas. Interest in such channels faced a sudden rise of interest when in 1999 Telatar proved that in the presence of Gaussian noise and ergodic fading the capacity of multiple antenna channel is considerably higher than that of a single antenna system. One of the key challenges in all of coding theory is to build capacity achieving structured codes. So far, and in most MIMO channel models, known coding strategies leave at least a constant gap to capacity and lack structure. In the case of classical single antenna Gaussian channels there exist a rich theory of lattice codes developed to attack these questions. In the heart of this theory are sphere packing arguments that prove that the performance of a lattice code can be roughly estimated by the size of a geometrical invariant of the lattice. This connection has been extremely fruitful and has motivated a large body of work connecting algebra, geometry and information theory. In recent joint work with L.Luzzi we proved that an analogous theory exists in fading MIMO channels. Based on this observation we developed a general theory that connects capacity questions and geometric properties of multiple antenna lattices codes. Building on this theory and on number theoretic existence results we constructed and analyzed capacity approaching coding schemes for several single user fading channel models. In the first part of the talk I will describe some of the key results in multiple antenna information theory and survey the main results of our recent work. In the second part I will discuss the algebraic and geometric part in more detail.

27.1. 15:15  Padraig Ó Catháin (Aalto University): Mathematics of Compressed Sensing – M237

Traditionally signal sampling and signal processing have been regarded as two separate tasks. Shannon's theorem relates the number of samples to the quality of the reconstruction: more samples are required for higher quality data. Compressed sensing is a new paradigm in signal processing in which sampling and compressing are combined into a single step. Under certain weak conditions, this reduces the number of samples required below the Shannon limit, without any loss in quality. Terence Tao's breakthrough papers on this topic showed that random matrices make good compressed sensing matrices. But such arrays are difficult to compute and to store, so are of limited practical use. In this talk we will outline the properties required of a good compressed sensing matrix, and describe a construction for such arrays using Hadamard matrices and pairwise balanced designs. We will conclude with potential applications to image processing, big data and cybersecurity. The talk will be accessible to a broad audience - no specialist knowledge will be assumed.

20.1. 15:15  Dr. Esa Vesalainen (Aalto University): Introduction to Quantum Ergodicity – M237

This expository talk introduces some of the background and ideas on quantum ergodicity from the standpoint of spectral theory and number theory.

11.1. 14:15  Dr. Eric Swartz (The College of William and Mary): Highly symmetric Hadamard matrices – U250a

A Hadamard matrix is a square matrix whose entries are either 1 or -1 such that distinct rows are orthogonal vectors. Such a matrix has the maximal possible determinant of any matrix of that size whose entries have absolute value (or norm) at most 1, and they have proven very useful in applications. In this talk, I will discuss basic properties of Hadamard matrices, some known constructions and classifications of Hadamard matrices with symmetry, and recent and ongoing joint work with Padraig Ó Catháin studying Hadamard matrices with primitive automorphism groups.

9.12. 15:15  Matti Karppa (Aalto University): Finding Outlier Correlations in Subquadratic Time – Y228a

We study the problem of detecting outlier pairs of strongy correlated variables among a collection of n variables with otherwise weak pairwise correlations. After normalization, this task amounts to the geometric task where we are given as input a set of n vectors with unit Euclidean norm and dimension d, and we are asked to find all the outlier pairs of vectors whose inner product is at least ρ in absolute value, subject to the promise that all but at most q pairs of vectors have inner product at most τ in absolute value for some constants 0 < τ < ρ < 1. Improving on an algorithm of G. Valiant [FOCS 2012; JACM 2015], we present a randomized algorithm that for {-1,1}-valued inputs runs in time Õ(n^{max(1-γM(Δγ,γ), M(1-γ,2Δγ)}+qdn^{2γ}) where 0<γ<1 is a constant tradeoff parameter and M(μ,ν) is the exponent to multiply an n^μ × n^ν matrix with an n^ν × n^µ matrix, and Δ = 1 / (1 - log ρ / log τ). Corollaries include randomized algorithms running in time Õ(n^{2ω/(3 - log ρ / log τ)}+qdn^{2(1-log ρ / log τ)/(3-log ρ / log τ)} and in time Õ(n^{4/(2+α(1-log ρ / log τ))} + qdn^{2α(1-log ρ / log τ)/(2+α(1-log ρ / log τ))} where 2 ≤ ω < 2.38 is the exponent for square matrix multiplication and 0.3 < α ≤ 1 is the exponent for rectangular matrix multiplication. Importantly, the latter corollary guarantees a subquadratic runtime whenver the gap (ρ-τ) is a positive constant. Applications include corollaries for the Light Bulb Problem and for learning sparse Boolean functions.

2.12. 15:15  Jukka Kohonen (Aalto University): Fast zeta transform in semimodular lattices – Y228a

Many algebraic and combinatorial problems involve partially ordered sets or "posets", e.g. the collection of subsets of a given set. A lattice is a kind of a poset. The structure can be visualized as a directed acyclic graph (DAG). Each element of a lattice may have an associated number or "value", and one wishes to take sums of these values over (large) collections of elements efficiently. This is called the zeta transform. Counting problems in combinatorics are often of this type. I will describe some recent advances in the algorithmics of such addition. For certain kinds of lattices we now know addition algorithms that are as fast as theoretically possible, namely O(e) additions if the lattice has e edges. I will also discuss some open problems, such as: Are there any lattices where the zeta transform is very difficult? How difficult can it be?

25.11. 16:15  Jelena Luketina (Aalto University): Optimizational Challenges of Deep Learning (Part 2) – Y228a

MSc thesis presentation (N5TeAM). Advisor Tapani Raiko, supervisor Camilla Hollanti. A class of machine learning models known as deep neural networks (DNNs), have recently brought major improvements to the field, accomplishing state-of-the-art on a variety of tasks. DNNs consist of multiple compositions of parametrised non-linear transformations called layers. By modifying the parameters with a variant of gradient-descent algorithm, DNNs can discover complex structures in the data set. The result is often a hierarchical representation of the data, with the more abstract features discovered by the higher layers. Despite these recent successes, using DNNs is still more of an art than a science. Two of the main problems are: - a lack of theoretical understanding, particularly of optimizational difficulties encountered while modifying the parameters; - setting up the appropriate model complexity for the task at hand, through the process of hyper-parameter selection. In this talk, we will present some of the very recent theoretical results which shed light on the former; as well as some work done in our lab, addressing the latter problem.

25.11. 15:15  Prof. Tapani Raiko (Aalto University): Optimizational Challenges of Deep Learning (Part 1) – Y228a

A class of machine learning models known as deep neural networks (DNNs), have recently brought major improvements to the field, accomplishing state-of-the-art on a variety of tasks. DNNs consist of multiple compositions of parametrised non-linear transformations called layers. By modifying the parameters with a variant of gradient-descent algorithm, DNNs can discover complex structures in the data set. The result is often a hierarchical representation of the data, with the more abstract features discovered by the higher layers. Despite these recent successes, using DNNs is still more of an art than a science. Two of the main problems are: - a lack of theoretical understanding, particularly of optimizational difficulties encountered while modifying the parameters; - setting up the appropriate model complexity for the task at hand, through the process of hyper-parameter selection. In this talk, we will present some of the very recent theoretical results which shed light on the former; as well as some work done in our lab, addressing the latter problem.

11.11. 15:15  David Karpuk (Aalto University): Sphere Encoding – Y228a

In this talk we will discuss the basics of sphere encoding, an encoding method for wireless systems which delivers data simultaneously to a large number of users. The method is based on solving the lattice shortest vector problem. We will review recent results which predict the performance of this scheme, and outline future research directions which allow for algebraic and number theoretic encoding methods.

28.10. 15:15  Eveliina Peltola (University of Helsinki): Hidden quantum group structure on solution spaces of certain PDE systems – Y228a

I describe a systematic method for solving PDEs of certain type, which arise in conformal field theory, and in the theory of Schramm-Loewner evolutions, with boundary conditions given by specified asymptotic behaviour of the solutions. Our method is a correspondence associating vectors in a tensor product representation of a quantum group (i.e., a certain braided noncommutative Hopf algebra) to Coulomb gas type integral functions, in which properties of the functions are encoded in natural, representation theoretical properties of the vectors. In particular, this hidden quantum group structure on the solution space of such PDEs enables explicit calculation of the monodromy properties of the solutions. The study of the monodromy also leads us to a generalization of the Temperley-Lieb algebra, defined in terms of a diagrammatic representation. This generalized diagram algebra turns out to be the commutant algebra of the quantum group, in the sense of the so-called quantum Schur-Weyl duality.

21.10. 15:15  Ferdinand Blomqvist: Private Information Retrieval - A Short Introduction – Y228a


30.9. 15:15  Padraig Ó Catháin: Two problems in algebraic combinatorics – Y228a

Existence of (complex) Hadamard matrices and of systems of equiangular lines are two classical problems in algebraic combinatorics. I will define these objects and discuss some methods by which I have tried to approach these problems. Time permitting I will discuss applications to compressed sensing. Only a basic knowledge of linear algebra will be assumed.

16.9. 15:15  Kim Solin, Uppsala University/University of Helsinki/University of Queensland: Abstract algebras for reasoning about programs – Y228a

I present some abstract algebras for reasoning about imperative programs in both partial and total correctness frameworks. The algebras centre around Dexter Kozen's formalisation of Kleene algebra (an idempotent semiring extended with closure operators). I look forward to discussing possible research directions with the audience.

9.9. 16:35  Esa Vesalainen: Exponential sums related to cusp forms – Y228a

Presentation of/by new postdocs in Number Theory.

9.9. 16:15  Jukka Keränen : Cohomology of Shimura Varieties in Number Theory – Y228a

Presentation of/by new postdocs in Number Theory.

9.9. 15:15  Madeleine Ekblom: Applications of homomorphic encryption – Y228a

MSc thesis presentation (N5TeAM program). Advisors: Kaisa Nyberg, Ian Oliver (Nokia), supervisors: Camilla Hollanti, Andrey Bogdanov (DTU)

19.8. 15:15  Iván Blanco Chacón, University College Dublin: Supersingular hyperelliptic curves. Their use in cryptography and some new results. – Y228a

We will discuss the role of supersingular and superspecial curves in cryptography, in particular hyperelliptic and Artin-Schreier ones. For the supersingular case, we will explain several problems which naturally arise, mainly estimates of the slopes of the Newton polygons and divisibility results for their L functions. The talk will be accessible for students.

17.8. 14:15  Anton Mallasto: Lie Groups and Applications to Shape Analysis – M2 (M233)

MSc thesis presentation. Advisor David Karpuk, supervisor Camilla Hollanti.

13.8. 13:15  Elias Jäämeri, Veli Peltola: Theses presentations – M2 (M233)

Elias Jäämeri: kandiesitelmä aiheesta "Nopeasti dekoodattavat tila-aikakoodit" 13:15-14 (ohjaajat Camilla Hollanti ja Oliver Gnilke); Veli Peltola: MSc presentation on "Interactively explorable formal proofs for textbooks of mathematics" 14:15-15 (advisor Tomi Janhunen, supervisor Camilla Hollanti);

3.6. 16:15  Iván Blanco Chacón, University College Dublin: The Mazur-Tate-Teitelbaum p-adic L-function. Orders of vanishing and related questions. – M2 (M233)

In the present talk we explain the p-adic analogue of the Birch and Swinnerton-Dyer conjecture by Mazur, Tate and Teitelbaum. We review some related problems, as the exceptional zero conjecture and the orders of vanishing at infinite order characters.

3.6. 15:15  Julia Brandes, University of Göttingen: Simultaneous additive equations: Repeated and differing degrees – M2 (M233)

We obtain bounds for the number of variables required to establish Hasse principles, both for existence of solutions and for asymptotic formulae, for systems of additive equations containing forms of differing degree but also multiple forms of like degree. Apart from the very general estimates of Schmidt and Browning-Heath-Brown, which give weak results when specialised to the diagonal situation, this is the first result on such "hybrid" systems, and in certain special cases we obtain an asymptotic formula whenever the number of variables exceeds twice the total degree of the system, thus attaining the square root barrier. This is joint work with Scott T. Parsell.

28.5. 9:30  X Lukuteorian päivät / X Finnish Number Theory Days 28.-29.5. (further info) – R001/A2

Kymmenennet Lukuteorian päivät järjestetään Aalto-yliopistolla 28. ja 29. päivä toukokuuta. Tervetuloa luennoimaan ja seuraamaan esitelmiä sekä osallistumaan lukuteorian yhteisön tapaamiseen. The tenth Finnish Number Theory Days will be organized at Aalto University in May 28-29 2015. We wish you all welcome to attend lectures and give talks as well as to gather together with the Finnish Number Theory community. Organizers: Amaro Barreal, Toni Ernvall, Anne-Maria Ernvall-Hytönen, Camilla Hollanti, David Karpuk. Location: Otakaari 1, auditorium A2

27.5. 16:30  Boris Bartolomé, University of Göttingen: On the equation X^n-1=B.Z^n – M2 (M233)

We consider the Diophantine equation X^n-1=B.Z^n (which we call "binary Thue"), where the integer B is understood as a parameter. We give new conditions for the existence of solutions to this equation. These reduce the amount of possible solutions to at most one explicit pair (X;Z) for a given (n;B) such that no prime in the radical of B is congruent to 1 mod n. The proof uses recent results on the diagonal Nagell-Ljunggren equation (X^n-1)/(X-1) = n^eY^n; e=0 or 1, together with a new estimate approach, specific to the equation under consideration. This equation is a special case of the general Pillai conjecture. Joint with Preda Mihailescu.

27.5. 16:00  Andrea Conti, Université Paris 13: Big image of modular Galois representations associated with p-adic families of bounded slope (further info) – M2 (M233)

27.5. 15:15  Prof. Preda Mihailescu, University of Göttingen : Well rounded lattices, codes and some results of Lenny Fukshanski – M2 (M233)

In this talk I will use some slides, generously provided by Lenny Fukshanski, in order to provide an introduction on current research about well rounded lattices. This is a brief survey requested by my hosts on a subject in which I have done no personal research.

6.5. 15:15  Tuomas Tajakka: Cohomology of vector bundles – M2 (M233)

Master's thesis presentation. Advisor Ragnar Freij, supervisor Camilla Hollanti. The talk will also contain an introduction to the topic and should hence be accessible to other students as well.

22.4. 15:15  Franz Kiraly, University College London: Matrices, matroids and marginals - a tutorial to the algebra, combinatorics, and statistics of low-rank matrix completion (further info) – M2 (M233)

22.4. 14:15  Alex Karrila: A Comparison of Skewed and Orthogonal Lattices in Gaussian Wiretap Channels – M2 (M233)

Pre-presentation of an ITW 2014 talk. 30 minutes. The paper can be found on arxiv:

8.4. 15:15  Toni Ernvall: Introduction to Fractional Repetition Codes – M2 (M233)

Fractional repetition codes and DRESS codes are families of storage codes with good repair properties. These concepts were introduced by El Rouayheb et al. in 2010 and Pawar et al. in 2011. This talk presents the definitions and basic results related to these code types.

1.4. 15:15  Ha Tran: On reduced Arakelov divisors of a number field (further info) – M2 (M233)

18.3. 14:15  David Karpuk: Interference alignment and connections to distributed storage systems (NOTE earlier starting time!) – M2 (M233)

The presence of interference in communications systems places fundamental limits on the amount data that can be passed through a network. Using a technique they dubbed 'interference alignment', Cadambe and Jafar have shown that coding schemes exist which allow every users to achieve half of the total channel capacity. These schemes require coding over arbitrarily many time instances at arbitrarily high SNR. Over a single time instance, performing successful interference alignment is equivalent to finding certain subvarieties of products of Grassmannians, and can therefore be treated using algebro-geometric techniques. In the first half of this talk we will summarize some of these techniques. Recent work by Ramchandran and others has demonstrated that interference alignment strategies are necessary for data reconstruction in certain distributed storage systems. The second half of this talk will be devoted to understanding this connection and suggesting possible future work in this area.

11.3. 15:15  Renaud-Alexandre Pitaval: Part 1: A Brief Introduction on Optimization With Unitary Constraints / Part 2: Convergence of Gradient Descent for Low-Rank Matrix Approximation – M2 (M233)

Recently, there has been a renewed interest on first-order optimization methods for computing truncated SVDs in big data settings, as well as for dictionary learning for sparse signal processing and matrix completion. An idealized gradient search for low-rank matrix approximation is shown to converge globally with probability one. The proof is based on the interpretation as an optimization problem on the Grassmann manifold using the Fubiny-Study distance. The Grassmann manifold is shown to be almost everywhere the basin of attraction of the global optimum.

25.2. 16:15  Petteri Kaski: A brief introduction to Möbius algebras – M2 (M233)

A finite lattice is a finite partially ordered set L where every pair of elements has both a greatest lower bound (meet) and a least upper bound (join). Equivalently, L is a finite commutative idempotent semigroup with identity. The Möbius algebra K[L] over a field K is the semigroup algebra obtained by extending a K-vector space whose basis vectors are indexed by L with multiplication defined by taking the join of basis vectors. This talk will review the basic structure of K[L] together with efficient multiplication algorithms.

25.2. 15:15  Camilla Hollanti: Locally repairable codes from expander graphs – M2 (M233)

Distributed storage systems are nowadays popular due to their ability to store scalable amounts of information by using cheap commodity disks. A typical bottle neck in large-scale data centres is the number of storage nodes that have to be contacted in order to repair a lost node. This talk considers this problem via introducing locally repairable codes and their construction via expander graphs.

18.2. 15:15  Kalle Kytölä: Algebraic structures in conformal field theory – M2 (M233)

This talk is an introduction and invitation to some remarkable algebraic structures that appear in the physics of two-dimensional conformal field theories. The symmetry under infinitesimal conformal transformations is described by representations of an infinite dimensional Lie algebra known as the Virasoro algebra. Degenerate representations of the Virasoro algebra lead to partial differential equations for correlation functions of the conformal field theory. Such partial differential equations can in turn can be solved using representations of a certain "quantum group".

11.2. 16:15  Prof. Joachim Rosenthal: Cryptography after the time of Shannon and in the presence of a quantum computer (further info) – M237

11.2. 15:15  Prof. Joachim Rosenthal: Colloquium talk: Three research challenges from Claude Shannon (further info) – M237

22.1. 9:00  ANTA/COST Workshop 22.-23.1. @ 9:15-17 (further info) – R001/A034

This workshop follows the themes of the ANTA research group, that is, Algebra, Number Theory, and their applications to communications and computing in a broad sense. The workshop falls under the general themes of the European Science Foundation COST Action IC1104 on Random Network Coding, including physical layer network coding, distributed storage, compute & forward protocols, device-to-device communications, and physical layer security. The workshop is organized by four of the Action's Management Committee members, Marcus Greferath (Ireland/Finland), Camilla Hollanti (Finland), Gunes Kurt (Turkey), and Vitaly Skachek (Estonia), and it gathers together both researchers within the Action and potential future members. The schedule will consist of plenary talks and short talks, as well as ample time for networking. More information from Camilla.

9.1. 11:15  Alex Karrila: Algebraic Number Theory and the eavesdropper's inverse norm sum on wiretap channels (NOTE the unusual day and time!) – M240

This is an MSc thesis talk on the open problem of finding good code lattices for wireless communications by use of algebraic number theory. We present the wiretap problem and describe the design criteria for a (number-theoretic) code lattice. As an example of number-theoretic problems motivated by the design criteria, we prove a theorem on prime-ideal factorizations of rational-prime generated ideals pO_K in algebraic integer rings O_K. As a prerequisite, the talk only requires the knowledge of basic algebraic structures such as groups, rings and fields, so it is accessible for, e.g., fellow students and interested undergraduates. Advisor: Camilla Hollanti.

9.1. 10:15  Mikael Simberg: Linear-time encoding and decoding of LDPC codes (NOTE the unusual day and time!) (further info) – M240

Master's thesis presentation. Advisors: Petteri Kaski and Camilla Hollanti.

19.11. 15:15  Prof. Mario Di Francesco: Number-theoretic approaches for energy-efficient wireless communications – Y229c

This talk will overview number-theoretic approaches for energy-efficient wireless communications, with focus on power-management in wireless sensor networks and algorithms for node discovery in mobile opportunistic networks.

8.10. 15:15  Thomas Westerbäck: Almost affine locally repairable codes – Y229c

The ever growing need for more efficient and larger scaled systems for data storage has made distributed storage an increasingly important ingredient in many data systems. In such distributed storage systems, it is desirable that data can be reliably stored over a network of nodes so that the data can can be retrieved even if some nodes fail. One class of repair efficient codes for node failures is locally repairable codes (LRCs). In this talk I will present some new results on LRCs that are almost affine and how these results are connected to matroid theory. The talk is based on a joint work with Toni Ernvall, Ragnar Freij and Camilla Hollanti.

19.9. 8:00  Iván Blanco Chacón: Modularity, Heegner points and the Birch and Swinnerton-Dyer conjecture minicourse – M3 (M234)

Monday, 15/9, 10:00-12:00: Review of algebraic number theory; Tuesday, 16/9, 10:00-12:00: Review of elliptic curves; Wednesday, 17/9, 12:00-14:00: Modular forms and modularity; Friday, 19/9, 08:00-10:00: Heegner points and complex multiplication. It is possible to get 2 cr for this course. Contact Iván for more information.

17.9. 12:00  Iván Blanco Chacón: Modularity, Heegner points and the Birch and Swinnerton-Dyer conjecture minicourse – M3 (M234)

Monday, 15/9, 10:00-12:00: Review of algebraic number theory; Tuesday, 16/9, 10:00-12:00: Review of elliptic curves; Wednesday, 17/9, 12:00-14:00: Modular forms and modularity; Friday, 19/9, 08:00-10:00: Heegner points and complex multiplication. It is possible to get 2 cr for this course. Contact Iván for more information.

16.9. 10:00  Iván Blanco Chacón: Modularity, Heegner points and the Birch and Swinnerton-Dyer conjecture minicourse – M3 (M234)

Monday, 15/9, 10:00-12:00: Review of algebraic number theory; Tuesday, 16/9, 10:00-12:00: Review of elliptic curves; Wednesday, 17/9, 12:00-14:00: Modular forms and modularity; Friday, 19/9, 08:00-10:00: Heegner points and complex multiplication. It is possible to get 2 cr for this course. Contact Iván for more information.

15.9. 10:00  Iván Blanco Chacón: Modularity, Heegner points and the Birch and Swinnerton-Dyer conjecture minicourse – M3 (M234)

Monday, 15/9, 10:00-12:00: Review of algebraic number theory Tuesday, 16/9, 10:00-12:00: Review of elliptic curves Wednesday, 17/9, 12:00-14:00: Modular forms and modularity Friday, 19/9, 08:00-10:00: Heegner points and complex multiplication Contact Iván for more information.

27.8. 15:15  Eelis Hyvärinen: Yksinkertainen dekonvoluutio-ongelma (in Finnish) – Y228b

Kandiseminaari, ohjaaja Nuutti Hyvönen (esitelmä saattaa alkaa jo aikaisemmin mikäli ensimmäinen esitelmä on alle 45 minuuttia)

27.8. 14:15  Niko Väisänen: Analysis on discriminants and regulators motivated by wiretap channels – Y228b

Kandiseminaari/Bachelor thesis presentation (NOTE THE EARLIER STARTING TIME!)

20.8. 15:15  Aleksi Lahti: Cryptographic algorithms – Y228b

Kandiseminaari/Bachelor thesis presentation

20.8. 14:15  Leo Tuhkanen: Hamiltonian quaternions and space-time codes – Y228b

Kandiseminaari/Bachelor thesis presentation (NOTE THE EARLIER STARTING TIME!)

2.7. 14:15  Anton Mallasto : Algebraic number theory and connections to wiretap channels – Y228b

Kandiseminaari/Bachelor thesis presentation (NOTE THE EARLIER STARTING TIME!)

11.6. 15:15  Ferdinand Blomqvist: Kleptography - Introduction and Beyond – Y228b

Kleptography is the study of stealing information securely and subliminally. A kleptographic attack is an attack which uses asymmetric encryption to implement a cryptographic backdoor. First the basic principles of kleptography are introduced. After that kleptographic attacks on RSA, the Diffie-Hellman key exchange and DSA will be presented. Finally, we conclude by presenting an attack on the Universal Mobile Telecommunications System (the 3G network) that gives the attacker the possibility to read all communication between mobile devices and the network. In addition the attacker gains the ability to impersonate said devices. (MSc thesis presentation. Advisor: Kaisa Nyberg, ICS, Supervisor: Camilla Hollanti, MS)

5.6. 10:15  Prof. Marcus Greferath, University College Dublin: Crash Course on Modules and Rings – Y228b

Thursday/Friday 05/06.06.14 10:15-12:00 and 14:15-16:00 This short course (2 cr) is intended to lead students with a sound preparation in Linear Algebra to the general field of Module Theory with a particular emphasis on finite rings. We will discuss material from the following list of items: submodules, quotient modules, minimal and maximal submodules, homomorphisms, free modules, projective, and injective modules, Jacobson radical, socle, small and large submodules, semi-simple modules and rings, Frobenius rings, characters, discrete Fourier Transform. We will also discuss some applications to Coding Theory. Contact Camilla for more details.

4.6. 15:15  Marc Härkönen: Distributed storage systems and product matrix codes – Y228b

Kandiseminaari/Bachelor thesis presentation.

21.5. 15:15  Prof. Marcus Greferath (University College Dublin / Aalto Science Institute): Finite Rings and Modules in Communications - A Beautiful Chapter of Applicable Algebra – Seminar lounge TUAS 3rd floor, AScI open space 3161

Ring-linear algebraic coding theory gained importance at the beginning of the previous decade, when it was discovered that certain non-linear binary codes of high quality could be understood as linear codes over the ring of integers modulo 4. This talk gives some insight into this amazing and beautiful chapter of applied algebra. We will report on a collection of results from the literature and from our own previous and current research.

14.5. 15:15  Prof. Salim El Rouayheb (IIT Chicago): Index coding, network coding and related combinatorial problems – Seminar lounge TUAS 3rd floor, AScI open space 3161

The index coding problem is defined as follows. A wireless transmitter, e.g., a base station, holds a set of information sources, X={X1,…, Xn}, and wants to satisfy the demands of receivers, each requesting one of the Xi’s but have a subset of X\{Xi} as side information. What is the minimum number of bits that the base station needs to broadcast to allow all the receivers to decode their requested data? For instance, suppose X={X1,X2}, and receiver 1 wants X1 and has X2, and receiver 2 wants X2 and has X1. Then, the transmitter needs to broadcast only X1+X2 to satisfy the users, instead of transmitting X1 and X2. The code used to obtain the transmitted data is referred to as index code. The motivation behind index coding comes from investigating the benefits of data caching on smart devices. This talk will be divided in two parts and will assume no prior knowledge of index coding. The first part will be a quick tutorial on index coding with a focus on results obtained from rank minimization and graph theoretical techniques. In the second part, I will talk about our recent results on the equivalence between index coding and the network coding problem. This equivalence implies that it is enough to focus on index coding when solving the general network coding problem, which is still open, and permits to easily transfer results and algorithms between the two areas. I will conclude with a number of open problems that I am currently exploring.

30.4. 15:15  Dr. Arsenia Chorti (University of Essex): Optimal Power Allocation in Block Fading Gaussian Channels with Secrecy Constraints – Y228b

In this talk we focus on block fading Gaussian (BF-Gaussian) networks with both acausal and causal channel state information (CSI) feedback, M-block delay tolerance, frame based power and secrecy constraints. First we investigate secure waterfilling algorithms for the acausal multi-user scenario and discuss the feasibility of physical layer techniques in cooperative networks. Secondly, using dynamic programming (DP) techniques we study networks without any CSI at the transmitter; in this case the SC is shown to be maximized by equidistribution of the power budget - a “blind policy”. Finally, we introduce a novel universal approximation in the resource allocation problem - the “blind horizon approximation” (BHA) - by imposing a blind policy in the horizon of unknown events. VAPPUTARJOILU!

23.4. 15:15  Camilla Hollanti (Aalto University): Distributed Storage Systems and Multiple Access Channel Space-Time Codes – Y228b

In a distributed storage system (DSS) data is stored redundantly over multiple storage nodes. Data is distributed to the nodes by using some erasure code, and the system is maintained by replacing failed nodes by new nodes. Regenerating codes are a special class of storage codes that are optimal in terms of the node storage usage and repair bandwidth, and enable data retrieval and system repair by means of simple linear algebra. In wireless storage networks, storage nodes communicate over a wireless fading channel. The setting resembles that of a multiple access channel (MAC), where multiple users transmit data simultaneously to a joint destination. We will see how MAC space-time codes can be used to reliably transmit stored data from one node to another, and point out some weaknesses in the proposed protocol.

9.4. 15:15  Camilla Hollanti (Aalto University): Algebraic Number Theory Meets Space-Time Codes – Y228b

26.3. 10:15  Hunter Brooks (École Polytechnique Fédérale de Lausanne): Elliptic curves and special values of L-Functions – Y347

An elliptic curve is a certain class of polynomial equation. Although the general problem of classifying rational solutions to polynomial equations is too hard to solve, elliptic curves admit many symmetries that make the problem more tractable. In fact, the set of rational solutions to an elliptic curve forms a finitely generated abelian group. The conjecture of Birch and Swinnerton-Dyer says that the rank of this group is the order of vanishing of a particular complex analytic function at z = 1. We will give an overview of this conjecture and discuss recent developments.

19.3. 15:15  Aleksander Mozeika (ICS, Aalto University): LDPC error-correction codes: A statistical physics approach – Y228b

We present a statistical physics perspective on LDPC error-correction codes. This talk is aimed at all researchers (mathematicians, physicists, etc.) interested in LDPC codes.

5.3. 15:15  Jukka Suomela (Aalto University): Lower Bounds for Distributed Algorithms – Y228b

Recently, we have discovered new techniques for proving lower bounds for distributed graph algorithms. To construct difficult instances for fast distributed algorithms, we will use so-called "homogeneously ordered graphs". We say that a graph is (alpha,r)-homogeneous if its nodes are linearly ordered so that an alpha fraction of nodes have pairwise isomorphic radius-r neighbourhoods. An algebraic constructions shows that there exists a finite (alpha,r)-homogeneous 2k-regular graph of girth at least g for any alpha < 1 and any r, k, and g. This result, together with an application of Ramsey's theorem, gives us new lower bounds for fast distributed algorithms; see and for more information.

5.2. 15:15  David Karpuk (Aalto University): An Introduction to LDPC Codes – Y228b

LDPC codes are a vital part of many communications protocols used in industry. In this talk, we present an introduction to their basic mathematical structure, as well as insights into where they are used in practical scenarios.

15.1. 15:15  Mika Göös (University of Toronto): Information and Communication Complexity – Y228b

I will talk about the information theory revolution in the analysis of communication protocols (following Bar-Yossef et al., If time permits, I will also discuss some new directions for designing zero-information protocols using linear algebraic methods.

11.12. 14:15  Amaro Barreal (Aalto University): Fermat's Last Theorem for Regular Primes – Y228a

Before a complete proof of Fermat's Last Theorem was given by Andrew Wiles in 1995, a major breakthrough was due to Kummer in 1847. In this talk, we follow Kummer's proof of Fermat's Last Theorem for regular primes, which involves working in cyclotomic fields, an important class of algebraic number fields.

4.12. 14:15  Dr. Iván Blanco-Chacón (Aalto University): Fuchsian codes with arbitrary rates – Y228a

In this talk we present a recent work generalizing Fuchsian codes with rank 3. Fuchsian codes are non-linear codes for wireless communications attached to orders in quaternion algebras over totally real number fields. They have logarithmc decoding complexity, and for a base field of degree n the code rate is 3n. This is joint work with Montserrat Alsina, Camilla Hollanti and Dionis Remón.

27.11. 14:15  Prof. Petteri Kaski (Aalto University, Department of Information and Computer Science): Identity testing and pattern detection with random homomorphisms – Y228a

This talk will give an introduction to the use of random homomorphisms in the design of randomized algorithms for identity testing and pattern detection on graphs and strings.

20.11. 14:15  Prof. Capi Corrales (Universidad Complutense de Madrid): Matrices and units in quaternion algebras (further info) – Y228a