Title

_D 01.04.2009 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Amir Hesam Salavati, Sharif University of Technology. TI QoS Network Coding AB 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-to-end delay constraints. I will only discuss the case of one and multiple multicast sessions in wired networks and leave the extensions to wireless networks for whomever interested.
In the second part of my talk, I will discuss a new idea about QoS network coding which I am currently working on. In summary, I think one of the biggest advantagess of network coding over routing is its ability to solve some NP-complete routing problems in polynomial time, or more precisely, in transforming NP-Complete problems to polynomial time ones. A good example is finding the minimum cost multicast subgraphs, which is know as finding Steiner trees problem in routing area. Lun et al. (2006) have shown that while Steiner trees problem belongs to the NP-complete class, by using network coding, the equivalent problem could be solved in polynomial time.
Since many QoS routing problems are NP-complete (and this is why there are many heuristic algorithms to provide QoS using routing), we are working on finding polynomial time solutions for the equivalent QoS network coding problems. _F NA24

_D 25.03.2009 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Dr. Juliane Iten, Armasuisse. TI Effect of Intelligent Antennas on Radio System Planning and on Mitigation AB 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 statistical models for them and investigates the performance measures of cellular radio systems with and without smart antennas deployed at base stations. In the second part of the research, a 3D ray tracing tool is developed to predict the propagation for real scenarios using UMTS systems. This tool takes into account 3D radiation diagrams and multipath propagation. It was used in real scenarios to compare the real field levels with the levels obtained by the approximate methods defined by the regulation standards _F NA23

_D 11.03.2009 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Prof. Joachim von zur Gathen, Bonn-Aachen International Center for Information Technology. TI The subset sum pseudorandom generator AB 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 reduces the security from the previously assumed n^2 bit to n bits. It is conjectured that the generator is secure at this level.
Next come improved implementations of the generator. Some special choices of the secret parameters speed up the naive usage of this generator without losing the property of uniform distribution. These results confirm that the generator can be useful for both cryptographic and Quasi Monte Carlo applications. _F NA22

