Combinatorics Seminar

When: Sunday, November 6, 10am
Where: Schreiber 309
Speaker: Guy Rutenberg, Tel Aviv University
Title: Priority Transmission


We consider a broadcast model involving multiple transmitters and receivers. Transmission is performed in rounds, where in each round any transmitter is allowed to broadcast a single message, and each receiver can receive only a single broadcast message, determined by a priority permutation over the transmitters. The message received by receiver R in a given transmission round is the one sent by the first transmitter among all those broadcasting in that round according to the permutation of R. In our model, each pair of transmitter and receiver has a unique message which the transmitter has to send to the receiver. We prove upper and lower bounds on the minimal number of rounds needed for transmitting all the messages to their respective receivers. We also consider the case where the priority permutations are determined geometrically.

Joint work with Noga Alon.