# Program

The first Latin American Week on Coding and Information consists of a three-day school followed by a three-day workshop.
Students can apply for the whole week program and researchers for the workshop.
Our aim is to bring together researchers in all aspects of coding and information theory from all over the world, with special emphasis on Latin American researchers. The program aims to be attended by mathematicians, engineers and computer scientists. The LAWCI is an official satellite event of the International Congress of Mathematicians 2018, to be held in Rio de Janeiro in the following week.

__JULY 22-24 - INTENSIVE SCHOOL FOR GRADUATE STUDENTS__

Support kindly provided by IEEE - Information Theory Society

__CONFERENCE SUBJECTS__

• coding theory: error-correcting codes, decoding algorithms, related combinatorial problems;

• discrete mathematics and algorithmic tools related to these two areas including: finite fields, discrete geometry, lattices and related algebraic structures.

**CONFIRMED LECTURES**

**Daniel Panario (Carleton University, Canada)**

**Title:** Finite fields, applications and open problems

**Abstract:** After a brief revision of finite fields concepts we describe several applications of finite fields in combinatorics. These include Latin squares and several types of combinatorial
arrays and some of their applications and conexions to coding theory and cryptography. In the second lecture we review finite fields applications to cryptography, focusing on the
differential map, permutation polynomials. It time allows we also comment on how random a pseudorandom sequence is, and criteria for cryptographically good pseudorandom sequences. We provide open problems for each of these topics.

**Markus Grassl (Max Planck Institute, Erlangen, Germany)**

**Title:** Quantum Error-Correcting Codes: Discrete Maths meets Physics

**Abstract:** Quantum error-correcting codes (QECCs) are essential for building a quantum computer. Without assuming prior knowledge in quantum mechanics, the basic principles of QECCs will be introduced. This includes both the modeling of quantum information and quantum channels as well as the construction of QECCs based on classical error-correcting codes. It will be shown how the discrete structure enables efficient algorithms for encoding QECCs. Special attention will be given to CSS codes and stabilizer codes. In the second part, some more specific concepts will be highlighted, including code concatenation and quantum MDS codes.

**Max Costa (Unicamp, Brazil)**

**Title:** Information Theory Fundamentals and Multiple User Applications

**Abstract:** This seminar will review the fundamental concepts of information theory and focus on
applications in communications systems with multiple users. We will highlight the additive
white Gaussian noise cases and show that the search for capacity has an interesting
water filling interpretation. Multiple access, broadcast, interference and relay channels will be
considered as examples.

**Moshe Schwartz (Ben-Gurion University, Israel)**

**Title:** Coding for DNA Storage in Live Organisms

**Abstract:** DNA storage is slowly becoming a reality, bringing the promise of a
super-dense storage medium. Recent experiments show it is possible to
store information in living organisms, perhaps for unbounded time, as
we ourselves are evidence of. Obviously, any storage system is
susceptible to errors, and in the case of living DNA, mutations.

The coding literature has extensive knowledge on substitution errors,
and insertions/deletion, as these are common in other application. However,
a rarely studied but common form of mutation is duplication,
causing repetitions in DNA
sequences. Amazingly, the majority of the human genome is made up of
repeated sequences. Repetitions were shown to be connected with
diseases such as as cancer, myotonic dystrophy, Huntington's disease,
and important phenomena such as chromosome fragility, expansion
diseases, silencing genes, and rapid morphological
variation. Repetitions are common in other species as well, and are
claimed to be a major evolutionary force during vertebrate evolution.

In this talk we mathematically model string duplication, and ask
several coding-theoretic questions:

1. Is there new information created strictly by duplication? What is
the capacity of such systems? Is there a difference between the combinatorial (adversarial) model and the probabilistic model?

2. Can string duplication account for diversity? Can we reach every
possible substring?

3. How do we correct strings corrupted by duplication?

4. What happens when we mix string-duplication errors with point mutations?

The talk is based on joint works with Ohad Elishco, Farzad Farnoud,
Siddharth Jain, Yonatan Yehezkeally, and Jehoshua Bruck.

**Ram Zamir (Tel Aviv University, Israel) - ITSoc Distinguished Lecturer (TBC)**

**Title:** On the Superiority of Equiangular Tight Frames

**Abstract:** Over-complete bases (frames) can be thought of as analog codes for compression (compressed sensing) or for redundant signaling (noise and erasure correction). Their goodness can be determined by the eigenvalue distribution of a random subset of the frame vectors. We focus on the highly symmetric class of equiangular tight frames (ETF). We show first that if we keep the frame aspect ratio and the selection probability fixed, then the eigenvalue distribution of a random subset of ETF converges to the MANOVA distribution in the limit as the dimension goes to infinity. Secondly, random subsets of ETF minimize the first four moments among all frames of a given aspect ratio. Finally, we conjecture that ETFs minimize also the "inverse moment", i.e., the noise enhancement under subset inversion. If true, then ETFs are the most robust analog codes, and their noise enhancement is asymptotically given by the inverse moment of the MANOVA distribution.

