We will start by reviewing the arguments of Krichevskii, Hansel and Pippenger on covering graphs using bipartite graphs, and using them motivate Korner’s graph entropy. We will combine the graph covering argument with some counting of increasing complexity to derive the following:
- The Fredman-Komlos lower bound on the size of a family of perfect hash functions;
- A bound on the zero-error list decoding capacity of the 4/3 channel;
- A bound on the zero-error list decoding capacity of the q(q-1) channel.
Handwritten notes for the talk can be found here.
References
- M. Dalai, V. Guruswami and J. Radhakrishnan, “An Improved Bound on the Zero-Error List-Decoding Capacity of the 4/3 Channel,” in IEEE Transactions on Information Theory, vol. 66, no. 2, pp. 749-756, Feb. 2020, doi: 10.1109/TIT.2019.2933424. Link
- S. Bhandari and J. Radhakrishnan, “Bounds on the Zero-Error List-Decoding Capacity of the q/(q-1) Channel,” 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, 2018, pp. 906-910, doi: 10.1109/ISIT.2018.8437609. Link