français | english		EPFL > people@EPFL > Amin Shokrollahi login

Full Professor SB SB-SMA SMA-ENS Full Professor IC IC-SIN SIN-ENS

Amin Shokrollahi Professor PhD (Bonn, 1991) web site: http://algo.epfl.ch/index.php?p=group_members_amin office(s): BC110 phone(s): [+41 21 69] 37512,37511 BIOGRAPHY Amin Shokrollahi has worked on a variety of topics, including coding theory, computational number theory and algebra, and computational/algebraic complexity theory. He is best known for his work on iterative decoding algorithms of graph based codes, an area in which he holds a number of granted and pending patents. He is the co-inventor of Tornado codes, and the inventor of Raptor codes. His codes have been standardized and successfully deployed in practical areas dealing with data transmission over lossy networks. Prior to joining EPFL, Amin Shokrollahi has held positions as the chief scientist of Digital Fountain, member of the technical staff at Bell Laboratories, senior researcher at the International Computer Science Insitute in Berkeley, and assistant professor at the department of computer science of the university of Bonn. He is a Fellow of the IEEE, and he was awarded the Best Paper Award of the IEEE IT Society in 2002 for his work on iterative decoding of LDPC code, the IEEE Eric Sumner Award in 2007 for the development of Fountain Codes, and the joint Communication Society/Information Theory Society best paper award of 2007 for his paper on Raptor Codes. MAIN PUBLICATIONS M. H. Taghavi, A. Shokrollahi, and P. H. Siegel. Efficient Implementation of Linear Programming Decoding. Ieee Transactions On Information Theory, 57:5960-5982, 2011. [ DOI | Details ] A. H. Salavati, K. R. Kumar, and A. Shokrollahi. Molecular associative memory: An associative memory framework with exponential storage capacity for DNA computing. 2011. [ Details | Full Text ] K. R. Kumar, A. H. Salavati, and A. Shokrollahi. Exponential Pattern Retrieval Capacity with Non-Binary Associative Memory. In IEEE Information Theory Workshop (ITW 2011), 2011. [ Details | Full Text ] A. H. Salavati, K. R. Kumar, A. Shokrollahi, and W. Gerstner. Neural Pre-coding Increases the Pattern Retrieval Capacity of Hopï¬�eld and Bidirectional Associative Memories. In IEEE International Symposium on Information Theory (ISIT 2011), 2011. [ Details | Full Text ] K. Kumar, R. Kumar, P. Pakzad, A. H. Salavati, and M. A. Shokrollahi. Phase Transitions for Mutual Information. In Proc. 6th Intl. Symposium on Turbo Codes and Iterative Information Processing (ISTC - 2010), pages 137-141. IEEE, 2010. [ Details | Full Text ] M. Cheraghchi Bashi Astaneh and M. A. Shokrollahi. Applications of Derandomization Theory in Coding. PhD thesis, Lausanne, 2010. [ DOI | Details | Full Text | Link ] M. Perrenoud and M. A. Shokrollahi. Randomized and Deterministic Primality Testing. 2009. [ Details | Full Text ] M. Perrenoud and M. A. Shokrollahi. Randomized and Deterministic Primality Testing. 2009. [ Details | Full Text ] A. Shokrollahi. Theory and applications of Raptor codes. In Mathknow: Mathematics, Applied Sciences And Real Life, volume 3 of MS&A-Modeling Simulation and Applications, pages 59-89. Springer-Verlag Italia, Milan, Italy, 2009. [ Details ] G. Maatouk and A. Shokrollahi. Analysis of the Second Moment of the LT Decoder. In 2009 Ieee International Symposium On Information Theory, Vols 1- 4, pages 2326-2330. Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa, 2009. [ Details ] M. Cheraghchi, F. Didier, and A. Shokrollahi. Invertible Extractors and Wiretap Protocols. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), pages 1934-1938, 2009. [ Details | Full Text | Link ] E. Ardestanizadeh, M. Cheraghchi, and A. Shokrollahi. Bit Precision Analysis for Compressed Sensing. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), pages 1-5, 2009. [ Details | Full Text | Link ] M. Cheraghchi and A. Shokrollahi. Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties. In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS), 2009. [ Details | Full Text | Link ] B. Ndzana Ndzana and M. A. Shokrollahi. Source and channel coding using Fountain codes. PhD thesis, Lausanne, 2009. [ DOI | Details | Full Text | Link ] B. Ndzana Ndzana, A. Shokrollahi, A. Eckford, and G. Shamir. Fountain codes for piecewise stationary channels. In Proceedings of the IEEE International Symposium on Information Theory, pages 2242 - 2246, Toronto, 2008. IEEE. [ Details | Link ] A. Shokrollahi. Asymmetric information embedding. Applicable Algebra in Engineering, Communication and Computing, 19(3):229-239, 2008. [ DOI | Details | Link ] B. Furhet, S. Ahson, T. Stockhammer, A. Shokrollahi, M. Watson, M. Luby, and T. Gasiba. Application Layer Forward Error Correction for Mobile Multimedia Broadcasting. In Handbook of Mobile Broadcasting: DVB-H, DMB, ISDB-T and Media FLO, pages 239-280. CRC Press, Boca Raton, FL, 2008. [ Details | Link ] J. von zur Gathen, A. Shokrollahi, and J. Shokrollahi. Efficient multiplication using type 2 optimal normal bases. In International Workshop on the Arithmetic of Finite Fields, WAIFI 2007, pages 55-68, 2007. [ Details | Full Text | Link ] L. Minder and A. Shokrollahi. Cryptanalysis of the Sidelnikov cryptosystem. In Proceedings of Eurocrypt 2007, Lecture Notes in Computer Science, pages 347-360. Springer Verlag, 2007. [ Details | Full Text | Link ] M. Molkaraie and M. A. Shokrollahi. Subtree-based bounds and simulation-based estimations for the partition function. PhD thesis, Lausanne, 2007. [ DOI | Details | Full Text | Link ] L. Minder and M. A. Shokrollahi. Cryptography based on error correcting codes. PhD thesis, Lausanne, 2007. [ DOI | Details | Full Text | Link ] A. Brown and M. A. Shokrollahi. Codes, graphs and graph based codes. PhD thesis, Lausanne, 2007. [ DOI | Details | Full Text | Link ] M. Cheraghchi, A. Shokrollahi, and A. Wigderson. Computational Hardness and Explicit Constructions of Error Correcting Codes. In Allerton 2006, 2006. Invited paper. [ Details | Full Text | Link ] A. Shokrollahi. Raptor Codes. IEEE Transactions on Information Theory, 52(6):2551-2567, 2006. [ DOI | Details | Link ] P. Pakzad and A. Shokrollahi. Design Principles for Raptor Codes. In Proceedings of the IEEE Information Theory Workshop, 2006, pages 165-169, 2006. [ DOI | Details | Link ] B. N. Ndzana, A. Shokrollahi, and J. Abel. Burrows-Wheeler text compression with fountain codes. In Proceedings of the Data Compression Conference, DCC 2006, pages 28-30, 2006. [ DOI | Details | Link ] B. Ndzana, A. Shokrollahi, and J. Abel. Fountain Codes for the Slepian-Wolf Problem. In Proceedings of Annual Allerton Conference on Communication, Control, and Computing - Invited Paper, 2006. [ Details | Link ] E. Maneva and A. Shokrollahi. New model for rigorous analysis of LT-codes. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2006, pages 2677-2679, 2006. [ DOI | Details | Link ] R. Karp, M. Luby, and A. Shokrollahi. Verification decoding of raptor codes. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2006, pages 1310-1314, 2006. [ DOI | Details | Link ] O. Etesami and A. Shokrollahi. Raptor Codes on Binary Memoryless Symmetric Channels. IEEE Transactions on Information Theory, 52(5):2033-2051, 2006. [ DOI | Details | Link ] A. Brown and A. Shokrollahi. Some graph products and their expansion properties. In Proceedings of the IEEE Information Theory Workshop, 2006, pages 170-174, 2006. [ DOI | Details | Link ] A. Brown, L. Minder, and A. Shokrollahi. Improved Decoding of Interleaved AG-Codes. In Proc. 10th IMA Conf. on Cryptography and Coding, volume 1 of Lecture Notes in Computer Science, pages 37-46, 2005. [ Details | Full Text | Link ] M. Rashidpour, A. Shokrollahi, and S. H. Jamali. Optimal regular LDPC codes for the binary erasure channel. IEEE Communication Letters, 9(6):546-548, 2005. [ DOI | Details | Link ] P. Pakzad, C. Fragouli, and A. Shokrollahi. Coding schemes for line networks. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2005, pages 1853-1857, 2005. [ DOI | Details | Link ] A. Brown, M. Luby, and A. Shokrollahi. Repeat-accumulate codes that approach the Gilbert-Varshamov bound. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2005, pages 169-173, 2005. [ DOI | Details | Link ] P. Pakzad, C. Fragouli, and A. Shokrollahi. Coding Schemes for Line Networks. In IEEE International Symposium on Information Theory (ISIT'05), 2005. [ Details | Full Text ] C. Fragouli, E. Soljanin, and A. Shokrollahi. Network coding as a coloring problem (Invited paper). In In Proceedings, 2004. [ Details | Full Text | Link ] A. Shokrollahi and W. Wang. Low-density parity-check codes with rates very close to the capacity of the q-ary symmetric channel for large q. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2004, page 275, 2004. [ DOI | Details | Link ] A. Shokrollahi. Capacity-approaching codes on the q-ary symmetric channel for large q. In Proceedings of the IEEE Information Theory Workshop, 2004, pages 204-208, 2004. [ DOI | Details | Link ] A. Shokrollahi. Raptor codes. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2004, page 36, 2004. [ DOI | Details | Link ] R. Karp, M. Luby, and A. Shokrollahi. Finite length analysis of LT codes. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2004, page 39, 2004. [ DOI | Details | Link ] O. Etesami, M. Molkaraie, and A. Shokrollahi. Raptor codes on symmetric channels. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2004, page 38, 2004. [ DOI | Details | Link ] G. Caire, S. Shamai, A. Shokrollahi, and S. Verdu. Universal variable-length data compression of binary sources using fountain codes. In Proceedings of the IEEE Information Theory Workshop, 2004, pages 123-128, 2004. [ DOI | Details | Link ] A. Brown and A. Shokrollahi. Algebraic-geometric codes on the erasure channel. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2004, page 76, 2004. [ DOI | Details | Link ] A. Brown, L. Minder, and A. Shokrollahi. Probabilistic decoding of interleaved RS-codes on the q-ary symmetric channel. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2004, page 326, 2004. [ DOI | Details | Link ] V. Olshevsky and A. Shokrollahi. A displacement approach to decoding algebraic codes. In Fast Algorithms for Structured Matrices: Theory and Applications, volume 323, Providence, 2003. AMS/SIAM. [ Details | Link ] J. von zur Gathen, A. Shokrollahi, and I. Shparlinski. An authentication scheme based on roots of sparse polynomials. In Proceedings of the IEEE Information Theory Workshop, 2003, pages 159-162, 2003. [ Details | Link ] A. Shokrollahi. Computing the performance of unitary space-time group codes from their character table. IEEE Transactions on Information Theory, 48(6):1355-1371, 2002. [ DOI | Details | Link ] A. Shokrollahi. An Introduction to Low-Density Parity-Check Codes. In Theoretical Aspects of Computer Science : Advanced Lectures, volume 2292 of Lecture Notes in Computer Science, page 175. Springer, 2002. [ Details | Link ] T. Richrdson, A. Shokrollahi, and R. Urbanke. Finite-length analysis of various low-density parity-check ensembles for the binary erasure channel. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2002, page 1, 2002. [ DOI | Details | Link ] P. Oswald and A. Shokrollahi. Capacity-achieving sequences for the erasure channel. IEEE Transactions on Information Theory, 48(12):3017 - 3028, 2002. [ DOI | Details | Link ] T. Richardson, A. Shokrollahi, and R. Urbanke. Finite-Length Analysis of Various Low-Density Parity-Check Ensembles for the Binary Erasure Channel. In IEEE International Symposium on Information Theory. Proceedings, volume -, page 1, 2002. [ Details ] A. Shokrollahi, B. Hassibi, B. M. Hochwald, and W. Sweldens. Representation theory for high-rate multiple-antenna code design. IEEE Transactions on Information Theory, 47(6):2335-2367, 2001. [ DOI | Details | Link ] A. Shokrollahi. Design of unitary space-time codes from representations of SU(2). In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2001, page 241, 2001. [ DOI | Details | Link ] A. Shokrollahi. Group characters and unitary space-time codes. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2001, page 107, 2001. [ DOI | Details | Link ] A. Shokrollahi. Double antenna diagonal space-time codes and continued fractions. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2001, page 108, 2001. [ DOI | Details | Link ] A. Shokrollahi. Design of Differential Space-Time Codes Using Group Theory. In Proceedings of the 14th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-14, 2001, volume 2227 of Lecture Notes in Computer Science, pages 22-35. Springer, 2001. [ Details | Link ] T. J. Richardson, M. A. Shokrollahi, and R. L. Urbanke. Design of capacity-approaching irregular low-density parity-check codes. IEEE Transactions on Information Theory, 47(2):619-637, 2001. [ DOI | Details | Link ] V. Olshevsky and A. Shokrollahi. The displacement method in coding theory. In Contemporary mathematics: theory and applications, pages 265-292, 2001. [ DOI | Details | Link ] M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman. Efficient erasure correcting codes. IEEE Transactions on Information Theory, 47(2):569-584, 2001. [ DOI | Details | Link ] M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman. Improved low-density parity-check codes using irregular graphs. IEEE Transactions on Information Theory, 47(2):619-637, 2001. [ DOI | Details | Link ] J. Buhler, R. Crandall, R. Ernvall, T. Mesänkylä, and A. Shokrollahi. Irregular primes and Cyclotomic Invariants to Twelve Million. Journal of Symbolic Computation, 31:98-96, 2001. [ DOI | Details | Link ] T. Richardson, A. Shokrollahi, and R. Urbanke. Design of capacity-approaching irregular low-density parity-check codes. IEEE Transactions on Information Theory, 47(2):619-637, 2001. [ DOI | Details ] A. Shokrollahi, H. Reichel, and S. Tison. Codes and Graphs. In Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, volume 1770 of Lecture Notes in Computer Science, pages 1-12. Springer, 2000. [ Details | Link ] V. Olshevsky and A. Shokrollahi. Matrix vector product for confluent Cauchy-like matrices with applications to confluent rational interpolation. In Proceedings of the 32nd annual ACM Symposium on Theory of Computing, STOC 2000, pages 573-581, 2000. [ DOI | Details | Link ] A. Shokrollahi and R. Storn. Design of efficient erasure codes with differential evolution. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2000, page 5, 2000. [ DOI | Details | Link ] A. Shokrollahi, B. Marcus, and J. Rosenthal. Capacity-achieving sequences. IMA volumes in Mathematics and its Applications, 123:153-166, 2000. [ DOI | Details | Link ] T. Richardson, A. Shokrollahi, and R. Urbanke. Design of provably good low-density parity check codes. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2000, page 199, 2000. [ DOI | Details | Link ] C. Monico, J. Rosenthal, and A. Shokrollahi. Using low density parity check codes in the McEliece cryptosystem. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2000, page 215, 2000. [ DOI | Details | Link ] B. Hassibi, B. Hochwald, A. Shokrollahi, and W. Sweldens. Multiple antennas and representation theory. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2000, page 337, 2000. [ DOI | Details | Link ] B. Hassibi, B. Hochwald, A. Shokrollahi, and W. Sweldens. Codes for differential signaling with many antennas. In Proceedings of the IEEE Wireless Communication and Networking Conference, WCNC 2000, volume 1, pages 23-24, 2000. [ DOI | Details | Link ] J. P. Buhler, A. Shokrollahi, and V. Stemann. Fast and precise Fourier Transforms. IEEE Transactions on Information Theory, 46(1):213-228, 2000. [ DOI | Details | Link ] A. Shokrollahi. On cyclic MDS codes. In Coding Theory and Cryptography: from Enigma and Geheimschreiber to Quantum Theory, pages 202-213. Springer, 1999. [ Details | Link ] V. Olshevksy and A. Shokrollahi. A displacement structure approach to decoding algebraic geometric codes. In Proceedings of the 31st annual ACM Symposium on Theory of Computing, STOC 1999, pages 235-244, 1999. [ DOI | Details | Link ] S. Gao and A. Shokrollahi. Computing Roots of Polynomials over Function Fields of Curves. In Coding Theory and Cryptography: from Enigma and Geheimschreiber to Quantum Theory, pages 180-201. Springer, 1999. [ Details | Link ] S. Gao, A. Shokrollahi, and D. Joyner. Computing roots of polynomials over function fields of curves. In Proceedings of the Annapolis Conference on Number Theory, Coding Theory, and Cryptography, pages 214-228. Springer-Verlag, 1999. [ Details | Link ] S. Feisel, J. von zur Gathen, and A. Shokrollahi. Normal bases in finite fields via general Gauss periods. Mathematics of Computation, 68(225):271-290, 1999. [ DOI | Details | Link ] A. Shokrollahi and H. Wasserman. List decoding of algebraic geometric codes. IEEE Transactions on Information Theory, 45(2):432-437, 1999. [ DOI | Details | Link ] A. Shokrollahi. Relative class number of Abelian number fields of prime conductor below 10000. Mathematics of Computation, 68(228):1717-1728, 1999. [ DOI | Details | Link ] A. Shokrollahi and H. Wasserman. Decoding algebraic geometric codes. In Proceedings of the 35th Annual Allerton Conference on Communication, Control, and Computing, pages 225-228, 1998. [ Details | Link ] M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. A. Spielman. Analysis of low-density codes and improved designs using irregular graphs. In Proceedings of the 30th annual ACM Symposium on Theory of Computing, STOC 1998, pages 249-258. ACM Press, 1998. [ DOI | Details | Link ] A. Shokrollahi and H. Wasserman. Decoding algebraic-geometric codes beyond the error-correction bound. In Proceedings of the 30th annual ACM symposium on Theory of computing, STOC 1998, pages 241-248. ACM Press, 1998. [ Details | Link ] M. Luby, M. Mitzenmacher, and A. Shokrollahi. Analysis of random processes via AND/OR tree evaluations. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1998, pages 364-373, 1998. [ Details | Link ] T. Sander and A. Shokrollahi. Deciding properties of number fields without factoring. In Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science, FOCS 1997, pages 46-55, 1997. [ DOI | Details | Link ] J. P. Buhler, A. Shokrollahi, and V. Stemann. Fast and precise computation of discrete Fourier Transforms using cyclotomic integers. In Proceedings of the 29th annual ACM Symposium on Theory of Computing, STOC 1997, pages 40-47, 1997. [ DOI | Details | Link ] A. Omrani and A. Shokrollahi. Computing irreducible representations of supersolvable groups over small finite fields. Mathematics of Computation, 66(218):779-786, 1997. [ DOI | Details | Link ] M. Luby, M. Mitzenmacher, A. Shokrollahi, D. A. Spielman, and V. Stemann. Practical loss-resilient codes. In Proceedings of the 29th annual ACM Symposium on Theory of Computing, STOC 1997, pages 150-159. ACM Press, 1997. [ DOI | Details | Link ] P. Buergisser, M. Clausen, and A. Shokrollahi. Algebraic Complexity Theory. Grundlehren der mathematischen Wissenschaften. Springer Verlag, Heidelberg, 1996. [ Details | Link ] A. Shokrollahi. Stickelberger Codes. Designs, Codes, and Cryptography, 9(2):203-213, 1996. [ DOI | Details | Link ] E. S. Mahmoodian and A. Shokrollahi. Open problems at the combinatorics workshop of AIMC25 (Tehran, 1994). In Combinatorics Advances, volume 329 of Mathematics and its applications, pages 321-324. 1995. [ Details | Link ] A. Shokrollahi. An introduction to the theory of bilinear complexity. Matemática Contemporânea, 7:37-58, 1994. [ DOI | Details | Link ] S. Shokranian and A. Shokrollahi. Coding Theory and Bilinear Complexity. International Cooperation. International Office of the Forschungszentrum Juelich, Juelich, 1993. [ Details | Link ] A. Shokrollahi. Optimal algorithms for multiplication in certain finite fields using elliptic curves. SIAM Journal of Computing, 21(6):1193-1198, 1992. [ DOI | Details | Link ] A. Shokrollahi. Efficient randomized generation of optimal algorithms for multiplication in certain finite fields. Computational Complexity, 2(1):67-96, 1992. [ DOI | Details | Link ] A. Shokrollahi. Minimum distance of elliptic codes. Advances in Mathematics, 93(2):251-281, 1992. [ DOI | Details | Link ] A. Shokrollahi. Codes on hermitian curves. In Proceedings of the 4th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-4, 1988, volume 307 of Lecture Notes in Computer Science, pages 168-176. Springer, 1988. [ Details | Link ] Current work Fountain: Design of methods and processes for use of fountain codes in various communication scenarios. RapTV: A system for enabling TV-broadcast on unreliable packet networks Compression: Design of new compression schemes based on fountain codes Complexity: Study of complexity of classical and quantum algorithms Crypto: study and design of public-key cryptosystems based on hard problems Amin Shokrollahi's research is supported by the Swiss National Science Foundation, and by Digital Fountain Corporation.

Skills Design and analysis of coding systems, Development and implementation of fast coding algorithms, Computational number theory, Computational algebra, Algebra Teaching Mathematics Algorithms [en] (SSC SPH SMA SIN) Discrete mathematics [fr] (SMTE SMA) Phd programs Mathematics (edoc) Computer, Communication and Information Sciences Phd Students Alipour Babaei Masoud Maatouk Ghid Salavati Amir Hesam Yartseva Lyudmila