CIMPA Research School and Workshop: Quasi-Cyclic and Related Algebraic Codes
CIMPA Research School and Workshop
QUASI-CYCLIC AND RELATED ALGEBRAIC CODES
August 27 - September 7, 2018
Middle East Technical University, Ankara, Turkey
APPLICATION PROCESS: Application for people not from Turkey must be done on the website of CIMPA. People from Turkey can apply filling in the form and sending it to firstname.lastname@example.org and email@example.com. Please note that the application deadline is April 22, 2018
This school is an introduction to subjects of algebraic coding theory and quasi-cyclic codes. The purpose of this school is to introduce young mathematicians and students to the foundations of the study of error-correcting codes by means of algebra over finite rings and finite fields. Powerful decoding algorithms and connections with geometric codes will be emphasized when relevant. Applications to convolutional codes will be presented. It will consist of several courses given by, Cem Güneri, Ferruh Özbudak, Buket Özkaya, Joachim Rosenthal, Peter Trifonov, Olfa Yemen and Jens Zumbrägel. Moreover there will be around 15 talks on topics related to School's concentration, given by different speakers. All courses and talks will be in English.
Administrative and scientific coordinators
- Cem Güneri, Sabancı University, TURKEY
- Ferruh Özbudak, Middle East Technical University, TURKEY
- Patrick Sole, Telecom ParisTech, FRANCE
- Erdal Arıkan, TURKEY
- Elisa Gorla, SWITZERLAND
- Burcu Gülmez Temür, TURKEY
- Cem Güneri, TURKEY
- San Ling, SINGAPORE
- Buket Ozkaya, TURKEY
- Ferruh Özbudak, TURKEY
- Joachim Rosenthal, SWITZERLAND
- Eda Tekin, TURKEY
- Olfa Yemen, TUNISIA
Local Organizing Committee
- Levent Aybak
- Damla Çenesiz
- Pınar Çomak
- Cem Güneri
- Murat Burhan İlter
- Kübra Kaytancı
- Kamil Otal
- Ferruh Özbudak
- Funda Özdemir
- Eda Tekin
- Burcu Gülmez Temür
- Hasan Bartu Yünüak
- Erdal Arıkan: Title: Polar coding: theory and applications
The lectures will cover four topics: Introduction to polarization and polar coding, performance analysis of polar codes, polar codes in 5G, and open problems.
- Serdar Boztaş: Title: Sequences, arrays, and distributions with applications.
- Heide Gluesing-Luerssen: Title: Introduction to Skew-Cyclic Block Codes.
Cyclic block codes form the showpiece of classical coding theory because they provide the algebraic framework for the construction of powerful codes such as Reed-Solomon codes and BCH codes. A natural generalization of these codes are the so-called skew-cyclic codes. They are based on skew-polynomial rings in one indeterminate. The only difference to a commutative polynomial ring is that in the skew version the indeterminate does not commute with its coefficients. This leads to intriguing phenomena when evaluating such polynomials at field elements and counting roots. In this course we will first discuss various properties of skew-polynomial rings. We will then move on and generalize the algebraic theory of cyclic codes to the skew case and finally discuss some recent results pertaining to the distance of skew-cyclic codes. The presentation is based on literature on skew-polynomial rings by Ore (1933) and Lam/Leroy (between 1988 and 2014) as well as literature on skew-cyclic codes by Boucher/Ulmer et al. (between 2009 and 2014), and on joint work with Fogarty (2015).
- Cem Güneri: Title: On Linear Complementary Dual (LCD) and Linear Complementary Pair (LCP) of Codes
LCD and LCP of codes have drawn much attention lately due to their applications in cryptography. The first lecture will focus on main properties and results on these classes of codes. In the second lecture, I will present joint work with Carlet, Özbudak, Özkaya and Sole on LCP of cyclic, quasi-cyclic and 2D cyclic codes.
- Frederich Ezerman: Title : Quantum Codes from Cyclic-Type Classical Codes.
We start by discussing established connections between classical algebraic codes and quantum error-control codes. Special attention will be given to the class of quantum stabilizer codes and their variants. We will review known quantum codes with good parameters from cyclic, nega-cyclic, consta-cyclic, and quasi-cyclic codes. Open research directions will be discussed, highlighting salient aspects from quasi-cyclic codes that remain to be investigated to come up with good or better quantum codes.
- Buket Özkaya: Title: Some Recent Results on LCD Codes
Linear complementary dual (LCD) codes are linear codes that intersect with their dual trivially. In the first lecture, a few constructions of LCD codes will be covered, then we will continue with the linear programming bound on the largest size of an LCD code of given length and minimum distance. The remaining lectures will cover special classes of LCD codes, namely quasi-cyclic, generalized quasi-cyclic and a particular class of one-generator quasi-twisted codes called multinegacirculant codes that are LCD will be discussed. All these classes of LCD codes have closely related algebraic structures, which allow us an easy characterization as well as an effective study of their asymptotic performance.
- Ferruh Özbudak: To be announced.
- Joachim Rosenthal: Title: Three Challenges coming from Claude Shannon.
In 1948/1949 Claude Shannon wrote two papers [Sha48,Sha49] which became the foundation of modern information theory. The papers showed that information can be compressed up to the `entropy', that data can be transmitted error free at a rate below the capacity and that there exist provable secure cryptographic systems. These were all fundamental theoretical result. The challenge remained to build practical systems which came close to the theoretical optimal systems predicted by Shannon.
In this overview talk we will explain how the first two challenges concerning coding theory have resulted in practical solutions which are very close to optimal. Then we explain why the gap between the practical implementation of cryptographic protocols with the theoretical result of Shannon is largest.
[Sha48] C.E. Shannon, ``A mathematical theory of communication'',
Bell Syst. Tech. J. 27, (1948), 379--423 and 623--656.
[Sha49] C.~E. Shannon, ``Communication theory of secrecy systems'',
Bell System Tech. J. 28, (1949), 656--715.
Title: An introduction to Convolutional Coding Theory
It is well known that a convolutional code is essentially a linear system defined over a finite field. Despite this well known connection convolutional codes have been studied in the past mainly by graph theoretic methods or by methods of linear algebra over the field of formal Laurent series.
In contrast to the situation of block codes there exist only few algebraic constructions. It is a fundamental problem in coding theory to construct convolutional codes with a designed distance which is as large as possible. Equally important is the construction of codes which can be efficiently decoded.
In a first part of the talk we will explain the connection between convolutional codes and linear systems via a natural duality. In doing so convolutional codes can be viewed as submodules of $R^n$ where $R:=F[z]$ is a polynomial ring and this identification allows one also to study properties using state space descriptions. On the algebraic side the set of all convolutional codes of a fixed degree is parameterized by the Grothendieck Quot Scheme. If the degree is zero this scheme describes a Grassmann variety. In this last situation the set of linear block codes of a fixed rate are parameterized.
In a second part of the talk we study codes with maximum or near maximum distance. Codes of a fixed rate and fixed McMillan degree which are maximum distance separable (MDS). On the application side such codes can be used in situations where errors appear as erasures. This has then a direct application for video streaming over packet switched systems like the Internet.
Title: An overview on Code based Cryptography
With the realization that a quantum computer would make many practically used public key cryptographic systems obsolete it became an important research topic to design public key systems which are expected to be secure even if a powerful quantum computer would exist.
In the talk we will explain about the major possible candidates for post-quantum cryptography and we will then concentrate on so called code based systems which were first proposed in 1978 by Robert McEliece who demonstrated how the hardness of decoding a general linear code up to half the minimum distance can be used as the basis for a public key crypto system.
- Patrick Sole: Title: On Long Algebraic Codes
- Peter Trifonov: Evaluation codes include well-known classes of Reed-Solomon, Reed-Muller and BCH codes. Connections between the evaluation codes and recently introduced polar codes will be presented. The construction of polar subcodes, which combines the ideas of evaluation codes and channel polarization will be presented. A fast decoding method for polar (sub)codes and some evaluation codes will be introduced. Connections with generalized concatenated codes and polar codes with big kernels will be presented. Titles: Reed-Solomon, Reed-Muller and BCH codes, Polar subcodes, Sequential decoding of polar subcodes and related codes, Generalized concatenated codes and polar codes with big kernels.
- Olfa Yemen: Skew polynomial rings have been on the forefront of research in coding theory as alternative ambient space for cyclic codes leading to the notion of skew-cyclic codes. They also provide an inroad into QC codes. Difficult factorization problems are raised. Joint work with Patrick Sole.
- Jens Zumbrägel: Title: Codes over rings gained considerable interest since the 1990's with the observation that several families of exceptionally good non-linear binary codes can be viewed as linear codes over the ring Z_4, equipped with the Lee metric. They have since sparked a fruitful interplay between algebraic coding theory and ring theory. In these lectures I discuss various current topics of ring-linear coding, including chain rings, Frobenius rings, weights, decoding, negacyclic codes, BCH bound and the MacWilliams extension theorem.
SCHEDULE: Click here.
All lectures will take place in Department of Mathematics, Cahit Arf Auditorium. For the location of the Mathematics department click here. The guest houses and the lecture hall for the congress are all within 10-20 minutes of walking distances to each other.
Travel Information and Accommodation
All the important locations in METU can be seen in this map.
Participants will be staying in METU dormitories which are about 15 minutes walking distance away from the Mathematics Department where the lectures will take place.
Please send your arrival/departure dates (including hours) to firstname.lastname@example.org or email@example.com. Upon your arrival to Esenboga Airport, you should first find the buses of "Havas". These vehicles are 40-50 passenger, white buses written "HAVAŞ" on them. This bus will take you to ASTI (bus terminal of Ankara ). You should inform the bus driver that you will get off the bus at ASTI before getting on the bus. It costs 11 TL and you will pay it cash in the bus. You don't have to make reservations or buy online tickets (for details about Havas buses click here. You will get off the bus at ASTI. There will be taxis around (the yellow cars). You can come to METU campus by taxi. In daytime (between 06:00-24:00), it costs about 25 TL. You should tell the taxi driver that you will go to METU (ODTÜ in Turkish) and you will get off in the dormitories region. You don't need to give the explicit address of the METU campus to the driver since it is very well known. The taxi will probably be stopped at one of the gates of METU Campus. The security will ask the purpose of your visit. You should tell them that you came for CIMPA Summer School. We will inform the security beforehand and you will be let in. You will get off the taxi at the dormitories region. You will be staying in EBI Guest House. When you arrive the dormitory, you should first see the person at the information desk. You should tell him/her that you are a participant of the CIMPA Summer School. He/she will show you your room. Some of the local organizers will be in the Campus.
For the location of the EBI Guest House click here.
For the location of the Mathematics department click here.
For information about METU campus click here.
Some food centers on METU Campus are:
Cafeteria (Yemekhane or kafeterya in Turkish) (for lunch only) For location click here.
Shopping Center (Carşı in Turkish) (for all kinds of meals) For location click here.
The following translations can be helpful during your transportation:
- When getting on Havas bus:
English: I want to go to ASTI. Please let me know when we get there.
Turkish: Asti ye gitmek istiyorum. Vardigimizda lutfen beni haberdar edin.
- When getting on Taxi:
English: I want to go to METU. I will get off at the dormitories region.
Turkish: ODTÜ ye gitmek istiyorum. Yurtlar bolgesinde inecegim.
- When entering METU Campus and at Dormitory:
English: I came here for CIMPA Summer School.
Turkish: CIMPA Yaz okulu icin geldim.
For general information about Turkey see: http://www.kultur.gov.tr/
For general information about Ankara see:
You can learn the exchange rates at the web page of Central Bank of Turkey:
The currency of Turkey is Turkish Lira (TL). Currency exchange facilities are available in all banks, airports and in many hotels. 24-hour cash machines providing banking services by different banks are located at suitable points throughout the 3 terminals of Ankara Esenboğa Airport. Credit cards are accepted at most restaurants and shops, the most widely used being MasterCard & Visa. Please kindly note that American Express, Diners Club and JCB Cards are not commonly accepted. Banks are generally open from 09:30 – 16:30 hours Monday – Friday. Turkey operates on 220 volts, 50 Hz, with round-prong European-style plugs that fit into recessed wall sockets/points. Check your appliances before leaving home to see what you'll need to plug in when you travel in Turkey. Many appliances such as laptop computers and digital cameras with their own power adapters can be plugged into either 120-volt or 220-volt sockets/points and will adapt to the voltage automatically. But you will need a plug adaptor that can fit into the recessed wall socket/point. Read the technical stuff on your power adapter to see "INPUT: A.C. 100-240V". If it reads that way, it can operate on either 120 or 220 voltage. If it says something like "INPUT: 100-125V", then it can't run on Turkey 's 220 volts and you'll need to bring a voltage converter. Local time is equal to GMT + 3 hours. Same time zone all over the country (seven hours ahead of U.S. eastern standard time).