Content: Information theory studies the transmission, processing, extraction, and utilization of information. This course covers the basic theory of information theory and selected applications to data management, machine learning and information retrieval. Topics include entropy, mutual information, cross entropy, data processing theorem, information inequalities, Cox' theorem, maximum entropy solutions, and applications such as data normalization, decision trees, maximum likelihood, logistic regression, cross-entropy, VC dimensions. Students will gain hands-on experience through a project. The latter will be flexible, allowing students to explore information theory in aspects related to their PhD research.
Prerequisites: The course is fast-paced but self-contained. Standard undergraduate CS knowledge of probability theory (e.g., random variables, basic probability distributions, expectation, etc.), algorithms and complexity theory (e.g., from textbooks such as [Erickson'19], [Dasgupta, Papadimitriou, Vazirani'06], [Cormen, Leiserson, Rivest, Stein'09], [Kleinberg, Tardos'05], or [Lehman, Leighton, and Meyer'15]) will be helpful
PhD program: The course counts as "non-seminar" Theory course for the PhD breadth requirement.
Time/location
Instructor: Wolfgang Gatterbauer
Contact: Please use Piazza (via direct access from within Canvas) for all questions related to lectures, coursework, and the project. Notice you can post questions anonymously to all other students, or anonymously even to the instructors. Alternatively, please use my anonymous feedback form to send comments and suggestions that only I can see.
50%: Course project: The main component of this course will be a research project in the latter part of this class. This project can be a new application of one of the techniques presented or theoretically-oriented. The topic will be flexible, allowing students to explore information-theoretic questions related to their own PhD research. This will involve an initial project proposal, an intermediate report, a project presentation and a final report. The final report should resemble a workshop paper. A publishable new result is not required for a high grade. The contribution may instead be a careful synthesis, illuminating comparison, or a well-analyzed failed approach. The problem formulation and the followed approach need to be clear. More details are posted on the project page.
30%: Mini-projects: You complete 6 mini "explorations" of your own choice and create an intuitive slide deck with your lessons learned for each mini-project. Thus, each mini project is an independent mini deep dive into some issue motivated by the topics covered in class and your own interests. Your goal is to illustrate an interesting aspect of the seminar topic with imaginative, concrete, and ideally "tricky" illustrating examples. Importantly, you ask your own question, you decide what you find interesting!
cs7840-fa26-[YOUR NAME]-mini[NUMBER]-[SOME DESCRIPTIVE TITLE].PDF
Rationale: Georg Cantor is quoted as saying: "To ask the right question is harder than to answer it." In that spirit, our mini projects are closer to research than routine assignments: What particular aspect in a class is worthy to be "illustrated"? That's often the most difficult part. For additional pedagogic motivation, see:
20%: Participation and Class Contributions: Classes will be interactive and require concentration and participation. I am a big fan of the Socratic Method (please watch this 1:30min video clip from the 1973 movie "The Paper Chase" to see what we as teachers should strive for).
Learning goal of our class project and mini-projects: These assignments develop your ability to ask useful questions, reason carefully, construct illustrative examples, and clearly explain your ideas and insights to others. The main goal is not to have a polished submission, but an interesting and insightful submission. Your intellectual decisions and your own understanding must be evident.
Responsibility and verification: You are responsible for the accuracy and integrity of everything you submit, regardless of how it was produced. Check calculations, arguments, code, figures, and references. Clearly distinguish established results, your own derivations, experimental observations, and conjectures. An AI answer is not evidence that a claim is correct.
Provenance & source attribution: Cite the sources from which you obtained ideas, examples, arguments, wording, figures, code, or data, including course materials and web pages where relevant. Identify adaptations of similar ideas and explain what you changed. Put citations near the relevant material, not only in a bibliography. Whenever you cite a source, remember that you are the one citing it and putting your name on the document: you must have actually consulted the source and verified that it supports what you claim. Do not blindly copy citations suggested by an AI tool. If an AI tool gives you what sounds like an interesting or new idea, make a reasonable effort to find relevant prior work and determine whether the idea is already known. Cite the relevant sources you find. AI tools can be useful for finding possible sources, but you must verify those sources yourself.
AI assistance and disclosure: You may use AI tools. Include a brief assistance statement identifying the AI tools used and how they helped you. State whether AI helped formulate the question, construct the example, develop the argument, write code, produce text or figures, or find related work, and explain how you checked the resulting material. A short statement is sufficient but remember that an AI disclosure supplements and does not replace citations. Here is my AI disclosure for this section: For this section on academic integrity, I used an LLM to rephrase an originally supplied bullet list of ideas, asking it to reformulate them for clarity. I then reformulated the suggestions and iterated a few times to shorten the final wording.
Overall philosophy: You are the driver and help advance understanding: I expect you to completely understand what you submit and to make an effort to explain it clearly to your audience. Optimize for intuition, not sophistication! Clarify, don't obfuscate! Terence Tao, in his Aug 2026 lecture write-up "Mathematics in the age of AI", quoted Thurston: "The measure of our success is whether what we do enables people to understand and think more clearly and effectively," and emphasized that "Other mathematicians need to digest the result" and "ensure that the results can be clearly communicated to and understood." I apply these criteria here: you need to understand what you submit, and communicate that understanding clearly. You are in the driver's seat. If you give up that role, you are being driven rather than driving. Let AI assist your thinking, not replace your thinking.
Recommended textbook: Cover & Thomas. Elements of Information Theory, 2nd ed, 2006. Additional material (like papers and selected chapters) are made available on the calendar page.
The class in its current form was first co-created and co-taught by Javed Aslam and Wolfgang Gatterbauer in Fall 2024. Earlier versions of this course were taught by Javed Aslam in Fall 2015 and Fall 2011. The pedagogy of this class is inspired by 7240: Principles of scalable data management taught by Wolfgang Gatterbauer.