Theory Seminar

  • JONATHAN MOSHEIFF
  • Postdoctoral Fellow
  • Department of Computer Science and Applied Mathematics
  • Weizmann Institute
Seminars

On the Weight Distribution of Random Binary Linear Codes

random (binary) linear code is a dimension lambda*n (0<\lambda<1) linear subspace of the binary n-dimensional hypercube, chosen uniformly from among all such subspaces. Such codes play an important role in the theory of error correcting codes, since they achieve the best known rate vs. distance trade-off, i.e., the Gilbert-Varshamov lower bound. Under a random errors regime, the problem of decoding these codes is known as Learning Parity with Noise, and has many cryptographic applications.  This work is motivated by the contrast between the importance of random linear codes and how little we know about them.

Much of the interesting information about a code C is captured by its weight distribution. This is the vector (w_0,w_1,...,w_n) where w_i counts the elements of C with Hamming weight i. In this work we study the weight distribution of random linear codes. In our main result we compute the moments of the random variable w_(gamma*n), where 0 < \gamma < 1 is a fixed constant and n goes to infinity.

This is joint work with Nati Linial.

Jonathan Mostheiff is a postdoc at the Faculty of Mathematics and Computer Science at the Weizmann Institute, working with Prof. Irit Dinur. He has recently finished his PhD at the School of Computer Science and Engineering of The Hebrew University under the guidance of Prof. Nati Linial. During his PhD, I was an Adams Fellow. He has a B.Sc in Mathematics and Computer Science, and an M.Sc in computer science, both from the Hebrew University. His M.Sc advisor was Prof. Orna Kupferman.

Jonathan has a broad interest in theoretical computer science and combinatorics. His recent focus has been on codes, property testing, and applications of group theory to computer science. He is also interested in graph theory and the analysis of boolean functions.

Faculty Host: Venkat Guruswami

For More Information, Please Contact: 
Keywords: