Coding theory
There have been 2 completed talks and 2 topic suggestions tagged with coding theory.
Related Tags
- complexity theory
- graph theory
- theoretical computer science
- information theory
- probability
- statistics
- geometry
- number theory
Completed Talks
Expander Graphs
Delivered by Frieda Rong on Wednesday November 29, 2017
In this talk, we’ll study graphs which are “sparse” yet “highly connected”. Known as expanders, these graphs exhibit interesting properties which can be viewed from a rich array of analytic, combinatorial, and probabilistic perspectives. Contributions of expanders range from the proof of important results in complexity theory to derandomization of algorithms to the construction of robust networks and cryptographic hash functions. We’ll see one application to coding theory, where expanders can be used to provide asymptotically “good” error-correcting codes with linear time encoding and decoding.
Prerequisites: linear algebra (familiarity with eigenvalues and eigenvectors).
Information Theory
Delivered by Sidhant Saraogi on Friday October 14, 2016
I will try to provide a brief introduction to Information Theory working towards motivating Shannon's Source Coding Theorem. We will use rather simple examples (for e.g. Repetition Codes) to explain the idea of noisy channels and similarly simple examples to explain the idea behind the theorem and eventually try to prove it for a rather specific example. (if we have the time !)
Talk Suggestions
Expander Graphs and Applications
Expander graphs are sparse graphs with strong connectivity properties and finds applications in complexity theory, designing of computer networks and the theory of error-correcting codes.
Possible reference materials for this topic include
Quick links: Google search, arXiv.org search, propose to present a talk
coding theory complexity theory graph theory theoretical computer science
Lattices, Linear Codes, and Invariants
This topic studies sphere packing and the connection to lattices and linear codes.
Possible reference materials for this topic include
Quick links: Google search, arXiv.org search, propose to present a talk