Combinatorial search with lies, error-correcting codes, and other applications of finite fields

We start from the following famous variation of Twenty Questions Problem when one needs to find one of 10⁶ objects by asking an oracle the minimal possible number of questions of the following type "if the given object belongs to some subset", but the oracle may sometimes lie, see [1,2]. And what if not one, but many elements should be "guessed"? A question-answer model is important here and there are many of them. These discrete problems turned out to be very close to the following continuous problem, known as compressed sensing [3,4], namely, to find an unknown sparse vector in n-dimensional Euclidean space by the minimal number of linear measurements which aren’t exact. In these lectures, we show how finite fields, via error-correcting codes, help solve these and many other problems that arise in practice.

Outline:
Lecture 1. The Renyi-Ulam game or how to find an object among a million in just 25 questions, if one answer can be wrong
Lecture 2. On various modifications of the Renyi-Ulam game
Lecture 3. Finding counterfeit coins on accurate scales with a harmful oracle
Lecture 4. Time for finite fields and error correcting codes -simplex and Hamming codes
Lecture 5. Polynomials over finite fields and Reed-Muller and BCH codes
Lecture 6. Non-overlapping convex polytopes with Boolean cube vertices and multimedia digital fingerprinting
Lecture 7. How to find sparse vector support using imprecise linear measurements
Lecture 8. Connections with Big Mathematics