Events by date

Title:‘Coloring 3-colorable graphs with o(n^1⁄5) colors’ by Kawarabayashi and Thorup

Abstract: Much attention has been devoted to nding polynomial time algorithms for coloring three-
colorable graphs with the fewest possible colors.

Title: The rank of random matrices over finite fields

Abstract:

We determine the rank of a random matrix over a finite field with prescribed numbers of non-zero entries in each row and column. As an application we obtain a formula for the rate of low-density parity check codes.