Tata Institute of Fundamental Research
Liar Liar, Pants on Fire
STCS Student Seminar
Speaker:
K. Gajjar, S. Bhandari (School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Navy Nagar
Mumbai 400005)
Organiser:
Anand Deo
Date:
Friday, 24 Mar 2017, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
The Liars Game is a turn-based two-player game (lets call the two players Alice and Bob). The game is specified by two positive integers $k$ and $n$ which are known to both Alice and Bob.
The game begins with Alice choosing two positive integers $x$ and $N$ such that $x$ lies between $1$ and $N$ (inclusive). Alice keeps $x$ secret, and truthfully tells $N$ to Bob. Now Bob tries to obtain information about $x$ by asking Alice questions. Each question consists of Bob specifying a set $S$ of positive integers of his choice, and asking Alice whether $x$ belongs to the set $S$. Bob may ask an unbounded (but finite) number of such questions to Alice. Alice must answer each question with a yes or a no, but she is permitted to lie. The only restriction is that, among any $k+1$ consecutive questions asked by Bob, Alice must answer at least one of them truthfully.
After Bob has finished his interrogation, he must specify a set $X$ of at most n positive integers. If $x$ belongs to $X$, then Bob wins. If he is unable to do this, Alice wins. In this talk, we will see the following results.
* For all $k$, if $n$ is at least $2^k$, then there is a strategy that guarantees a win for Bob.
* For all sufficiently large $k$, there exists an $k$ such that if $n$ is at least $1.99^k$, then there is a strategy for Alice that can prevent Bob from guaranteeing a win.
In the first half of the talk, Kshitij will explain the problem statement with the help of an example and provide a proof of $1$ using elementary counting techniques. In the second part of the talk, Siddharth will provide two different proofs of $2$, one using Lováss local lemma and the other using a potential function. Time permitting, we will also see a generalization of the Liars Game.
| Speaker: | K. Gajjar, S. Bhandari (School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road Navy Nagar Mumbai 400005) |
| Organiser: | Anand Deo |
| Date: | Friday, 24 Mar 2017, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
The Liars Game is a turn-based two-player game (lets call the two players Alice and Bob). The game is specified by two positive integers $k$ and $n$ which are known to both Alice and Bob.
The game begins with Alice choosing two positive integers $x$ and $N$ such that $x$ lies between $1$ and $N$ (inclusive). Alice keeps $x$ secret, and truthfully tells $N$ to Bob. Now Bob tries to obtain information about $x$ by asking Alice questions. Each question consists of Bob specifying a set $S$ of positive integers of his choice, and asking Alice whether $x$ belongs to the set $S$. Bob may ask an unbounded (but finite) number of such questions to Alice. Alice must answer each question with a yes or a no, but she is permitted to lie. The only restriction is that, among any $k+1$ consecutive questions asked by Bob, Alice must answer at least one of them truthfully.
After Bob has finished his interrogation, he must specify a set $X$ of at most n positive integers. If $x$ belongs to $X$, then Bob wins. If he is unable to do this, Alice wins. In this talk, we will see the following results.
* For all $k$, if $n$ is at least $2^k$, then there is a strategy that guarantees a win for Bob.
* For all sufficiently large $k$, there exists an $k$ such that if $n$ is at least $1.99^k$, then there is a strategy for Alice that can prevent Bob from guaranteeing a win.
In the first half of the talk, Kshitij will explain the problem statement with the help of an example and provide a proof of $1$ using elementary counting techniques. In the second part of the talk, Siddharth will provide two different proofs of $2$, one using Lováss local lemma and the other using a potential function. Time permitting, we will also see a generalization of the Liars Game.
The game begins with Alice choosing two positive integers $x$ and $N$ such that $x$ lies between $1$ and $N$ (inclusive). Alice keeps $x$ secret, and truthfully tells $N$ to Bob. Now Bob tries to obtain information about $x$ by asking Alice questions. Each question consists of Bob specifying a set $S$ of positive integers of his choice, and asking Alice whether $x$ belongs to the set $S$. Bob may ask an unbounded (but finite) number of such questions to Alice. Alice must answer each question with a yes or a no, but she is permitted to lie. The only restriction is that, among any $k+1$ consecutive questions asked by Bob, Alice must answer at least one of them truthfully.
After Bob has finished his interrogation, he must specify a set $X$ of at most n positive integers. If $x$ belongs to $X$, then Bob wins. If he is unable to do this, Alice wins. In this talk, we will see the following results.
* For all $k$, if $n$ is at least $2^k$, then there is a strategy that guarantees a win for Bob.
* For all sufficiently large $k$, there exists an $k$ such that if $n$ is at least $1.99^k$, then there is a strategy for Alice that can prevent Bob from guaranteeing a win.
In the first half of the talk, Kshitij will explain the problem statement with the help of an example and provide a proof of $1$ using elementary counting techniques. In the second part of the talk, Siddharth will provide two different proofs of $2$, one using Lováss local lemma and the other using a potential function. Time permitting, we will also see a generalization of the Liars Game.