Special Topics in Theoretical Computer Science - Bayesian Online Selection

Course codeCOL863
InstructorAshish Chiplunkar (ashishc@...)
ClassesBlock III, Room 342 SIT building, room 001; Monday and Wednesday 11:00 - 12:00, Thursday 12:00 - 13:00 (Slot H)


Suppose you wish to sell an item to one of several potential buyers. The buyers approach you one at a time, offer you a price, after which you need to either accept their offer and sell the item, or reject them and move to the next buyer. How do you strategize to maximize your revenue? The course concerns modelling and analysis of problems with this flavor, and design of algorithms for solving them.

The following talks by Prof. Matt Weinberg should serve as a gentle introduction to the course.

Eligibility and Prerequisites

All the institute-prescribed prerequisites for 800 level courses will apply. Additionally, a strong foundation in probability, linear algebra, and calculus is desirable.

Content (tentative; subject to minor changes)

Reference Material

No textbooks; we will refer to the following papers.

Useful Platforms


30 marks easy short surprise Quizzes, best 6 of 8, no compesation for missed quizzes
30 marks Reading Project -- read (sections of) 1-2 papers, write report, and present the result
40 marks End-semester Exam

Passing criterion: >= 30 marks
Audit pass criterion: >= 30 marks in reading project + end-semester exam

Paper reading projects

Paper reading projects will involving choosing a paper (or two related papers), reading and understanding them, writing a report explaining the results in your own words, and presenting them to the class. Original contributions such as proving a new result, writing better proofs, validating results through experiments, etc. will get bonus credit. The following is an indicative list of papers that can be studied. Students are free to choose papers outside this list for their project, provided the papers are related to the content of the course. This will need the instructor's approval.

Attendance Policy

Grade will be completely determined by the marks obtained in the components listed in the Grading section. Mathematically, grade and attendance will be conditionally independent given marks. (However, rest assured that unconditionally, grade and attendance will be heavily correlated!)

The only exception to the above rule is if you fall into the E grade range. In this case, if your attendance is less than 75%, your E grade changes to F.