We will begin this course (MS-EV0030) by reviewing Euler's change of paradigm, with respect to Euclid, and his proof on infinitude of primes. Then, we will study the generalization made by Dirichlet, and will prove Dirichlet's theorem on arithmetic progression. Through the course we will learn about the development of L-functions, character theory and the beginning of the relation between Galois representations and certain complex functions. There will be 5 sessions during 2 weeks. For students interested in credits: attendance gives 2 cr and more can be obtained (upon request) by completing further assignments. Sessions take place on Tue, Thu on the first week and Mon, Wed, Fri the second week, all at 10:15-12.
We will begin this course by reviewing Euler's change of paradigm, with respect to Euclid, and his proof on infinitude of primes. Then, we will study the generalization made by Dirichlet, and will prove Dirichlet's theorem on arithmetic progression. Through the course we will learn about the development of L-functions, character theory and the beginning of the relation between Galois representations and certain complex functions. There will be 5 sessions during 2 weeks. For students interested in credits: attendance gives 2 cr and more can be obtained (upon request) by completing further assignments. Sessions take place on Tue, Thu on the first week and Mon, Wed, Fri the second week, all at 10:15-12.
We will begin this course (MS-EV0030) by reviewing Euler's change of paradigm, with respect to Euclid, and his proof on infinitude of primes. Then, we will study the generalization made by Dirichlet, and will prove Dirichlet's theorem on arithmetic progression. Through the course we will learn about the development of L-functions, character theory and the beginning of the relation between Galois representations and certain complex functions. There will be 5 sessions during 2 weeks. For students interested in credits: attendance gives 2 cr and more can be obtained (upon request) by completing further assignments. Sessions take place on Tue, Thu on the first week and Mon, Wed, Fri the second week, all at 10:15-12.
We will begin this course (MS-EV0030) by reviewing Euler's change of paradigm, with respect to Euclid, and his proof on infinitude of primes. Then, we will study the generalization made by Dirichlet, and will prove Dirichlet's theorem on arithmetic progression. Through the course we will learn about the development of L-functions, character theory and the beginning of the relation between Galois representations and certain complex functions. There will be 5 sessions during 2 weeks. For students interested in credits: attendance gives 2 cr and more can be obtained (upon request) by completing further assignments. Sessions take place on Tue, Thu on the first week and Mon, Wed, Fri the second week, all at 10:15-12.
We will begin this course (MS-EV0030) by reviewing Euler's change of paradigm, with respect to Euclid, and his proof on infinitude of primes. Then, we will study the generalization made by Dirichlet, and will prove Dirichlet's theorem on arithmetic progression. Through the course we will learn about the development of L-functions, character theory and the beginning of the relation between Galois representations and certain complex functions. There will be 5 sessions during 2 weeks. For students interested in credits: attendance gives 2 cr and more can be obtained (upon request) by completing further assignments. Sessions take place on Tue, Thu on the first week and Mon, Wed, Fri the second week, all at 10:15-12.
TBA
Geometric Langlands seems very abstract, does it have any concrete applications? Ill explain how to use it to construct (new) vertex algebras.
The original idea of formality applies to a dg algebra, such as cochains on a space, and characterizes those dg algebras whose structure can be recovered from their cohomology, up to quasi-isomorphism. There is an obstruction-theoretic perspective on formality: a dg algebra is formal if and only if a certain characteristic class, called the Kaledin class, vanishes. From studying this class one deduces the formality of the algebra of cochains on spheres and other highly connected spaces. In this talk I will describe how an extension of this definition for properadic algebras allows us to address formality questions not only of space in its own, but of (possibly noncommutative) spaces endowed with a certain type of Poincaré duality structure. I will then describe a simple calculation of these obstructions for spheres. This is joint work with Coline Emprin.
The exponent $\sigma(T)$ of a tensor $T\in\mathbb{F}^d\otimes\mathbb{F}^d\otimes\mathbb{F}^d$ over a field $\mathbb{F}$ captures the base of the exponential growth rate of the tensor rank of $T$ under Kronecker powers. Tensor exponents are fundamental from the standpoint of algorithms and computational complexity theory; for example, the exponent $\omega$ of matrix multiplication can be characterized as $\omega=2\sigma(\mathrm{MM}_2)$, where $\mathrm{MM}_2\in\mathbb{F}^4\otimes\mathbb{F}^4\otimes\mathbb{F}^4$ is the tensor that represents $2\times 2$ matrix multiplication. Our main result is an explicit construction of a sequence $\mathcal{U}_d$ of zero-one-valued tensors that is universal for the worst-case tensor exponent; more precisely, we show that $\sigma(\mathcal{U}_d)=\sigma(d)$ where $\sigma(d)=\sup_{T\in\mathbb{F}^d\otimes\mathbb{F}^d\otimes\mathbb{F}^d}\sigma(T)$. We also supply an explicit universal sequence $\mathcal{U}_\Delta$ localised to capture the worst-case exponent $\sigma(\Delta)$ of tensors with support contained in $\Delta\subseteq [d]\times[d]\times [d]$; by combining such sequences, we obtain a universal sequence $\mathcal{T}_d$ such that $\sigma(\mathcal{T}_d)=1$ holds if and only if Strassen's asymptotic rank conjecture [Progr. Math. 120 (1994)] holds for $d$. Finally, we show that the limit $\lim_{d\rightarrow\infty}\sigma(d)$ exists and can be captured as $\lim_{d\rightarrow\infty} \sigma(D_d)$ for an explicit sequence $(D_d)_{d=1}^\infty$ of tensors obtained by diagonalisation of the sequences $\mathcal{U}_d$. As our second result we relate the absence of polynomials of fixed degree vanishing on tensors of low rank, or more generally asymptotic rank, with upper bounds on the exponent $\sigma(d)$. Using this technique, one may bound asymptotic rank for all tensors of a given format, knowing enough specific tensors of low asymptotic rank. Joint work with Mateusz Michałek (U. Konstanz). arXiv: https://arxiv.org/abs/2404.06427
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.
Counting the number of higher dimensional partitions is a hard classical problem. Computing the motive of the Hilbert schemes of points is even harder, and should be seen as the geometric counterpart of the classical combinatorial problem. I will discuss some structural formulas for the generating series of both problems, their stabilisation properties when the dimension grows very large and how to apply all of this to obtain (infinite) new examples of motives of singular Hilbert schemes. This is joint work with M. Graffeo, R. Moschetti and A. Ricolfi.
Characters play a key role in representation theory. Lusztigs character sheaves and Springer theory provide one way to work with characters geometrically. In this talk I will explain how to develop the theory of character sheaves in the context of graded Lie algebras. Graded Lie algebras naturally arise from the Moy-Prasad filtration of p-adic groups. In the graded case interesting Hessenberg varieties arise. Affine bundles over these varieties provide a paving of certain affine Springer fibers. At the end of the talk I will explain how one obtains a complete classification of the cuspidal character sheaves on graded Lie algebras via a near by cycle construction. The new results presented are joint work with Grinberg, Liu, Tsai, and Xue.
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.
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)
A generalized polygon is a point-line incidence structure that includes projective planes (generalized 3-gons). Incidence graphs of generalized m-gons are connected bipartite graphs of diameter m and girth 2m. Associated to any group presentation is a graph called the star graph, which encodes structural information about the group defined by the presentation. Transitional behaviour can occur for groups defined by presentations whose star graph components are incidence graphs of generalized polygons; such presentations are called special. A cyclic presentation of a group is a type of group presentation that admits a cyclic symmetry. In this talk I will discuss joint work with Ihechukwu Chinyere in which we classify the special cyclic presentations.
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.
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.
Page content by: webmaster-math [at] list [dot] aalto [dot] fi