Theory Reading Seminar, summer, 2009

Time: Every Tuesday, 35pm. (34 for the
talk and 45 for free discussions.)

Venue: Rm 121, Ho SinHang 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 "pullbased"
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
NPhard 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 multiquery 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 pointtopoint information theory paradigm to a network of
sender's and receivers. Despite the spectacular success of pointtopoint
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,y2x) )
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 ) symbolbysymbol over a communication channel. The
adversarial jammer can view the transmitted symbols xi one at a time, and can
change up to a pfraction 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 sufﬁciently large ﬁeld F. We present a tight
characterization of the amount of information one can transmit in both the
0delay and, more generally, the ddelay online setting. We show that for
0delay 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 jamorlisten 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 rateregions we prove for each model are informationaltheoretic 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 readonce formula (the third paper
below).

Information
Statistics Approach to Data Stream and Communication Complexity, BarYossef, 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 readonce functions, Leonardos,
Saks, CCC'09.