_D 04.09.2007
_TPL 16h15-17h15 at BC-129
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 BC-129
AU Andrew Brown, ALGO+LMA, EPFL
TI Codes, Graphs and Graph-Based Codes
AB
_F NA4
_D 08.03.2007
_TPL 16h15-17h15 at BC-229
AU Andrew Brown, 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 BC-129
AU Mahdi Cheraghchi, 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 BC-129
AU Mahdi Cheraghchi, 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