Past Talks
After a recent talk on the extrema of the lattice theta series and its strong connections to error-correcting codes and cryptography, we will dive a bit deeper into the mathematical side of this problem. More specifically, we will discuss the Regev and Stephens-Davidowitz conjectures, which state that the integer lattice maximises the theta series among stable lattices and integral lattices. We will present the main ideas behind two papers of the above authors, motivate how their conjectures arose and connect them to other areas of interest in lattice theory.
The theta series describes the geometry of a lattice by characterizing the number of lattice vectors with a given norm. In this talk, we will explore the minimum and the maximum of the lattice theta series and its respective applications to secure wiretap channel communications and lattice-based cryptography.
The Siegel-Shidlovskii theory is a powerful method for studying transcendence and algebraic independence questions of analytic functions, in particular, of E-functions including entire hypergeometric series.
A crucial step in this method involves a non-vanishing proof for the determinants attached to the linear forms, derivatives of an auxiliary function L(t). Instead of the usual derivative D we use the derivative tD.
We give a short proof for the non-vanishing of modified determinants for a class of differential equations including a subclass of hypergeometric differential equations. As a corollary we get an irreducible criterion for the corresponding differential operator. Further, by some basics from differential modules we prove a converse statement.
Given a lattice L, an extension of L is a lattice M of strictly greater rank such that the intersection of M and the subspace spanned by L is equal to L. In this talk we will discuss constructions of such lattice extensions where particular geometric invariants of M, such as the determinant, covering radius and successive minima, are related the corresponding geometric invariants of L. This talk is based on joint work with Lenny Fukshansky.
9.8.2024 10:00 Matilde Costa and Antti Haavikko: Student project presentations: Modular forms and curves – M3 (M234)
There will be two 45 min talks 10:00-10:45 and 11:00-11:45. The topic for the first talk is an introduction to modular forms (Diamond-Schurman Chapter 1, Sections 1,2) and the second an introduction to modular curves (Diamond Schurman Chapter 1 Section 5 and Chapter 2 Sections 1,2). Project advisor Iván Blanco-Chacón.
Advisor: Wilmar Bolanos
In this seminar, we will revisit various key areas of mathematical
optimization. Starting from linear optimization and classical solution
approaches exploiting the polyhedral feasible sets, we will continue to
mixed-integer linear programming. Here, solution approaches from linear
programming can be transferred in the context of cutting-plane and
branch-and-bound methods striving towards integral polyhedra. As a
special case of mixed-integer linear programs, we consider combinatorial
optimization. Classical combinatorial optimization problems contain both
polynomially solvable problems such as matchings and minimum spanning
trees as well as many famous NP-hard problems such as the traveling
salesperson problem and maximum cut.
As a second generalization of linear programming, we consider
semidefinite optimization. Here, we see how combinatorial optimization
problems can be approximated by semidefinite programs and have a look at
interior-point-based solution approaches.
This talk aims to present a general approach to some lattice applications in communications emphasizing topics we have been working on recently as well others of interest. Those are related to spherical codes, index coding, multilevel coding/ decoding, Construction Pi-A from Hurwitz quaternions, twisted embeddings in lattice based cryptography and federated learning.
12:00 Valtteri Lipiäinen: CodedPaddedFL and CodedSecAgg: Straggler mitigation and secure aggregation in federated learning.
12:30 Johan Dinesen: McEliece cryptosystem.
13:15 Tuomo Valtonen: Secure distributed matrix multiplication.
13:45 Neehar Verma: Private polynomial computation from Lagrange encoding.
In the last decade, Locally Recoverable Codes (LRC) have been a critical topic in communication and distributed storage. In addition to the minimum distance, dimension and length of a code, LRCs also consider the locality parameter, i.e. the minimum number of entries needed to recover a given entry for any codeword. The parameters of LRCs are subject to a general Singleton bound and codes achieving the bound are called optimal LRCs. Constructions are known when the underlying field size of the code is larger than the length of the code. However, still little is known about the existence of optimal LRCs over small underlying field sizes. In this talk, I will show how we established new bounds that depend on locality and the field size of code using a duality theory of LRCs and
the combinatorial structure of the code. This talk is based on joint work with A. Gruica and A. Ravagnani.
The Polynomial Learning With Errors problem (PLWE) serves as the background of two of the four cryptosystems standardised in July 2022 by the National Institute of Standards and Technology to replace non-quantum resistant current primitives like those based on RSA, finite field based Diffie-Hellman and its elliptic curve analogue. Although PLWE is highly believed to be quantum resistant, unlike other post-quantum proposals like multivariate and some code based ones, this fact has not yet been established. Moreover, several vulnerabilities have been encountered for a number of specific instances. In a search for more flexibility, it becomes fully relevant to study the robustness of PLWE based on other polynomials, not necessarily cyclotomic. In 2015, Lauter et al. found a good number of attacks based on different features of the roots of the polynomial. In the present talk we present an overview of the approximations made against PLWE derived from these work, along with several new attacks which refine those by Lauter exploiting the order of the trace of roots over finite extensions of the finite field under the three scenarios laid out by Lauter et al, allowing to generalize the setting in which the attacks can be carried out. This is joint work with I. Blanco-Chacón and R. Durán.
Advisors: Lassi Helanti (National Bureau of Investigation Forensic Laboratory) and Estuardo Alpirez Bock (Xiphera)
The Learning with Errors (LWE) problem w.r.t. a matrix B asks to recover the secret-error tuple (s,e) given the sample c = sB+e mod q. In typical settings, e.g. when B mod q is uniformly random, the solution (s,e) is uniquely determined by (B,c). In lattice terminology, this is due to the non-existence of short vectors in the lattice spanned by the rows of B modulo q.
We propose the notion of "primal lattice trapdoors", a suit of algorithms which generates a matrix B together with a trapdoor, such that the lattice of B contains hidden exceptionally short vectors, allowing LWE samples w.r.t. B to admit multiple solutions, whereas the trapdoor allows to sample from the solution space. We provide a construction and prove that it satisfies a set of desirable properties, either unconditionally or computationally based on the NTRU assumption.
Leveraging our tool, we construct a lattice-based indistinguishability obfuscator, a powerful cryptographic primitive known to imply most in cryptography.
Advisors: Okko Makkonen and Serge Kas Hanna
Strassen's asymptotic rank conjecture [Progr. Math. 120 (1994)] claims a strong submultiplicative upper bound on the rank of a three-tensor obtained as an iterated Kronecker product of a constant-size base tensor. The conjecture, if true, most notably would put square matrix multiplication in quadratic time. We note here that some more-or-less unexpected algorithmic results in the area of exponential-time algorithms would also follow. Specifically, we study the so-called set cover conjecture, which states that for any ε>0 there exists a positive integer constant k such that no algorithm solves the k-Set Cover problem in worst-case time O((2-ε)^n|F|poly(n)). The k-Set Cover problem asks, given as input an n-element universe U, a family F of size-at-most-k subsets of U, and a positive integer t, whether there is a subfamily of at most t sets in F whose union is U. The conjecture was formulated by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh in the monograph Parameterized Algorithms [Springer, 2015], but was implicit as a hypothesis already in Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, and Wahlström [CCC 2012, TALG 2016], there conjectured to follow from the Strong Exponential Time Hypothesis. We prove that if the asymptotic rank conjecture is true, then the set cover conjecture is false. Using a reduction by Krauthgamer and Trabelsi [STACS 2019], in this scenario we would also get an O((2-δ)^n)-time randomized algorithm for some constant δ>0 for another well-studied problem for which no such algorithm is known, namely that of deciding whether a given -vertex directed graph has a Hamiltonian cycle.
This is joint work with Andreas Björklund (ITU Copenhagen).
Advisor Tapani Matala-aho.
Lattices, that is, discrete subgroups of Euclidean space, are a fundamental object in mathematics with connections to Lie Group Theory, Cryptography, and Algebraic Number Theory. The sphere-packing density of a lattice roughly measures how efficiently its points are packed into Euclidean space. The search for the optimal lattice packing in n-dimensional space is a long-standing problem, with known solutions only for certain small n. On the other hand, certain lattices arising naturally from Algebraic Number Theory have natural properties that make them especially suitable for applications in communications. In this talk, we will discuss an apparently new class of lattices, which we deem R_n-lattices, whose properties attempt to capture those coming from Number Theoretic lattices while also yielding efficient sphere packing. Falling into this class of lattices are unit lattices coming from totally real Galois number fields, and we apply our results to understand the sphere-packing densities of some well-known classes of unit lattices. This is joint work with Jose Cruz of the University of Calgary.
There is a direct connection between linear codes over fields and matroids, commonly referred to as representable matroids. Specifically, a generator matrix for a linear code over a field not only serves as a coding tool but also as a representation for a representable matroid. Exploiting this connection, matroid theory has proven important in establishing numerous results in information theory, for example, in the areas of distributed storage, field linear codes with Hamming weights, network coding, index coding, and caching. Representable matroids also constitute an intriguing class in their own right, with connections to various areas within mathematics.
In this talk, I will present a generalization of matroids and how this generalization can be associated with modules. I will also illustrate how this connection can be used to establish results in information theory, especially in scenarios where algebraic structures other than vector spaces are considered.
Opponent Prof. Alberto Ravagnani (Eindhoven), Custos Camilla Hollanti
For a number field K, its class group measures the extent that unique factorisation fails in the ring of integers of K. When K is an imaginary quadratic field such that unique factorisation fails miserably, its class group turns out to exhibit nice properties which are found useful in cryptographic constructions.
In this short talk, I will briefly recall some background on class groups, focused on the case of imaginary quadratic fields, and highlight some reasons for their uses in cryptography. For example, assuming certain computational problems are hard over class groups, we shall see that class groups imply encryption schemes that are more space-efficient than the well-known RSA encryption, and there exist cryptographic primitives with desirable properties that are, as of today, only known to be achievable from class groups.
In this talk, I will give an introduction to my PhD project, which focuses on privacy-preserving techniques.
As technology enables more powerful collection and curation of data, it has become a relevant need to assure the privacy of individuals and their associated data. An information-theoretic approach offers unconditional privacy guarantees without relying on the hardness of certain computational problems, i.e., the system cannot be broken even if the adversary has unlimited computing power. There are a variety of security tasks for which information-theoretic security is a meaningful and useful requirement, such as secret sharing, secure multiparty computation, and private information retrieval.
For instance, against side-channel attacks on systems and hardware, to protect one single crucial value (like a byte of a key), one of the most common, not hardware, countermeasures is masking, which applies a secret sharing scheme to expand this single value into a set of several random values. This forces an attacker to target all these random values (instead of a single value) to extract any meaningful secret information, making the attack more difficult.
This presentation, focusing on privacy-preserving techniques with information-theoretic approaches (i.e. secret sharing schemes), gives insights over the planned research during my PhD project. In this project, the results of Venkatesan Guruswami and Mary Wootters, which show that Reed-Solomon codes with evaluation points in the whole (finite) field, a failed evaluation point can be recovered using information from the remaining functional nodes. Due to the close connection between RS-code and Shamirs secret-sharing scheme vulnerabilities with respect to leakage can be concluded, which set the starting point for the doctoral research project. For instance, if a smaller, incomplete, amount of information is obtained by the adversary from each share (instead of the whole share) the secret can still be recovered. Finally, one of the major goals within the doctoral project is to find the minimal amount of leakage that can be tolerated while preserving the secrecy.
Some of the main methods for deciding whether or not a difference set of given parameters exists are the self-conjugacy test developed by Turyn in 1965, the field descent and its variations developed by Schmidt et al. in late 1990's, and importantly, the multiplier theorems by Hall, which date back to 1950's. All of these methods are based on knowledge about the decomposition groups in certain cyclotomic fields. In this talk I show that the multiplier groups of cyclic groups G, where v=|G| is non-squarefree, cannot contain a large set of residues. Together with a small "multiplier lemma" this gives a new existence test that can be used to rule out cyclic difference sets.
Given a lattice L, an extension of L is a lattice M of strictly greater rank such that the intersection of M and the subspace spanned by L is equal to L. In this talk we will discuss constructions of such lattice extensions where particular geometric invariants of M, such as the determinant, covering radius and successive minima, are related the corresponding geometric invariants of L. This talk is based on joint work with Lenny Fukshansky. Zoom: https://aalto.zoom.us/j/62956597693
I will discuss some recent work, joint with Alon Nishry and Brad Rodgers, concerning the distribution of Dirichlet and trigonometric polynomials generated by multiplicative coefficients f(n). In the first part of the talk we will explore some old and new results for deterministic sequences f(n) (Möbius, Legendre symbol,...), stopping along our journey to marvel at a variety of wild and thorny conjectures. The second half of the talk will be devoted to Steinhaus random multiplicative coefficients f(n) = X(n). These considerations give rise to a couple of intriguing arithmetic problems.
Advisors: Wilmar Bolanos, Visa Vallivaara
A Private Information Retrieval (PIR) scheme allows users to retrieve data from a database without disclosing to the server information about the identity of the data retrieved. A single-server PIR scheme is based on computational privacy and assumes computers have limited power. Therefore, it requires computational difficulty. When a system consists of a single server, it is possible to achieve information-theoretic privacy by transmitting the entire database. However, this approach is not feasible. The first computational PIR scheme based on coding theory is presented [2020 IEEE International Symposium on Information Theory (ISIT), pp. 10651070 (2020] by Holzbaur, Hollanti, and Wachter-Zeh. However, Bordage and Lavauzelle presented an attack that occurs in polynomial time and with high probability [Cryptogr. Commun. 13, 519526 (2020)]. We present a single-server PIR scheme using codes over rings that utilize the coding theory perspective of Holzbaur, Hollanti, and Wachter-Zeh, which provides resistance against the attack described in [Cryptogr. Commun. 13, 519526 (2020)]. This talk is based on a joint work with Edgar Martínez-Moro and Diego Ruano.
Universal quadratic forms generalize the sum of four squares about which it is well known that it represents all positive rational integers. In the talk, I'll start by discussing some results on universal quadratic forms over totally real number fields. Then I'll move on to the - markedly different! - situation over infinite degree extensions K of Q. In particular, I'll show that if K doesn't have many small elements (i.e., "K has the Northcott property"), then it admits no universal form. The talk should be broadly accessible, and is based on a very recent joint work with Nicolas Daans and Siu Hang Man.
MSc thesis presentation (advisor Jukka Suomela, CS)
This talk is a brief introduction to the Post-Quantum Cryptography (PQC) standardization process and its two current competitions. Within this setting, the notion of Key Encapsulation Mechanism (KEM) is critical to the development of key establishment on PQC, as an alternative to traditional key establishment mechanisms. We will focus on PQC protocols based on this concept over unauthenticated channels. A number of KEM-based protocols between two parties are proposed, and their resistance over unauthenticated channels is studied. This means analyzing the security of the protocol itself, and its robustness against Man-in-the-Middle attacks. A comparison with their KEX-based counterparts is made in terms of the protocol itself and the types of attacks they are subject to. Finally, a number of go-to KEM-based protocol instances to migrate to, based on the conditions of currently-in-use KEX-based protocols, are proposed.
We introduce the first candidate lattice-based Designated Verifier (DV) ZK-SNARK protocol with \emph{quasi-optimal proof length} (quasi-linear in the security/privacy parameter), avoiding the use of the exponential smudging technique. Our ZK-SNARK also achieves significant improvements in proof length in practice, with proofs length below KB for 128-bit security/privacy level.
Our main technical result is a new regularity theorem for `private' re-randomization of Module LWE (MLWE) samples using discrete Gaussian randomization vectors, also known as a lattice-based leftover hash lemma with leakage, which applies with a discrete Gaussian re-randomization parameter that is polynomial in the statistical privacy parameter.
To obtain this result, we obtain bounds on the smoothing parameter of an intersection of a random -ary SIS module lattice, Gadget SIS module lattice, and Gaussian orthogonal module lattice over standard power of 2 cyclotomic rings, and a bound on the minimum of module gadget lattices. We then introduce a new candidate \emph{linear-only} homomorphic encryption scheme called Module Half-GSW (HGSW), which is a variant of the GSW somewhat homomorphic encryption scheme over modules, and apply our regularity theorem to provide smudging-free circuit-private homomorphic linear operations for Module HGSW. The talk is based on https://eprint.iacr.org/2022/1690.
During the years of the COVID19 pandemic my collaborators and I have tried to revisit and possibly remodel the discipline of group testing in such a way, that it can be seen as a finite linear algebra over the binary semifield. Residuation Theory as presented in a textbook by T. S. Blyth and M. F. Janowitz plays a prominent role in our account on this topic, and we will also attempt to address the error-prone part. The presentation will be complemented by a number of examples.
In this talk we will discuss some of the benefits and shortcomings of using Homomorphic Encryption (HE) for two very different types of practical applications. Firstly, we will talk about Federated Learning, and how to tailor HE for the efficient execution of secure average aggregation. In the last part of the talk, we will modify current HE schemes with the objective of better dealing with privacy-sensitive multidimensional signals (e.g., images). In particular, we will explore the possibility of substituting the more conventional power-of-two cyclotomic rings for different types of multivariate rings.
We introduce and study Diophantine equation (n+1)x^2-ny^2 = 1. It resembles the more complicated Lagrange's theory of Pell's equation x^2-ny^2=1. Positive n \in Z is called P-smooth if its prime factors belong to a subset P of the primes. In tonal music, the melodic intervals n: (n+1) are nearly always {2,3,5,7}-smooth. In 1897, Størmer used Pell's equation to find the P-smooth pairs (n,n+1). We give a simple well-motivated method for Størmer's problem.
In this talk we first recall the notion of arboreal Galois representation and then we develop a method to effectively determine the set of primes p for which certain arboreal Galois representations are surjective modulo p.
Our method is based on a combination of height bounds on integral points on elliptic curves over function fields in positive characteristic and the ABC theorem for function fields.
Using this technique we prove Jones' conjecture on the surjectivity of the arboreal Galois representation attached to f=x^2+t [Conjecture 6.7, Compositio Math. 43 (5) (2007)].
This is a joint work with Andrea Ferraguti.
DNA storage is a promising candidate for next-generation storage systems due to its compactness, high durability, and energy efficiency. However, the process of storing digital data in synthetic DNA suffers from deletion and insertion errors that may affect the sequence of nucleotides during synthesis, sequencing, and storage. The reliability of the DNA storage can be improved by integrating codes that correct deletions and insertions within the storage system. This talk will give a general overview of deletion/insertion correcting codes and discuss the specific encoding and decoding constraints imposed by the technologies used in DNA storage systems.
The following conjecture was made in the 2016 Ireland BT Young Scientist Competition: every prime number q>3 can be expressed as q=p+n(n+1), with p a twin prime and n>0. This conjecture was satisfactorily tested for the first 100 millions of primes, and puzzled by such phenomenon, Gary McGuire asked me to think about a possible proof (or disproof) of the conjecture. The first result I came across is the proof that the validity of the conjecture would easily yield the existence of infinitely many twin primes. The conjecture remains open, but we proved that for each prime q of a set of primes of density 1, can be written as q=p+n(n+1), with p < q also prime (not necessarily twin), which is a weak version of a conjecture by Sun. In the present talk we give a sketch of this proof.
In this talk we will explore some recent results in Secure Distributed Computation, in which a user distributes a computational task across several worker nodes while protecting sensitive aspects of the computation from potential adversaries with access to the worker nodes. This presentation will focus on the case of matrix multiplication, but we will discuss generalizations with potential applications to decentralized machine learning. Many of our results represent joint work with Razan Tajeddine.
Nonlinear dynamical systems pose a significant challenge when it comes to controlling them. The challenge raises to another level if we require fault tolerance. In this talk, I introduce Byzantine fault tolerance (BFT) protocols that aim at resiliency by guaranteeing consistency. I will discuss the essential combinatorial geometry behind BFT, which it shares with seemingly distant areas in math, such as Cantor's work on cardinality of reals and Turing's Halting problem. Finally, if time permits (i.e., when the eyes start rolling), I will discuss how the Diagonal Argument (from category theory) provides a unifying framework to discuss all. I assume no prior knowledge of these subjects and will try to introduce and discuss the basics.
8.2.2023 16:15 Prof. William Mance, University of Adam Mickiewicz in Poznan: Normal numbers – M3 (M234)
Informally, a real number is normal in base b if in its b-ary expansion all digits and blocks of digits occur as often as one would expect them to uniformly at random. Borel introduced normal numbers in 1909 and proved that Lebesgue-almost every real number is normal in all bases b \geq 2. Even though this shows that, in some sense, normal numbers are "typical," no example of a number normal in all bases was given until 1939 by Turing. In the last 100 years, the study of normal numbers has spread over a wide breadth of seemingly unrelated disciplines. Normality is closely related to number theory, ergodic theory, theoretical computer science, probability theory, fractal geometry, descriptive set theory, and others areas of math. We will explore the basic properties of normal numbers and surprising connections they have, depending on the interest of the audience.
Graphs can be used as a diagrammatic representation of entangled states: vertices represent qubits, and edges are the entangling gates performed between the qubits. Arbitrary quantum circuits can be compiled into a fault-tolerant gate set, and the resulting circuit can be reformulated as a graph state. Such graphs can be manipulated by local operations (single qubit/vertex gates) such that edges are added and removed in a well defined manner during a process called local complementation. The latter might have interesting applications for the optimisation of (fault-tolerant) quantum circuits, quantum communication networks and in general whenever, either: a) there is a need to minimize the number of edges (entangling gates) without affecting the functionality of the state, or b) the state has to be embedded into a quantum hardware architecture that has a different connectivity. This talk is partially based on the work from https://arxiv.org/abs/2209.07345
For a given number field K, the integral trace form of K is the quadratic form defined by the trace operator Tr_K/Q(x^2) over the ring of integers of K. In the mid 80's Conner and Perlis showed that for cyclic number fields of prime degree p the isometry class of integral trace is completely determined by the discriminant. The main objective of this talk is to discuss the principal aspects of Conner and Perlis' work and a completed generalization for tame cyclic number fields of arbitrary degree. Furthermore, for such fields, we give an explicit description of a Gram matrix of the integral trace in terms of the discriminant of the field.
Private information retrieval (PIR) addresses the question of how to retrieve data items from a database or cloud without disclosing information about the identity of the data items retrieved. The area has received renewed attention in the context of PIR from coded storage. Here, the files are distributed over the servers according to a storage code instead of mere replication. Alongside with the basic principles of PIR, we will review recent capacity results and demonstrate the usefulness of the so-called star product PIR scheme.
The talk is based on joint work with Ragnar Freij-Hollanti, Oliver Gnilke, Lukas Holzbaur, David Karpuk, and Jie Li.
The complexity of matrix multiplication represents the number of operations needed to compute a matrix product in the asymptotic limit. The first advance in asymptotic complexity was made in 1969 when Strassen introduced an algorithm that is capable of computing the product of two N × N matrices with O(N^{2.81}) operations, which is better than the naive algorithm that takes O(N^3) operations. The current record is an algorithm that is able to compute the product using just O(N^{2.372}) operations. We present the basic tools that are used to analyze this problem and present an algorithm that is even better than the Strassen algorithm. This includes studying the matrix multiplication tensor, its rank, and the so-called border rank.
14.11.2022 10:00 Kirthivaasan Puniamurthy (PhD midterm review talk): On proving adaptive security for Yao's garbling scheme – Y229c
Distributed learning (DL) is a machine learning (ML) setting where several parties (e.g., mobile devices or computer clusters) collaboratively train an ML model under the orchestration of a central entity. DL can be applied in the case where the data is centralized, i.e., owned by a single entity, and also when the data is decentralized, i.e., owned by several parties. In the centralized data setting, DL is attractive when the data is too large for one entity to process by itself. Here, a central entity can make the learning process tractable by distributing the data across several helper nodes and outsourcing part of the computations. The DL setting can also present itself naturally when the training data is owned by several decentralized parties.
Federated learning (FL) is a branch of DL where the data is decentralized and owned by several independent parties who agree to collaboratively train an ML model but want to maintain the privacy of their local data. In addition to privacy, communication efficiency is also a first-order concern in FL, especially when the data is owned by several mobile devices operating over a network.
In this talk, I will introduce distributed learning and federated learning and discuss some of the challenges associated with such distributed systems. I will also explain how basic optimization algorithms, such as gradient descent, can be applied to distributed learning and adapted to the setting of federated learning.
Take your favorite real or p-adic number, say Phi. Let us assume there exist nice rational approximations for your number. Then these approximations will be written as numerical linear forms. We will give a criterion for the irrationality of your number by using a sequence of these numerical linear forms. Moreover, a lower bound is given for the quantity N*Phi-M, where N, M are integers and N is nonzero. However, it is a challenge to find an appropriate sequence of numerical linear forms for an arbitrary number. In this lecture we will not consider this problem. But we note, if your number is a value of a Taylor series or a (generalized) continued fraction, then we may build a candidate sequence from the truncated series or Padé approximations or use the convergents of the continued fraction.
Let M be an arbitrary matroid. In the 70's, Gian-Carlo Rota and Henry Crapo asked for a natural definition of a matroid dM that has as its ground set the collection of (co)circuits of M. We will first survey two earlier such constructions, namely the Exley-Wang derived matroid, and (co)-adjoint lattices. These constructions have several nice properties, but are only defined for certain special classes of matroids, and are not necessarily unique. We will then introduce a recent construction by the speaker, called combinatorial derived matroids. These are uniquely defined for any matroid M, but computing them has proven an elusive task. We will give all the definitions, compute some illuminating examples, and offer a few conjectures. This is joint work with Relinde Jurrius and Olga Kuznetsova.
In combinatorics, a q-analog of a discrete structure is defined by replacing finite sets with finite dimensional vector spaces. On the other hand, matroids are defined as a combinatorial abstraction of several objects such as linearly independent vectors or graphs.
In this talk, we first define a matroid with certain equivalent axiomatic definitions by supporting them with examples. Then we discuss their q-analogs by comparing differences and similarities with the classical case. Finally, as a construction and an application of a q-matroid, we mention their relation with a q-analog of other combinatorial objects called designs, and state some open questions.
This work is a part of the research project supported by Women in Numbers - Europe.
This talk will be about the representation of integers by quadratic forms. We will survey what is known about the quadratic forms that represent all eligible integers of totally real number fields. It will include the recent results, from the joint work with Vitezslav Kala, Dayoon Park, and Blazej Zmija, on the density of real quadratic number fields that have a universal quadratic form with a fixed number of variables.
This talk is an exposition of [1], where we produce modular representations of arbitrary weight lifting a given representation of fixed weight satisfying certain local properties at a given prime. This work has its motivation in the Langlands functoriality for GL(2), a topic which we will also comment about. It is highly advisable to have attended the first introductory talk.
[1]: Blanco-Chacon, I., Dieulefait, L.: "Potentially diagonalisable modular lifts of large weights". Journal of Number Theory, 228, 188-207 (2021).
NB: different zoom address! In this talk we address the equivalence between the RLWE and the PLWE problems for the maximal totally real subextension of the cyclotomic field of conductor 2^rpq, with p, q primes, joint work with López-Hernanz. These fields have been recently used to cryptoanalyse several cyclotomic instances. Likewise, we will show that these fields are immune under one of the attacks presented by Lauter et al in 2016 against PLWE. If time permits, we will comment our ongoing work towards the generalisation of this equivalence to abelian Q-extensions.
Since the introduction of the learning with errors (LWE) problem in 2005, various variants of this problem have emerged. Notably, RLWE is a variant which adds a ring structure to LWE samples, to reduce key size, for a potential loss in security. In this talk, I will present an article by Grover, Mendelsohn, Ling and Vehkalahti, where they introduce yet another variant, CLWE, where the samples come from orders of cyclic algebras. CLWE can be seen as a structured variant of module learning with errors (MLWE). CLWE is claimed to provide computational efficiency and security.
Padé approximations and Siegel's lemma are widely used tools in Diophantine approximation theory.
The homogeneous matrix equation representing both methods has an M x (L+1) coefficient matrix, where M is at most L. Due to the Bombieri-Vaaler version of Siegel's lemma, the upper bound of the minimal non-zero solution of the matrix equation can be improved by finding a big common factor of all the M x M minors of the coefficient matrix. Further, in the case M = L, the existence of this common factor is a step towards understanding the nature of the 'twin-type' Hermite-Padé approximations to the exponential function.
In this second lecture we reproduce the classical type II Hermite-Padé approximations of the exponential series by computing the homogeneous vector of the L x L minors (Cramer's rule).
These minors are Vandermonde-type block determinants which are challenging to unwrap.
For that we introduce appropriate determinant calculus tools which have interest of their own sake.
Joint work with Louna Seppälä.
Padé approximations and Siegel's lemma are widely used tools in Diophantine approximation theory.
The homogeneous matrix equation representing both methods has an M x (L+1) coefficient matrix, where M is at most L. Due to the Bombieri-Vaaler version of Siegel's lemma, the upper bound of the minimal non-zero solution of the matrix equation can be improved by finding a big common factor of all the M x M minors of the coefficient matrix. Further, in the case M = L, the existence of this common factor is a step towards understanding the nature of the 'twin-type' Hermite-Padé approximations to the exponential function.
In this second lecture we reproduce the classical type II Hermite-Padé approximations of the exponential series by computing the homogeneous vector of the L x L minors (Cramer's rule).
These minors are Vandermonde-type block determinants which are challenging to unwrap.
For that we introduce appropriate determinant calculus tools which have interest of their own sake.
Joint work with Louna Seppälä.
Since the introduction of the learning with errors (LWE) problem in 2005, various variants of this problem have emerged. Notably, RLWE is a variant which adds a ring structure to LWE samples, to reduce key size, for a potential loss in security. In this talk, I will present an article by Grover, Mendelsohn, Ling and Vehkalahti, where they introduce yet another variant, CLWE, where the samples come from orders of cyclic algebras. CLWE can be seen as a structured variant of module learning with errors (MLWE). CLWE is claimed to provide computational efficiency and security.
In this seminar, we will first show the Quantum Teleportation algorithm, one of the most important known quantum algorithms. After a short description of quantum channels and quantum noise, we will finally show an example of a 3-qubit quantum error correction algorithm.
Padé approximations and Siegel's lemma are widely used tools in Diophantine approximation theory.
The homogeneous matrix equation representing both methods has an M x (L+1) coefficient matrix, where M is at most L. Due to the Bombieri-Vaaler version of Siegel's lemma, the upper bound of the minimal non-zero solution of the matrix equation can be improved by finding a big common factor of all the M x M minors of the coefficient matrix. Further, in the case M = L, the existence of this common factor is a step towards understanding the nature of the 'twin-type' Hermite-Padé approximations to the exponential function.
In this second lecture we reproduce the classical type II Hermite-Padé approximations of the exponential series by computing the homogeneous vector of the L x L minors (Cramer's rule).
These minors are Vandermonde-type block determinants which are challenging to unwrap.
For that we introduce appropriate determinant calculus tools which have interest of their own sake.
Joint work with Louna Seppälä.
Tame lattices were introduced in 2020 by Mantilla-Soler and Damir, to capture the key properties of lattices arising from tame abelian number fields of either prime degree or conductor, via the Minkowski embedding. Families of well-rounded sublattices of tame lattices were constructed to generalize the observations of Costa et al., that certain submodules of the ring of integers of tame number fields of odd prime degree produce well-rounded lattices.
Later the packing density of well-rounded tame sublattices was characterized and it was also noted that they are either generic well-rounded or similar to the root lattice A_n. Tame well-rounded sublattices closely resemble nearly orthogonal lattices, which have a basis of almost orthogonal vectors. In a 2020 paper by Fukshansky et al., nearly orthogonal well-rounded lattices were studied in more detail, and it was shown that they are, among other things, not local maxima to the sphere packing density function.
In this seminar, we will introduce some definitions of quantum information theory in order to describe some quantum error correction algorithms. We will first define density operators and mixed state to introduce the Von Neumann entropy and some distance measures for quantum systems. After a brief review of classical error correction, we will show an example in the quantum setting.
In this seminar, we will introduce the basic notations and definitions of Quantum Information Theory. We will first describe the three postulates of quantum mechanics and then we will introduce the notions of qubit, quantum state, quantum gate, entanglement and possibly distance measures.
In an interesting paper by Ortiz, Araujo, Aranha, Costa and Dahab, the authors consider a generalisation of the Ring-LWE problem. The usual RLWE uses the canonical embedding to map an underlying ring to a lattice in R^n. The twisted RLWE (RLWE^t) generalises this by considering a twisted embedding. The authors provide a security reduction from RLWE to RLWE^t, and show that the twisted embedding allows for more algebraic lattices to be used in lattice-based cryptosystems.
Let s be a string of length n over the alphabet [m]:={1,2,...,m}. We say that a set S occurs as a substring in s, if some substring of s contains precisely the elements of S, some possibly repeated. We write C(m,n) for the maximum number of subsets occurring as substrings across all strings of length n over [m]. We will present both an efficient algorithm for computing C(m,n) and exact analytic expressions for entries on the diagonal C(m,m) and first superdiagonal C(m,m+1).
Padé approximations and Siegels lemma are widely used tools in Diophantine approximation theory. The appropriate homogeneous matrix equation representing both methods has an M x (L+1) coefficient matrix, where M≤L. Due to the Bombieri-Vaaler version of Siegels lemma, the upper bound of the minimal non-zero solution of the matrix equation can be improved by finding a big common factor of all the M x M minors of the coefficient matrix. We will present some key ingredients on how to find such a big common factor in the case of the exponential function. Further, in the case M=L, the existence of this common factor is a step towards understanding the nature of the twin type Hermite-Padé approximations to the exponential function. Joint work with Louna Seppälä.
Nowadays, with the growing technological expansion of the world, there is a huge amount of data that is created every day. Currently, one of the best approaches for storing data is distributed systems. The earliest example of distributed storage systems was invented in 1970 when for the first time computers would be able to send messages to other systems with a local IP address. Telephone and cellular networks are other examples of distributed systems. These systems perform machine learning tasks in a distributed environment. In this talk, I'll present an introduction to distributed machine learning, which refers to multi-node machine learning algorithms and systems that are designed to improve performance, increase accuracy, and scale to larger input data sizes.
Two number fields are called arithmetically equivalent if their Dedekind zeta functions coincide. It is known that two arithmetically equivalent number fields share degree, discriminant, Galois closure and several other invariants. In this talk I'll recall briefly all these classical results and show how the a perspective of Galois representations and one from arithmetic geometry lead us to prove new results, and put all previous in a clear context, about A.E.
Predictive machine learning uses big amounts of data to predict the likelihood of future outcomes. To build predictive models, confidential personal data needs to be collected and shared. Therefore, user data privacy is a major concern when training such models. In many cases, the data is partitioned between multiple servers or parties, where each party holds parts of the data which can not be revealed to the other parties due to privacy concerns. Combining data from different parties gives additional information, and thus the quality of the model is significantly improved. Applying machine learning algorithms to a partitioned dataset without violating the privacy of the users is a challenging task. This talk will be concerned with methods for building predictive models on partitioned data while preserving user privacy.
Table ideals are monomial ideals that come from tables, i.e. arrangements of integers that satisfy some conditions on the entries, and these ideals have many nice properties. Given a table, the ideal coming from it in a non-minimal form is easy to compute. However, the other direction is not as easy, that is, given a monomial ideal how do we know if it is a table ideal? In this talk, I will introduce the machine learning problem of distinguishing table ideals from non-table ideals, and the results we have obtained from using machine learning to this maths question.
This talk is aimed at mathematicians that have heard about machine learning and are interested in getting more familiar with the field, but dont know where to start. Machine learning (ML) covers a huge amount of algorithms that aim at learning useful information from data. Whether the best learning option is supervised, unsupervised or any other kind of learning depends on the type of our data. It turns out that handling the data takes most of the effort, and defining a model to make predictions out of the data can be done with a few simple lines of Python. We will see some easy examples in a Python notebook environment, so the interested mathematician can reproduce the experiments with their own data. We will show how ML can in particular be used to learn information about mathematical objects, which in turn can be useful to better know your data, be it monomial ideals, number fields or Calabi-Yau hypersurfaces.
For the slides and related material, click "further info".
Link for joining the online defense:
https://aalto.zoom.us/j/651995701
The reading circle will gather around 10 times, check the ANTA seminar page for detailed times and talk titles.
The reading circle will gather around 10 times, check the ANTA seminar page for detailed times and talk titles.
The reading circle will gather around 10 times, check the ANTA seminar page for detailed times and talk titles.
17.12.2019 16:15 Dr. Riikka Kangaslampi (Tampere University): Introduction to hypergraphs – M3 (M234)
In network science problems complex systems or datasets are often modelled as weighted graphs. These models are simple and powerful, but in some cases insufficient to capture the network structure information, if there are higher-order interactions among more than a pair of nodes. Hypergraphs are a generalisation that can be used to tackle this difficulty.
In this talk I will introduce hypergraphs and some of their basic properties and provide a few examples of networks where hypergraphs would be a natural way to describe the interactions. If time permits, I will also discuss current results and research problems related to Ricci curvatures of hypergraphs.
17.12.2019 15:15 Prof. Norbert Peyerimhoff (Durham University): Expander graphs and curvature – M3 (M234)
Expander graphs are increasing families of graphs which are at the same time sparse and very well connected. They are not only of
practical relevance for the construction of robust networks but their theoretical research uncovered many suprising connections with various mathematical disciplines: representation theory (Kazdhan property (T)), geometric group theory (Cayley graphs), combinatorics (zigzag products), number theory (Ramanujan graphs), spectral theory (Cheeger inequalities) and probability theory (random walks and random covers). Another challenging question about graphs are to introduce proper notions of curvature. In this talk, I will briefly present an analytical approach, due to Bakry-Emery, which allows to define curvature on graphs. Once these concepts are introduced, I will discuss relations between expander graphs and Bakry-Emery curvature.
Subspace codes are sets of subspaces in a finite vector space augmented with a suitable metric. This talk presents an application in network coding, introduces basic notation, commonly used tools, symmetry, and relations to related structures. Rank metric codes and a connection to subspace codes are depicted. A family of constructions commonly referred to as "linkage constructions" is presented.
The goal of steganography is to communicate in secrecy by hiding the very presence of the message within a host object called the cover. The actual embedding involves making small modifications to
the cover. Error correction codes gave steganography the perfect environment to develop over the past few decades. In this talk we will explore the relations between steganography and error correcting codes, and describe some of the most prominent steganographic algorithms.
Matrix multiplication is one of the key operations in various engineering applications. A user who has limited computation capability may wish to compute the product of two matrices with the assistance of several distributed servers. However, security becomes an issue when these servers are untrustworthy. In this talk, we focus on information-theoretically secure distributed matrix multiplication with the goal of minimizing the communication overhead.
In this talk I will give an introduction to $\tau$-Li coefficients and my results considering the coefficients and explicit zero-free regions. The $\tau$-Li coefficients are members of an infinite sequence of real numbers which can be used to determine whether certain functions satisfy the Generalized Riemann Hypothesis or not. In the talk, I describe how finitely many $\tau$-Li coefficients can be used to determine whether certain functions have certain zero-free regions inside the critical strip or not.
Defense of doctoral dissertation in mathematics. Opponent Prof. Thomas Britz, Custos Prof. Camilla Hollanti.
This is a brief excursion to the methods and results of my doctoral thesis. The focus is on two functions: the exponential function and Euler's factorial series. By constructing explicit Padé approximations, we are able to improve lower bounds for linear forms in the values of these functions. The first part of the talk contains some historical background and auxiliary techniques. In the second part, some selected results are presented.
27.6.2019 14:15 Prof. Ahmad Yousefian Darani (University of Mohaghegh Ardabili): Cyclic DNA Codes over ${F}_2+u{F}_2+u^2{F}_2$ – M3 (M234)
In this talk we study the structure of cyclic DNA codes of even length over the ring
${F}_2+u{F}_2+u^2{F}_2$ where $u^3=0$.
We investigate two presentations of cyclic codes of even length over
${F}_2+u{F}_2+u^2{F}_2$ satisfying the reverse
constraint and the reverse-complement constraint.
In this talk I will survey the main problems on isogenies of elliptic cuves believed to be hard in a quantum setting and how these problems relate to the security and the cryptanalysis of isogeny-based hash functions.
We consider the problem of private computation in a distributed storage system. In private computation, a user wishes to compute a function of f messages stored in noncolluding databases while revealing no information about the computation result to the databases. We first employ computation of a linear function of the messages, where linear codes are used to encode the information on the databases. We show that this private linear computation capacity, which is the ratio of the desired linear function size and the total amount of downloaded information, matches the maximum distance separable (MDS) coded capacity of private information retrieval for a large class of linear codes that includes MDS codes. Our converse result is valid for any number of messages and linear combinations, and the capacity expression depends on the rank of the coefficient matrix obtained from all linear combinations. We also present how our linear computation approach can be extended to computing arbitrary multivariate polynomials of the messages. Here, the presented schemes yield improved rates compared to the best known schemes from the literature for a small number of messages, while in the asymptotic case the rates match.
When an ideal is defined only by combinatorial means, one expects to have a combinatorial description of its algebraic invariants. An attempt to achieve this description often leads to surprisingly deep combinatorial questions. White's conjecture is an example. It asserts that the toric ideal associated to a matroid is generated by quadratic binomials. Another example is a question of Herzog and Hibi about existence of a quadratic Gröbner basis of the toric ideal of a matroid. Both problems reduce to questions about arrangements of bases in a matroid. We will review recent progress and state some intriguing open problems.
Guest lecture on the Applications of Coding Theory to Security course.
I will present applications of secant varieties in topology through k-regular embeddings. An embedding of a variety in an affine space is called k-regular if any k points are mapped to linearly independent points. Numeric conditions for the existence of such maps are an object of intensive studies of algebraic topologists dating back to the problem posed by Borsuk in the fifties. Current world record results were obtained by Pavle Blagojevic, Wolfgang Lueck and Guenter Ziegler. Our results relate k-regular maps to punctual versions of secant varieties. This allows us to prove existence of such maps in special cases. The main new ingredient is providing relations to the geometry of the punctual Hilbert scheme and its Gorenstein locus. The talk is based on two joint works: with Jarosław Buczynski, Tadeusz Januszkiewicz and Joachim Jelisiejew and with Christopher Miller: arXiv:1511.05707 and arXiv:1512.00609.
25.4.2019 11:15 Professor Ago-Erik Riet (University of Tartu): Permutation Codes – M140 (Majakka)
Codes over permutations can potentially be applied for error correction in flash memories. Information in a flash memory is stored as electric charge in memory cells. Permutation codes are useful to combat errors of charge leakage over time and overshoot while writing. In this approach, within a block of numbered cells all charges are assumed to be different and their relative ranking defines a permutation.
Various distance metrics can be defined in the symmetric group of all permutations over the set $\{1,2,\ldots,n\}$, used to define codes, with varying degrees of usefulness to flash memories.
In this talk I review some of my work with coauthors on permutation codes for error correction. I also review a potential source coding into permutations framework proposed by us. I also introduce multipermutation codes which is a possible relaxation of permutation codes to the case when some charges within the block can be equal. I briefly discuss the difficulties of encoding information into and decoding from permutations.
NOTE: TUESDAY!
Distributed storage systems with high reliability have wide applications in large data centers, peer-to-peer storage systems, and storage in wireless networks. To ensure reliability, the redundancy is crucial for these systems. A popular option to introduce redundancy is to employ erasure codes such as MDS (Maximum Distance Separable) codes, which can efficiently store data and protect against node failures. In this talk, we will introduce several novel high-rate MDS code constructions which have optimal repair bandwidth and some other key properties. In addition, two generic transformations for MDS codes will also be given, one is to enable optimal repair in MDS code and the other is to reduce the sub-packetization level of existing MDS codes, which address two major concerns in high-rate MDS codes for DSSs.
Channels with partial erasures were recently introduced to characterize erasure events in applications where some partial information about an erased symbol or packet is known. After some background on partial erasure channels, we will introduce a multilevel coding scheme for designing codes over these channels. We also characterize cases of channel parameters when capacity can be achieved using such a scheme. Time permitting, we will look at fountain codes over partial erasure channels as well as simple relay channels where at least one link is a partial erasure channel.
Opponent: Prof. Simon Blackburn, Custos: Prof. Camilla Hollanti.
NOTE different day and time!
Walnut is a digital signature algorithm that was first proposed in 2017 by Anshel, Atkins, Goldfeld and Gunnells. The algorithm is based on techniques from braid group theory, and is one of the submissions for the high-profile NIST Post Quantum Cryptography standardisation process. The talk will describe Walnut, and some of the attacks that have been mounted on it. No knowledge of cryptography or the braid group will be assumed. Based on joint work with Ward Beullens (KU Leuven).
In the first part of the talk we will describe basic notions in quantum computation with a view toward error-correction. We will describe in detail Shor's 9 qubit code, and then motivate an algebraic approach to the stabilizer formalism. In the second part of the talk we will define stabilizer codes over Frobenius rings and point out why MacWilliams Extension Theorem fails in this case. The latter motivates the study of isometry groups, for which we show how to construct stabilizer codes with predetermined isometry groups. If time permits, we will end with some remarks on the LU-LC conjecture.
Mid-term PhD talk.
Mid-term PhD talk.
Mid-term PhD talk.
Traditional regenerating codes are efficient tools to optimize both storage and repair bandwidth in storing data across a distributed storage system, particularly in comparison to erasure codes and data replication. In traditional regenerating codes, the collection of any k nodes can reconstruct the information file and is called the reconstruction set, N_R. Also, a failed node can be regenerated from any d surviving nodes. These collections of d nodes are called the regeneration sets, N_H. The number of reconstruction sets and the number of regeneration sets satisfies N_R= C_n^k and N _H=C_{n-1}^d, where C_n^k denotes "n choose k". In generalized regenerating codes, we will have, 1 \le N_R \le C^k_n and 1 \le N_H \le C_{n-1}^d. In this talk, I address the problem of secure generalized regenerating codes and present a coding scheme by focusing on the features of the generalized regenerating codes that protect data in the distributed storage system in presence of an active omniscient adversary.
In coded Private Information Retrieval (PIR), a user wants to download a file from a coded database without revealing the identity of the file. We consider the setting where certain subsets of servers collude to deduce the requested file. These subsets form an abstract simplicial complex called the collusion pattern. In this talk we will discuss the combinatorics of the general star product scheme for PIR under the assumption that the database is encoded using a repetition code.
Advisor Ragnar Freij-Hollanti, supervisor Camilla Hollanti.
In this survey talk, we discuss two related families of codes: batch codes and codes for private information retrieval. These two families can be viewed as natural generalizations of locally repairable codes, which were extensively studied in the context of coding for fault tolerance in distributed data storage systems. Bounds on the parameters of the codes, as well as basic constructions, are presented. Connections between different code families are discussed.
In the first part of the talk, we discuss private keyword search (PKS). Some work has been done to ensure privacy for the user when searching for keywords from a distributed storage system.
In the second part of the talk, we discuss the concept of private search on streaming data (PSS), and its connection to PIR and PKS on the example of a scheme given by Ostrovsky et al. The problem of private search on streaming data (PSS) has been considered under various cryptographic assumptions, e.g. by means of homomorphic cryptosystems and public-key program obfuscation.
13.9.2018 15:15 Jens Zumbrägel (Universität Passau): Indiscrete Logarithms? – M2 (M233)
The modern public-key cryptography, as originated from the seminal work
by Diffie and Hellman, is since connected with the difficulty of the
discrete logarithm problem. However, for finite fields of small
characteristic, this problem turns out to be not as intractable as
thought for a long time. In fact, some striking observations have
recently led to considerable record computations and severe consequences
for the security of certain cryptosystems. This talk aims to illustrate
the main mathematical ideas behind these rather new developments.
BSc presentation. Advised by Laia Amoros.
BSc presentation. Advised by Oliver Gnilke and Razane Tajeddine.
I study the use of formal methods in protocol verification, in particular Tamarin language. Tamarin (https://tamarin-prover.github.io) is an automated symbolic verification tool for security protocols. It allows you to specify a protocol and its security properties using so called facts, rewrite rules and lemmas. You can then use it to check the validity of the security properties.
In the talk I explain the theory and syntax of Tamarin and show how to use it to specify and validate a part of an access protocol. I work for a company called Bitwards that provides access sharing software for electronic locks and the protocol I am going to present is part of their access sharing system that we want to formally validate.
MSc thesis presentation. Thesis work is carried out at Bitwards. Advisor Chris Brzuska, supervisor Camilla Hollanti.
23.5.2018 15:15 Ferenc Szöllösi (Aalto - Department of Communications and Networking ): Constructions of maximum few-distance sets – M2 (M233)
Abstract: A finite set of distinct vectors X in the d-dimensional Euclidean space is called an s-distance set, if the set of mutual distances between distinct elements of X has cardinality exactly s. In this talk I will present a computer-aided approach for construction and classification of s-distances for small parameter values. In particular, I will discuss the largest 3-distance set in dimension 4.
Let $D$ be a t-(v,k,\lambda) design. If there is a
(t+1)-(v+1,k+1,\lambda) design E such that the derived design
with respect to some point is D, then E is called an extension
of D and D is called extendable. In 1973, P. Cameron classified
the extendable symmetric designs. In this talk we shall look at
extensions of quasi-symmetric designs. Although no parametric
classification is in sight, there is a known infinite family and
several sporadic examples. There are also numerous parameter sets
for which extensions seem feasible, but it is not known whether the
designs and their extensions exist.
14.2.2018 15:15 Marzieh Arabi Kakavand: Cyclic Subspace Codes – M205
Subspaces codes are of great interest due to their applications to multiple sender-receiver schemes. As in classical algebraic coding theory, one of the most important research area in random network coding is the existence and construction of subspace codes and cyclic subspace codes with good parameters.
Recently Etzion et al. have presented a method for constructing cyclic subspace codes, which includes some special kind of linearized polynomials, namely subspaces polynomials and also Frobenius mappings. This new approach, especially the representation of some families of subspace codes via polynomials, is a very interesting contribution to this area of research. Some of the research on cyclic subspace codes, it becomes relevant the following conjecture.
Conjecture: For every positive integers n, k such that k < n/2, there exists a subspace cyclic code of size (q^n-1)/(q-1) in G_q(n,k) and minimum distance 2k-2.
For a fixed natural number k<= n let G_q(n,k) denote the set of all subspaces of F_q^n of dimension k and we call it the k-Grassmannian.
I will talk about the efforts that were done for solving this Conjecture.
I will introduce quaternion algebras and show how one can construct Shimura curves with them. Quaternion algebras arise as a natural generalisation of matrix algebras. In the same way that the action of SL(2,Q) (and of all its congruence subgroups) on the complex upper half-plane give us modular curves, the action of certain subgroups of quaternion algebras will give us some algebraic structure (the so called Shimura curves). After this introduction I will explain some applications of Shimura curves and sketch how one can compute the bad reduction of certain families Shimura curves, based on a joint work with P. Milione.
In modern wireless communication systems, it is a well-known assumption that the received signal amplitude is $y = hx + n$, where $x$ is the transmitted amplitude, $h$ is the fading coefficient and $n$ is thermal receiver noise. This model has been the bedrock for deriving a myriad of mathematical results. However, it might be forgotten that this model does not always apply. In this lecture-like, rather informal talk, I will not present new results, but show from where this formula comes and under what circumstances it is reasonable.
Consider a linear $[n, k, d]_q$ code $C$. The $i$th
coordinate of $C$ has locality $r$, if the value at this coordinate can
be recovered from accessing some $r$ other coordinates of $C$. Data
storage applications require codes with low locality
for information coordinates and low locality for parity coordinates.
Motivated by applications to data storage, Gopalan and his collaborators (2012) introduce $(r, d)$-codes, which are systematic codes that have distance $d$ and also have the property that any information coordinate has locality $r$ or less.
In this presentation, I will talk about results that are obtained
on the linear codes and nonlinear codes with locality property.
Given a set of monomials M ={m_1, ..., m_r} in a polynomial ring,
one can form the set L of all least common multiples of
subsets of M. This set is a partially ordered set, (even a lattice)
ordered by divisibility.
It is known that the betti numbers of the ring S/(M) can be computed
as the homology of the simplicial complex of L. In the talk,
I will explain how this relationship can be lifted to hold on the level
of resolutions, between modules over S on one hand, and modules over
the incidence algebra of L on the other hand.
11.10.2017 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.
MSc thesis presentation
4.10.2017 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.2017 15:15 Ville Kujala: Achieving the capacity of coded PIR using arbitrary linear code (BSc presentation) – M3 (M234)
24.8.2017 14:15 Juuso Korvuo: Hilojen lähimmän vektorin ongelma (kandiesitelmä) – M3 (M234)
24.8.2017 9:15 Aki Malinen: Algebraic methods in maximum likelihood estimation (BSc presentation) – M3 (M234)
Informal presentations during the visit of our new Cryptology professor Chris Brzuska
2.8.2017 11:15 Leevi Korkeala: Hyperbolisten ryhmien pinta-aliryhmät (kandiesitelmä) – M3 (M234)
2.8.2017 10:15 Miio Taarna : Julkisen liikenteen verkostojen tarkastelu verkkoteorian keinoin (kandiesitelmä) – M3 (M234)
20.7.2017 11:15 Valtteri Lipiäinen: Verkkojen Ollivier-Ricci -kaarevuus (kandiesitelmä) – M3 (M234)
20.7.2017 10:15 Miika Leinonen: Kvaternioalgebrat ja hyvin pyöristyvät hilat (kandiesitelmä) – 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.
Opponent Prof. Bharath Sethuraman, custos Camilla Hollanti.
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.
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.
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.
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
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.
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.
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.
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.
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.
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.
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.
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.
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).
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.
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.2016 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 MerlinArthur proofs of batch
evaluation of Williams [Proc. 31st IEEE Conference on Computational
Complexity (CCC'16, May 29--June 1, 2016, Tokyo), 2:117]
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: http://dx.doi.org/10.1145/2933057.2933101
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].
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.
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).
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.
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 https://arxiv.org/abs/1606.04770.
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.
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.
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.
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
(https://arxiv.org/abs/1407.6692).
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 employees 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.
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.
Distributed storage systems are becoming
a vital infrastructure of todays 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: camilla.hollanti-at-aalto.fi.
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:
http://arxiv.org/pdf/1602.09134.pdf
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.
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.
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.
Lagranges 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.
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.
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.
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.2016 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.
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.
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.
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.
This expository talk introduces some of the background and ideas on quantum ergodicity from the standpoint of spectral theory and number theory.
11.1.2016 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.
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.
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?
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.
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.2015 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.
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.
TBA
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.2015 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.
Presentation of/by new postdocs in Number Theory.
Presentation of/by new postdocs in Number Theory.
MSc thesis presentation (N5TeAM program). Advisors: Kaisa Nyberg, Ian Oliver (Nokia), supervisors: Camilla Hollanti, Andrey Bogdanov (DTU)
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.
MSc thesis presentation. Advisor David Karpuk, supervisor Camilla Hollanti.
13.8.2015 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);
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.
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.
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.2015 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.
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.
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.
Pre-presentation of an ITW 2014 talk. 30 minutes. The paper can be found on arxiv: http://arxiv.org/abs/1411.5861.
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.
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.
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.
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.
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.
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".
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.
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.
Master's thesis presentation. Advisors: Petteri Kaski and Camilla Hollanti.
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.
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.
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.
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.
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.
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.
Kandiseminaari, ohjaaja Nuutti Hyvönen (esitelmä saattaa alkaa jo aikaisemmin mikäli ensimmäinen esitelmä on alle 45 minuuttia)
Kandiseminaari/Bachelor thesis presentation (NOTE THE EARLIER STARTING TIME!)
Kandiseminaari/Bachelor thesis presentation
Kandiseminaari/Bachelor thesis presentation (NOTE THE EARLIER STARTING TIME!)
Kandiseminaari/Bachelor thesis presentation (NOTE THE EARLIER STARTING TIME!)
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.2014 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.
Kandiseminaari/Bachelor thesis presentation.
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.
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 Xis 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.
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!
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.
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.
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.
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 http://dx.doi.org/10.1145/2528405 and http://arxiv.org/abs/1304.1007 for more information.
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.
I will talk about the information theory revolution in the analysis of communication protocols (following Bar-Yossef et al., http://dx.doi.org/10.1016/j.jcss.2003.11.006). If time permits, I will also discuss some new directions for designing zero-information protocols using linear algebraic methods.
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.
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.
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.
