Description

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.

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.

Description

Ramanujan Hall, Department of Mathematics

Date

Wed, February 14, 2018

Start Time

2:00pm IST

Priority

5-Medium

Access

Public

Created by

DEFAULT ADMINISTRATOR

Updated

Tue, February 13, 2018 9:58pm IST