EPFL

Algo+LMA

_D 04.09.2007 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Dr. Martin Hassner, Hitachi Global Storage Technologies TI Magnetic Data Storage Applications of Integrable Dynamical Systems AB Traditionally, in Magnetic Data Storage Channels, separate Digital Data Codes control the written Recorded Magnetization Patterns and its read Data Integrity, they are respectively labeled as “Modulation” and “Error Correction” Codes. Nonlinear Modulation Codes, efficiently implemented by Finite State Automata, with 30% redundancy were used throughout the Magnetic Data Storage Industry through the early 90's. However, due to the fact that the redundancy of these Nonlinear Modulation Codes could never be effectively used for algebraic error correction, current Modulation Codes redundancy is less than 1%. On the other hand, due to their practical disappearance, coding gains are severely limited by Nonlinear Magnetization Noise, which they were originally designed to minimize. In this talk I describe a class of Integrable Dynamical Systems, whose Dynamical Trajectories, effectively generated by Finite State Automata, can be labeled by Finite Field Codewords of a Linear Error Correcting Code. This State Space description, permits the simultaneous control of both the written Recorded Magnetization Patterns, as well as the read Data Integrity, within the same Nonlinear Modulation Code. The coding gain implication of such systems will be discussed. _F NA5

_D 07.05.2007 _TPL 15h30-16h30 at <a href=“http://plan.epfl.ch/?room=BC229”>BC-129</a> AU <a href=“http://algo.epfl.ch/index.php?p=group_members_andrew”>Andrew Brown</a>, ALGO+LMA, EPFL TI Codes, Graphs and Graph-Based Codes AB _F NA4

_D 08.03.2007 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC229”>BC-229</a> AU <a href=“http://algo.epfl.ch/index.php?p=group_members_andrew”>Andrew Brown</a>, ALGO+LMA, EPFL TI The zig-zag product and its expander families AB The zig-zag is a graph product enabling the recursive construction

of explicit expander families. These graphs are remarkable in that the proof of expansion relies on combinatorial rather than algebraic arguments, and is considerably simpler than that of other known constructions. We will first present the zig-zag product, its expansion properties and the constructions it yields. We will then explore the link with the semi-direct product of groups, which was used to show that expansion of Cayley graphs is not a group property (i.e. it depends on the choice of generators).

_F NA3

_D 23.02.2007 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU <a href=“http://algo.epfl.ch/index.php?p=group_members_mahdi”>Mahdi Cheraghchi</a>, ALGO+LMA, EPFL TI Computational Hardness and Explicit Constructions of Error Correcting Codes (Part II) AB We outline a procedure for using pseudorandom generators to construct binary codes with good properties, assuming the existence of sufficiently hard functions. Specifically, we give a polynomial time algorithm, which for every integers $n$ and $k$, constructs polynomially many linear codes of block length $n$ and dimension $k$, most of which achieving the Gilbert-Varshamov bound. The success of the procedure relies on the assumption that the exponential time class of $E := DTIME[2^{O(n)}]$ is not contained in the sub-exponential space class $DSPACE[2^{o(n)}]$. The methods used in this paper are by now standard within computational complexity theory, and the main contribution of this note is observing that they are relevant to the construction of optimal codes. We attempt to make this note self contained, and describe the relevant results and proofs from the theory of pseudorandomness in some detail. _F NA2

_D 15.02.2007 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU <a href=“http://algo.epfl.ch/index.php?p=group_members_mahdi”>Mahdi Cheraghchi</a>, ALGO+LMA, EPFL TI Computational Hardness and Explicit Constructions of Error Correcting Codes (Part I) AB We outline a procedure for using pseudorandom generators to construct binary codes with good properties, assuming the existence of sufficiently hard functions. Specifically, we give a polynomial time algorithm, which for every integers $n$ and $k$, constructs polynomially many linear codes of block length $n$ and dimension $k$, most of which achieving the Gilbert-Varshamov bound. The success of the procedure relies on the assumption that the exponential time class of $E := DTIME[2^{O(n)}]$ is not contained in the sub-exponential space class $DSPACE[2^{o(n)}]$. The methods used in this paper are by now standard within computational complexity theory, and the main contribution of this note is observing that they are relevant to the construction of optimal codes. We attempt to make this note self contained, and describe the relevant results and proofs from the theory of pseudorandomness in some detail. _F NA1