Thu, March 23, 2017
Public Access Category: All |
|||||||||||||||||||||
|
- Time:
- 2:10pm-3:10pm
- Location:
- Ramanujan Hall
- Description:
- Time: 2.15-3.15
Title: Error Correction and List Decoding for Reed Solomon Codes
Abstract:
In this talk, we will have a look at three results, starting with the following.
[Berlekamp-Welch] Given a univariate polynomial function over F_q
with data corruption at t < q/2 points, we can recover the function
completely if the degree of the function is sufficiently low.
A generalization of the above is as follows, where instead of
'recovering' the function, we find all its 'close approximates'.
[Madhu Sudan] Given data points (x_i,y_i), i \in [n], and parameters
k and t, we can list all polynomials with degree at most k, which
satisfy at least t data points.
This result can further be generalized as follows.
[Madhu Sudan] Given data points (x_i,y_i) with weights w_i, i \in
[n], and parameters k and W, we can list all polynomials with degree
at most k such that the sum of weights of data points satisfied by the
polynomial is at least W.
The last two results provide list-decoding of Reed-Solomon codes.
- Time:
- 4:00pm-5:00pm
- Location:
- Room 113
- Description:
- Title: Asymptotics of the number of points of symplectic lattices in subsets of Euclidean spaces
Abstract: It is well known that a "good" large subset of the Euclidean space contains approximately as many lattice points as its volume. This need not hold for a general subset. On the other hand, a classical theorem of Siegel asserts that for any subset of positive measure, the "average" number of points (in an appropriate sense) of a general unimodular lattice contained in it, equals the measure of the set. In place of the average over the entire space of lattices one may also ask for analogous results for smaller subclasses. In a recent work with Jayadev Athreya, we explored this issue, with some modifications that place the problem in perspective, for the case of symplectic lattices, viz. lattices (in even-dimensional spaces) obtained from the standard lattice under symplectic transformations. In this talk I shall describe the overall asymptotics in this case, together with the historical background of the results and techniques involved.