Coding Theory Seminar
Speaker: Birenjith Sasidharan (IIT Palakkad)
Host: Sudhir R. Ghorpade
Title: Block circulant codes with application to blockchain networks
Time, day and date: 11:00:00 AM - 12:00:00 PM, Monday, July 7
Venue: Ramanujan Hall
Abstract: In this talk, we present a family of [n,k,d] block circulant codes composed of many [n0 << n, k0 << k, d0 < d] local codes and that satisfy two properties: (1) the global code supports distributed decoding of up to (d-1) erasures without a central coordinator, and (2) the local codes support cryptographic verification of code symbols using a commitment scheme. These properties make the code ideal for use in a blockchain protocol that ensures data availability by random sampling - an emerging application of block codes. Compared to the currently used 2D Reed-Solomon (RS) code, the block circulant code achieves a larger fractional distance (d/n), as desired in the protocol, for the same rate (k/n) in the high-rate regime. We will discuss the code's topology, its instantiation using RS codes as local codes, and provide a proof of its minimum distance.

Thesis Defence
Speaker: Utkarsh Tripathi (IIT Bombay)
Host: Srikanth Srinivasan
Title: On the AC0[⊕] Circuit Complexity of the Coin Problem and Variants
Time, day and date: 11:00:00 AM, Wednesday, July 9
Venue: Ramanujan Hall
Abstract: -

Date: 9th July 2025
Venue: Ramanujan Hall
Time: 4:00 pm to 5:00 pm
Host Radhendushka Srivastava

Title: Signal-to-noise ratio aware minimax analysis of sparse linear
regression
Speaker: Shubhangi Ghosh ( Columbia University)

Abstract:

We consider parameter estimation under sparse linear regression – an
extensively studied problem in high-dimensional statistics and compressed
sensing. While the minimax framework has been one of the most fundamental
approaches for studying statistical optimality in this problem, we
identify two important issues that the existing minimax analyses face: (i)
The signal-to-noise ratio appears to have no effect on the minimax
optimality, while it shows a major impact in numerical simulations. (ii)
Estimators such as best subset selection and Lasso are shown to be minimax
optimal, yet they exhibit significantly different performances in
simulations. In this paper, we tackle the two issues by employing a
minimax framework that accounts for variations in the signal-to-noise
ratio (SNR), termed the SNR-aware minimax framework. We adopt a delicate
higher-order asymptotic analysis technique to obtain the SNR-aware minimax
risk. Our theoretical findings determine three distinct SNR regimes:
low-SNR, medium-SNR, and high-SNR, wherein minimax optimal estimators
exhibit markedly different behaviors. The new theory not only offers much
better elaborations for empirical results, but also brings new insights to
the estimation of sparse signals in noisy data.