_D 04.03.2009 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Dr. David Xiao, Princeton University. TI On the Black-box Complexity of PAC Learning AB 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 that the black-box complexity of PAC learning lies strictly between NP and ZK. More precisely, if P = NP then PAC learning is easy and if ZK != BPP then PAC learning is hard, but black-box techniques (with some additional restrictions) do not suffice to prove equivalence in either case.
With regard to NP, we rule out non-adaptive reductions using a PAC learning oracle to solve an NP-complete problem by showing this would imply that NP is contained in coAM, which is considered implausible.
With regard to ZK, we rule out relativizing proofs that ZK != BPP based on hardness of learning. Using the characterization of ZK of Ong and Vadhan (EUROCRYPT '07), we also show that any black-box construction of a (computational) ZK protocol for a language L based on hardness of learning implies that L actually has a *statistical* zero knowledge proof (i.e. L is in SZK), and hence such a black-box construction is unlikely to exist for NP-complete languages.
Parts of this talk are based on joint work with Benny Applebaum and Boaz Barak. _F NA21

_D 25.02.2009 _TPL 14h00-15h00 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Dr. Bertrand Meyer, Universit&eacute; Bordeaux 1 TI Generalised Hermite constant and flag variety AB 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 spirit of Voronoi work and developp a technique based on representation theory and designs to exhibit such examples. _F NA20

_D 21.01.2009 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Dr. Alp Bassa, School of Mathematics, EPFL. TI Asymptotically Good Self-Dual Codes over Cubic Finite Fields AB 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 construction also gives a simpler proof for the quadratic case. [joint work with H. Stichtenoth]. _F NA11

_D 14.01.2009 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Mahdi Cheraghchi, ALGO, EPFL. TI Noise-Resilient Group Testing: Limitations and Constructions AB 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 us to break the information theoretic lower bound of $\Omega(d^{2} \log(n)/\log(d))$ that is known for exact reconstruction of $d$-sparse vectors of length $n$ via non-adaptive measurements, by a multiplicative factor of almost linear in $d$.
Specifically, we give simple randomized constructions of non-adaptive measurement schemes, with $m=O(d \log(n))$ measurements, that allow efficient reconstruction of d-sparse vectors up to $O(d)$ false positives even in the presence of $\deltam$ false positives and $O(m/d)$ false negatives within the measurement outcomes, for any constant $\delta < 1$. We show that, information theoretically, none of these parameters can be substantially improved without dramatically affecting the others. Furthermore, we obtain several explicit constructions, in particular one matching the randomized trade-off but using $m = O(d^{1+o(1)}\log(n))$ measurements. We also obtain explicit constructions that allow fast reconstruction in time polynomial in $m$, which would be sublinear in $n$ for sufficiently sparse vectors.
An immediate consequence of our result is an adaptive scheme that runs in only two non-adaptive “rounds” and exactly reconstructs any $d$-sparse vector using a total $O(d \log(n))$ measurements, a task that would be impossible in one round and fairly easy in $O(\log(n/d))$ rounds. _F NA12

_D 12.01.2009 _TPL 15h00-16h00 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Prof. Amin Shokrollahi, ALGO, EPFL. TI Lecture Series on Fast Matrix Multiplication (Lecture 7) AB 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 second part, I will lay out the method by Cohn and Umans using the theory of finite groups and their representations, and will show how that theory can be used to get fast matrix multiplication algorithms. Using the same combinatorics as in the classical approach, we obtain algorithms of the same asymptotic complexity. _F NA13

_D 15.12.2008 _TPL 15h00-16h00 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Prof. Amin Shokrollahi, ALGO, EPFL. TI Lecture Series on Fast Matrix Multiplication (Lecture 6) AB 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 second part, I will lay out the method by Cohn and Umans using the theory of finite groups and their representations, and will show how that theory can be used to get fast matrix multiplication algorithms. Using the same combinatorics as in the classical approach, we obtain algorithms of the same asymptotic complexity. _F NA10

_D 08.12.2008 _TPL 15h00-16h00 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Prof. Amin Shokrollahi, ALGO, EPFL. TI Lecture Series on Fast Matrix Multiplication (Lecture 5) AB 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 second part, I will lay out the method by Cohn and Umans using the theory of finite groups and their representations, and will show how that theory can be used to get fast matrix multiplication algorithms. Using the same combinatorics as in the classical approach, we obtain algorithms of the same asymptotic complexity. _F NA9

_D 03.12.2008 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Prof. Amin Shokrollahi, ALGO, EPFL. TI Lecture Series on Fast Matrix Multiplication (Lecture 4) AB 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 second part, I will lay out the method by Cohn and Umans using the theory of finite groups and their representations, and will show how that theory can be used to get fast matrix multiplication algorithms. Using the same combinatorics as in the classical approach, we obtain algorithms of the same asymptotic complexity. _F NA8

_D 24.11.2008 _TPL 15h00-16h00 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Prof. Amin Shokrollahi, ALGO, EPFL. TI Lecture Series on Fast Matrix Multiplication (Lecture 3) AB 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 second part, I will lay out the method by Cohn and Umans using the theory of finite groups and their representations, and will show how that theory can be used to get fast matrix multiplication algorithms. Using the same combinatorics as in the classical approach, we obtain algorithms of the same asymptotic complexity. _F NA7

_D 20.11.2008 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Prof. Christina Fragouli, ARNI, EPFL. TI Combinatorial Algorithms for Wireless Information Flow AB 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 interactions rather than the background noise. They generalized the min-cut max-flow theorem for graphs to networks of deterministic channels and proved that the capacity can be achieved using information theoretical tools. They showed that the value of the minimum cut is in this case the minimum rank of all the binary adjacency matrices describing source-destination cuts. However, since there exists an exponential number of cuts, identifying the capacity through exhaustive search becomes infeasible. In this work, we develop a polynomial time algorithm that discovers the relay encoding strategy to achieve the min-cut value in binary linear deterministic (wireless) networks, for the case of a unicast connection. Our algorithm crucially uses a notion of linear independence between edges to calculate the capacity in polynomial time. Moreover, we can achieve the capacity by using very simple one-bit processing at the intermediate nodes, thereby constructively yielding finite length strategies that achieve the unicast capacity of the linear deterministic (wireless) relay network. [Joint work with A. Amaudruz]

_F NA6

_D 17.11.2008 _TPL 15h00-16h00 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Prof. Amin Shokrollahi, ALGO, EPFL. TI Lecture Series on Fast Matrix Multiplication (Lecture 2) AB 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 second part, I will lay out the method by Cohn and Umans using the theory of finite groups and their representations, and will show how that theory can be used to get fast matrix multiplication algorithms. Using the same combinatorics as in the classical approach, we obtain algorithms of the same asymptotic complexity. _F NA5

_D 10.11.2008 _TPL 15h00-16h00 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Prof. Amin Shokrollahi, ALGO, EPFL. TI Lecture Series on Fast Matrix Multiplication (Lecture 1) AB 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 second part, I will lay out the method by Cohn and Umans using the theory of finite groups and their representations, and will show how that theory can be used to get fast matrix multiplication algorithms. Using the same combinatorics as in the classical approach, we obtain algorithms of the same asymptotic complexity. _F NA4

_D 29.10.2008 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Ghid Maatouk, ALGO, EPFL. TI Recursions for the LT Decoder AB 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 from this recursion, we will extend the analysis of Karp, Luby, and Shokrollahi to find explicit formulas for the variance of the main state parameters of the decoder. These formulas describe an explicit “corridor” within which the decoding state parameters can move, and lead to explicit good upper bounds on the decoding error. They can also be used to compute good finite length designs for LT-codes. [Joint work with Amin Shokrollahi] _F NA3

_D 15.10.2008 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Prof. Martin F&uuml;rer, Pennsylvania State University and ALGO, EPFL. TI Fast Integer Multiplication AB 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 (FFT) and runs in time O(n log n log log n). Since then, the prevailing conjecture has been that the complexity of an optimal integer multiplication algorithm is O(n log n). A recent multiplication algorithm with a running time of n log n exp(O(log* n) is presented. It is a step towards closing the gap from above. The running time bound holds for multitape Turing machines. The same bound is valid for the size of boolean circuits. _F NA2

_D 01.10.2008 _TPL 16h15-17h15 at <a href=“http://plan.epfl.ch/?room=BC129”>BC-129</a> AU Prof. Venkatesan Guruswami, University of Washington & Carnegie Mellon University TI Expander codes, Explicit Euclidean sections, and compressed sensing AB 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 asymptotic convex geometry. Similar randomized geometric constructions arise in areas like dimensionality reduction and compressed sensing. Explicit constructions of such objects , however, seem very hard to come by. We will describe constructions inspired by expander codes that can be used to produce subspaces with distortion nearly as good as a random subspace either explicitly or with sublinear randomness. Specifically, we construct an explicit subspace of R^N with dimension N(1-o(1)) and distortion (slightly worse than) poly(log N). The construction combines various ingredients such as Ramanujan graphs, sum-product theorems in finite fields, and Kerdock codes. We are also able to construct subspaces of R^N of dimension N/2 with O(1) distortion using N^d random bits for any constant d > 0 (and hence deterministically in sub-exponential time). The talk will also briefly discuss connections to sparse signal recovery (aka compressed sensing). [Based on joint works with James Lee, Alexander Razborov, and Avi Wigderson] _F NA1