**JULY 25-27 - WORKSHOP**

Call for participation

**INVITED SPEAKERS**

**Alexander Barg (University of Maryland, US)**

**Title:** Different facets of the repair problem

**Abstract:** The repair problem refers to correcting one or several erasures with a given error-correcting code using as little inter-nodal communication as possible. An information-theoretic lower bound on the repair bandwidth is known from the literature, and codes that meet it with equality are said to support optimal repair. In this talk we consider several versions of the repair problem, illustrating different techniques behind the construction of optimal codes. We begin with describing an approach to optimal-repair codes using the notion of interference alignment, presenting several families of codes with a number of additional properties (universality, error tolerance, optimal updates). Then we discuss optimal repair of Reed-Solomon codes, presenting codes from this family that support optimal repair of a single failed node or of several failed nodes. In the final part of the talk we discuss one more setting of the problem, where the task is to perform repair of several nodes in a distributed way, and again construct a family of codes with optimal repair bandwidth. Based on joint works with Min Ye and Itzhak Tamo.

**Gadiel Seroussi (Universidad de La República, Uruguay)**

**Title:** Q-ary Antipodal Matchings and Applications

**Abstract:** We study the problem of encoding arbitrary data into n x n arrays over the integer alphabet Q={0,1, ... , q-1}, all of whose row and column sums are at most n(q-1)/2. For this purpose, we define a q-ary antipodal matching to be a perfect matching in the bipartite graph with vertices corresponding to words of length m over Q, with left vertices corresponding to words with component sums greater m(q-1)/2, right vertices corresponding to words with component sums smaller than m(q-1)/2, and wherein two vertices are connected by an edge if one of the corresponding words dominates the other. We present two different constructions of efficiently computable q-ary antipodal matchings. We then show how such matchings can be used to implement the mentioned encodings into n x n q-ary matrices. The problem is motivated by the need to mitigate parasitic currents in envisioned multi-level memory systems based on crossbar arrays of resistive devices.

(Based on joint work with Erik Ordentlich and Ronny Roth.)

**Olgica Milenkovic (ECE Illinois, US)**

**Title:** String reconstruction problems inspired by problems in -omic data analysis

**Abstract:** String reconstruction problems frequently arise in many areas of genomic data processing and synthetic biology. In the most general setting, they may be described as follows: one is given a single or multiple copies of a coded or uncoded string, and the copies are subsequently subjected to some form of (random) processing such as fragmentation or repeated transmission through a noise-inducing channel. The goal of the reconstruction method is to obtain an exact or approximate version of the string based on the processed outputs. Examples of string reconstruction questions include reconstruction from noisy traces, reconstruction from substrings and k-decks and reconstruction from compositional substring information. We review the above and some related problems and then proceed to describe coding methods that lead to strings that can be reconstructed exactly from their noisy traces and substrings. In particular, we focus on DNA profile codes, hybrid reconstruction from traces and uniquely reconstructable code designs. In the process, we introduce new questions in the areas of restricted de Bruin graphs, counting of rational points in polytopes and string replacement methods.

(This is a joint work with Ryan Gabrys, Han Mao Kiah and Gregory Puleo.)

**Patrick Solé (CNRS, France)**

**Title:** Good algebraic codes exist

**Abstract:** We survey the algebraic structure and asymptotic performance of the
self-dual and LCD classes of
quasi-cyclic, quasi-twisted, and dihedral codes over finite fields and finite rings.
Of special interest is the case of low index: double circulant codes and four circulant codes.
An application to additive cyclic codes is given.

**Vinay Vaishampayan (City University of New York, USA)**

**Title:** Function Computation in Networked Environments

**Abstract:** We address communication issues that underlie computation of a function f(x,y,z,...)
when the variables x, y, z... are known at distinct nodes in a network. This falls under
the broad subject of communication complexity, and has surprising and deep implications
in areas like theoretical physics and economics. The first part of the talk will address
origins of the problem and theoretical developments, in both the computer science and
the information theory literature, with an attempt to bridge the ‘terminology’ gap. The
second part of the talk will address constructions—the problem of building codes for this
problem, tracing origins in quantization theory to recent developments. The last part will
address some of the current applications that are driving interest in the problem along with
open issues. Specifically, we will consider collaborative systems that arise in distributed
machine learning and and distributed security. The underlying communication required
for collaboration and cooperation, which can often place an unreasonable burden on a wide
area network, can be significantly reduced through careful code design.