Wed, February 12, 2020
Public Access

Category: All

February 2020
Mon Tue Wed Thu Fri Sat Sun
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29  
11:00am [11:00am] Anuj Vora : Systems and Control Dept., IIT Bombay
Combinatorics Seminar. Speaker: Anuj Vora. Affiliation: Systems and Control Dept., IIT Bombay. Date and Time: Wednesday 12 February, 11:00 am - 12:30 pm. Venue: Room 114, Department of Mathematics. Title: Zero Error Strategic Communication. Abstract: We consider a setting between a sender and a receiver, where the receiver tries to exactly recover a source sequence privately known to the sender. However, unlike the usual setting of communication, the sender here aims to maximize its utility and may have an incentive to lie about its true information. We show that the maximum number of sequences that can be recovered by the receiver grows exponentially and is given by the largest independent set of a graph defined on sequences. We then define a notion of the strategic capacity of a graph and show that it is lower bounded by the independence number of a suitably defined graph on the alphabet. Moreover, the Shannon capacity of the graph is an upper bound on the capacity. This talk will briefly discuss the Shannon's zero-error capacity problem. We then proceed to derive bounds on the strategic capacity and give exact values for perfect graphs. If time permits, we will also discuss the case where the receiver aims for asymptotically vanishing probability of error.