Sagnik | Projects

Extensions of the Linear Programming bound on codes

August 2018 - ongoing

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.

[Report]

Volumes of spheres in discrete metrics, and applications to the Lee metric

August 2018 - January 2019

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.

[Paper]

Common Randomness for Communication over Adversarial Channels

May 2018 - January 2019

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.

[Paper]

Approximate Degree and Quantum Query Complexity

January 2018 - ongoing

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.

[Preliminary Report]

Quantum Shannon Theory

August - November, 2017

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.

[Report]