@comment{ generated by } @InProceedings{Karp2006/ALGO, abstract = { }, address = { }, affiliation = {EPFL}, author = {Karp, R. and Luby, M. and Shokrollahi, A.}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2006}, details = {http://infoscience.epfl.ch/record/99174}, doi = {10.1109/ISIT.2005.1523554}, keywords = {algoweb_fountain}, location = { }, oai-id = {oai:infoscience.epfl.ch:99174}, oai-set = {conf}, pages = {1310--1314}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Verification decoding of raptor codes}, unit = {ALGO}, url = { }, year = 2006 } @InProceedings{Monico2000/ALGO, abstract = {We examine the implications of using a low density parity check code (LDPCC) in place of the usual Goppa code in McEliece's cryptosystem. Using a LDPCC allows for larger block lengths and the possibility of a combined error correction/encryption protocol}, address = { }, affiliation = {OTHER}, author = {Monico, C. and Rosenthal, J. and Shokrollahi, A.}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2000}, details = {http://infoscience.epfl.ch/record/99194}, doi = {10.1109/ISIT.2000.866513}, keywords = {algoweb_ldpc}, location = { }, oai-id = {oai:infoscience.epfl.ch:99194}, oai-set = {conf}, pages = {215}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Using low density parity check codes in the {M}c{E}liece cryptosystem}, unit = {ALGO}, url = { }, year = 2000 } @InProceedings{EPFL-CONF-185108, abstract = {In networks that perform linear network coding, an intermediate network node may receive a much larger number of linear equations of the source symbols than the number of messages it needs to send. For networks constructed by untrusted nodes, we propose a relaxed measure of security: we want to be untrusting, and allow each intermediate node to only learn as much information as the number of independent messages it needs to send. In this paper we formulate this problem and provide sufficient and necessary conditions for classes of combination networks. ©2012 IEEE.}, affiliation = {EPFL}, author = {Büyükalp, Yasin and Maatouk, Ghid and Prabhakaran, Vinod M. and Fragouli, Christina}, booktitle = {2012 International {S}ymposium on {N}etwork {C}oding, {N}et{C}od 2012}, details = {http://infoscience.epfl.ch/record/185108}, documenturl = {http://infoscience.epfl.ch/record/185108/files/untrusting network coding.pdf}, doi = {10.1109/NETCOD.2012.6261888}, isbn = { 978-1-4673-1890-7}, location = {Cambridge, Massachusetts, USA}, number = {null}, oai-id = {oai:infoscience.epfl.ch:185108}, oai-set = {conf}, pages = {79--84}, review = {REVIEWED}, status = {PUBLISHED}, submitter = {173510}, title = {Untrusting network coding}, unit = {ALGO ARNI}, volume = {null}, year = 2012 } @InProceedings{Caire2004/ALGO, abstract = {This paper proposes a universal variable-length lossless compression algorithm based on fountain codes. The compressor concatenates the Burrows-Wheeler block sorting transform (BWT) with a fountain encoder, together with the closed-loop iterative doping algorithm. The decompressor uses a belief propagation algorithm in conjunction with the iterative doping algorithm and the inverse BWT. Linear-time compression/decompression complexity and competitive performance with respect to state-of-the-art compression algorithms are achieved.}, address = { }, affiliation = {EPFL}, author = {Caire, G. and Shamai, S. and Shokrollahi, A. and Verdu, S.}, booktitle = {Proceedings of the {IEEE} {I}nformation {T}heory {W}orkshop, 2004}, details = {http://infoscience.epfl.ch/record/99163}, doi = {10.1109/ITW.2004.1405286}, keywords = {algoweb_fountain}, location = { }, oai-id = {oai:infoscience.epfl.ch:99163}, oai-set = {conf}, pages = {123--128}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Universal variable-length data compression of binary sources using fountain codes}, unit = {ALGO}, url = { }, year = 2004 } @InProceedings{Olhoevsky2001/ALGO, abstract = {Algebraic coding theory is one of the areas that routinely gives rise to computational problems involving various structured matrices, such as Hankel, Vandermonde, Cauchy matrices, and certain generalizations thereof. Their structure has often been used to derive efficient algorithms; however, the use of the structure was pattern-specific, without applying a unified technique. In contrast, in several other areas, where structured matrices are also widely encountered, the concept of displacement rank was found to be useful to derive efficient algorithms in a unified manner (i.e., not depending on a particular pattern of structure). The latter technique allows one to "compress," in a unified way, different types of n x n structured matrices to only $alpha n$ parameters. This typically leads to computational savings (in many applications the number $alpha$, called the displacement rank, is a small fixed constant).In this paper we demonstrate the power of the displacement structure approach by deriving in a unified way efficient algorithms for a number of decoding problems. We accelerate the Sudan's list decoding algorithm for Reed-Solomon codes, its generalization to algebraic- geometric codes by Shokrollahi and Wasserman, and the improvement of Guruswami and Sudan in the case of Reed-Solomon codes. In particular, we notice that matrices that occur in the context of list decoding have low displacement rank, and use this fact to derive algorithms that use $O(n^2 l)$ and $O(n^7/3 l)$ operations over the base field for list decoding of Reed- Solomon codes and algebraic-geometric codes from certain plane curves, respectively. Here l denotes the length of the list; assuming that l is constant, this gives algorithms of running time $O(n^2)$ and $O(n^7/3)$, which is the same as the running time of conventional decoding algorithms. We also present efficient parallel algorithms for the above tasks.To the best of our knowledge this is the first application of the concept of displacement rank to the unified derivation of several decoding algorithms; the technique can be useful in finding efficient and fast methods for solving other decoding problems}, address = { }, affiliation = {OTHER}, author = {Olshevsky, V. and Shokrollahi, A}, booktitle = {Contemporary mathematics: theory and applications}, details = {http://infoscience.epfl.ch/record/99202}, keywords = {algoweb_structmat}, location = { }, oai-id = {oai:infoscience.epfl.ch:99202}, oai-set = {conf}, pages = {265--292}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {The displacement method in coding theory}, unit = {ALGO}, url = { }, year = 2001 } @InProceedings{EPFL-CONF-163770, 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. The only exception was in the work of Ben-Sasson et al. (SICOMP, 2005) who showed that random LDPC codes are not locally testable. Random codes lack "structure" and in particular "symmetries" motivating the possibility that "symmetric LDPC" codes are locally testable, a question raised in the work of Alon et al. (IEEE IT, 2005). If true such a result would capture many of the basic ingredients of known locally testable codes. In this work we rule out such a possibility by giving a highly symmetric ("2-transitive") family of LDPC codes that are not testable with a constant number of queries. We do so by continuing the exploration of "affine-invariant codes" --- codes where the coordinates of the words are associated with a finite field, and the code is invariant under affine transformations of the field. New to our study is the use of fields that have many subfields, and showing that such a setting allows sufficient richness to provide new obstacles to local testability, even in the presence of structure and symmetry.}, affiliation = {EPFL}, author = {Ben-Sasson, Eli and Maatouk, Ghid and Shpilka, Amir and Sudan, Madhu}, booktitle = {26{t}h {IEEE} {C}onference on {C}omputational {C}omplexity}, details = {http://infoscience.epfl.ch/record/163770}, keywords = { affine invariance; Locally testable codes; LDPC codes; algoweb_misc}, location = {San Jose, California, USA}, oai-id = {oai:infoscience.epfl.ch:163770}, oai-set = {conf}, review = {REVIEWED}, status = {ACCEPTED}, submitter = {173510}, title = {Symmetric {LDPC} codes are not necessarily locally testable}, unit = {ALGO}, year = 2010 } @InProceedings{Brown2006/ALGO, abstract = {We introduce "derandomized" versions of the tensor product and the zig-zag product, extending the ideas in the derandomized squaring operation of Rozenman and Vadhan. These enable us to obtain graphs with smaller degrees than those obtained using their non-derandomized counterparts, though at the cost of slightly worse expansion. In this paper we give bounds on these expansions (measured by their second eigenvalues), and also obtain an improved bound on the expansion of the derandomized square.}, address = { }, affiliation = {EPFL}, author = {Brown, A. and Shokrollahi, A.}, booktitle = {Proceedings of the {IEEE} {I}nformation {T}heory {W}orkshop, 2006}, details = {http://infoscience.epfl.ch/record/99172}, doi = {10.1109/ITW.2006.1633804}, extra-id = {000245205900036}, keywords = {Graph Theory; Expanders; Coding Theory; algoweb_misc}, location = { }, oai-id = {oai:infoscience.epfl.ch:99172}, oai-set = {conf}, pages = {170--174}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Some graph products and their expansion properties}, unit = {ALGO}, url = { }, year = 2006 } @InProceedings{Brown2005/ALGO, abstract = { }, address = { }, affiliation = {EPFL}, author = {Brown, A. and Luby, M. and Shokrollahi, A.}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2005}, details = {http://infoscience.epfl.ch/record/99169}, doi = {10.1109/ISIT.2005.1523316}, extra-id = {000234713800037}, keywords = {algoweb_misc}, location = { }, oai-id = {oai:infoscience.epfl.ch:99169}, oai-set = {conf}, pages = {169--173}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Repeat-accumulate codes that approach the {G}ilbert-{V}arshamov bound}, unit = {ALGO}, url = { }, year = 2005 } @InProceedings{Etesami2004/ALGO, abstract = {This paper extends the construction and analysis of Raptor codes originally designed in A. Shokrollahi (2004) for the erasure channel to general symmetric channels. We explicitly calculate the asymptotic fraction of output nodes of degree one and two for capacity-achieving Raptor codes, and discuss techniques to optimize the output degree distribution.}, address = { }, affiliation = {EPFL}, author = {Etesami, O. and Molkaraie, M. and Shokrollahi, A.}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2004}, details = {http://infoscience.epfl.ch/record/99164}, doi = {10.1109/ISIT.2004.1365076}, keywords = {algoweb_fountain}, location = { }, oai-id = {oai:infoscience.epfl.ch:99164}, oai-set = {conf}, pages = {38}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Raptor codes on symmetric channels}, unit = {ALGO}, url = { }, year = 2004 } @InProceedings{Shokrollahi2004/ALGO, abstract = {This paper exhibits a class of universal Raptor codes: for a given integer k, and any real /spl epsiv/>0, Raptor codes in this class produce a potentially infinite stream of symbols such that any subset of symbols of size k(1 + /spl epsiv/) is sufficient to recover the original k symbols, with high probability. Each output symbol is generated using O(log(1//spl epsiv/)) operations, and the original symbols are recovered from the collected ones with O(klog(1//spl epsiv/)) operations.}, address = { }, affiliation = {EPFL}, author = {Shokrollahi, Amin}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2004}, details = {http://infoscience.epfl.ch/record/99166}, doi = {10.1109/ISIT.2004.1365073}, keywords = {algoweb_fountain}, location = { }, oai-id = {oai:infoscience.epfl.ch:99166}, oai-set = {conf}, pages = {36}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Raptor codes}, unit = {ALGO}, url = { }, year = 2004 } @InProceedings{Brown2004/ALGO, abstract = { }, address = { }, affiliation = {EPFL}, author = {Brown, A. and Minder, L. and Shokrollahi, A.}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2004}, details = {http://infoscience.epfl.ch/record/99161}, doi = {10.1109/ISIT.2004.1365363}, extra-id = {000223202600327}, keywords = {algoweb_agcodes}, location = { }, oai-id = {oai:infoscience.epfl.ch:99161}, oai-set = {conf}, pages = {326}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Probabilistic decoding of interleaved {RS}-codes on the q-ary symmetric channel}, unit = {ALGO}, url = { }, year = 2004 } @InProceedings{Luby1997/ALGO, abstract = {We present randomized constructions of linear-time encodable and decodable codes that can transmit over lossy channels at rates extremely close to capacity. The encod-ing and decoding algorithms for these codes have fast and simple software implementations. Partial implementationsof our algorithms are faster by orders of magnitude than the best software implementations of any previous algorithm forthis problem. We expect these codes will be extremely useful for applications such as real-time audio and video transmission over the Internet, where lossy channels are common and fast decoding is a requirement. Despite the simplicity of the algorithms, their design andanalysis are mathematically intricate. The design requires the careful choice of a random irregular bipartite graph,where the structure of the irregular graph is extremely important. We model the progress of the decoding algorithmby a set of differential equations. The solution to these equations can then be expressed as polynomials in one variable with coefficients determined by the graph structure. Based on these polynomials, we design a graph structure that guarantees successful decoding with high probability}, address = { }, affiliation = {OTHER}, author = {Luby, M. and Mitzenmacher, M. and Shokrollahi, A. and Spielman, D. A. and Stemann, V}, booktitle = {Proceedings of the 29th annual {ACM} {S}ymposium on {T}heory of {C}omputing, {STOC} 1997}, details = {http://infoscience.epfl.ch/record/99185}, doi = {10.1145/258533.258573}, keywords = {LDPC codes; algoweb_ldpc}, location = { }, oai-id = {oai:infoscience.epfl.ch:99185}, oai-set = {conf}, pages = {150--159}, publisher = {ACM Press}, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Practical loss-resilient codes}, unit = {ALGO}, url = { }, year = 1997 } @InProceedings{EPFL-CONF-162366, abstract = {We consider ensembles of binary linear error correcting codes, obtained by sampling each column of the generator matrix G or parity check matrix H independently from the set of all binary vectors of weight d (of appropriate dimension). We investigate the circumstances under which the mutual information between a randomly chosen codeword and the vector obtained after its transmission over a binary input memoryless symmetric channel (BIMSC) C is exactly n times the capacity of C, where n is the length of the code. For several channels such as the binary symmetric channel (BSC) and the binary-input additive white Gaussian noise (AWGN) channel, we prove that the probability of this event has a threshold behaviour, depending on whether n/k is smaller than a certain quantity (that depends on the particular channel C and d), where k is the number of source bits. To show this, we prove a generalization of the following well-known theorem: the expectation of the size of the right kernel of G has a phase transition from 1 to infinity, depending on whether or not n/k is smaller than a certain quantity depending on the chosen ensemble.}, affiliation = {EPFL}, author = {Kumar, Krishna and Kumar, Raj and Pakzad, Payam and Salavati, Amir Hesam and Shokrollahi, Mohammad Amin}, booktitle = {Proc. 6{t}h {I}ntl. Symposium on {T}urbo {C}odes and {I}terative {I}nformation {P}rocessing ({ISTC} - 2010)}, details = {http://infoscience.epfl.ch/record/162366}, documenturl = {http://infoscience.epfl.ch/record/162366/files/Phase Transition for Mutual Information.pdf}, keywords = {algoweb_structmat; algoweb_fountain; Phase transition; Fountain codes; mutual information; Channel capacity}, location = {Brest, France}, oai-id = {oai:infoscience.epfl.ch:162366}, oai-set = {conf}, pages = {137--141}, publisher = {IEEE}, review = {REVIEWED}, status = {PUBLISHED}, submitter = {190838}, title = {Phase {T}ransitions for {M}utual {I}nformation}, unit = {ALGO}, year = 2010 } @InProceedings{ALGO-CONF-2009-005, 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 give a general framework for construction of highly noise-resilient group testing schemes using randomness condensers. Simple randomized instantiations of this construction give 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 $\delta m$ false positives and $\Omega(m/d)$ false negatives within the measurement outcomes, for any constant $\delta < 1$. None of these parameters can be substantially improved without dramatically affecting the others. Furthermore, we obtain several explicit (and incomparable) 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 $poly(m)$, which would be sublinear in $n$ for sufficiently sparse vectors.}, address = { }, affiliation = {EPFL}, author = {Cheraghchi, Mahdi}, booktitle = {Proceedings of the 17th {I}nternational {S}ymposium on {F}undamentals of {C}omputation {T}heory ({FCT})}, details = {http://infoscience.epfl.ch/record/141321}, documenturl = {http://infoscience.epfl.ch/record/141321/files/testingCR.pdf}, extra-id = {000270320900006}, keywords = {algoweb_misc}, location = {Wroclaw, Poland}, oai-id = {oai:infoscience.epfl.ch:141321}, oai-set = {conf}, pages = {62--73}, publisher = {Springer}, review = {REVIEWED}, series = {Lecture Notes in Computer Science}, status = {PUBLISHED}, title = {Noise-{R}esilient {G}roup {T}esting: {L}imitations and {C}onstructions}, unit = {ALGO}, url = {http://fct2009.im.pwr.wroc.pl/}, year = 2009 } @InProceedings{Maneva2006/ALGO, abstract = {We present a new model for LT codes which simplifies the analysis of the error probability of decoding by belief propagation. For any given degree distribution, we provide the first rigorous expression for the limiting bit-error probability as the length of the code goes to infinity via recent results in random hypergraphs by Darling and Norris, Ann. Appl. Probab., 2005. For a code of finite length, we provide an algorithm for computing the probability of block-error of the decoder. This algorithm improves by a linear factor the algorithm of Karp, Luby, and Shokrollahi, Proc. of ISIT, 2004.}, address = { }, affiliation = {EPFL}, author = {Maneva, E. and Shokrollahi, A.}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2006}, details = {http://infoscience.epfl.ch/record/99175}, doi = {10.1109/ISIT.2006.262139}, keywords = {Fountain Codes; LT Codes; Graph based Codes; Probability; algoweb_fountain}, location = { }, oai-id = {oai:infoscience.epfl.ch:99175}, oai-set = {conf}, pages = {2677--2679}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {New model for rigorous analysis of {LT}-codes}, unit = {ALGO}, url = { }, year = 2006 } @InProceedings{EPFL-CONF-168881, abstract = {We consider the problem of neural association, which deals with the retrieval of a previously memorized pattern from its noisy version. The performance of various neural networks developed for this task may be judged in terms of their pattern retrieval capacities (the number of patterns that can be stored), and their error-correction (noise tolerance) capabilities. While significant progress has been made, most prior works in this area show poor performance with regard to pattern retrieval capacity and/or error correction. In this paper, we propose two new methods to significantly increase the pattern retrieval capacity of the Hopfield and Bidirectional Associative Memories (BAM). The main idea is to store patterns drawn from a family of low correlation sequences, similar to those used in Code Division Multiple Access (CDMA) communications, instead of storing purely random patterns as in prior works. These low correlation patterns can be obtained from random sequences by pre-coding the original sequences via simple operations that both real and artificial neurons are capable of accomplishing.}, affiliation = {EPFL}, author = {Salavati, Amir Hesam and Kumar, K. Raj and Shokrollahi, Amin and Gerstner, Wulfram}, booktitle = {2011 Ieee {I}nternational {S}ymposium {O}n {I}nformation {T}heory {P}roceedings ({I}sit)}, details = {http://infoscience.epfl.ch/record/168881}, documenturl = {http://infoscience.epfl.ch/record/168881/files/ISIT_camera_ready.pdf}, extra-id = {000297465101006}, keywords = {Neural networks; CDMA communications; Hopfield Networks; Associative memory; Coding theory; algoweb_bio}, location = {Saint-Petersburg, Russia}, oai-id = {oai:infoscience.epfl.ch:168881}, oai-set = {conf}, pages = {850--854}, publisher = {Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa}, review = {REVIEWED}, status = {PUBLISHED}, submitter = {190838; 190838; 190838}, title = {Neural {P}re-coding {I}ncreases the {P}attern {R}etrieval {C}apacity of {H}opfield and {B}idirectional {A}ssociative {M}emories}, unit = {ALGO LCN}, year = 2011 } @InProceedings{Hassibi2000a/ALGO, abstract = {Multiple antennas can greatly increase the data rate and reliability of a wireless communication link in a fading environment, but the practical success of using multiple antennas depends crucially on our ability to design high-rate space-time constellations with low encoding and decoding complexity. It has been shown that full transmitter diversity, where the constellation is a set of unitary matrices whose differences have nonzero determinant, is a desirable property for good performance. We use the powerful theory of fixed-point-free groups and their representations to design high-rate constellations with full diversity. Furthermore, we thereby classify all full-diversity constellations that form a group, for all rates and numbers of transmitter antennas. The group structure makes the constellations especially suitable for differential modulation and low- complexity decoding algorithms. The classification also reveals that the number of different group structures with full diversity is very limited when the number of transmitter antennas is large and odd. We therefore also consider extensions of the constellation designs to nongroups. We conclude by showing that many of our designed constellations perform excellently on both simulated and real wireless channels}, address = { }, affiliation = {OTHER}, author = {Hassibi, B. and Hochwald, B. and Shokrollahi, A. and Sweldens, W.}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2000}, details = {http://infoscience.epfl.ch/record/99193}, doi = {10.1109/ISIT.2000.866635}, keywords = {algoweb_multantenna}, location = { }, oai-id = {oai:infoscience.epfl.ch:99193}, oai-set = {conf}, pages = {337}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Multiple antennas and representation theory}, unit = {ALGO}, url = { }, year = 2000 } @InProceedings{EPFL-CONF-176920, abstract = {The problem of neural network association is to retrieve a previously memorized pattern from its noisy version using a network of neurons. An ideal neural network should include three components simultaneously: a learning algorithm, a large pattern retrieval capacity and resilience against noise. Prior works in this area usually improve one or two aspects at the cost of the third. Our work takes a step forward in closing this gap. More specifically, we show that by forcing natural constraints on the set of learning patterns, we can drastically improve the retrieval capacity of our neural network. Moreover, we devise a learning algorithm whose role is to learn those patterns satisfying the above mentioned constraints. Finally we show that our neural network can cope with a fair amount of noise.}, address = {New York}, affiliation = {EPFL}, author = {Salavati, Amir Hesam and Karbasi, Amin}, booktitle = {Proceedings of {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory ({ISIT} 2012)}, details = {http://infoscience.epfl.ch/record/176920}, documenturl = {http://infoscience.epfl.ch/record/176920/files/SK_ISIT_2012.pdf}, extra-id = {000312544301032}, isbn = {978-1-4673-2579-0}, keywords = {Neural networks; Associative memory; Message passing; Coding theory; Iterative learning; Stochastic learning; algoweb_bio}, location = {Boston, Massachusetts, USA}, oai-id = {oai:infoscience.epfl.ch:176920}, oai-set = {conf}, pagecount = {5}, pages = {1064 -- 1068}, publisher = {IEEE}, review = {REVIEWED}, series = {IEEE International Symposium on Information Theory}, status = {PUBLISHED}, submitter = {190838; 190838}, title = {Multi-{L}evel {E}rror-{R}esilient {N}eural {N}etworks}, unit = {ALGO}, url = {https://docs.google.com/open?id=0B2poqrkA0LCyT2ZSMXZCbzQ1TzA}, year = 2012 } @InProceedings{Olhoevsky2000/ALGO, abstract = {Many important problems in pure and applied mathematics and engineering can be reduced to linear algebra on dense structured matrices. The structure of these dense matrices is understood in the sense that their n2 entries can be "compressed" to a smaller number O(n) of parameters. Operating directly on these parameters allows one to design efficient fast algorithms for these matrices. One of the most prominent matrix problems is that of multiplying a (structured) matrix with a vector. Many fundamental algorithms like convolution, Fast Fourier Transform, Fast Cosine/Sine Transform, and polynomial and rational multipoint evaluation and interpolation can be interpreted as superfast multiplication of a vector by structured matrices (like Toeplitz, DFT, Vandermonde, Cauchy). In this paper, we introduce a novel and fairly general class of structured matrices, which we call confluent Cauchy- like matrices, that contains all the above classes as a special case, and we will des a confluent Cauchy-like matrix by a vector. This is precisely what has been done in this paper}, address = { }, affiliation = {OTHER}, author = {Olshevsky, V. and Shokrollahi, A}, booktitle = {Proceedings of the 32nd annual {ACM} {S}ymposium on {T}heory of {C}omputing, {STOC} 2000}, details = {http://infoscience.epfl.ch/record/99706}, doi = {10.1145/335305.335380}, keywords = {algoweb_structmat}, location = { }, oai-id = {oai:infoscience.epfl.ch:99706}, oai-set = {conf}, pages = {573--581}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Matrix vector product for confluent {C}auchy-like matrices with applications to confluent rational interpolation}, unit = {ALGO}, url = { }, year = 2000 } @InProceedings{Shokrollahi2004b/ALGO, abstract = {Transmission of packets over computer networks is subject to packet-level errors, which appear as "bursts" of bit-level errors and are not well modeled by memoryless binary channels. A standard scrambling technique is used for transmission of packets by the q-ary symmetric channel (q-SC) with alphabet size q and error probability p. Furthermore, significant improvements in computational efficiency can be obtained by codes that operate at the packet-level instead of the bit-level. The capacity of the q-SC is 1+p log/sub q/ (p)+(1-p)log/sub q/ (1-p)-plog/sub q/ (1-q), which is close to 1-p for large q. First designed an efficient decoding algorithm for LDPC codes on the q-SC, and showed that it can afford rates arbitrarily close to 1-2p. We improve the analysis of this decoding algorithm to show that LDPC codes with the Tornado edge distribution, together with an erasure precode, can achieve rates e-close to capacity. We also extend this decoder into a family of decoding algorithms, which become progressively more powerful but also more complex. We show that in the limit, when the decoder is allowed to look infinitely deep into the decoding tree, it can achieve capacity without precoding. However computational requirements make this decoder impractical.}, address = { }, affiliation = {EPFL}, author = {Shokrollahi, A. and Wang, W.}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2004}, details = {http://infoscience.epfl.ch/record/99168}, doi = {10.1109/ISIT.2004.1365310}, extra-id = {000223202600275}, keywords = {algoweb_ldpc}, location = { }, oai-id = {oai:infoscience.epfl.ch:99168}, oai-set = {conf}, pages = {275}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Low-density parity-check codes with rates very close to the capacity of the q-ary symmetric channel for large q}, unit = {ALGO}, url = { }, year = 2004 } @InProceedings{EPFL-CONF-185202, abstract = {The task of a neural associative memory is to retrieve a set of previously memorized pat- terns from their noisy versions by using a net- work of neurons. Hence, an ideal network should be able to 1) gradually learn a set of patterns, 2) retrieve the correct pattern from noisy queries and 3) maximize the number of memorized patterns while maintaining the reliability in responding to queries. We show that by considering the inherent redundancy in the memorized patterns, one can obtain all the mentioned properties at once. This is in sharp contrast with previous work that could only improve one or two aspects at the expense of the others. More specifically, we devise an iterative algorithm that learns the redundancy among the patterns. The resulting network has a retrieval capacity that is exponential in the size of the network. Lastly, by considering the local structures of the net- work, the asymptotic error correction performance can be made linear in the size of the network.}, affiliation = {EPFL}, author = {Karbasi, Amin and Salavati, Amir Hesam and Shokrollahi, Amin}, booktitle = {Proceedings 30th {I}nternational {C}onference on {M}achine {L}earning ({ICML})}, details = {http://infoscience.epfl.ch/record/185202}, documenturl = {http://infoscience.epfl.ch/record/185202/files/Iterative Learning and Denoising in Convolutional Neural Associative Memories.pdf}, keywords = {algoweb_bio; Neural networks; Associative memory; Message passing; Coding theory; Iterative learning; Stochastic learning; Convolutional neural networks; Convolutional codes}, location = {Atlanta, USA}, number = {1}, oai-id = {oai:infoscience.epfl.ch:185202}, oai-set = {conf}, pages = {445--453}, review = {NON-REVIEWED}, status = {PUBLISHED}, submitter = {190838}, title = {Iterative {L}earning and {D}enoising in {C}onvolutional {N}eural {A}ssociative {M}emories}, unit = {ALGO LTHC}, url = {http://jmlr.csail.mit.edu/proceedings/papers/v28/karbasi13.pdf}, volume = {28}, year = 2013 } @InProceedings{EPFL-CONF-185109, abstract = {We introduce irregular product codes, a class of codes where each codeword is represented by a matrix and the entries in each row (column) of the matrix come from a component row (column) code. As opposed to standard product codes, we do not require that all component row codes nor all component column codes be the same. Relaxing this requirement can provide some additional attractive features such as allowing some regions of the codeword to be more error-resilient, providing a more refined spectrum of rates for finite lengths, and improved performance for some of these rates. We study these codes over erasure channels and prove that for any 0 < ε < 1, for many rate distributions on component row codes, there is a matching rate distribution on component column codes such that an irregular product code based on MDS codes with those rate distributions on the component codes has asymptotic rate 1 - ε and can decode on erasure channels having erasure probability <; ε (and having alphabet size equal to the alphabet size of the component MDS codes).}, address = {New York}, affiliation = {EPFL}, author = {Alipour Babaei, Masoud and Etesami, Seyed Omid and Maatouk, Ghid and Shokrollahi, Amin}, booktitle = {2012 {IEEE} {INFORMATION} {THEORY} {WORKSHOP} ({ITW})}, details = {http://infoscience.epfl.ch/record/185109}, documenturl = {http://infoscience.epfl.ch/record/185109/files/irregular_product_codes.pdf}, doi = {10.1109/ITW.2012.6404656}, extra-id = {000313526400042}, isbn = {978-1-4673-0222-7}, location = {Lausanne, Switzerland}, oai-id = {oai:infoscience.epfl.ch:185109}, oai-set = {conf}, pagecount = {5}, pages = {197--201}, publisher = {Ieee}, review = {REVIEWED}, status = {PUBLISHED}, submitter = {173510}, title = {Irregular {P}roduct {C}odes}, unit = {ALGO}, year = 2012 } @InProceedings{ALGO-CONF-2009-003, abstract = {A wiretap protocol is a pair of randomized encoding and decoding functions such that knowledge of a bounded fraction of the encoding of a message reveals essentially no information about the message, while knowledge of the entire encoding reveals the message using the decoder. In this paper we study the notion of efficiently invertible extractors and show that a wiretap protocol can be constructed from such an extractor. We will then construct invertible extractors for symbol-fixing, affine, and general sources and apply them to create wiretap protocols with asymptotically optimal trade-offs between their rate (ratio of the length of the message versus its encoding) and resilience (ratio of the observed positions of the encoding and the length of the encoding). We will then apply our results to create wiretap protocols for challenging communication problems, such as active intruders who change portions of the encoding, network coding, and intruders observing arbitrary boolean functions of the encoding.}, address = { }, affiliation = {EPFL}, author = {Cheraghchi, Mahdi and Didier, Feredric and Shokrollahi, Amin}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory ({ISIT})}, details = {http://infoscience.epfl.ch/record/141319}, documenturl = {http://infoscience.epfl.ch/record/141319/files/ISIT09camera.pdf}, keywords = {algoweb_misc}, location = { }, oai-id = {oai:infoscience.epfl.ch:141319}, oai-set = {conf}, pages = {1934--1938}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Invertible {E}xtractors and {W}iretap {P}rotocols}, unit = {ALGO}, url = { }, year = 2009 } @InProceedings{ALGO-CONF-2007-001, abstract = {We analyze a generalization of a recent algorithm of Bleichenbacher et al.~for decoding interleaved codes on the $Q$-ary symmetric channel for large $Q$. We will show that for any $m$ and any $\epsilon$ the new algorithms can decode up to a fraction of at least $\frac{\beta m}{\beta m+1}(1-R-2Q^{- 1/2m})-\epsilon$ errors (where $\beta = \frac{\ln(q^m - 1)}{\ln(q^m)}$), and that the error probability of the decoder is upper bounded by $O(1/q^{\epsilon n})$, where $n$ is the block-length. The codes we construct do not have a- priori any bound on their length.}, address = { }, affiliation = {EPFL}, author = {Brown, Andrew and Minder, Lorenz and Shokrollahi, Amin}, booktitle = {Proc. 10{t}h {IMA} {C}onf. {o}n {C}ryptography and {C}oding}, details = {http://infoscience.epfl.ch/record/101002}, documenturl = {http://infoscience.epfl.ch/record/101002/files/finalPaper.pdf}, extra-id = {000235773700003}, keywords = {Reed-Solomon; Algebraic-Geometric; interleaved; code; algoweb_agcodes}, location = {Cirencester, UK}, number = {1}, oai-id = {oai:infoscience.epfl.ch:101002}, oai-set = {conf}, pages = {37--46}, publisher = { }, review = {REVIEWED}, series = {Lecture Notes in Computer Science}, status = {PUBLISHED}, title = {Improved {D}ecoding of {I}nterleaved {AG}-{C}odes}, unit = {ALGO}, url = { }, volume = {1}, year = 2005 } @InProceedings{EPFL-CONF-151699, abstract = {The basic goal in combinatorial group testing is to identify a set of up to d defective items within a large population of size n >> d using a pooling strategy. Namely, the items can be grouped together in pools, and a single measurement would reveal whether there are one or more defectives in the pool. The threshold model is a generalization of this idea where a measurement returns positive if the number of defectives in the pool passes a fixed threshold u, negative if this number is below a fixed lower threshold L <= u, and may behave arbitrarily otherwise. We study non-adaptive threshold group testing (in a possibly noisy setting) and show that, for this problem, O(d^{g+2} (\log d) log(n/d)) measurements (where g := u-L) suffice to identify the defectives, and also present almost matching lower bounds. This significantly improves the previously known non-constructive) upper bound O(d^{u+1} log(n/d)). Moreover, we obtain a framework for explicit construction of measurement schemes using lossless condensers. The number of measurements resulting from this scheme is ideally bounded by O(d^{g+3} (\log d) \log n). Using state-of-the-art constructions of lossless condensers, however, we come up with explicit testing schemes with O(d^{g+3} (\log d) quasipoly(log n)) and O(d^{g+3+beta} poly(log n)) measurements, for arbitrary constant beta > 0.}, affiliation = {EPFL}, author = {Cheraghchi, Mahdi}, booktitle = {Proceedings of the 37th {I}nternational {C}olloquium on {A}utomata, {L}anguages and {P}rogramming ({ICALP})}, details = {http://infoscience.epfl.ch/record/151699}, extra-id = {000286345400047}, keywords = {algo_misc}, location = {Bordeaux, France}, oai-id = {oai:infoscience.epfl.ch:151699}, oai-set = {conf}, publisher = {Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa}, review = {REVIEWED}, series = {Lecture Notes in Computer Science}, status = {PUBLISHED}, submitter = {166246; 166246}, title = {Improved {C}onstructions for {N}on-adaptive {T}hreshold {G}roup {T}esting}, unit = {ALGO}, year = 2010 } @InProceedings{Shokrollahi2001b/ALGO, abstract = {Hassibi, Hochwald, Shokrollahi and Sweldens (see tech. rep., Bell Laboratories, Lucent Technologies, 2000) classified all finite groups of unitary matrices with nonzero diversity product. It is well-known, however, that differential space- time codes with vanishing diversity product still can perform reasonably well under certain conditions. We show how to compute parameters of finite groups crucial for their use as space-time constellations, using only the character table of the group. Simulations are given for the group SL(2,17)}, address = { }, affiliation = {OTHER}, author = {Shokrollahi, Amin}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2001}, details = {http://infoscience.epfl.ch/record/99206}, doi = {10.1109/ISIT.2001.935970}, keywords = {algoweb_spacetime}, location = { }, oai-id = {oai:infoscience.epfl.ch:99206}, oai-set = {conf}, pages = {107}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Group characters and unitary space-time codes}, unit = {ALGO}, url = { }, year = 2001 } @InProceedings{Ndzana2006/ALGO, abstract = {In this paper, we describe one solution to the two-user Slepian-Wolf problem in a certain part of the achievable region using fountain codes. Symmetric case of memoryless compression of two correlated sources is considered and modeled by a BSC channel. The compression is done by two separate compressors without any exchange of information between them. The decompressor uses a Belief propagation algorithm in conjunction with the Blind Iterative Doping strategy. Simulation results indicate performance close to the Slepian-Wolf limit.}, address = { }, affiliation = {EPFL}, author = {Ndzana, Bertrand and Shokrollahi, Amin and Abel, J}, booktitle = {Proceedings of {A}nnual {A}llerton {C}onference on {C}ommunication, {C}ontrol, and {C}omputing -- {I}nvited {P}aper}, details = {http://infoscience.epfl.ch/record/99176}, keywords = {algoweb_fountain}, location = { }, oai-id = {oai:infoscience.epfl.ch:99176}, oai-set = {conf}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Fountain {C}odes for the {S}lepian-{W}olf {P}roblem}, unit = {ALGO}, url = { }, year = 2006 } @InProceedings{ALGO-CONF-2008-007, abstract = {In this paper, two fixed per-information symbol complexity lossless source coding algorithms are modified for estimation and incremental LT decoding over piecewise stationary memoryless channels (PSMC's) with a bounded number of abrupt changes in channel statistics. In particular, as a class of PSMC's, binary symmetric channels are considered with a crossover probability that changes a bounded number of times with no repetitions in the statistics. Simulation results are given which illustrate the benefits of using our algorithms, both in terms of probability of error and in terms of redundancy.}, address = {Toronto}, affiliation = {EPFL}, author = {Ndzana Ndzana, Bertrand and Shokrollahi, Amin and Eckford, Andrew and Shamir, Gil}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory}, details = {http://infoscience.epfl.ch/record/128398}, extra-id = {000260364401172}, keywords = {Fountain codes; Source coding; Piecewise stationary channels; algoweb_fountain}, location = {Toronto}, oai-id = {oai:infoscience.epfl.ch:128398}, oai-set = {conf}, pages = {2242 -- 2246}, publisher = {IEEE}, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Fountain codes for piecewise stationary channels}, unit = {ALGO}, url = { }, year = 2008 } @InProceedings{Richrdson2002/ALGO, abstract = {We investigate the average erasure probability of the belief propagation algorithm over the binary erasure channel (BEC) for various finite-length low- density parity-check (LDPC) ensembles. In particular, we give tight upper bounds on the "error floor", i.e., on the contribution to the erasure probability stemming from relatively small deficiencies in the graph. We also define and analyse "expurgated" ensembles and give upper bounds on the error floor of "typical" codes. Finally, we show that typical codes of properly chosen ensembles have an erasure correcting radius which grows linearly in the block length. The presented method provides valuable insight into how finite- length codes should be designed. Although the standard ensemble can achieve capacity on the BEC, the construction of good finite-length codes requires careful control of the structure of the degree two variable nodes. In this paper, we investigate the standard ensemble, the Poisson ensemble, an ensemble in which degree two nodes are added in a cycle, and an ensemble in which different degree two variable nodes have distinct neighboring check nodes.}, address = { }, affiliation = {OTHER}, author = {Richrdson, T. and Shokrollahi, A. and Urbanke, R.}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2002}, details = {http://infoscience.epfl.ch/record/99210}, doi = {10.1109/ISIT.2002.1023273}, keywords = {algoweb_ldpc}, location = { }, oai-id = {oai:infoscience.epfl.ch:99210}, oai-set = {conf}, pages = {1}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Finite-length analysis of various low-density parity-check ensembles for the binary erasure channel}, unit = {ALGO}, url = { }, year = 2002 } @InProceedings{Karp2004/ALGO, abstract = {This paper provides an efficient method for analyzing the error probability of the belief propagation (BP) decoder applied to LT Codes. Each output symbol is generated independently by sampling from a distribution and adding the input symbols corresponding to the support of the sampled vector.}, address = { }, affiliation = {EPFL}, author = {Karp, R. and Luby, M. and Shokrollahi, A.}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2004}, details = {http://infoscience.epfl.ch/record/99165}, doi = {10.1109/ISIT.2004.1365074}, keywords = {algoweb_ldpc}, location = { }, oai-id = {oai:infoscience.epfl.ch:99165}, oai-set = {conf}, pages = {39}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Finite length analysis of {LT} codes}, unit = {ALGO}, url = { }, year = 2004 } @InProceedings{Buhler1997/ALGO, abstract = {Many applications of fast fourier transforms (FFT's), such as computer- tomography, geophysical signal processing, high resolution imaging radars, and prediction filters, require high precision output. The usual method of fixed point computation of FFT's of vectors of length 2l leads to an average loss of l/2 bits of precision. This phenomenon, often referred to as computational noise, causes major problems for arithmetic units with limited precision which are often used for real time applications. Several researchers have noted that calculation of FFT's with algebraic integers avoids computational noise entirely, see, e.g., [3]. We will show that complex numbers can be approximated accurately by cyclotomic integers, and combine this idea with Chinese remaindering strategies in the cyclotomic integers to, roughly, give a O(b1+? L log (L)) algorithm to compute b-bit precision FFT's of length L. The first part of the paper will describe the FFT strategy, assuming good app..}, address = { }, affiliation = {OTHER}, author = {Buhler, J. P. and Shokrollahi, A. and Stemann, V.}, booktitle = {Proceedings of the 29th annual {ACM} {S}ymposium on {T}heory of {C}omputing, {STOC} 1997}, details = {http://infoscience.epfl.ch/record/99697}, doi = {10.1145/258533.258545}, keywords = {algoweb_numbertheory}, location = { }, oai-id = {oai:infoscience.epfl.ch:99697}, oai-set = {conf}, pages = {40--47}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Fast and precise computation of discrete {F}ourier {T}ransforms using cyclotomic integers}, unit = {ALGO}, url = { }, year = 1997 } @InProceedings{EPFL-CONF-168882, abstract = {We consider 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 linearly with the number of neurons in the network. In our formulation of the problem, we consider storing patterns from a suitably chosen set of patterns, that are obtained by enforcing a set of simple constraints on the coordinates (such as those enforced in graph based codes). Such patterns may be generated from purely random information symbols by simple neural operations. Two simple neural update algorithms are presented, and it is shown that our proposed mechanisms result in a pattern retrieval capacity that is exponential in terms of the network size. Furthermore, using analytical results and simulations, we show that the suggested methods can tolerate a fair amount of errors in the input.}, affiliation = {EPFL}, author = {Kumar, K. Raj and Salavati, Amir Hesam and Shokrollahi, Amin}, booktitle = {2011 Ieee {I}nformation {T}heory {W}orkshop ({I}tw)}, details = {http://infoscience.epfl.ch/record/168882}, documenturl = {http://infoscience.epfl.ch/record/168882/files/ITW11_May13.pdf}, extra-id = {000299416200017}, keywords = {Neural networks; Associative memory; Compressed sensing; Expander codes; algoweb_bio}, location = {Paraty, Brazil}, oai-id = {oai:infoscience.epfl.ch:168882}, oai-set = {conf}, pages = {--}, publisher = {Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa}, review = {REVIEWED}, status = {PUBLISHED}, submitter = {190838; 190838; 190838}, title = {Exponential {P}attern {R}etrieval {C}apacity with {N}on-{B}inary {A}ssociative {M}emory}, unit = {ALGO}, year = 2011 } @InProceedings{ALGO-CONF-2007-005, abstract = {In this paper we propose a new structure for multiplication using optimal normal bases of type $2$. The multiplier uses an efficient linear transformation to convert the normal basis representations of elements of $F_{q^{n}}$ to suitable polynomials of degree at most $n$ over $F_{q}$. These polynomials are multiplied using any method which is suitable for the implementation platform, then the product is converted back to the normal basis using the inverse of the above transformation. The efficiency of the transformation arises from a special factorization of its matrix into sparse matrices. This factorization --- which resembles the FFT factorization of the DFT matrix --- allows to compute the transformation and its inverse using $O(n \log n)$ operations in $F_{q}$, rather than $O(n^{2})$ operations needed for a general change of basis. Using this technique we can reduce the asymptotic cost of multiplication in optimal normal bases of type $2$ from $2 M(n) + O(n)$ reported by Gao et al.~(2000)\nocite{gaogat00} to $M(n)+O(n \log n)$ operations in $F_{q}$, where $M(n)$ is the number of $F_{q}$-operations to multiply two polynomials of degree $n-1$ over $F_{q}$. We show that this cost is also smaller than other proposed multipliers for $n > 160$, values which are used in elliptic curve cryptography.}, address = { }, affiliation = {EPFL}, author = {von zur Gathen, Joachim and Shokrollahi, Amin and Shokrollahi, Jamshid}, booktitle = {International {W}orkshop on the {A}rithmetic of {F}inite {F}ields, {WAIFI} 2007}, details = {http://infoscience.epfl.ch/record/112310}, documenturl = {http://infoscience.epfl.ch/record/112310/files/WaiFi-Final.pdf}, keywords = {Finite field arithmetic; optimal normal bases; asymptotically fast algorithms; algoweb_numbertheory}, location = {Madrid}, oai-id = {oai:infoscience.epfl.ch:112310}, oai-set = {conf}, pages = {55--68}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Efficient multiplication using type $2$ optimal normal bases}, unit = {ALGO}, url = { }, year = 2007 } @InProceedings{Shokrollahi2001a/ALGO, abstract = {We establish a relationship between optimization of the diversity product for two-antenna diagonal space-time codes and the elementary theory of continued fractions}, address = { }, affiliation = {OTHER}, author = {Shokrollahi, Amin}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2001}, details = {http://infoscience.epfl.ch/record/99205}, doi = {10.1109/ISIT.2001.935971}, keywords = {algoweb_spacetime}, location = { }, oai-id = {oai:infoscience.epfl.ch:99205}, oai-set = {conf}, pages = {108}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Double antenna diagonal space-time codes and continued fractions}, unit = {ALGO}, url = { }, year = 2001 } @InProceedings{Pakzad2006/ALGO, abstract = {In this paper we describe some practical aspects of the design process of good Raptor codes for finite block lengths over arbitrary binary input symmetric channels. In particular we introduce a simple model for the finite-length convergence behavior of the iterative decoding algorithm based on density evolution, and propose a practical design procedure. We report simulation results for some example codes.}, address = { }, affiliation = {EPFL}, author = {Pakzad, P. and Shokrollahi, A.}, booktitle = {Proceedings of the {IEEE} {I}nformation {T}heory {W}orkshop, 2006}, details = {http://infoscience.epfl.ch/record/99178}, doi = {10.1109/ITW.2006.1633803}, extra-id = {000245205900035}, keywords = {algoweb_fountain}, location = { }, oai-id = {oai:infoscience.epfl.ch:99178}, oai-set = {conf}, pages = {165--169}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Design {P}rinciples for {R}aptor {C}odes}, unit = {ALGO}, url = { }, year = 2006 } @InProceedings{Shokrollahi2001c/ALGO, abstract = {We explicitly construct an irreducible four-dimensional unitary representation of the Lie group SU(2) and use it for the construction of high-rate unitary space- time codes for four transmit antennas. Our construction calls for the design of such spherical codes in which the angle between any two points is well separated from 120 degrees. We give a partial solution to this restricted design problem and use numerical optimization techniques to optimize our solution}, address = { }, affiliation = {OTHER}, author = {Shokrollahi, Amin}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2001}, details = {http://infoscience.epfl.ch/record/99207}, doi = {10.1109/ISIT.2001.936104}, keywords = {algoweb_multantenna}, location = { }, oai-id = {oai:infoscience.epfl.ch:99207}, oai-set = {conf}, pages = {241}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Design of unitary space-time codes from representations of {SU}(2)}, unit = {ALGO}, url = { }, year = 2001 } @InProceedings{Richardson2000/ALGO, abstract = {We design sequences of low-density parity check codes that provably perform at rates extremely close to the Shannon capacity. These codes are built from highly irregular bipartite graphs with carefully chosen degree patterns on both sides. We further show that under suitable conditions the message densities fulfil a certain symmetry condition which we call the consistency condition and we present a stability condition which is the most powerful tool to date to bound/determine the threshold of a given family of low-density parity check codes}, address = { }, affiliation = {OTHER}, author = {Richardson, T. and Shokrollahi, A. and Urbanke, R.}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2000}, details = {http://infoscience.epfl.ch/record/99195}, doi = {10.1109/ISIT.2000.866497}, keywords = {algoweb_ldpc}, location = { }, oai-id = {oai:infoscience.epfl.ch:99195}, oai-set = {conf}, pages = {199}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Design of provably good low-density parity check codes}, unit = {ALGO}, url = { }, year = 2000 } @InProceedings{Shokrollahi2000b/ALGO, abstract = {The design of practical and powerful codes for protection against erasures can be reduced to optimizing solutions of a highly nonlinear constraint satisfaction problem. In this paper we will attack this problem using the differential evolution approach and significantly improve results previously obtained using classical optimization procedures}, address = { }, affiliation = {OTHER}, author = {Shokrollahi, A. and Storn, R.}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2000}, details = {http://infoscience.epfl.ch/record/99198}, doi = {10.1109/ISIT.2000.866295}, keywords = {algoweb_ldpc}, location = { }, oai-id = {oai:infoscience.epfl.ch:99198}, oai-set = {conf}, pages = {5}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Design of efficient erasure codes with differential evolution}, unit = {ALGO}, url = { }, year = 2000 } @InProceedings{Shokrollahi2001/ALGO, abstract = {It is well-known that multiple transmit and receiving antennas can significantly improve the performance of wireless networks. The design of good modulation schemes for the model of multiple antenna wireless transmission in a fast fading environment (e.g., mobile communication) leads to an interesting packing problem for unitary matrices. Surprisingly, the latter problem is related to certain aspects of finite (and infinite) group theory. In this paper we will give a brief survey of some of these connections.}, address = { }, affiliation = {OTHER}, author = {Shokrollahi, Amin}, booktitle = {Proceedings of the 14th {I}nternational {S}ymposium on {A}pplied {A}lgebra, {A}lgebraic {A}lgorithms and {E}rror-{C}orrecting {C}odes, {AAECC}-14, 2001}, details = {http://infoscience.epfl.ch/record/99204}, keywords = {algoweb_spacetime}, location = { }, oai-id = {oai:infoscience.epfl.ch:99204}, oai-set = {conf}, pages = {22--35}, publisher = {Springer}, review = {REVIEWED}, series = {Lecture Notes in Computer Science}, status = {PUBLISHED}, title = {Design of {D}ifferential {S}pace-{T}ime {C}odes {U}sing {G}roup {T}heory}, unit = {ALGO}, url = {http://www.springerlink.com/content/mwgatjv3amy7y0nh/url.pdf}, volume = {2227}, year = 2001 } @InProceedings{EPFL-CONF-152532, abstract = {The rapid development of derandomization theory, which is a fundamental area in theoretical computer science, has recently led to many surprising applications outside its initial intention. We will review some recent such developments related to combinatorial group testing. In its most basic setting, the aim of group testing is to identify a set of "positive" individuals in a population of items by taking groups of items and asking whether there is a positive in each group. In particular, we will discuss explicit constructions of optimal or nearly-optimal group testing schemes using "randomness-conducting" functions. Among such developments are constructions of error-correcting group testing schemes using randomness extractors and condensers, as well as threshold group testing schemes from lossless condensers.}, affiliation = {EPFL}, author = {Cheraghchi, Mahdi}, booktitle = {Proceedings of the 48th {A}nnual {A}llerton {C}onference on {C}ommunication, {C}ontrol, and {C}omputing}, details = {http://infoscience.epfl.ch/record/152532}, keywords = {algo_misc}, location = {Allerton Retreat Center, Monticello, Illinois, USA}, note = {Invited Paper in Proceedings of 48th Annual Allerton Conference on Communication, Control, and Computing, 2010.}, oai-id = {oai:infoscience.epfl.ch:152532}, oai-set = {conf}, review = {NON-REVIEWED}, status = {PUBLISHED}, submitter = {166246; 166246}, title = {Derandomization and {G}roup {T}esting}, unit = {ALGO}, year = 2010 } @InProceedings{Shokrollahi1998/ALGO, abstract = {The past few years have witnessed exciting discoveries in different areas of coding theory and computational number theory. The present monograph, which exhibits the author's "Habilitationsschrift," is a collection of five different topics dealing with these two important fields. We will start with a purely coding theoretic question and finish with a discussion of some problems from computational number theory. Along the way, we will gradually change our focus from coding theory to number theory. Our emphasis is almost entirely on the development of fast and practical algorithms for the problems involved. In many cases it turns out that having a view for both number theory and coding theory is a clear advantage. This is best demonstrated by Chapters 2 and 3, where we encounter most of the interrelations between coding and number theory}, address = { }, affiliation = {OTHER}, author = {Shokrollahi, A. and Wasserman, H.}, booktitle = {Proceedings of the 30th annual {ACM} symposium on {T}heory of computing, {STOC} 1998}, details = {http://infoscience.epfl.ch/record/99188}, keywords = {algoweb_agcodes}, location = { }, oai-id = {oai:infoscience.epfl.ch:99188}, oai-set = {conf}, pages = {241--248}, publisher = {ACM Press}, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Decoding algebraic-geometric codes beyond the error-correction bound}, unit = {ALGO}, url = {http://citeseer.ist.psu.edu/132070.html}, year = 1998 } @InProceedings{Shokrollahi1998b/ALGO, abstract = {The past few years have witnessed exciting discoveries in different areas of coding theory and computational number theory. The present monograph, which exhibits the author's "Habilitationsschrift," is a collection of five different topics dealing with these two important fields. We will start with a purely coding theoretic question and finish with a discussion of some problems from computational number theory. Along the way, we will gradually change our focus from coding theory to number theory. Our emphasis is almost entirely on the development of fast and practical algorithms for the problems involved. In many cases it turns out that having a view for both number theory and coding theory is a clear advantage. This is best demonstrated by Chapters 2 and 3, where we encounter most of the interrelations between coding and number theory}, address = { }, affiliation = {OTHER}, author = {Shokrollahi, Amin and Wasserman, Hal}, booktitle = {Proceedings of the 35th {A}nnual {A}llerton {C}onference on {C}ommunication, {C}ontrol, and {C}omputing}, details = {http://infoscience.epfl.ch/record/99700}, keywords = {algoweb_agcodes}, location = { }, oai-id = {oai:infoscience.epfl.ch:99700}, oai-set = {conf}, pages = {225--228}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Decoding algebraic geometric codes}, unit = {ALGO}, url = {http://citeseer.ist.psu.edu/273955.html}, year = 1998 } @InProceedings{Sander1997/ALGO, abstract = {The polynomial time algorithm of Lenstra, Lenstra, and Lovász [15] for factoring integer polynomials and variants thereof have been widely used to show that various computational problems in number theory have polynomial time solutions. Among them is the problem of factoring polynomials over algebraic number fields, which is used itself as a major subroutine for several other algorithms. Although a theoretical breakthrough, algorithms based on factorization of polynomials are notoriously slow and hard to implement, with running times ranging between $O(n^12)$ and $O(n^18)$ depending on which variant of the lattice basis reduction is used. Here, n is an upper bound for the maximum of the degrees and the bit-lengths of the coefficients of the polynomials involved. On the other hand, in many situations one does not need the full power of factorization, so one may ask whether there exist faster algorithms in these cases. In this paper we develop more efficient Monte Carlo algorithms to decide certain properties of roots of integer polynomials, without factoring them. Such problems arise, e.g., when solving systems of algebraic equations. Our methods applied to this situation give thus information about the solutions of such systems of equations. Assuming the validity of the Extended Riemann Hypothesis, our algorithms run in time $O(n^6+?)$ in worst case, though they usually terminate much faster if the input polynomials do not have the properties the algorithm is testing. Besides this substantial improvement in the running time, our algorithms have the advantage of being conceptually easy. Their building blocks are gcd- computations in polynomial rings over finite fields, and primality tests for integers. However, despite the simplicity of our algorithms, their analysis is involved and uses tools from algebraic and analytic number theory. Our methods yield polynomial time algorithms even in cases where the factorization method does not. We exhibit such an example by showing that the language consisting of pairs $(g, m)$ where $g$ is a monic irreducible polynomial such that all its roots are integral linear combinations of mth roots of unity, is in co-RP. Currently, we do not know of any deterministic polynomial time algorithm to decide this problem, even if we assume the validity of the Extended Riemann Hypothesis. We will also show that computing the minimal m such that $(g, m)$ belongs to this language is intractable by means of present methods: we prove that this problem is polynomial time equivalent to that of computing the largest square free divisor of an integer}, address = { }, affiliation = {OTHER}, author = {Sander, T. and Shokrollahi, A}, booktitle = {Proceedings of the 28th {IEEE} {S}ymposium on the {F}oundations of {C}omputer {S}cience, {FOCS} 1997}, details = {http://infoscience.epfl.ch/record/99698}, doi = {10.1109/SFCS.1997.646092}, keywords = {algoweb_numbertheory}, location = { }, oai-id = {oai:infoscience.epfl.ch:99698}, oai-set = {conf}, pages = {46--55}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Deciding properties of number fields without factoring}, unit = {ALGO}, url = {http://ieeexplore.ieee.org/iel3/5208/14088/00646092.pdf?isnumber=&arnumber=646092}, year = 1997 } @InProceedings{ALGO-CONF-2007-004, abstract = {We present a structural attack against the Sidelnikov cryptosystem. The attack creats a private key from a give public key. Its running time is subexponential and it is effective if the parameters of the Reed-Muller code allow for efficient sampling of minimum weight codewords. For example, the length 2048, 3rd order Reed-Muller code takes roughly an hour to break on a stock PC using the presented metho.}, address = { }, affiliation = {EPFL}, author = {Minder, Lorenz and Shokrollahi, Amin}, booktitle = {Proceedings of {E}urocrypt 2007}, details = {http://infoscience.epfl.ch/record/112308}, documenturl = {http://infoscience.epfl.ch/record/112308/files/2007_cryptanalysis_sidelnikov.pdf}, keywords = {Public Key Cryptoraphy; McEliece Cryptosystem; Reed-Muller Codes; algoweb_pkc}, location = {Madrid}, oai-id = {oai:infoscience.epfl.ch:112308}, oai-set = {conf}, pages = {347--360}, publisher = {Springer Verlag}, review = {REVIEWED}, series = {Lecture Notes in Computer Science}, status = {PUBLISHED}, title = {Cryptanalysis of the {S}idelnikov cryptosystem}, unit = {ALGO}, url = { }, year = 2007 } @InProceedings{Shuhong1999a/ALGO, abstract = {We design algorithms for finding roots of polynomials over function fields of curves. Such algorithms are useful for list decoding of Reed-Solomon and algebraic-geometric codes. In the first half of the paper we will focus on bivariate polynomials, i.e., polynomials over the coordinate ring of the affine line. In the second half we will design algorithms for computing roots of polynomials over the function field of a nonsingular absolutely irreducible plane algebraic curve. Several examples are included}, address = { }, affiliation = {OTHER}, author = {Gao, Shuhong and Shokrollahi, Amin and Joyner, D.}, booktitle = {Proceedings of the {A}nnapolis {C}onference on {N}umber {T}heory, {C}oding {T}heory, and {C}ryptography}, details = {http://infoscience.epfl.ch/record/99702}, keywords = {algoweb_numbertheory}, location = { }, oai-id = {oai:infoscience.epfl.ch:99702}, oai-set = {conf}, pages = {214--228}, publisher = {Springer-Verlag}, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Computing roots of polynomials over function fields of curves}, unit = {ALGO}, url = {http://citeseer.ist.psu.edu/270626.html}, year = 1999 } @InProceedings{ALGO-CONF-2007-002, 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)}]$ is not contained in the sub-exponential space class $DSPACE[2^{o(n)}]$. The methods used in this paper are by now standard within computational complexity theory, and the main contribution of this note is observing that they are relevant to the construction of optimal codes. We attempt to make this note self contained, and describe the relevant results and proofs from the theory of pseudorandomness in some detail.}, address = { }, affiliation = {EPFL}, author = {Cheraghchi, Mahdi and Shokrollahi, Amin and Wigderson, Avi}, booktitle = {Allerton 2006}, details = {http://infoscience.epfl.ch/record/101078}, documenturl = {http://infoscience.epfl.ch/record/101078/files/final.pdf}, keywords = {algoweb_misc}, location = {Allerton House, IL, USA}, note = {Invited paper}, oai-id = {oai:infoscience.epfl.ch:101078}, oai-set = {conf}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Computational {H}ardness and {E}xplicit {C}onstructions of {E}rror {C}orrecting {C}odes}, unit = {ALGO}, url = {http://www.csl.uiuc.edu/allerton/}, year = 2006 } @InProceedings{Pakzad2005/ALGO, abstract = { }, address = { }, affiliation = {EPFL}, author = {Pakzad, P. and Fragouli, C. and Shokrollahi, A.}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2005}, details = {http://infoscience.epfl.ch/record/99170}, doi = {10.1109/ISIT.2005.1523666}, keywords = {algoweb_network}, location = { }, oai-id = {oai:infoscience.epfl.ch:99170}, oai-set = {conf}, pages = {1853--1857}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Coding schemes for line networks}, unit = {ALGO}, url = { }, year = 2005 } @InProceedings{Shokrollahi1988/ALGO, abstract = { }, address = { }, affiliation = {OTHER}, author = {Shokrollahi, Amin}, booktitle = {Proceedings of the 4th {I}nternational {S}ymposium on {A}pplied {A}lgebra, {A}lgebraic {A}lgorithms and {E}rror-{C}orrecting {C}odes, {AAECC}-4, 1988}, details = {http://infoscience.epfl.ch/record/99695}, keywords = {algoweb_agcodes}, location = { }, oai-id = {oai:infoscience.epfl.ch:99695}, oai-set = {conf}, pages = {168--176}, publisher = {Springer}, review = {REVIEWED}, series = {Lecture Notes in Computer Science}, status = {PUBLISHED}, title = {Codes on hermitian curves}, unit = {ALGO}, url = {http://www.springerlink.com/content/g507468741773528/url.pdf}, volume = {307}, year = 1988 } @InProceedings{Hassibi2000/ALGO, abstract = {We construct signal constellations for differential transmission with multiple basestation antennas. The signals are derived using the theory of fixed-point- free groups and are especially suitable for mobile cellular applications because they do not require the handset to have more than one antenna or to know the time-varying propagation environment. Yet we achieve full transmitter diversity and excellent performance gains over a single-antenna system}, address = { }, affiliation = {OTHER}, author = {Hassibi, B. and Hochwald, B. and Shokrollahi, A. and Sweldens, W.}, booktitle = {Proceedings of the {IEEE} {W}ireless {C}ommunication and {N}etworking {C}onference, {WCNC} 2000}, details = {http://infoscience.epfl.ch/record/99192}, doi = {10.1109/WCNC.2000.904593}, keywords = {algoweb_multantenna}, location = { }, oai-id = {oai:infoscience.epfl.ch:99192}, oai-set = {conf}, pages = {23--24}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Codes for differential signaling with many antennas}, unit = {ALGO}, url = { }, volume = {1}, year = 2000 } @InProceedings{Shokrollahi2000c/ALGO, abstract = {In this paper, I will give a brief introduction to the theory of low-density parity- check codes, and their decoding. I will emphasize the case of correcting erasures as it is still the best understood and most accessible case. At the end of the paper, I will also describe more recent developments}, address = { }, affiliation = {OTHER}, author = {Shokrollahi, Amin and Reichel, H. and Tison, S.}, booktitle = {Proceedings of the 17th {A}nnual {S}ymposium on {T}heoretical {A}spects of {C}omputer {S}cience, {STACS} 2000}, details = {http://infoscience.epfl.ch/record/99707}, keywords = {algoweb_ldpc}, location = { }, oai-id = {oai:infoscience.epfl.ch:99707}, oai-set = {conf}, pages = {1--12}, publisher = {Springer}, review = {REVIEWED}, series = {Lecture Notes in Computer Science}, status = {PUBLISHED}, title = {Codes and {G}raphs}, unit = {ALGO}, url = {http://www.springerlink.com/content/7kr8vbrp5mgylrpr/url.pdf}, volume = {1770}, year = 2000 } @InProceedings{Shokrollahi2004a/ALGO, abstract = {We give a short survey of several techniques to construct codes on GF(q) that approach the capacity of the q-ary symmetric channel. The q-ary symmetric channel represents the next level of difficulty after the binary erasure channel (BEC). Since the channel is more complex than the BEC, one may hope that codes and decoding algorithms that approach the capacity of this channel for large q may be modified to yield capacity-approaching codes for smaller values of q as well.}, address = { }, affiliation = {EPFL}, author = {Shokrollahi, Amin}, booktitle = {Proceedings of the {IEEE} {I}nformation {T}heory {W}orkshop, 2004}, details = {http://infoscience.epfl.ch/record/99167}, doi = {10.1109/ITW.2004.1405300}, extra-id = {000226087200037}, keywords = {algoweb_misc}, location = { }, oai-id = {oai:infoscience.epfl.ch:99167}, oai-set = {conf}, pages = {204--208}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Capacity-approaching codes on the q-ary symmetric channel for large q}, unit = {ALGO}, url = { }, year = 2004 } @InProceedings{ALGO-CONF-2009-004, abstract = {We give a general framework for construction of small ensembles of capacity achieving linear codes for a wide range of (not necessarily memoryless) discrete symmetric channels, and in particular, the binary erasure and symmetric channels. The main tool used in our constructions is the notion of randomness extractors and lossless condensers that are regarded as central tools in theoretical computer science. Same as random codes, the resulting ensembles preserve their capacity achieving properties under any change of basis. Our methods can potentially lead to polynomial-sized ensembles; however, using known explicit constructions of randomness conductors we obtain specific ensembles whose size is as small as quasipolynomial in the block length. By applying our construction to Justesen's concatenation scheme (Justesen, 1972) we obtain explicit capacity achieving codes for BEC (resp., BSC) with almost linear time encoding and almost linear time (resp., quadratic time) decoding and exponentially small error probability. The explicit code for BEC is defined and capacity achieving for every block length, a property lacked in previously known explicit constructions.}, address = { }, affiliation = {EPFL}, author = {Cheraghchi, Mahdi}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory ({ISIT})}, details = {http://infoscience.epfl.ch/record/141320}, documenturl = {http://infoscience.epfl.ch/record/141320/files/capacityCR.pdf}, extra-id = {000280141401244}, keywords = {algoweb_misc}, location = {Seoul, Korea Republic}, oai-id = {oai:infoscience.epfl.ch:141320}, oai-set = {conf}, pages = {2639--2643}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Capacity {A}chieving {C}odes from {R}andomness {C}onductors}, unit = {ALGO}, url = {http://www.isit2009.info/}, year = 2009 } @InProceedings{Ndzana2006a/ALGO, abstract = {This paper presents an algorithm in a purely lossless text compression setting based on fountain codes and the Burrows-Wheeler transform (BWT). The scheme consists of five stages, each of which is briefly described in the paper. The algorithm offers encouraging compression rate performance for large files. A summary of the results of the proposed scheme and other compression schemes is provided.}, address = { }, affiliation = {EPFL}, author = {Ndzana, B. N. and Shokrollahi, A. and Abel, J.}, booktitle = {Proceedings of the {D}ata {C}ompression {C}onference, {DCC} 2006}, details = {http://infoscience.epfl.ch/record/99177}, doi = {10.1109/DCC.2006.9}, keywords = {algoweb_fountain}, location = { }, oai-id = {oai:infoscience.epfl.ch:99177}, oai-set = {conf}, pages = {28--30}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Burrows-{W}heeler text compression with fountain codes}, unit = {ALGO}, url = { }, year = 2006 } @InProceedings{ALGO-CONF-2009-002, abstract = {This paper studies the stability of some reconstruction algorithms for compressed sensing in terms of the bit precision. Considering the fact that practical digital systems deal with discretized signals, we motivate the importance of the total number of accurate bits needed from the measurement outcomes in addition to the number of measurements. It is shown that if one uses a $2k \times n $ Vandermonde matrix with roots on the unit circle as the measurement matrix, $O(\ell + k \log \frac{n}{k})$ bits of precision per measurement are sufficient to reconstruct a $k$-sparse signal $x \in \R^n$ with dynamic range (i.e., the absolute ratio between the largest and the smallest nonzero coefficients) at most $2^\ell$ within $\ell$ bits of precision, hence identifying its correct support. Finally, we obtain an upper bound on the total number of required bits when the measurement matrix satisfies a restricted isometry property, which is in particular the case for random Fourier and Gaussian matrices. For very sparse signals, the upper bound on the number of required bits for Vandermonde matrices is shown to be better than this general upper bound.}, address = { }, affiliation = {EPFL}, author = {Ardestanizadeh, Ehsan and Cheraghchi, Mahdi and Shokrollahi, Amin}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory ({ISIT})}, details = {http://infoscience.epfl.ch/record/141317}, documenturl = {http://infoscience.epfl.ch/record/141317/files/CS_ISIT09_camera.pdf}, keywords = {algoweb_misc}, location = {Seoul, Korea Republic}, oai-id = {oai:infoscience.epfl.ch:141317}, oai-set = {conf}, pages = {1--5}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Bit {P}recision {A}nalysis for {C}ompressed {S}ensing}, unit = {ALGO}, url = {http://www.isit2009.info/}, year = 2009 } @InProceedings{EPFL-CONF-151701, abstract = {We study constraint satisfaction problems on the domain {-1,1}, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form sgn(w_1 x_1 + ... + w_n x_n) for some positive integer weights w_1, ..., w_n. Despite their simplicity, current techniques fall short of providing a classification of these predicates in terms of approximability. In fact, it is not easy to guess whether there exists a homogeneous linear threshold predicate that is approximation resistant or not. The focus of this paper is to identify and study the approximation curve of a class of threshold predicates that allow for non-trivial approximation. Arguably the simplest such predicate is the Majority predicate sgn(x_1+ ... + x_n), for which we obtain an almost complete understanding of the asymptotic approximation curve, assuming the Unique Games Conjecture. Our techniques extend to a more general class of "majority-like" predicates and we obtain parallel results for them. In order to classify these predicates, we introduce the notion of Chow-robustness that might be of independent interest.}, affiliation = {OTHER}, author = {Cheraghchi, Mahdi and Hastad, Johan and Isaksson, Marcus and Svensson, Ola}, booktitle = {Proceedings of the 13th {I}nternational {W}orkshop on {A}pproximation {A}lgorithms for {C}ombinatorial {O}ptimization {P}roblems ({APPROX})}, details = {http://infoscience.epfl.ch/record/151701}, extra-id = {000284820600009}, keywords = {algo_misc}, location = {Barcelona, Spain}, oai-id = {oai:infoscience.epfl.ch:151701}, oai-set = {conf}, publisher = {Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa}, review = {REVIEWED}, series = {Lecture Notes in Computer Science}, status = {PUBLISHED}, submitter = {166246}, title = {Approximating {L}inear {T}hreshold {P}redicates}, unit = {ALGO THL2}, year = 2010 } @InProceedings{EPFL-CONF-158869, abstract = {We analyze the second moment of the ripple size during the LT decoding process and prove that the standard deviation of the ripple size for an LT-code with length k is of the order of root k. Together with a result by Karp et. al (2004) stating that the expectation of the ripple size is of the order of k, this gives bounds on the error probability of the LT decoder. We also give an analytic expression for the variance of the ripple size up to terms of constant order, and refine the expression of Karp et. al for the expectation of the ripple size up to terms of the order of 1/k, thus providing a first step towards an analytic finite-length analysis of LT decoding.}, affiliation = {EPFL}, author = {Maatouk, Ghid and Shokrollahi, Amin}, booktitle = {2009 Ieee {I}nternational {S}ymposium {O}n {I}nformation {T}heory, {V}ols 1- 4}, details = {http://infoscience.epfl.ch/record/158869}, extra-id = {000280141401180}, keywords = {algoweb_fountain}, location = {Seoul, SOUTH KOREA}, oai-id = {oai:infoscience.epfl.ch:158869}, oai-set = {conf}, pages = {2326--2330}, publisher = {Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa}, review = {REVIEWED}, status = {PUBLISHED}, submitter = {WOS-2010-11-30; 173510}, title = {Analysis of the {S}econd {M}oment of the {LT} {D}ecoder}, unit = {ALGO}, year = 2009 } @InProceedings{Luby1998/ALGO, abstract = {We introduce a new set of probabilistic analysis tools based on the analysis of And-Or trees with random inputs. These tools provide a unifying, intuitive, and powerful framework for carrying out the analysis of several previously studied random processes of interest, including random loss-resilient codes, solving random k-SAT formula using the pure literal rule, and the greedy algorithm for matchings in random graphs. In addition, these tools allow generalizations of these problems not previously analyzed to be analyzed in a straightforward manner. We illustrate our methodology on the three problems listed above}, address = { }, affiliation = {OTHER}, author = {Luby, M. and Mitzenmacher, M. and Shokrollahi, A}, booktitle = {Proceedings of the 9th {A}nnual {ACM}-{SIAM} {S}ymposium on {D}iscrete {A}lgorithms, {SODA} 1998}, details = {http://infoscience.epfl.ch/record/99187}, keywords = {algoweb_ldpc}, location = { }, oai-id = {oai:infoscience.epfl.ch:99187}, oai-set = {conf}, pages = {364--373}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Analysis of random processes via {AND}/{OR} tree evaluations}, unit = {ALGO}, url = {http://www.icsi.berkeley.edu/~luby/PAPERS/tree.ps}, year = 1998 } @InProceedings{Luby1998b/ALGO, abstract = {We introduce a new set of probabilistic analysis tools based on the analysis of And-Or trees with random inputs. These tools provide a unifying, intuitive, and powerful framework for carrying out the analysis of several previously studied random processes of interest, includingrandom loss-resilient codes, solving random k-SAT formula using the pure literal rule, and thegreedy algorithm for matchings in random graphs. In addition, these tools allow generalizations of these problems not previously analyzed to be analyzed in a straightforward manner. We illustrate our methodology on the three problems listed above}, address = { }, affiliation = {OTHER}, author = {Luby, M. and Mitzenmacher, M. and Shokrollahi, A. and Spielman, D. A}, booktitle = {Proceedings of the 30th annual {ACM} {S}ymposium on {T}heory of {C}omputing, {STOC} 1998}, details = {http://infoscience.epfl.ch/record/99699}, doi = {10.1145/276698.276756}, keywords = {algoweb_ldpc}, location = { }, oai-id = {oai:infoscience.epfl.ch:99699}, oai-set = {conf}, pages = {249--258}, publisher = {ACM Press}, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Analysis of low-density codes and improved designs using irregular graphs}, unit = {ALGO}, url = { }, year = 1998 } @InProceedings{Gathen2003/ALGO, abstract = {We describe an authentication scheme whose security is based on the hardness of finding roots of systems of sparse polynomial equations in many variables and of high degree. One of the new ideas is the use of many keys. In one authentication session, a small amount of information about only one of them, chosen randomly, is released; this may be useful in other situations as well. Although the practicality of this scheme has still to be investigated, we believe that the new ideas described here may be of independent interest.}, address = { }, affiliation = {EPFL}, author = {von zur Gathen, J. and Shokrollahi, A. and Shparlinski, I.}, booktitle = {Proceedings of the {IEEE} {I}nformation {T}heory {W}orkshop, 2003}, details = {http://infoscience.epfl.ch/record/99160}, keywords = {algoweb_misc}, location = { }, oai-id = {oai:infoscience.epfl.ch:99160}, oai-set = {conf}, pages = {159--162}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {An authentication scheme based on roots of sparse polynomials}, unit = {ALGO}, url = { }, year = 2003 } @InProceedings{ALGO-CONF-2009-001, abstract = {We consider the problem of uniform sampling of points on an algebraic variety. Specifically, we develop a randomized algorithm that, given a small set of multivariate polynomials over a sufficiently large finite field, produces a common zero of the polynomials almost uniformly at random. The statistical distance between the output distribution of the algorithm and the uniform distribution on the set of common zeros is polynomially small in the field size, and the running time of the algorithm is polynomial in the description of the polynomials and their degrees provided that the number of the polynomials is a constant.}, address = { }, affiliation = {EPFL}, author = {Cheraghchi, Mahdi and Shokrollahi, Amin}, booktitle = {Proceedings of the 26th {I}nternational {S}ymposium on {T}heoretical {A}spects of {C}omputer {S}cience ({STACS})}, details = {http://infoscience.epfl.ch/record/141316}, documenturl = {http://infoscience.epfl.ch/record/141316/files/final.pdf}, keywords = {algoweb_misc}, location = {Freibourg, Germany}, oai-id = {oai:infoscience.epfl.ch:141316}, oai-set = {conf}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Almost-{U}niform {S}ampling of {P}oints on {H}igh-{D}imensional {A}lgebraic {V}arieties}, unit = {ALGO}, url = {http://stacs2009.informatik.uni-freiburg.de/}, year = 2009 } @InProceedings{Brown2004a/ALGO, abstract = {This paper investigates the use of algebraic-geometric codes for data transmission over a packet network, by comparing their encoding/decoding speeds to those of the ubiquitous Reed-Solomon Codes. We take advantage of the fact that AG codes allow the construction of longer codes over a given alphabet, which in turn means we can create an [n, k]-code over a smaller field in which the encoding/decoding algorithms run faster. We also obtain some probabilistic bounds on the overheads required for the codes we use.}, address = { }, affiliation = {EPFL}, author = {Brown, A. and Shokrollahi, A.}, booktitle = {Proceedings of the {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {ISIT} 2004}, details = {http://infoscience.epfl.ch/record/99162}, doi = {10.1109/ISIT.2004.1365114}, extra-id = {000223202600076}, keywords = {algoweb_agcodes}, location = { }, oai-id = {oai:infoscience.epfl.ch:99162}, oai-set = {conf}, pages = {76}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {Algebraic-geometric codes on the erasure channel}, unit = {ALGO}, url = { }, year = 2004 } @InProceedings{Olhoevsky1999/ALGO, abstract = {Using methods originating in numerical analysis, we will develop a unified framework for derivation of efficient list decoding algorithms for algebraicgeometric codes. We will demonstrate our method by accelerating Sudan's list decoding algorithm for Reed-Solomon codes [22], its generalization to algebraic-geometric codes by Shokrollahi and Wasserman [21], and the recent improvement of Guruswami and Sudan [8] in the case of ReedSolomon codes. The basic problem we attack in this paper is that of efficiently finding nonzero elements in the kernel of a structured matrix. The structure of such an n x n-matrix allows it to be "compressed" to ? n parameters for some ? which is usually a constant in applications. The concept of structure is formalized using the displacement operator. The displacement operator allows to perform matrix operations on the compressed version of the matrix. In particular, we can find a PLU- decomposition of the original matrix in time O(? n2), which is quadratic in n for constant ?. We will derive appropriate displacement operators for matrices that occur in the context of list decoding, and apply our general algorithm to them. For example, we will obtain algorithms that use O(n2 l) and O(n7/3 l) operations over the base field for list decoding of Reed-Solomon codes and algebraic-geometric codes from certain plane curves, respectively, where l is the length of the list. Assuming that l is constant, this gives algorithms of running time O(n2) and O(n7/3), which is the same as the running time of conventional decoding algorithms. We will also sketch methods to parallelize our algorithms}, address = { }, affiliation = {OTHER}, author = {Olshevksy, V. and Shokrollahi, A}, booktitle = {Proceedings of the 31st annual {ACM} {S}ymposium on {T}heory of {C}omputing, {STOC} 1999}, details = {http://infoscience.epfl.ch/record/99704}, doi = {10.1145/301250.301311}, keywords = {algoweb_agcodes}, location = { }, oai-id = {oai:infoscience.epfl.ch:99704}, oai-set = {conf}, pages = {235--244}, publisher = { }, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {A displacement structure approach to decoding algebraic geometric codes}, unit = {ALGO}, url = { }, year = 1999 } @InProceedings{ALGO-CONF-2007-006, abstract = { }, address = {Providence}, affiliation = {EPFL}, author = {Olshevsky, Vadim and Shokrollahi, Amin}, booktitle = {Fast {A}lgorithms for {S}tructured {M}atrices: {T}heory and {A}pplications}, details = {http://infoscience.epfl.ch/record/112513}, keywords = {algoweb_agcodes}, location = {Mount Holyoke}, oai-id = {oai:infoscience.epfl.ch:112513}, oai-set = {conf}, publisher = {AMS/SIAM}, review = {REVIEWED}, series = { }, status = {PUBLISHED}, title = {A displacement approach to decoding algebraic codes}, unit = {ALGO}, url = { }, volume = {323}, year = 2003 }