EPFL

Algo+LMA

_D 14.07.2005 AU Alyson Fletcher, UC Berkeley TI Estimation and Predictive Coding for Channels with Markovian Losses AB The reliable estimation of signals sent over noisy and lossy channels is a fundamental problem of communications and signal processing. This talk presents a general linear systems approach to analyzing and designing for such losses. The talk gives a new, general analysis of state estimation in “jump linear systems,” which are linear state space systems with discrete Markov dynamics. For communication problems, the discrete dynamics can model discrete changes in channel conditions such as sample erasures, while the continuous dynamics can model correlations in the source data to be transmitted. The main result provides a bound on the minimum achievable estimation error for a general jump linear system. A simple estimator that achieves this bound is also found and can be computed efficiently as a convex optimization with linear matrix inequality (LMI) constraints. A direct application of this framework provides bounds for tracking a time-varying signal from noisy observations with losses. Such bounds are relevant in designing sensor networks, where the communication of data may be subject to losses. Another application is a method for making standard predictive quantization robust to communication losses without channel coding. _F NA15

_D 07.07.2005 AU Professor Irit Dinur, Hebrew University TI The PCP Theorem by gap amplification AB Given a set of variables, and a set of local constraints over them (e.g.a 3CNF formula) define the “satisfiability-gap” of the system as the smallest fraction of unsatisfiable constraints. We will describe a new proof for the PCP theorem of [AS,ALMSS] based on an iterative gap amplification step. This step is a linear-time transformation that doubles the satisfiability gap of a given system. The transformation is based on applying ``graph powering“ to a system of constraints. It is proven via random-walk arguments, relying on expansion of the underlying graph structure. The main result can also be applied towards constructing *short* PCPs and locally-testable codes whose length is linear up to a polylog factor, and whose correctness can be probabilistically verified by making a constant number of queries. This answers an open question of Ben-Sasson et al. (STOC '04). _F Alex0705.pdf

_D 17.06.2005 AU Professor Alex Vardy, UC San Diego TI Multivariate interpolation decoding beyond the Guruswami-Sudan radius AB We first present a new decoding algorithm for Reed-Solomon codes. The algorithm attempts to decode $M-1$ transmitted codewords together,using $M$-variate polynomial interpolation. It is shown that if the channel errors are synchronized – occur in the same positions in all the $M-1$ codewords – this algorithm can, in principle, correct up to n ( 1 - R^{(M-1)/M} ) errors in a Reed-Solomon code of length $n$ and rate $R$, which is significantly higher than the Guruswami-Sudan decoding radius. The first nontrivial case $M = 3$ is will be discussed in detail. For this case, we show how to achieve trivariate interpolation using a gen eralized version of Koetter's iterative algorithm. We then recover the transmitted polynomials $f(X)$ and $g(X)$ from the output of this algorithm. In contrast to the bivariate case, the recovery of $f(X)$ and $g(X)$ requires at least TWO polynomials that satisfy the interpolation constraints. In fact, our recovery method is based upon computing certain resultants of the elements of a Groebner basis for the ideal of ALL such polynomials. In order to achieve deterministic decoding in polynomial time, our algorithm gradually reduces its decoding radius until the number of codewords within a certain decoding region becomes polynomially bounded. Thus it decodes beyond the Guruswami-Sudan radius only with a certain (high) probability. However, recently, we have constructed a family of algebraic codes that are provably decodable beyond the Guruswami-Sudan radius in the WORST-CASE. The key idea is to combine multivariate interpolation decoding with a kind of “inverted” algebraic-geometric construction. That is, instead of evaluating certain functions at the rational points of a curve, we evaluate the rational points THEMSELVES, viewed as pairs of polynomials over a subfield, at certain elements of the subfield. The equation that defines the curve thus provides the second polynomial we need in the recovery process. (*joint work with Farzad Parvaresh (University of California San Diego)) _F NA13

_D 30.07.2005 AU Leonard J. Schulman, California Institute of Technology TI Error-Correcting Codes for Automatic Control AB In many control-theory applications one can classify all possible states of the device by an infinite state graph with polynomially-growing expansion. In order for a controller to control or estimate the state of such a device, it must receive reliable communications from its sensors; if there is channel noise, the encoding task is subject to a stringent real-time constraint. We show a constructive on-line error correcting code that works for this class of applications. Our code is asymptotically optimal subject to the channel capacity constraint, is computationally efficient, and enables on-line estimation and control in the presence of channel noise. Our construction establishes a constructive and asymptotically-optimal analog of Shannon coding theorem for control applications. Joint work with Rafail Ostrovsky and Yuval Rabani. _F NA121

_D 02.06.2005 AU <a href=“http://www.math.unizh.ch/user/gmaze/”>Gérard Maze</a>,

<a href="http://www.math.unizh.ch/">math</a> - <a href="http://www.mnf.unizh.ch/">mnf</a> - <a href="http://www.unizh.ch/">Uni ZH</a>

TI A new result in the average case analysis of the binary GCD algorithm AB The binary Euclidean Algorithm is a variant of the classical

Euclidean algorithm. It avoids divisions and multiplications, except by powers of two, so is potentially faster than the classical algorithm on a binary machine. In this talk, we will define the binary Euclidean algorithm and outline its history from 1976 to nowadays. We will present Richard Brent's heuristic model and sketch the proof of the existence of a unique limiting distribution that plays a central role in this model.

_F NA12

_D 19.05.2005 AU <a href=“http://lthiwww.epfl.ch/~leveque/”> Olivier Leveque </a>,

<a href="http://lthiwww.epfl.ch">LTHI</a>, <a href="http://www.epfl.ch/">EPFL</a>

TI Scaling laws for ad hoc wireless networks AB Our aim is to obtain an information theoretic

confirmation of Gupta and Kumar's result on the transport capacity of ad hoc wireless networks. The approach we take leads us to the study of determinants of large random matrices. My intention for the talk is to shortly explain how do we get to the study of determinants and then to spend some time on the mathematics that we have recently developed for analyzing these determinants. This is joint work with Emmanuel Preissmann and Emre Telatar.

_F NA1005.pdf

_D 21.04.2005 AU <a href=“index.php?p=group_members_bertrand”>Bertrand Ndzana Ndzana</a>,

<a href="index.php">ALGO</a>, <a href="http://www.epfl.ch/">EPFL</a>

TI Universal lossless compression system based on Fountain codes AB In this talk, I will present a recent universal lossless

compressor that uses the Burrows-Wheeler block sorting Transform (BWT). This compression system is based on ratelsess Fountain codes. For this part, I consider only the binary sources. The second part of the talk will be based specifically on the non-binary sources like texts. We will look at some of the proposed approaches, and discuss their limitations. Some ideas for solving this problem will also be presented.

_F bertrand0405.pdf

_D 15.04.2005 AU <a href=“http://math.berkeley.edu/~bernd/ ”> Bernd Sturmfels (UC Berkeley </a>, UC Berkeley TI Solving the Likelihood Equations AB Given a model in algebraic statistics and some data, the

likelihood function is a rational function on a projective variety. We discuss algebraic methods for computing all critical points of this function, with the aim of identifying the local maxima in the probability simplex. Joint work with Serkan Hosten and Amit Khetan. Reference: http://front.math.ucdavis.edu/math.ST/0408270

_F NA9

_D 07.04.2005 AU <a href=“http://lthcwww.epfl.ch”>Nicolas Macris</a>,

<a href="http://lthcwww.epfl.ch">LTHC</a>, <a href="http://www.epfl.ch/">EPFL</a>

TI Applications of the Griffiths-Kelly-Sherman correlation inequality to LDPC codes AB It will be explained how a correlation inequality of

statistical mechanics can be applied to the theory of low density parity check codes. Two applications will be considered. The first one yields a proof that the growth rate can be computed exactly by iterative methods at least on the interval where it is concave. The second concerns sharp bounds for the "generalised EXIT curve" in the case of communication through a noisy gaussian channel.

_F NA8

_D 10.03.2005 AU <a href=“index.php?p=group_members_amin”>Amin Shokrollahi</a>,

<a href="index.php">ALGO+LMA</a>, <a href="http://www.epfl.ch/">EPFL</a>

TI Verification Decoding of Raptor Codes AB Verification decoding is a technique introduced by Luby and

Mitzenmacher for decoding LDPC codes on the q-ary symmetric channel for large q. In this talk we will adapt this technique to the setting of Raptor codes, and will derive a series of decoding algorithms for such codes on the q-ary symmetric channel for large q. We will analyze the algorithms, and derive optimal codes (in certain cases). We will also show that capacity-achieving Raptor codes on the BEC will lead to capacity-approaching codes on the q-ary symmetric channel in the limiting case of the considered algorithms. This is joint work with R. Karp and M. Luby.

_F amin0305.pdf

_D 24.02.2005 AU <a href=“http://algo.epfl.ch/index.php?p=group_members_lorenz”>Lorenz Minder</a>,

<a href="http://algo.epfl.ch/index.php">LMA</a>, <a href="http://www.epfl.ch/">EPFL</a>

TI Conjunctive Keyword Search AB The problem of securely searching data over an encrypted database is a relatively young cryptographic challenge. In this talk, we will look at some of the proposed approaches, and discuss their strenghts and weaknesses. In a second part, the use of codes for solving this problem will also be explored. _F lorenz0205.pdf

_D 10.02.2005 AU <a href=“http://algo.epfl.ch/index.php?p=group_members_mehdi”>Mehdi Molkaraie</a>,

<a href="http://algo.epfl.ch/index.php">ALGO</a>, <a href="http://www.epfl.ch/">EPFL</a>

TI Entropy Decomposition on Trees and Bounds on the Partition Function AB NA _F NA5

_D 27.01.2005 AU <a href=“http://lsirpeople.epfl.ch/hauswirth”>Manfred Hauswirth</a>,

<a href="http://lsirwww.epfl.ch/">Distributed Information Systems Laboratory</a>, <a href="http://www.epfl.ch/">EPFL</a>

TI Peer-to-peer Systems: Concepts, Architectures, and State-of-the-art AB NA _F NA4

_D 13.01.2005 AU <a href=“http://mlg.anu.edu.au/~smola”>Alex J. Smola</a>,

<a href="http://nicta.com.au/">NICTA</a>, <a href="http://www.anu.edu.au/">Australian National University</a>

TI Exponential Families and Kernel Methods AB NA _F NA3

_D 13.12.2004 AU <a href=“http://www.dcc.fc.up.pt/~barros”>Joao Barros</a>,

<a href="http://www.dcc.fc.up.pt/">Computer Science Dept.</a>, <a href="http://www.up.pt/">University of Porto</a>

TI Network Information Flow with Correlated Data AB Wireless sensor networks, i.e. networks of tiny, low-cost devices with limited sensing, processing and transmission capabilities, have sparked a fair amount of interest in information theory problems involving correlated information sources and large-scale wireless networks. In the first part of this talk, we will model the sensor network as directed graph G with M+1 nodes, each of which observes a distinct source U(i), i=0,…,M. The sources U(0),U(1),…., U(M) are correlated in the sense that they are generated according to the joint probability distribution p(u(0),u(1),…,u(M)). We assume that each edge e(i,j) in G, represents a discrete memoryless channel of capacity C(i,j) over which nodes i and j can communicate, such that after multiple rounds of communication the data collector node 0 is able to provide a perfect reconstruction of all the source data. The goal of the problem is to characterize the conditions on the sources and the channels under which this reconstruction is possible. For this setup, we will present a complete solution. The proof, which uses classical network flow methods offers two fundamental insights: (a) Separate source/channel coding is optimal in any network where theinterference is dealt with at the MAC layer by creating independent links between nodes. (b) In such networks, the properties of Shannon information are exactly identical to those of water in pipes – information is a flow. The second part of this talk will be entirely dedicated to the practical implications of this result. After presenting an optimal protocol stack for this class of sensor networks, we will discuss the tractability of a natural network decision problem and give an example of information theoretically optimal routing. Joint work with Sergio D. Servetto, Cornell University _F barros1204.pdf

_D 02.12.2004 AU <a href=“http://algo.epfl.ch/index.php?p=group_members_payam”>Payam Pakzad</a>,

<a href="http://algo.epfl.ch/index.php">ALGO</a>, <a href="http://www.epfl.ch/">EPFL</a>

TI Probabilistic Juction Trees AB NA _F payam1204.pdf

_D 18.11.2004 AU <a href=“http://alg-geo.epfl.ch/”>Frederique Oggier</a>,

<a href="http://bernoulli.epfl.ch/en/index.php">Institut de mathematiques Bernoulli</a>, <a href="http://www.epfl.ch/">EPFL</a>

TI From the Golden Coe to Perfect Space-Time Block Code AB NA _F frederique1104.pdf