http://algo.epfl.ch/ 2012-05-16T22:53:08+02:00 http://algo.epfl.ch/ http://algo.epfl.ch/lib/images/favicon.ico text/html 2009-04-07T11:35:13+02:00 http://algo.epfl.ch/en/group/seminars/2003-2004?rev=1239096913&do=diff Algo seminars 2003 - 2004 text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20031028?rev=1284388232&do=diff abstract NA text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20031110?rev=1284388232&do=diff abstract NA text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20031124?rev=1284388232&do=diff abstract NA text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20031208?rev=1284388232&do=diff abstract NA text/html 2009-04-07T11:45:44+02:00 http://algo.epfl.ch/en/group/seminars/2004-2005?rev=1239097544&do=diff Algo seminars 2004 - 2005 text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20040110?rev=1284388232&do=diff abstract NA text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20040319?rev=1284388232&do=diff abstract NA text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20040407?rev=1284388232&do=diff abstract NA text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20040510?rev=1284388232&do=diff abstract NA text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20040517?rev=1284388232&do=diff abstract NA text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20040527?rev=1284388232&do=diff abstract NA text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20040603?rev=1284388232&do=diff abstract NA text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20040608?rev=1284388232&do=diff abstract NA text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20041118?rev=1284388232&do=diff abstract NA text/html 2009-04-07T12:21:05+02:00 http://algo.epfl.ch/en/group/seminars/20041202?rev=1239099665&do=diff [Full presentation] text/html 2009-04-07T12:13:43+02:00 http://algo.epfl.ch/en/group/seminars/20041213?rev=1239099223&do=diff abstract 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… text/html 2009-04-07T11:45:15+02:00 http://algo.epfl.ch/en/group/seminars/2005-2006?rev=1239097515&do=diff Algo seminars 2005 - 2006 text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20050113?rev=1284388232&do=diff abstract NA text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20050127?rev=1284388232&do=diff abstract NA text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20050210?rev=1284388232&do=diff abstract NA text/html 2009-04-07T12:17:36+02:00 http://algo.epfl.ch/en/group/seminars/20050224?rev=1239099456&do=diff abstract 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. text/html 2009-04-07T12:12:40+02:00 http://algo.epfl.ch/en/group/seminars/20050310?rev=1239099160&do=diff abstract 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-app… text/html 2009-04-07T12:28:31+02:00 http://algo.epfl.ch/en/group/seminars/20050407?rev=1239100111&do=diff abstract 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. text/html 2009-04-07T12:27:38+02:00 http://algo.epfl.ch/en/group/seminars/20050415?rev=1239100058&do=diff abstract 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> text/html 2009-04-07T12:14:48+02:00 http://algo.epfl.ch/en/group/seminars/20050421?rev=1239099288&do=diff abstract 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. text/html 2009-04-07T12:26:30+02:00 http://algo.epfl.ch/en/group/seminars/20050519?rev=1239099990&do=diff abstract 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 Telat… text/html 2009-04-07T12:25:42+02:00 http://algo.epfl.ch/en/group/seminars/20050602?rev=1239099942&do=diff abstract 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. text/html 2009-04-07T12:10:44+02:00 http://algo.epfl.ch/en/group/seminars/20050617?rev=1239099044&do=diff abstract 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… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20050707?rev=1284388232&do=diff abstract 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 pro… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20050714?rev=1284388232&do=diff abstract 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 … text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20050730?rev=1284388232&do=diff abstract 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 as… text/html 2009-04-07T12:19:38+02:00 http://algo.epfl.ch/en/group/seminars/20051031?rev=1239099578&do=diff abstract There has recently been and continues to be a large amount of work in cellular commercial standards that is focused on multimedia delivery using broadcast and multicast channels. The reasons for these standardization efforts are self-evident: while cellular services become ever more popular and as cellular multimedia applications grow richer, the available bandwidth for delivering these services remains fairly limited, and thus broadcast/multicast delivery is the only viable solution… text/html 2009-04-07T12:32:28+02:00 http://algo.epfl.ch/en/group/seminars/20051117?rev=1239100348&do=diff abstract Error-correcting codes which employ iterative decoding algorithms are now considered state of the art in communications. There is now a large collection of code families which achieve a small gap to capacity with feasible decoding complexity. Examples are low-density parity-check (LDPC) codes, irregular repeat-accumulate (IRA) codes, and Raptor codes. For each of these code families, one can construct code sequences which provably achieve capacity on the binary erasure channel (BEC)… text/html 2009-04-07T12:31:43+02:00 http://algo.epfl.ch/en/group/seminars/20051201?rev=1239100303&do=diff abstract Given positive integers $n$ and $d$, let $A_2(n,d)$ denote the maximum i size i of a binary code of length $n$ and minimum distance $d$. The well-known Gilbert-Varshamov bound asserts that $A_2(n,d) \geq 2^n/V(n,d-1)$, where $V(n,d) = \sum_{i=0}^d {n \choose i}$ is the volume of a Hamming sphere of radius $d$. We show that, in fact, there exists a positive constant $c$ such that $A_2(n,d) \geq c \frac{2^n}{V(n,d-1)} \log_2 V(n,d-1)$. This exceeds the Gilbert-Varshamov bound by a fact… text/html 2009-04-07T12:15:59+02:00 http://algo.epfl.ch/en/group/seminars/20051215?rev=1239099359&do=diff abstract There is a fundamental relationship between belief propagation (BP) and maximum a posteriori (MAP) decoding which is reminiscent of Maxwell's construction in thermodynamics. BP and MAP decoding are connected to a common object which is the (G)EXIT function. The (general) area theorem is the central element in this theory. As a main application of the area theorem it can be shown that a Maxwell-type construction determines the MAP threshold from the BP (G)EXIT curve. But there are many … text/html 2009-04-07T11:36:39+02:00 http://algo.epfl.ch/en/group/seminars/2006-2007?rev=1239096999&do=diff Algo seminars 2006 - 2007 text/html 2009-04-07T12:30:15+02:00 http://algo.epfl.ch/en/group/seminars/20060428?rev=1239100215&do=diff abstract It is well-known that there is an efficient method for decrypting/signing with RSA when the secret exponent d is small modulo p-1 and q-1. We call such an exponent d a small CRT-exponent. It is one of the major open problems in attacking RSA whether there exists a polynomial time attack for small CRT-exponents, i.e. a result that can be considered as an equivalent to the Wiener and Boneh-Durfee bound for small d. At Crypto 2002, May presented a partial solution in the case of an RSA mo… text/html 2009-04-07T12:16:45+02:00 http://algo.epfl.ch/en/group/seminars/20060505?rev=1239099405&do=diff abstract Recently, attention has been focused on wireless networks. Methods to exploit diversity using the antennas of different users in a cooperative way have been studied, in order to look for the diversity known to be achieved in the multiple antennas point to point case. We consider a wireless network where a transmitter and a receiver are distinguished, with enough computational capacity and power to encode/decode the data, and use several antennas to transmit/receive the signal. The o… text/html 2009-04-14T10:16:02+02:00 http://algo.epfl.ch/en/group/seminars/2007-2008?rev=1239696962&do=diff Algo seminars 2007 - 2008 text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20070215?rev=1284388232&do=diff abstract 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… text/html 2009-04-07T11:03:20+02:00 http://algo.epfl.ch/en/group/seminars/20070223?rev=1239095000&do=diff abstract 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… text/html 2009-04-07T12:06:32+02:00 http://algo.epfl.ch/en/group/seminars/20070308?rev=1239098792&do=diff abstract 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. text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20070507?rev=1284388232&do=diff abstract text/html 2010-09-13T16:30:31+02:00 http://algo.epfl.ch/en/group/seminars/20070604?rev=1284388231&do=diff abstract 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, burs t 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 increm ental d… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20070703?rev=1284388232&do=diff abstract 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 algebr aic structure behind this system. We will explain how these algebraic attacks wo rk and present some new ideas to improve them. text/html 2009-04-07T11:17:39+02:00 http://algo.epfl.ch/en/group/seminars/20070904?rev=1239095859&do=diff abstract 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 Co… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20071122?rev=1284388232&do=diff Abstract Low-density parity-check (LDPC) codes were introduced in 1962, but were almost forgotte n. 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 s till suffers performance disadvantages compared with “average” LDPC codes. The most promis ing approach for constructing specific LDPC codes is based on using expander graphs. Some of such codes (called expander codes) … text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20071211?rev=1284388232&do=diff Abstract A long standing problem in evolutionary biology is the evolution of cooperati on. Why do cooperators prevail that support others at a cost to themselves, whil e defectors would obtain a higher payoff? Recently, similar problems appear in s ocial communities on the internet. Some users just download from peer-to-peer ne tworks, others also contribute high-quality files. Many people use wikipedia, bu t few write or improve the articles. Different mechanisms for the evolution of c ooperat… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/2008-2009?rev=1284388232&do=diff Algo seminars 2008 - 2009 text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20080430?rev=1284388232&do=diff Abstract We consider large-scale networks with N nodes, out of which K are in possessi on, (e.g., have sensed or collected in some other way) K data packets. In the sc enarios in which network nodes are vulnerable because of, for example, limited e nergy or a hostile environment, it is desirable to disseminate the acquired info rmation 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 computa… text/html 2010-09-13T16:30:31+02:00 http://algo.epfl.ch/en/group/seminars/20080528?rev=1284388231&do=diff Abstract 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 co rrespond to m-sequences and cyclic codes of minimum distance 5. Many APN functio ns are useful as substitution boxes of block-ciphers, having optimal resistance to a di… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20081001?rev=1284388232&do=diff abstract Classical results from the 1970's state that a random subspace of R^N of dimension N/2 has “distortion” O(1) w.h.p where the distortion is measured by sqrt{N} times the largest ratio of the L_2 to L_1 norms of a vector in the subspace. (So O(1) distortion means each vector in the subspace has its mass spread nearly evenly over a constant fraction of the coordinates.) This result is a particular example of the use of the probabilistic method, a technique which is ubiquitous in asymptoti… text/html 2010-09-13T16:30:31+02:00 http://algo.epfl.ch/en/group/seminars/20081015?rev=1284388231&do=diff abstract All known methods for integer multiplication (except the trivial school method) are based on some version of the Chinese Remainder Theorem. Most methods reduce integer multiplication to fast polynomial multiplication, which is a scheme for the evaluation of polynomials, multiplication of their values, followed by interpolation. For more than 35 years, the fastest known method for integer multiplication has been the Schönhage-Strassen algorithm. It is based on the fast Fourier transform… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20081029?rev=1284388232&do=diff abstract LT codes are the first class of universal Fountain codes. They are well-suited for fault-tolerant transmission of information over the Internet, modeled as a binary erasure channel. We briefly describe these codes and their decoding algorithms, introduce the concept of a state in which a decoder can be at any given instance during decoding, and describe a recursion for the state-generating function of the LT decoder derived by Karp, Luby and Shokrollahi. Starting fro… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20081110?rev=1284388232&do=diff abstract I will give a series of lectures that will probably last until the end of the semeser, each one hour, on the main ideas that have led to the currently fastest known matrix multiplication algorithms. I will start with the “classical” approach of bilinear complexity, deformations, and its culmination given by the Laser method of Strassen and its extensions by Coppersmith and Winograd. I will isolate and emphasize the combinatorial constructions that underly these algorithms. In the secon… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20081117?rev=1284388232&do=diff abstract I will give a series of lectures that will probably last until the end of the semeser, each one hour, on the main ideas that have led to the currently fastest known matrix multiplication algorithms. I will start with the “classical” approach of bilinear complexity, deformations, and its culmination given by the Laser method of Strassen and its extensions by Coppersmith and Winograd. I will isolate and emphasize the combinatorial constructions that underly these algorithms. In the secon… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20081120?rev=1284388232&do=diff abstract A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently broadcasts the signals and there is interference among transmissions. Recently, Avestimehr, Diggavi and Tse proposed a linear binary deterministic model that takes into account the shared nature of wireless channels, focusing on the signal inter… text/html 2010-09-13T16:30:31+02:00 http://algo.epfl.ch/en/group/seminars/20081124?rev=1284388231&do=diff abstract I will give a series of lectures that will probably last until the end of the semeser, each one hour, on the main ideas that have led to the currently fastest known matrix multiplication algorithms. I will start with the “classical” approach of bilinear complexity, deformations, and its culmination given by the Laser method of Strassen and its extensions by Coppersmith and Winograd. I will isolate and emphasize the combinatorial constructions that underly these algorithms. In the secon… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20081203?rev=1284388232&do=diff abstract I will give a series of lectures that will probably last until the end of the semeser, each one hour, on the main ideas that have led to the currently fastest known matrix multiplication algorithms. I will start with the “classical” approach of bilinear complexity, deformations, and its culmination given by the Laser method of Strassen and its extensions by Coppersmith and Winograd. I will isolate and emphasize the combinatorial constructions that underly these algorithms. In the secon… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20081208?rev=1284388232&do=diff abstract I will give a series of lectures that will probably last until the end of the semeser, each one hour, on the main ideas that have led to the currently fastest known matrix multiplication algorithms. I will start with the “classical” approach of bilinear complexity, deformations, and its culmination given by the Laser method of Strassen and its extensions by Coppersmith and Winograd. I will isolate and emphasize the combinatorial constructions that underly these algorithms. In the secon… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20081211?rev=1284388232&do=diff Abstract Internet television (IPTV) is a rapidly growing way of wasting internet bandw idth. 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 intern et (TCP) is not well suited for large scale, long distance and good quality vide o streaming. A much better alternative is represented by standard UDP in conjunc tion with a robust forward error correction scheme. In this talk, I will describ e in so… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20081215?rev=1284388232&do=diff abstract I will give a series of lectures that will probably last until the end of the semeser, each one hour, on the main ideas that have led to the currently fastest known matrix multiplication algorithms. I will start with the “classical” approach of bilinear complexity, deformations, and its culmination given by the Laser method of Strassen and its extensions by Coppersmith and Winograd. I will isolate and emphasize the combinatorial constructions that underly these algorithms. In the secon… text/html 2010-11-03T09:35:33+02:00 http://algo.epfl.ch/en/group/seminars/2009-2010?rev=1288773333&do=diff Algo seminars 2009 - 2010 text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20090112?rev=1284388232&do=diff abstract I will give a series of lectures that will probably last until the end of the semeser, each one hour, on the main ideas that have led to the currently fastest known matrix multiplication algorithms. I will start with the “classical” approach of bilinear complexity, deformations, and its culmination given by the Laser method of Strassen and its extensions by Coppersmith and Winograd. I will isolate and emphasize the combinatorial constructions that underly these algorithms. In the secon… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20090114?rev=1284388232&do=diff abstract We study combinatorial group testing schemes for learning $d$-sparse boolean vectors using highly unreliable disjunctive measurements. We consider an adversarial noise model that only limits the number of false observations, and show that any noise-resilient scheme in this model can only approximately reconstruct the sparse vector. On the positive side, we take this barrier to our advantage and show that approximate reconstruction (within a satisfactory degree of approximation) allows … text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20090121?rev=1284388232&do=diff abstract It has been known for a long time that the class of self-dual codes over a finite field is asymptotically good and that it attains the Gilbert-Varshamov bound. Stichtenoth showed that over fields with quadratic cardinality self-dual codes even attain the Tsfasman-Vladut-Zink bound. In this talk I will explain how using some well-known facts about quadratic forms and a new cubic tower of curves an analogous result can be obtained for self-dual codes over cubic finite fields. This new co… text/html 2009-06-06T12:16:27+02:00 http://algo.epfl.ch/en/group/seminars/20090225?rev=1244283387&do=diff abstract The classical Hermite constant acounts for the highest density of a regular sphere packing. A generalised version of it consists more broadly in bounding the size of the biggest minimal sub-structure in some given object, such as the height of a rational flag (nested vector spaces) of fixed shape on some number field of given dimension. We shall show how one can obtain some values of this new Hermite constant, how to characterize the flags that locally achieve the constant in the spi… text/html 2010-09-13T16:30:31+02:00 http://algo.epfl.ch/en/group/seminars/20090304?rev=1284388231&do=diff abstract The PAC model (Valiant, CACM '84) is one of the central models studied in computational learning theory. There is evidence that many specific classes of functions (e.g. intersections of half-spaces, parity functions with noise, etc.) are hard to learn by efficient algorithms, and cryptographic assumptions imply that learning small circuits is hard. We say that PAC learning is hard if no efficient algorithm can learn all functions computable by small circuits. In this talk, we show t… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20090311?rev=1284388232&do=diff abstract I present several results concerning a pseudorandom generator introduced by Rueppel and Massey in 1985. It is a streamed version of the NP-complete subset sum problem, where the stream is given by a linearly recurrent sequence. I start with several attacks on this generator, some of which are rigorously proven while others are heuristic. They work when one “half” of the secret is given, either the linearly recurrent stream or the summands in the problem. In a typical setting, this red… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20090325?rev=1284388232&do=diff abstract Smart antennas promise a clear advantage in multi-service traffic scenario in comparison with non-adaptive antenna techniques. It is generally accepted that the adaptive antennas technique will be a key enable for the success of the European third generation mobile communication system known as Universal Mobile Telecommunication System (UMTS). The first part of this research presents two types of smart antenna systems: switched beam antennas and adaptive arrays. It introduces statistic… text/html 2009-06-06T12:18:33+02:00 http://algo.epfl.ch/en/group/seminars/20090401?rev=1244283513&do=diff abstract The topic of my talk is QoS network coding. I’ve divided my presentation to two parts. In the first part, I will briefly explain the algorithm that I suggested in my thesis for providing QoS using network coding. The algorithm is a decentralized optimization method to find minimum cost QoS flow subgraphs in network coded multicast schemes. The main objective of this algorithm is to find minimum cost subgraphs that also satisfy user-specified QoS constraints, namely, rate and end… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20090504?rev=1284388232&do=diff abstract Low density lattice codes (LDLC) are recently proposed lattice codes that can be decoded by linear-time iterative decoding and approach the capacity of the additive white Gaussian noise (AWGN) channel. In LDLC a codeword x is generated directly at the n-dimensional Euclidean space as a linear transformation of a corresponding integer message vector b, i.e., x = Gb, where H = G−1 is restricted to be sparse. In LDLC the messages are pdf's of the component of the real codeword x. In order… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20090506?rev=1284388232&do=diff abstract The cohomology groups of arithmetic groups can, in principle, be computed explicitely. On the other hand we have some speculative ideas about the connection between the structure of these cohomology groups and the arithmetic properties of special values of L-functions. This allows us to make some interesting numerical experiments. text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20090603?rev=1284388232&do=diff abstract Low-density parity-check (LDPC) codes have been the focus of much research over the past decade due to their capacity approaching performance even when decoded using low-complexity decoding algorithms such as iterative message passing algorithms. Traditional message passing decoders are based on belief propagation and operate on a graphical representation of the code known as the Tanner graph. While optimal only for loop-free graphs, they work surprisingly well on loopy graphs. However… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20090625?rev=1284388232&do=diff abstract Given k = 2^q random lists of n-bit vectors, L_1, ..., L_k, each list containing m vectors, we wish to find an XOR x_1 + ... + x_k (with x_i in L_i) equalling to zero. This problem has numerous applications for example in coding theory and in cryptography. The problem is likely to have a solution if m > 2^{n/k}, and the classical time/space tradeoff solves it in time O(2^{n/2} poly(log(m), n, k)). However, if the list size m is much larger, specifically if m >= 2^{n / (q + 1)}, the … text/html 2009-10-07T11:32:50+02:00 http://algo.epfl.ch/en/group/seminars/20091014?rev=1254907970&do=diff abstract Authentication and secrecy are two crucial concepts in cryptography and information security. Although independent in their nature, various scenarios require that both aspects hold simultaneously. For information-theoretic/unconditional security (i.e. robustness against an attacker that has unlimited computational resources), authentication and secrecy codes have been investigated for quite some time. In this talk, I will give an overview and discuss recent results from a combinatorial… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20091111?rev=1284388232&do=diff abstract Belyi's theorem establishes an equivalence between the arithmetic property of a curve being defined on a number field and the geometric and analytic property of the existence of a meromorphic function with at most critical values. Grothendieck's idea in his Sketch of a Program was to utilize this idea to define a natural action of the Absolute Galois Group on families of graphs satisfying certain necessary properties on topological surfaces, and thereby develop a new tool for gaining… text/html 2010-09-13T16:30:32+02:00 http://algo.epfl.ch/en/group/seminars/20091209?rev=1284388232&do=diff abstract McEliece public key cryptosystems (PKCs) have been receiving increasing attention recently as alternatives to the other PKCs because of several advantages. They are now seen to be quite practical because of exponential growth in the computing power. Furthermore, in a post-quantum computing world they are expected to remain secure, as opposed to the insecurity of RSA and other similar systems. text/html 2011-09-15T13:30:48+02:00 http://algo.epfl.ch/en/group/seminars/2010-2011?rev=1316086248&do=diff Algo seminars 2010 - 2011 text/html 2009-12-10T10:56:45+02:00 http://algo.epfl.ch/en/group/seminars/20100113?rev=1260439005&do=diff abstract In Property Testing the goal is to quickly distinguish objects that satisfy a property from objects that need to be changed in a large fraction of places in order to satisfy the property. In this context, Locally Testable Codes (LTCs) are error-correcting codes for which membership can be decided from reading only a small section of the input. Recent studies of LTCs focus on identifying what attributes of codes allow them to be testable by local inspection. In particular, the ``symmet… text/html 2010-01-14T12:29:53+02:00 http://algo.epfl.ch/en/group/seminars/20100127?rev=1263468593&do=diff abstract It is well-known in the theory of codes on curves that the dual of an algebraic-geometric code on a curve is an algebraic-geometric code on the same curve. It turns out that this property does not hold in general when the curve is replaced by an higher dimensional variety. This observation motivates the study of this new class of codes which are the duals of algebraic geometric codes on higher-dimensional varieties. text/html 2011-06-29T17:46:51+02:00 http://algo.epfl.ch/en/group/seminars/20101103?rev=1309362411&do=diff abstract One of the major issues in design of ultra-low power (ULP) integrated systems is the wasted power due to the leakage current in metal-oxide-semiconductor (MOS) devices. While technology scaling helps to improve the speed and implement more complicated integrated systems, leakage current gets worse and this effect makes the design of ULP systems very challenging. text/html 2010-12-09T09:56:23+02:00 http://algo.epfl.ch/en/group/seminars/20101214?rev=1291884983&do=diff abstract Motivated by mobile wireless networks we consider a random graph over R^2, where nodes perform independent Brownian motions and edges are kept between pairs of nodes within distance r of each other. Combining ideas from stochastic geometry, coupling and multi-scale analysis, we obtain precise asymptotics for detection (the time until a given target is within distance r to some node of the graph) and percolation (the time until a given node belongs to the infinite connected component of… text/html 2011-01-18T22:02:13+02:00 http://algo.epfl.ch/en/group/seminars/20110203?rev=1295384533&do=diff abstract Boolean functions are called bent when they lie at maximal distance to the first order Reed-Muller code $RM(1,n)$ ($n$ even). They play roles not only in coding theory but also in cryptography (where they can be used to design balanced functions with high nonlinearity), designs, difference sets in elementary Abelian 2-groups... Their study has been initiated in the 70's by Dillon and Rothaus in parallel with the design of the DES. One of the classes of bent Boolean functions introduced… text/html 2011-04-14T11:04:04+02:00 http://algo.epfl.ch/en/group/seminars/20110413?rev=1302771844&do=diff abstract Locally testable codes, i.e., codes where membership in the code is testable with a constant number of queries, have played a central role in complexity theory. It is well known that a code must be a “low-density parity check” (LDPC) code for it to be locally testable, but few LDPC codes are known to the locally testable, and even fewer classes of LDPC codes are known not to be locally testable. Indeed, most previous examples of codes that are not locally testable were also not LDPC. T… text/html 2011-05-10T09:45:58+02:00 http://algo.epfl.ch/en/group/seminars/20110518?rev=1305013558&do=diff abstract Two-dimensional Array Codes are a central tool to efficiently maintain data reliability and availability in commercial storage systems. Aggregating multiple storage devices into a large pool of storage requires protection from failures of individual devices. The effectiveness of Array Codes in that task is thanks to their two main features: text/html 2011-07-23T15:09:10+02:00 http://algo.epfl.ch/en/group/seminars/20110629?rev=1311426550&do=diff abstract In this talk, we address the problem of neural association for a network of non-binary neurons. Here, the task is to recall a previously memorized pattern from its noisy version using a network of neurons whose states assume values from a finite number of non-negative integer levels. Prior works in this area consider storing a finite number of purely random patterns, and have shown that the pattern retrieval capacities (maximum number of patterns that can be memorized) scale only linea… text/html 2011-07-18T11:04:35+02:00 http://algo.epfl.ch/en/group/seminars/20110722?rev=1310979875&do=diff abstract We prove a time-space tradeoff lower bound of T = Omega(n log(n/S) log log(n/S)) for randomized oblivious branching programs to compute 1GAP, also known as the pointer jumping problem, a problem for which there is a simple deterministic time n and space O(log n) RAM (random access machine) algorithm. We give a similar time-space tradeoff of T = Omega(n log(n/S) log log(n/S)) for Boolean randomized oblivious branching programs computing GIP-MAP, a variation of the generalized inner p… text/html 2011-07-22T14:13:36+02:00 http://algo.epfl.ch/en/group/seminars/20110810?rev=1311336816&do=diff abstract We present a framework for approximating the metric traveling salesman problem (TSP) based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost. text/html 2011-08-09T16:18:15+02:00 http://algo.epfl.ch/en/group/seminars/20110831?rev=1312899495&do=diff abstract A pseudorandom generator takes a short binary string called the seed as input and generates a longer pseudorandom binary string. This talk is concerned with minimizing the seed-length while the output of the generator remains pseudorandom to DNF (Disjunctive normal form)/CNF (Conjunctive normal form) formulas, i.e. these formulas cannot distinguish the output of the generator from a truly random string. This problem is a natural problem before the more ambitious goal of derandomization… text/html 2011-09-30T11:12:30+02:00 http://algo.epfl.ch/en/group/seminars/20111005?rev=1317373950&do=diff abstract Consider the following generalized notion of graph coloring: a coloring of the vertices of a graph G is \emph{valid} w.r.t. some given graph F if there is no copy of F in G whose vertices all receive the same color. We study the problem of computing valid colorings of the binomial random graph G_{n,p} on n vertices with edge probability p=p(n) in the following online setting: the vertices of an initially hidden instance of G_{n,p} are revealed one by one (together with all edges leadi… text/html 2011-11-07T11:04:49+02:00 http://algo.epfl.ch/en/group/seminars/20111109?rev=1320660289&do=diff abstract Consumers of video and other content in today's networks have very diverse display and computing equipment ranging from mobile phones and handheld devices to desktops, and HDTVs. Downloaded items range from simple stock quotes to news stories to full movies, as well as different segments within the same video content. Furthermore, multicast transmission to different users takes place over channels with very different qualities. Today's telecommunications techniques are confined to uni…