BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Buket Özkaya (Nanyang Technological University (Singapore)) DTSTART:20200506T070000Z DTEND:20200506T080000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/1 DESCRIPTION:Title: Good Stabilizer Codes from Quasi-Cyclic Codes\nby Buket Özkaya (Nanyang Technological University (Singapore)) as part of University of Z urich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nLison ek and Singh proposed an interesting modification to the construction of q ubit stabilizer codes by relaxing the Hermitian self-orthogonality require ment. Their framework\, inspired by Construction X in the classical setup\ , yielded a number of better qubit codes than the previous best-known. The se better codes came from applying their construction to specifically chos en quaternary cyclic codes. Construction X for qubit codes generalizes nat urally to q-ary quantum codes.\nThis work uses self-orthogonal or nearly s elf-orthogonal quasi-cyclic codes over F4 and F9 as ingredients in the qua ntum Construction X to derive good qubit and qutrit (3-ary quantum) codes. We consider quasi-cyclic codes with large Hermitian hulls\, which can be easily produced using their Chinese Remainder Theorem decomposition. Such codes have a good chance to be implemented in actual quantum processors. W e exhibit quantum codes with parameters that strictly improve on the curre ntly best-known ones and list those that match the best-known ones in perf ormance.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/1/ END:VEVENT BEGIN:VEVENT SUMMARY:Madhu Sudan (Harvard University (Cambridge\, Massachusetts)) DTSTART:20200506T130000Z DTEND:20200506T140000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/2 DESCRIPTION:Title: Codes for correcting editing errors\nby Madhu Sudan (Harvard Un iversity (Cambridge\, Massachusetts)) as part of University of Zurich (joi nt with Neuchatel) applied algebra seminars\n\n\nAbstract\nThe "edit dista nce''\, also known as the Levenstein distance\, between two strings X\, Y over some alphabet Sigma\, is the minimum number of insertions and deletio ns in X that will transform it to Y. For example if X = 010101010101 and Y = 101010101010\, then their Hamming distance is 12 while the edit distanc e is 2 - since you can delete the first 0 in X and insert a 0 in the last position to get Y. In this talk we will consider the task of correcting ed iting errors\, i.e.\, the task of recovering X\, given a string Y obtained from the transmission of X followed by a "few" editing errors.\nCoding th eory has traditionally focussed mostly on correcting Hamming errors and ti ll recently the theory of coding for editing errors was far behind. A rece nt series of works by Haeupler and Shaharasbi (with varying sets of author s) has completely transformed this picture\, and brought us to the stage w here the results subsume what we know for the Hamming setting\, at least f or large constant sized alphabets! (Of course the proofs also use the stat e of the art results in the Hamming setting to get there.)\nIn this talk\, I will use a recent theorem (from a paper with Haeupler and Shahrasbi) as an excuse to talk about these developments. Our theorem shows that for ev ery delta < 1\, gamma < infinity and epsilon > 0\, there is an constant q and an infinite family of q-ary codes of rate 1 - delta - epsilon which ca n be list decoded in polynomial time from delta fraction deletions and gam ma "fraction" insertions. (Note that gamma\, the fraction of insertions ca n be much larger than 1!) Depending on availability of time we will speak about the two main ingredients in this result: (1) The corresponding resul t in the Hamming setting (where we allow delta fraction deletions\, but on ly allow same number of insertions in the same locations) which comes from the Folded-Reed-Solomon-Codes of Guruswami and Rudra and the many followu ps. (2) Synchronization strings\, which are magical ingredients introduced by Haeupler and Shahrasbi that convert codes for Hamming settings into co des for editing errors.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/2/ END:VEVENT BEGIN:VEVENT SUMMARY:Kristin Lauter (Microsoft Research (Redmond\, Washington)) DTSTART:20200513T180000Z DTEND:20200513T190000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/3 DESCRIPTION:Title: Supersingular Isogeny Graphs in Cryptography\nby Kristin Lauter (Microsoft Research (Redmond\, Washington)) as part of University of Zuri ch (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nAs we mo ve towards a world which includes quantum computers which exist at scale\, we are forced to consider the question of what hard problems in mathemati cs our next generation of cryptographic systems will be based on. Supersi ngular Isogeny Graphs were proposed for use in cryptography in 2006 by Cha rles\, Goren\, and Lauter. Supersingular Isogeny Graphs are examples of R amanujan graphs\, which are optimal expander graphs. These graphs have th e property that relatively short walks on the graph approximate the unifor m distribution\, and for this reason\, walks on expander graphs are often used as a good source of randomness in computer science. But the reason t hese graphs are important for cryptography is that finding paths in these graphs\, i.e. routing\, is hard: there are no known subexponential algorit hms to solve this problem\, either classically or on a quantum computer. For this reason\, cryptosystems based on the hardness of problems on Super singular Isogeny Graphs are currently under consideration for standardizat ion in the NIST Post-Quantum Cryptography (PQC) Competition. This talk wi ll introduce these graphs\, the cryptographic applications\, and the vario us algorithmic approaches which have been tried to attack these systems.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/3/ END:VEVENT BEGIN:VEVENT SUMMARY:Gretchen Mathews (Virginia Tech (Blacksburg\, VA)) DTSTART:20200527T140000Z DTEND:20200527T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/4 DESCRIPTION:Title: Coding for local recovery\nby Gretchen Mathews (Virginia Tech ( Blacksburg\, VA)) as part of University of Zurich (joint with Neuchatel) a pplied algebra seminars\n\n\nAbstract\nCodes with locality are designed to recover erased symbols by accessing only a few others. Such codes are use ful in settings such as distributed storage where servers may routinely go offline for maintenance but users still need to access their information. This situation suggests that it is also desirable to have a variety of wa ys in which to recover a single symbol\, leading to the concept of availab ility. In this talk\, we share recent work on codes from curves which prov ide locality and availability.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/4/ END:VEVENT BEGIN:VEVENT SUMMARY:Daniel Cabarcas Jaramillo (Universidad Nacional de Colombia (Bogot a\, Kolumbien)) DTSTART:20200603T140000Z DTEND:20200603T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/6 DESCRIPTION:Title: From Minrank Attack to generic Bilinear\nby Daniel Cabarcas Jar amillo (Universidad Nacional de Colombia (Bogota\, Kolumbien)) as part of University of Zurich (joint with Neuchatel) applied algebra seminars\n\n\n Abstract\nThe Minrank (MR) problem is a computational problem closely rela ted to attacks on code- and multivariate-based schemes. MR can be reduced to a bilinear system of polynomial equations. In the quest to better estim ate the complexity of this approach\, we developed a more general theory f or generic bilinear systems. In this presentation\, we show some of the la test results for the complexity of MR and then\, we present some general r esults about bilinear systems.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/6/ END:VEVENT BEGIN:VEVENT SUMMARY:Antonia Wachter-Zeh (TU Munich (Munich)) DTSTART:20200617T130000Z DTEND:20200617T140000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/7 DESCRIPTION:Title: LIGA: A cryptosystem based on the hardness of rank-metric list and interleaved decoding.\nby Antonia Wachter-Zeh (TU Munich (Munich)) as part of University of Zurich (joint with Neuchatel) applied algebra semina rs\n\n\nAbstract\nWe propose the new rank-metric code-based cryptosystem L IGA which is based on the hardness of list decoding and interleaved decodi ng of Gabidulin codes. LIGA is an improved variant of the Faure-Loidreau ( FL) system\, which was broken in a structural attack by Gaborit\, Otmani\, and Talé Kalachi (GOT\, 2018). We keep the FL encryption and decryption algorithms\, but modify the insecure key generation algorithm. Our crucial observation is that the GOT attack is equivalent to decoding an interleav ed Gabidulin code. The new key generation algorithm constructs public keys for which all polynomial-time interleaved decoders fail---hence LIGA resi sts the GOT attack. We also prove that the public-key encryption version o f LIGA is IND-CPA secure in the standard model and the KEM version is IND- CCA2 secure in the random oracle model\, both under hardness assumptions o f formally defined problems related to list decoding and interleaved decod ing of Gabidulin codes. We propose and analyze various exponential-time at tacks on these problems\, calculate their work factors\, and compare the r esulting parameters to NIST proposals. The strengths of LIGA are short cip hertext sizes and (relatively) small key sizes. Further\, LIGA guarantees correct decryption and has no decryption failure rate. It is not based on hiding the structure of a code. Since there are efficient and constant-tim e algorithms for encoding and decoding Gabidulin codes\, timing attacks on the encryption and decryption algorithms can be easily prevented.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/7/ END:VEVENT BEGIN:VEVENT SUMMARY:Luca De Feo (IBM Research Zürich (Zürich)) DTSTART:20200429T140000Z DTEND:20200429T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/8 DESCRIPTION:Title: Faster Evaluation of Isogenies of Large Prime Degree\nby Luca D e Feo (IBM Research Zürich (Zürich)) as part of University of Zurich (jo int with Neuchatel) applied algebra seminars\n\n\nAbstract\nAn isogeny is a non-zero morphism of elliptic curves. The isogeny evaluation problem ask s\, given a description of an isogeny φ:E→E' and of a point P∈E\, to compute φ(P). It is a fundamental algorithmic problem in computational nu mber theory and has gained a fair amount of interest thanks to the recent developments in isogeny-based cryptography.\nThe "atomic" case for isogeny evaluation is that of isogenies of prime degree\, on top of which algorit hms for isogenies of any degree are easily constructed. For the prime degr ee case\, the classic solution is based on Vélu's formulas or any of thei r optimized variants. Vélu's formulas take as input the kernel of the iso geny\, e.g.\, as a list of points\, and output the isogeny as a pair of ra tional functions\, which are then used to evaluate the isogeny at the poin t. This algorithm can be implemented in time linear in the isogeny degree\ , which is asymptotically optimal in general\; however in the fundamental case where the kernel can be described by a single generator over the base field\, one could hope to find a more efficient algorithm which sidesteps the computation of the rational functions.\nThis is exactly what I will p resent in this talk: starting from a very simple idea\, already used by Po llard\, Strassen\, and Chudnovsky²\, among others\, I will present a baby -step/giant-step algorithm that solves the isogeny evaluation problem in t ime and space proportional to the square root of the degree. I will explai n why this is important for isogeny-based cryptography\, and highlight sev eral applications where the new algorithm produces practical speedups rang ing from the unimpressive to the spectacular.\nThis is joint work with D.J . Bernstein\, A. Leroux and B. Smith\, the preprint can be found at https: //ia.cr/2020/341.\n(**This talk will be live streamed at https://defeo.lu/ tube/**)\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/8/ END:VEVENT BEGIN:VEVENT SUMMARY:Markus Grassl (International Centre for Theory of Quantum Technolo gies) DTSTART:20200610T140000Z DTEND:20200610T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/9 DESCRIPTION:Title: On Quantum MDS Codes\nby Markus Grassl (International Centre fo r Theory of Quantum Technologies) as part of University of Zurich (joint w ith Neuchatel) applied algebra seminars\n\n\nAbstract\nA quantum error-cor recting code (QECC)\, denoted by ((n\,K\,d))q\, is a K-dimensional subspac e of the complex vector space Cq⊗n that is able to correct up do d-1 era sures. A quantum MDS (QMDS) code is a code of maximal possible dimension m eeting the quantum Singleton bound logqK ≤ n+2-2d. Most known QMDS codes are based on Hermitian self-orthogonal classical MDS codes. It has recent ly been shown [3] that regardless of the underlying construction\, QMDS co des share many (but not all) properties with their classical counterparts. The QMDS conjecture states that the length of nontrivial codes is bounded by q2+1 (or q2+2 in special cases). While QMDS codes of maximal length ar e known for many cases\, it appears to be difficult to find codes of dista nce d > q+1 (see [1\,2]).\nThe talk addresses the question of finding QMDS codes in general and presents a couple of related open questions in algeb raic coding theory.\n\n[1] Ball\, Simeon\, "Some constructions of quantum MDS codes''\, preprint arXiv:1907.04391\, (2019).\n[2] Grassl\, Markus and Roetteler\, Martin\, "Quantum MDS Codes over Small Fields''\, Proceedings 2015 IEEE International Symposium on Information Theory (ISIT 2015)\, pp. 1104--1108\, (2015). DOI: 10.1109/ISIT.2015.7282626\, preprint arXiv:1502 .05267.\n[3] Huber\, Felix and Grassl\, Markus\, "Quantum Codes of Maximal Distance and Highly Entangled Subspaces''\, preprint arXiv:1907.07733\, ( 2019).\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/9/ END:VEVENT BEGIN:VEVENT SUMMARY:Alain Couvreur (Ecole polytechnique (Palaiseau\, France)) DTSTART:20200520T130000Z DTEND:20200520T140000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/10 DESCRIPTION:Title: On the code equivalence problem in rank metric\nby Alain Couvr eur (Ecole polytechnique (Palaiseau\, France)) as part of University of Zu rich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nThe co de equivalence problem can roughly be stated as follows : "Given two codes \\(C_1\\)\, \\(C_2\\)\, is there an isometry \\(\\phi\\) of the ambient s pace such that \\(\\phi(C_1) = C_2\\)?" In Hamming metric\, this problem h as been intensively studied in the last decades\, with in particular the { \\it support splitting algorithm} by N. Sendrier which solves this problem in the generic case when the isometry \\(\\phi\\) is a permutation. On th e rank metric side\, the linear isometries of the ambient space are classi fied and various algebraic invariants related to a given matrix space have been identified. In this talk\, we will focus on the algorithmic aspects of the code equivalence problem in rank metric by focusing on three versio ns: 1. \\(\\mathbb{F}_{q^m}\\)--linear codes with a vector representation 2. \\(\\mathbb{F}_{q^m}\\)--linear codes with a matrix representation 3. N on structured matrix spaces. We propose efficient algorithms to solve vers ions (1) and (2) of the problem. Then we prove that (3) is at least as har d as the monomial equivalence problem in Hamming metric. This is a work in progress in collaboration with Thomas Debris-Alazard (Royal Holloway\, Lo ndon) and Philippe Gaborit (University of Limoges).\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/10/ END:VEVENT BEGIN:VEVENT SUMMARY:Alfred Wassermann (University of Bayreuth (Bayreuth\, Germany)) DTSTART:20200701T140000Z DTEND:20200701T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/11 DESCRIPTION:Title: Designs\, subspace designs and their codes\nby Alfred Wasserma nn (University of Bayreuth (Bayreuth\, Germany)) as part of University of Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nIn t his talk\, we give an overview of combinatorial designs\, their q-analogue s and related structures. Design theory has a venerable history starting i n the 1830s. The connection between combinatorial designs and linear error correcting codes is well studied. In recent years\, subspace designs - al so called q-analogues of designs - regained interest because of their appl ication as subspace codes in random network coding\, which led to many new results on structural properties of the subspace designs. Moreover\, it t urns out that also the linear codes spanned by the rows of the incidence m atrix of subspace designs are interesting. Another important class of subs paces codes is lifted MRD codes. Surprisingly\, lifted MRD codes can be re garded as transversal designs and the resulting linear codes can be studie d\, too. These codes may be useful as so called PIR codes for private info rmation retrieval.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/11/ END:VEVENT BEGIN:VEVENT SUMMARY:Daniel Panario (Carleton University) DTSTART:20200729T140000Z DTEND:20200729T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/13 DESCRIPTION:Title: Analytic and Probabilistic Combinatorics for Polynomials over Fini te Fields\nby Daniel Panario (Carleton University) as part of Universi ty of Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract \nThe central objects of this talk are univariate polynomials over finite fields. We survey methods and results to count polynomials satisfying cert ain properties\, and to understand their random behaviour.\nWe first comme nt on a methodology from analytic combinatorics that allows the study of t he decomposition of polynomials into irreducible factors\, the derivation of algorithmic properties\, and the estimation of average-case analysis of algorithms. This methodology can be naturally used to provide precise inf ormation on the factorization of polynomials into its irreducible factors similar to the classical problem of the decomposition of integers into pri mes. Examples of these results are provided. The shape of a random univari ate polynomial over a finite field is also given. As an example of the met hodology\, periodicity properties of the iterations of random polynomials over finite fields\, related to Pollard rho method\, are commented.\nThen\ , if time allows\, we briefly show several results for random polynomials over finite fields that were obtained using other methodologies based on p robabilistic combinatorics. We conclude providing open problems for polyno mials over finite fields related to number theory.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/13/ END:VEVENT BEGIN:VEVENT SUMMARY:Marc Newman (Master thesis defense) DTSTART:20200826T130000Z DTEND:20200826T140000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/17 DESCRIPTION:Title: A Study of Mathematical and Practical Aspects of SIDH and CSIDH\nby Marc Newman (Master thesis defense) as part of University of Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nIn this the sis\, we consider two different supersingular isogeny-based Diffie-Hellman schemes: SIDH and CSIDH. We review the fundamental definitions underpinni ng isogeny-based cryptography including Diffie-Hellman key exchange\, elli ptic curves\, algebraic number theory\, and graph theory providing various examples supported by SageMath. We cover the mathematical bases\, protoco ls\, and hardness assumptions of SIDH and CSIDH as well as surveying some numerical analysis of the practical uses of the schemes from the literatur e. We review additional cryptographic schemes and applications which also utilize isogenies and offer a brief direct comparison between SIDH and CSI DH. Finally\, we state certain open questions pertaining to approaches to better understanding isogeny-based cryptography using related branches of mathematics.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/17/ END:VEVENT BEGIN:VEVENT SUMMARY:Amin Shokrollahi (EPFL (Switzerland)) DTSTART:20201021T130000Z DTEND:20201021T140000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/18 DESCRIPTION:Title: Chord Signaling\nby Amin Shokrollahi (EPFL (Switzerland)) as p art of University of Zurich (joint with Neuchatel) applied algebra seminar s\n\n\nAbstract\nCommunication of data on electrical wires between chips i s fast gaining prominence in the electronics industry. Because most of the components of the transmitter and the receiver of such links are analog\, rather than digital\, they don’t benefit as much from Moore’s law. On the other hand\, the need to transmit data ever faster calls for higher r ates of transmission over existing electrical wires. Since in this type of communication\, noise is highly frequency dependent\, higher transmission rates lead to much higher noise\, and therefore a much higher growth of p ower consumption than linear. The industry has long recognised this proble m as the “Interconnect bottleneck”. Fundamental solutions to this impo rtant problem have remained elusive\, however. A look at the capacity of t hese channels reveals that today we are only transmitting at anywhere betw een 1% to 4% of the capacity. Therefore\, at least on the surface\, there is a lot to be gained by applying methods from communication theory to thi s problem. However\, unlike many other systems such as wireless\, DSL\, sa tellite\, or optical communication\, the constraints on the chip-to-chip c ommunication system are very different: transmission rates are typically 1 000 times those encountered in wireless communication. On the other hand\, the energy consumed for the transmission and recovery of each bit is abou t 1000 times less than what is customary in wireless. Also\, latency requi rements are extremely stringent\, allowing only latencies up to very few n anoseconds. Therefore\, it is not possible to use fancy processing methods . In this talk I will introduce a new modulation scheme for chip-to-chip c ommunication which we call chordal codes. These codes are somewhat reminis cent of spatial MIMO systems\, and provide a first step towards a better u tilisation of the available communication bandwidth between chips. Current implementations of systems based on these codes show a large reduction of total power of the communication PHY and a large increase of the communic ation speed compared to other classical systems.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/18/ END:VEVENT BEGIN:VEVENT SUMMARY:Michel Lavrauw (Sabanci University) DTSTART:20201118T140000Z DTEND:20201118T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/19 DESCRIPTION:Title: Tensors in Finite Geometry\nby Michel Lavrauw (Sabanci Univers ity) as part of University of Zurich (joint with Neuchatel) applied algebr a seminars\n\n\nAbstract\nThe concept of tensor products is ubiquitous in the scientific literature. In this talk\, we restrict our attention to the tensor product of a finite number of finite-dimensional vector spaces. Th e bulk of the research on such tensor products assumes the underlying fiel d to be the real numbers or the complex numbers.\nWith the advancement of our knowledge and technology\, the need for efficient algorithms to verify certain properties or compute numerical data from a given tensor has beco me a very popular research topic. In the first part of this talk\, we will give a short introduction explaining the main concepts and research probl ems.\nIn the second part\, we will focus on the case where the underlying field is finite.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/19/ END:VEVENT BEGIN:VEVENT SUMMARY:Amin Sakzad (Monash University (Melbourne\, Australia)) DTSTART:20201125T090000Z DTEND:20201125T100000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/20 DESCRIPTION:Title: Middle-product learning with errors (MP-LWE): foundations\, applic ations\, and implementations\nby Amin Sakzad (Monash University (Melbo urne\, Australia)) as part of University of Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nIn this talk\, I will introduce a new variant\, MP-LWE\, of the Learning With Errors problem (LWE) making us e of the Middle Product between polynomials modulo an integer q. We exhibi t a reduction from the Polynomial-LWE problem (PLWE) parametrized by a pol ynomial f\, to MP-LWE\, which is defined independently of any such f. We a lso explore some applications of different variants of MP-LWE into Titaniu m\, a public-key encryption (PKE) scheme and MPSign\, a digital signature scheme proven secure in the quantum random oracle model (QROM). If time al lows\, I will introduce FACCT\, a fast\, compact and constant-time impleme ntation technique in lattice-based crypto with applications to well-establ ished PKE and DS schemes.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/20/ END:VEVENT BEGIN:VEVENT SUMMARY:Sabrina Sewer (University of Zurich) DTSTART:20201125T140000Z DTEND:20201125T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/21 DESCRIPTION:Title: Post-Quantum Cryptosystem FrodoPKE Based on the Learning with Erro rs Problem (Masters thesis defense)\nby Sabrina Sewer (University of Z urich) as part of University of Zurich (joint with Neuchatel) applied alge bra seminars\n\n\nAbstract\nIn view of the ongoing research on quantum com puters\, which will be able to break many of the cryptographic systems in use today\, the National Institute of Standardization and Technology (NIST ) has initiated a process to evaluate and standardize one or more quantum- resistant public-key encryption schemes. In this thesis\, we consider one of the submitted proposals\, the lattice-based encryption scheme FrodoPKE\ , which is based on the learning with errors problem (LWE). LWE has been e xtensively studied and cryptanalyzed by countless works. It is conjectured to be hard to solve based on assumptions about the worst-case hardness of standard lattice problems like GapSVP or SIVP. After an overview on the v arious hardness results on LWE and its versatility\, we closely examine th e design of FrodoPKE and its implementation. Finally\, we derive the optim al parameters and show the impact of a single parameter on the security.In view of the ongoing research on quantum computers\, which will be able to break many of the cryptographic systems in use today\, the National Insti tute of Standardization and Technology (NIST) has initiated a process to e valuate and standardize one or more quantum-resistant public-key encryptio n schemes. In this thesis\, we consider one of the submitted proposals\, t he lattice-based encryption scheme FrodoPKE\, which is based on the learni ng with errors problem (LWE). LWE has been extensively studied and cryptan alyzed by countless works. It is conjectured to be hard to solve based on assumptions about the worst-case hardness of standard lattice problems lik e GapSVP or SIVP. After an overview on the various hardness results on LWE and its versatility\, we closely examine the design of FrodoPKE and its i mplementation. Finally\, we derive the optimal parameters and show the imp act of a single parameter on the security.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/21/ END:VEVENT BEGIN:VEVENT SUMMARY:Francesco Pavese (POLYTECHNIC OF BARI (Italy)) DTSTART:20201202T140000Z DTEND:20201202T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/22 DESCRIPTION:Title: On cutting blocking sets and their codes\nby Francesco Pavese (POLYTECHNIC OF BARI (Italy)) as part of University of Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nLet PG(r\, q) be the r- dimensional projective space over the \nfinite fi\neld GF(q). A set Χ of points of PG(r\, q) is a cutting blocking set if for each hyperplane Π of PG(r\, q) the set Π ∩ Χ spans Π. Cutting blocking sets give rise t o saturating sets and minimal linear codes. Of particular interest are tho se having a size as small as possible. In this talk\, I will discuss known constructions of cutting blocking sets\, from which there arise minimal l inear codes whose length grows linearly with respect to their dimension. I will also present two new constructions of cutting blocking sets whose si zes are smaller than the known ones.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/22/ END:VEVENT BEGIN:VEVENT SUMMARY:Eduardo Camps (University of Neuchâtel (Neuchâtel)) DTSTART:20201209T140000Z DTEND:20201209T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/23 DESCRIPTION:Title: Monomial Decreasing Codes\nby Eduardo Camps (University of Neu châtel (Neuchâtel)) as part of University of Zurich (joint with Neuchate l) applied algebra seminars\n\n\nAbstract\nIn this talk\, beginning with t he original construction of polar codes\, we explore the monomial decreasi ng codes as a generalization of those in channels with strong symmetry. We analyze their parameters and their relation with other well-known familie s of codes.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/23/ END:VEVENT BEGIN:VEVENT SUMMARY:Martino Borello (Université de Paris 8 (Paris)) DTSTART:20201216T140000Z DTEND:20201216T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/24 DESCRIPTION:Title: Asymptotic performance of G-codes and uncertainty principle.\n by Martino Borello (Université de Paris 8 (Paris)) as part of University of Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nT he uncertainty principle is a very famous inequality in Physics\, Signal P rocessing\, and Harmonic Analysis. It compares the supports of functions a nd of their complex-valued Fourier transforms. In a recent paper by Evra\, Kowalski\, and Lubotzky a connection between the uncertainty principle an d the asymptotic performance of cyclic codes was pointed out. Note that th e existence of an asymptotically good family of cyclic codes is a problem open for more than half a century. In the first part of the talk\, we will present some recent results about the asymptotic performance of group cod es\, which are a generalization of cyclic codes. In the second part\, we w ill give an overview of conjectural and proved results about the uncertain ty principle over finite fields. A naive version of this principle\, which is verified by any finite field\, implies that there exist sequences of c yclic codes of length n\, arbitrary rate\, and minimum distance Ω(n^α) f or all 0 < α < 1/2.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/24/ END:VEVENT BEGIN:VEVENT SUMMARY:Katerina Mitrokotsa (University of St. Gallen) DTSTART:20210217T140000Z DTEND:20210217T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/25 DESCRIPTION:Title: Outsourcing computations to a cloud that you don't trust\nby K aterina Mitrokotsa (University of St. Gallen) as part of University of Zur ich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nIn this talk\, we discuss the problem of outsourcing computations to untrusted se rvers in multiple settings (i.e.\, multiple clients\, multiple servers). M ore precisely\, we discuss three new cryptographic primitives\, verifiable homomorphic secret sharing\, homomorphic multi-key authenticators and hom omorphic signcryption. The first two can be used when multiple clients wan t to outsource joint computations\, while the third when both verifiabilit y and proof of the data's authenticity need to be provided. We provide hig hlights on the proposed cryptographic constructions and discuss the main c hallenges that are overcome when we employ them.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/25/ END:VEVENT BEGIN:VEVENT SUMMARY:Andreia Venzin (University of Zurich) DTSTART:20210224T140000Z DTEND:20210224T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/26 DESCRIPTION:Title: Castelnuovo-Mumford Regularity and the Complexity of Gröbner Basi s Algorithms (Master's thesis defense)\nby Andreia Venzin (University of Zurich) as part of University of Zurich (joint with Neuchatel) applied algebra seminars\n\nAbstract: TBA\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/26/ END:VEVENT BEGIN:VEVENT SUMMARY:Sebastian Heri ((Solothurn)) DTSTART:20210303T140000Z DTEND:20210303T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/27 DESCRIPTION:Title: Classification and Construction of Self-Dual Convolutional Codes ( Master's thesis defense)\nby Sebastian Heri ((Solothurn)) as part of U niversity of Zurich (joint with Neuchatel) applied algebra seminars\n\nAbs tract: TBA\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/27/ END:VEVENT BEGIN:VEVENT SUMMARY:Magali Bardet (University of Rouen (DIR) (Rouen)) DTSTART:20210310T140000Z DTEND:20210310T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/28 DESCRIPTION:Title: Algebraic Attacks for solving the Rank Decoding and Minrank proble ms\nby Magali Bardet (University of Rouen (DIR) (Rouen)) as part of Un iversity of Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAb stract\nIn this talk\, I will present the recent improvements in algebraic techniques for solving the MinRank problem\, which is ubiquitous in multi variate and rank metric code based cryptography. Algebraic attacks now out perform the combinatorial ones that were considered state of the art up un til now. In the particular case of Fqm-linear codes in rank metric\, for s olving the Rank Decoding problem\, the attack is even more efficient\, and completely break the parameters of various schemes submitted to the NIST- PQC standardisation process for quantum-resistant public key cryptography. \n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/28/ END:VEVENT BEGIN:VEVENT SUMMARY:Umberto Martinez-Penas (University of Neuchâtel (Switzerland)) DTSTART:20210317T140000Z DTEND:20210317T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/29 DESCRIPTION:Title: Constructions of Codes in the Sum-Rank Metric\nby Umberto Mart inez-Penas (University of Neuchâtel (Switzerland)) as part of University of Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nT he sum-rank metric simultaneously extends the Hamming metric and the rank metric. Thus it provides a general theory that includes both classical and rank-metric codes. In this talk\, we will present several constructions o f Maximum Sum-Rank Distance (MSRD) codes. Each of these codes outperforms all possible MRD codes in the applications\, as they require polynomial fi eld sizes (in contrast with exponential field sizes for MRD codes). Our co nstructions include our previous construction of linearized Reed-Solomon c odes\, which simultaneously generalize Reed-Solomon codes and Gabidulin co des. At the end\, we will present Sum-Rank BCH codes\, a family of subfiel d subcodes of linearized Reed-Solomon codes with small field sizes and goo d parameters\, and which extend classical BCH codes.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/29/ END:VEVENT BEGIN:VEVENT SUMMARY:Alberto Ravagnani (Eindhoven University of Technology (Eindhoven)) DTSTART:20210324T140000Z DTEND:20210324T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/30 DESCRIPTION:Title: The Sparseness of MRD Codes\nby Alberto Ravagnani (Eindhoven U niversity of Technology (Eindhoven)) as part of University of Zurich (join t with Neuchatel) applied algebra seminars\n\n\nAbstract\nAn open question in coding theory asks whether or not MRD codes with the rank metric are d ense as the field size tends to infinity. In this talk\, I will briefly su rvey this problem and its connections with the theory of spectrum-free mat rices and semifields. I will then describe a new combinatorial method to o btain upper and lower bounds for the number of codes of prescribed paramet ers\, based on the interpretation of optimal codes as the common complemen ts of a family of linear spaces. In particular\, I will answer the above q uestion in the negative\, showing that MRD codes are almost always (very) sparse as the field size grows. The approach offers an explanation for the strong divergence in the behaviour of MDS and MRD codes with respect to d ensity properties. I will also present partial results on the sparseness o f MRD codes as their column length tends to infinity. The new results in t his talk are joint work with A. Gruica.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/30/ END:VEVENT BEGIN:VEVENT SUMMARY:Stefan Tohaneanu (University of Idaho (Idaho)) DTSTART:20210331T140000Z DTEND:20210331T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/31 DESCRIPTION:Title: Linear codes with prescribed projective codewords of minimum weigh t\nby Stefan Tohaneanu (University of Idaho (Idaho)) as part of Univer sity of Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAbstra ct\nConsider $C$\, an $[n\,k\,d]$-linear code. Every projective codeword o f minimum weight $d$ corresponds to a point in $\\mathbb P^{k-1}$\, and th ere are strong connections between the algebraic and geometric properties of these points and the parameters of $C$\, especially with the minimum di stance $d$. The most non-trivial connection is the fact that the Castelnuo vo-Mumford regularity of the coordinate ring of these points is a lower bo und for $d$. Conversely\, given a finite set of points $X$ in $\\mathbb P^ {k-1}$\, it is possible to construct linear codes with projective codeword s of minimum weight corresponding to $X$. We will discuss about these cons tructions\, and we will also look at the particular case when the construc ted linear code has minimum distance equal to the regularity.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/31/ END:VEVENT BEGIN:VEVENT SUMMARY:Hunter Lehmann (University of Kentucky (Kentucky)) DTSTART:20210421T130000Z DTEND:20210421T140000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/32 DESCRIPTION:Title: Automorphisms of Cyclic Orbit Codes\nby Hunter Lehmann (Univer sity of Kentucky (Kentucky)) as part of University of Zurich (joint with N euchatel) applied algebra seminars\n\n\nAbstract\nCyclic orbit codes are a prominent class of subspace codes\, generated by taking the orbit of a si ngle subspace of the finite field $F_{q^n}$ under an action of a Singer su bgroup. We are interested in classifying the isometry classes of these cod es for various parameters. In order to do this\, we show that the automorp hism group of a cyclic orbit code is heavily related to the smallest subfi eld of the ambient field which contains a generating subspace for the code . When there is no proper subgroup of the ambient field containing a gener ator for the code\, we see that any possible isometry is an element of the normalizer of the Singer subgroup.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/32/ END:VEVENT BEGIN:VEVENT SUMMARY:Romy Minko (University of Oxford (Oxford\, UK)) DTSTART:20210428T130000Z DTEND:20210428T140000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/33 DESCRIPTION:Title: Connections between cryptography and quantum gate synthesis\nb y Romy Minko (University of Oxford (Oxford\, UK)) as part of University of Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nWit h advancements in quantum computing\, the search for efficient algorithms for synthesising gates (the building blocks of quantum algorithms) using c ost-effective gate sets has become an important area of research. Interest ingly\, the problems underlying gate synthesis have a number of connection s with cryptography. The first half of this talk will cover the history of research in this area and an overview of the main concepts. In the second half\, I will present recent advancements in quantum gate synthesis\, whi ch adapt path-finding results from cryptography. This talk is aimed at res earchers without a background in quantum computing\, so will be fairly int roductory.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/33/ END:VEVENT BEGIN:VEVENT SUMMARY:Igor Semaev (University of Bergen (Norway)) DTSTART:20210505T130000Z DTEND:20210505T140000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/34 DESCRIPTION:Title: EHT public-key crypto-system and digital signatures\nby Igor S emaev (University of Bergen (Norway)) as part of University of Zurich (joi nt with Neuchatel) applied algebra seminars\n\n\nAbstract\nTwo works will be surveyed: "New Public-Key Crypto-System EHT" (A.Budroni\, I.Semaev) and "EHT Digital Signature Algorithm" (I.Semaev). The LWE (Learning with Erro rs) problem was introduced by Regev in 2005\, where an LWE based public-ke y encryption was described. The problem was there proved to be hard assumi ng the hardness of computing shortest non-zero vectors in general lattices . Since then several lattice-based public-key crypto-systems were invented . The NIST Post-Quantum Standardisation Process stimulated interest in dev eloping new quantum computer resistant public-key protocols. A number of s ubmissions to this competition are LWE or Ring LWE based. In the first wor k\, an LWE problem with a hidden trapdoor is introduced. It is used to con struct a new efficient public-key crypto-system EHT. The new system may be used as a KEM (Key Encapsulating Mechanism) too. It is significantly diff erent from LWE based NIST public-key encryption candidates\, e.g.\, FrodoK EM. The performance of EHT compares favourably with FrodoKEM. In the secon d work\, a similar idea is used to construct a new digital signature algor ithm. It is significantly different from NIST digital signature candidates . Forging EHT signatures may be reduced to solving Closest Vector Problem for a specific lattice with a small approximation factor. The parameters o f the new system are comparable to those of the NIST candidates.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/34/ END:VEVENT BEGIN:VEVENT SUMMARY:Habibul Islam (Indian Institute of Technology Patna (Bihar\, India )) DTSTART:20210512T110000Z DTEND:20210512T120000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/35 DESCRIPTION:Title: Construction of Quantum Codes using Constacyclic Codes\nby Hab ibul Islam (Indian Institute of Technology Patna (Bihar\, India)) as part of University of Zurich (joint with Neuchatel) applied algebra seminars\n\ n\nAbstract\nThere are several convenient ways to construct quantum codes from classical codes\, the CSS and Hermitian construction are two popular among them. Here\, we describe how classical (particularly\, constacyclic) codes have been successfully producing new and better quantum codes under these constructions. First\, we implement the idea over finite fields and then extend to non-commutative rings followed by commutative rings. From an application point of view\, many quantum codes outperforming the best-k nown codes are constructed.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/35/ END:VEVENT BEGIN:VEVENT SUMMARY:Vincent Neiger (Université de Limoges (France)) DTSTART:20210519T130000Z DTEND:20210519T140000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/36 DESCRIPTION:Title: Faster modular composition of polynomials\nby Vincent Neiger ( Université de Limoges (France)) as part of University of Zurich (joint wi th Neuchatel) applied algebra seminars\n\n\nAbstract\nThis talk is about a lgorithms for modular composition of univariate polynomials\, and for comp uting minimal polynomials. For two univariate polynomials a and g over a c ommutative field\, modular composition asks to compute h(a) mod g for some given h\, while the minimal polynomial problem is to compute h of minimal degree such that h(a) = 0 mod g. We propose algorithms whose complexity b ound improves upon previous algorithms and in particular upon Brent and Ku ng's approach (1978)\; the new complexity bound is subquadratic in the deg ree of g and a even when using cubic-time matrix multiplication. Our impro vement comes from the fast computation of specific bases of bivariate idea ls\, and from efficient operations with these bases thanks to fast univari ate polynomial matrix algorithms. We report on preliminary experimental re sults using our new Polynomial Matrix Library ( https://github.com/vneiger /pml ). Contains joint work with Seung Gyu Hyun\, Bruno Salvy\, Eric Schos t\, Gilles Villard.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/36/ END:VEVENT BEGIN:VEVENT SUMMARY:Sven Puchinger (Technische Universität München (München)) DTSTART:20210526T130000Z DTEND:20210526T140000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/37 DESCRIPTION:by Sven Puchinger (Technische Universität München (München) ) as part of University of Zurich (joint with Neuchatel) applied algebra s eminars\n\n\nAbstract\nLinearized Reed-Solomon (LRS) codes are sum-rank-me tric codes that fulfill the Singleton bound with equality. In the two extr eme cases of the sum-rank metric\, they coincide with Reed–Solomon codes (Hamming metric) and Gabidulin codes (rank metric). List decoding in thes e extreme cases is well-studied\, and the two code classes behave very dif ferently in terms of list size\, but nothing is known for the general case . In this talk\, we derive a lower bound on the list size for LRS codes\, which is\, for a large class of LRS codes\, exponential directly above the Johnson radius. Furthermore\, we show that some families of linearized Re ed–Solomon codes with constant numbers of blocks cannot be list decoded beyond the unique decoding radius. The results are joint work with Johan R osenkilde.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/37/ END:VEVENT BEGIN:VEVENT SUMMARY:Giuseppe Cotardo (University College Dublin (Dublin\, Ireland)) DTSTART:20211006T130000Z DTEND:20211006T140000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/38 DESCRIPTION:Title: Parameters of Codes for the Binary Asymmetric Channel\nby Gius eppe Cotardo (University College Dublin (Dublin\, Ireland)) as part of Uni versity of Zurich (joint with Neuchatel) applied algebra seminars\n\nAbstr act: TBA\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/38/ END:VEVENT BEGIN:VEVENT SUMMARY:Hiram Lopez Valdez (Cleveland State University (Ohio)) DTSTART:20211013T130000Z DTEND:20211013T140000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/39 DESCRIPTION:Title: The dual of an evaluation code\nby Hiram Lopez Valdez (Clevela nd State University (Ohio)) as part of University of Zurich (joint with Ne uchatel) applied algebra seminars\n\n\nAbstract\nIn this talk we study the dual and the algebraic dual of an evaluation code using standard monomial s and indicator functions. We show that the dual of an evaluation code is the evaluation code of the algebraic dual. Given linear codes C1 and C2 sp anned by standard monomials\, we describe a combinatorial condition to det ermine if C2 is monomially equivalent to the dual of C1. Moreover\, we giv e an explicit description of a generator matrix of the dual of C_1 in term s of that of C_1 and coefficients of indicator functions. This is a joint work with Ivan Soprunov and Rafael H. Villarreal.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/39/ END:VEVENT BEGIN:VEVENT SUMMARY:Ferdinando Zullo (Università degli Studi della Campania "Luigi Va nvitelli" (Italy)) DTSTART:20211103T140000Z DTEND:20211103T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/40 DESCRIPTION:Title: Linear sets in coding theory\nby Ferdinando Zullo (Università degli Studi della Campania "Luigi Vanvitelli" (Italy)) as part of Univers ity of Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAbstrac t\nLinear sets are a natural generalization of projective subspaces and of subgeometries in a projective space over a finite field. They were introd uced by Lunardon in 1999 to construct some examples of blocking sets\, whi ch are now known as linear blocking sets. In recent years\, they have been intensively used to construct\, to classify and to characterize many diff erent geometrical and algebraic objects like two-intersection sets\, compl ete caps\, translation spreads of the Cayley Generalized Hexagon\, transla tion ovoids of polar spaces\, semifield flocks\, finite semifields and lin ear codes. In this talk we will explore how the geometry of linear sets ca n give constructions and classification results in coding theory.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/40/ END:VEVENT BEGIN:VEVENT SUMMARY:Margreta Kuijper (The University of Melbourne (Melbourne\, Austral ia)) DTSTART:20211110T090000Z DTEND:20211110T100000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/41 DESCRIPTION:Title: Coding for packet erasure channels\nby Margreta Kuijper (The U niversity of Melbourne (Melbourne\, Australia)) as part of University of Z urich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nPacke t channels are subject to packet losses and these can be modeled as packet erasures where we know the lost packet's location but not its content. Ch annel coding provides a way to recover much of this content and thus prote ct against the impact of packet losses. The straightforward choice is then for MDS block codes. When coding against burst erasure patterns\, a large r playing field is provided by the class of convolutional codes and it has been shown that these can also be optimal. In many modern interactive app lications\, such as interactive video and telesurgery\, there are requirem ents to optimize latency\, throughput and error rate. Since 2004 two diffe rent approaches to the coding of packets have emerged in the literature. I n this talk I review some of the results obtained in each of these approac hes. In all of the approaches the decoding delay time is explicitly involv ed. This area currently attracts attention because of its relevance to ULL C\, ultra-reliable low-latency communications.\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/41/ END:VEVENT BEGIN:VEVENT SUMMARY:Roxana Smarandache (University of Notre Dame (Indiana USA)) DTSTART:20211117T140000Z DTEND:20211117T150000Z DTSTAMP:20260422T225703Z UID:AppliedAlgebra/42 DESCRIPTION:by Roxana Smarandache (University of Notre Dame (Indiana USA)) as part of University of Zurich (joint with Neuchatel) applied algebra se minars\n\nAbstract: TBA\n LOCATION:https://researchseminars.org/talk/AppliedAlgebra/42/ END:VEVENT END:VCALENDAR