Sagnik | Projects
Extensions of the Linear Programming bound on codes
Studied possible ways of extending the linear programming bound on the rate of codes to more general channels than just binary codes under the Hamming metric. Generalised the Fourier analytic proof due to Navon and Samorodnitsky from the binary to the \(q\)-ary case. Currently attempting further generalisations of the same. Work done under the guidance of Prof Adrish Banerjee, IIT Kanpur.
Volumes of spheres in discrete metrics, and applications to the Lee metric
We developed general techniques to bound the size of the balls of a given radius \(r\) for \(q\)-ary discrete metrics, using the generating function for the metric and Sanov’s theorem, that reduces to the known bound in the case of the Hamming metric and gives us a new bound in the case of the Lee metric. We used the techniques developed to find Hamming, Elias-Bassalygo and Gilbert-Varshamov bounds for the Lee metric. Submitted to ISIT 2019.
Common Randomness for Communication over Adversarial Channels
Studied adversarial channels, their capacity characterisations and the role of common randomness. Improved the \(\theta(\log n)\) bound due to Langberg on the common randomness required to communicate reliably over a state-deterministic AVC to a tight \(\log n\) bound. Improved Langberg’s technique to show that precisely \(\log n\) bits of common randomness are necessary and used a technique based on polynomial hashing and list decoding to show that \((1 + \epsilon) \log n \) bits of common randomness are sufficient for reliable communication. We wrote a paper that is under review for ISIT 2019. Work done at The Chinese University of Hong Kong under the guidance of Prof Sidharth Jaggi.
Approximate Degree and Quantum Query Complexity
Work done as a semester long undergraduate project. Mainly focused on reading the paper The Polynomial Method Strikes Back by Kothari, Bun and Thaler, and understanding their constructions of explicit approximating polynomials and dual witnesses for different functions. Currently working on the dual block composition method due to Sherstov, trying to extend it to more general situations than just AND-OR composition. Advised by Prof Rajat Mittal.
Quantum Shannon Theory
Work done as part of a course project in the quantum computing course. Mainly focuses on quantum Shannon theory and introduces quantum channels, optimality of simple quantum protocols and resource theoretic arguments to prove the same. Advised by Prof Rajat Mittal.