Spring 2015

Reed-Muller and Other Subcodes of the Sierpinski Matrix

Thursday, Feb. 12, 2015 3:00 pm3:30 pm PST

Add to Calendar


Calvin Lab Auditorium

Reed-Muller codes have recently regained significant attention, from both the computer science and electrical engineering coding communities. As for polar codes, Reed-Muller codes are generated by selecting rows in the tensor product matrix [1,1;0,1]^{\otimes k}, the matrix with Sierpinski triangles on the upper-diagonal. While polar codes are proved to be capacity-achieving, RM codes have long been conjectured to be capacity achieving on symmetric channels, without theoretical validations. We will overview recent results on this conjecture (joint work with A. Shpilka and A. Wigderson), and discuss other code variants (joint work with Y. Wigderson).