Wednesday, February 14, 2018
Public Access

Category: All

February 2018
Mon Tue Wed Thu Fri Sat Sun
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28        
2:00pm [2:00pm]S. Venkitesh (IITB)
Combinatorics Seminar Title: Lift of Reed-Solomon code with an application to Nikodym sets Speaker: S. Venkitesh (IITB) Date and Time: Feb 14, 2018, 2PM Venue: Ramanujan Hall, Dept. of Mathematics Abstract: We will work over the finite field F_q, q = p^k. The Reed-Solomon code with parameters (q,d), denoted as RS(q,d), is the linear space of all polynomial functions from F_q to F_q with degree atmost d. The Reed-Muller code with parameters (q,m,d), denoted as RM(q,m,d), is the m-variable analog of RS(q,d), defined to be the linear space of all polynomial functions from F_q^m to F_q with total degree atmost d. A nonempty set N in F_q^m is called a Nikodym set if for every point p in F_q^m, there is a line L passing through p such that all points on L, except possibly p, are contained in N. Using the polynomial method and the code RM(q,m,q-2), we can prove the lower bound |N| >= q^m / m!. We will outline this proof. We will then define a new linear code called the m-lift of RS(q,d), denoted as L_m(RS(q,d)), and show that RM(q,m,d) is a proper subspace of L_m(RS(q,d)). We will use this fact crucially, in a proof very similar to the earlier one, to obtain the improved lower bound |N| >= (1 - o(1)) * q^m, when we fix p and allow q to tend to infinity. This result is due to Guo, Kopparty and Sudan.