EPFL

Algo+LMA

_D 03.07.2008 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC229”>BC-229</a> AU Dr. Frederic Didier, ALGO, EPFL. TI New ideas on algebraic attacks against the filter generator AB The filter generator is one of the simplest stream ciphers and, even if it is not used directly in practice, the best known attacks against it are still not that efficient. One of the main line of attacks tries to exploit the high algebraic structure behind this system. We will explain how these algebraic attacks work and present some new ideas to improve them. _F NA7

_D 04.06.2008 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Bertrand Ndzana Ndzana, ALGO, EPFL. TI LT codes over Piecewise Stationary Channels AB Many communication channels models explicitly allow for sudden changes in the channel state during a transmission period. An abruptly changing channel model may be used to describe any system that experiences sudden, and persistent, burst of interference or degradation, such as a mobile wireless channel, an optical CDMA channel, or a military communication channel in the presence of jamming. In this talk, we present three LT codes based algorithms for estimation and incremental decoding over piecewise memoryless stationary channels (PSMC) with a bounded number of abrupt changes in channel statistics. In particular, as a class of PSMC, we consider binary symmetric channels with a crossover probability that changes a bounded number of times with no repetitions in the statistics. _F NA5

_D 28.05.2008 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Dr. Eimear Byrne, School of Mathematical Sciences, University College Dublin, Ireland. TI Advances on APN Functions AB A function f defined on a finite field L is called almost perfect nonlinear (APN) if there are at most two solutions to the equation f(x+a)-f(x) = b for each a,b in L with a nonzero. APN functions arise in coding theory, cryptography and sequences, especially for fields of characteristic 2. Monomial APN functions correspond to m-sequences and cyclic codes of minimum distance 5. Many APN functions are useful as substitution boxes of block-ciphers, having optimal resistance to a differential attack (by definition) and to a linear attack when defined on a field of odd degree over GF(2). For some time, it was conjectured that any APN function was equivalent to one of a short list of monomials and much work has been done towards a full classification. However, since 2006, a number of new families of APN functions have been discovered, inequivalent to any of the known power functions. In this talk we discuss these new results and related open problems. _F NA4

_D 30.04.2008 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Dr. Emina Soljanin, Bell Labs, Lucent and ALGO, EPFL. TI Coding-Based Distributed Storage in Large-Scale Networks AB We consider large-scale networks with N nodes, out of which K are in possession, (e.g., have sensed or collected in some other way) K data packets. In the scenarios in which network nodes are vulnerable because of, for example, limited energy or a hostile environment, it is desirable to disseminate the acquired information throughout the network so that each of the N nodes stores one (possibly coded) packet so that the original K source packets can be recovered later in a computationally simple way from any K(1+e) nodes for some small e > 0. We present two Fountain codes based distributed algorithms solving this problem. Unlike all previously developed schemes, our algorithms are truly distributed, that is, nodes do not know N, K or connectivity in the network, except in their own neighborhoods, and they do not maintain any routing tables. _F NA3

_D 23.04.2008 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Dr. Giovanni Cangiani, ALGO, EPFL. TI Raptor Codes in practice: Implementing a server for live TV streaming AB Internet television (IPTV) is a rapidly growing way of wasting internet bandwidth. Internet is global and makes it easy to implement a true Video on Demand (VoD) system. On the other hand, the most used transport protocol over the internet (TCP) is not well suited for large scale, long distance and good quality video streaming. A much better alternative is represented by standard UDP in conjunction with a robust forward error correction scheme. In this talk, I will describe in some details the implementation of a prototype system that is being developed at ALGO for streaming live television over the internet using UDP and systematic Raptor as protection layer. _F pyRaptorServer.pdf

_D 11.12.2007 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Dr. Arne Traulsen, Max-Planck-Institute for Evolutionary Biology, Germany TI Cooperation among selfish individuals AB A long standing problem in evolutionary biology is the evolution of cooperation. Why do cooperators prevail that support others at a cost to themselves, while defectors would obtain a higher payoff? Recently, similar problems appear in social communities on the internet. Some users just download from peer-to-peer networks, others also contribute high-quality files. Many people use wikipedia, but few write or improve the articles. Different mechanisms for the evolution of cooperation in these systems can be of interest. For example, visible tags can indicate that someone is willing to cooperate. Another possibility is indirect reciprocity, where individuals interact with others based on their reputation. _F NA1

_D 22.11.2007 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Dr. Vitaly Skachek, Claude Shannon Institute, University College Dublin, Ireland TI Expander Codes: Constructions and Bounds AB Low-density parity-check (LDPC) codes were introduced in 1962, but were almost forgotten. In recent years, they have attracted a lot of attention due to the practical efficiency of “average” LDPC codes. However, the performance of explicitely constructed LDPC codes still suffers performance disadvantages compared with “average” LDPC codes. The most promising approach for constructing specific LDPC codes is based on using expander graphs. Some of such codes (called expander codes) allow both linear-time encoding and decoding. Recently, it was shown that expander codes can attain capacity of a variety of channels, while the decoding error probability decreases exponentially with the code length. Moreover, it was recently shown that binary expander codes surpass the so-called Zyablov bound. In this talk, we first survey some recent results relating to expander codes. Then, we present improvements on the known bounds on the parameters of expander codes; in particular, we improve the lower bound on the minimum distance of these codes. We show that expander codes can be viewed as a concatenation of a certain nearly-MDS code with an appropriate inner code. The alphabet size of those nearly-MDS codes is smaller than the alphabet size of any similar known codes. This approach allows us to use GMD decoding to decode expander codes, leading to linear-time encoding and decoding algorithms. Further, we discuss other results related to expander codes. In particular, we discuss the decoding of expander codes that are based on a non-bipartite underlying graph. We present a new family of generalized expander codes, which is different from all known families of expander codes, and discuss its parameters. We focus on the rate of decrease of the decoding error probability for capacity-achieving codes, and show how this rate can be accelerated by using a concatenation with expander codes as outer codes. Finally, we focus on expander codes that use weak constituent codes, and in some cases, we derive lower and upper bounds on the minimum distance of the corresponding expander codes. _F NA