Theory Reading Seminar, summer, 2009

• Time:     Every Tuesday, 3-5pm. (3-4 for the talk and 4-5 for free discussions.)

• Venue:   Rm 121, Ho Sin-Hang Engineering Building

Past meetings:

Aug 18, 2009, Samir Khuller

• Title: On Broadcast Scheduling
• Abstract: Broadcasting over a wireless channel is a standard mechanism to disseminate information to a set of clients. Clients request different pieces of information, called "pages", and in this "pull-based" model, the server responds with a broadcast schedule. The key property that distinguishes this problem from standard scheduling is that multiple requests may be satisfied by a single broadcast of the requested page. Surprisingly, this small change makes almost all the problems in this area NP-hard whereas without this property these problems can be solved optimally in polynomial time for unit sized pages. This overlap property arises in other contexts as well such as in multi-query processing.
  
  We consider a variety of different objective functions in our work minimizing the sum of response times, minimizing the maximum response time and maximizing the number of satisfied requests when requests have deadlines. This is a survey talk based on several papers and will cover a collection of results using a variety of techniques. Finally we propose some open problems.
  
  No background knowledge beyond undergraduate algorithms is expected.
   

Aug 4, 2009, Chandra Nair.

• Title: An introduction to issues in network information theory via the broadcast channel
• Abstract: Network information theory is a natural extension of Shannon's point-to-point information theory paradigm to a network of sender's and receivers. Despite the spectacular success of point-to-point information theory, most fundamental problems remain open in network information theory. In this talk I will present some known results and some open problems related to the most basic (personal bias) of all the open problems, the broadcast channel (a setting where one sender X wishes to communicate a message M1 to receiver Y1 and a different message M2 to receiver Y2 simultaneously over a noisy channel p(y1,y2|x) )

July 21, 2009, Andrew Yao and Xiaoming Sun.

• Title: Sorting on Complete Bipartite Graphs

• Abstract: Let X={x_1, x_2, …, x_n} and Y={y_1, y_2, …, y_n} be two sets of interleaving numbers. That is, their sorted order is of the form x_{i_1} < y_{j_1} < x_{i_2} < y_{j_2} < …. (or starting with y_{j_1}) for some unknown permutations i_1, i_2, … and j_1, j_2,… of 1, 2,…, n. We wish to sort these numbers using only comparisons of the form x_k: y_m.  We show that there exists a deterministic algorithm that uses O(n (log n)^c) comparisons.  Previously, it was known that there exist randomized algorithms using O(n log n) comparisons. This problem is a special case of the sorting problem on graphs.

July 14, 2009, Sidharth Jaggi.

• Title: Codes against Online Adversaries
• Abstract: In this work we consider the communication of information in the presence of an online adversarial jammer. In the setting  under study, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x1 , . . . , xn ) symbol-by-symbol over a communication channel. The adversarial jammer can view the transmitted symbols xi one at a time, and can change up to a p-fraction of them. However, the decisions of the jammer must be made in an online or causal manner. Namely, for each symbol xi the jammer’s decision on whether to corrupt it or not (and on how to change it) must depend only on xj for j ≤ i. This is in contrast to the “classical” adversarial jammer which may base its decisions on its complete knowledge of x.
  
  More generally, for a delay parameter d ∈ (0, 1), we study the scenario in which the jammer’s decision on the corruption of xi must depend solely on xj for j ≤ i − dn. In this work, we study codes for online adversaries when the transmitted symbols are assumed to be over a sufficiently large field F. We present a tight characterization of the amount of information one can transmit in both the 0-delay and, more generally, the d-delay online setting. We show that for 0-delay adversaries, the achievable rate asymptotically equals that of the classical
  adversarial model. For positive values of d we show that the achievable rate can be significantly greater than that of the classical model. We prove tight results for both additive and overwrite jammers. In the additive case the jammer may corrupt information xi ∈ F by adding onto it a corresponding error ei ∈ F. In this case the receiver gets the symbol yi = xi + ei . In the overwrite case, the jammer may corrupt information xi ∈ F by replacing it with a corresponding corrupted symbol yi ∈ F. For positive delay d, symbol xi may not be known to the adversarial jammer at the time it is being corrupted, hence these two error models, and the corresponding achievable rates, are shown to differ substantially. Finally, we extend our results to a jam-or-listen online model, where the online adversary can either jam a symbol or eavesdrop on it. This corresponds to several scenarios that arise in practice. We again provide a tight characterization of the achievable rate for several variants of this model. The rate-regions we prove for each model are informational-theoretic in nature and hold for computationally unbounded adversaries. The rate regions are characterized by “simple” piecewise linear functions of p and d. The codes we construct to attain the optimal rate for each scenario are computationally efficient.
  
  (work done with B. K. Dey and M. Langberg)

July 7, 2009, John Lui.

• Title: Mathematical Modeling of Incentive Policies in P2P Networks
• Abstract: In order to stimulate cooperation among nodes in P2P systems, some form of incentive mechanism is necessary so as to encourage service contribution. Hence, designing and evaluating the stability, robustness and performance of incentive policies is extremely critical. In this presentation, we propose a general mathematical framework to evaluate the stability and evolution of a family of shared history based incentive policies. To illustrate the utility of the framework, we present several incentive policies and show why some incentive policy can lead to a total system collapse while the other is stable and operates at the optimal point. One can use this mathematical framework to design and analyze various incentive policies and verify whether they match the design objectives of the underlying P2P systems.
   

Jun 30, 2009,  Shengyu Zhang.

• Title: Lower bounds of communication complexity by information complexity.

• Abstract: Information complexity is a new approach to lower bounding communication complexity. In the talk I'll introduce this method, covering the proof for the Disjointness function (the first paper below), Tribes function (the second paper below) and mentioning the main result of the general read-once formula (the third paper below).

  • Information Statistics Approach to Data Stream and Communication Complexity, Bar-Yossef, Jayram, Kumar, Sivakumar, FOCS'02, JCSS'04.

  • Two Applications of Information Complexity, Jayram, Kumar, Sivakumar, STOC'03.

  • Lower bounds on the randomized communication complexity of read-once functions, Leonardos, Saks, CCC'09.