We consider the online scheduling problem of minimizing total weighted flow time plus energy in the dynamic speed scaling model, where a processor can scale its speed dynamically between 0 and some maximum speed T. In the past few years this problem has been studied extensively under the clairvoyant setting, which requires the size of a job to be known at release time [AlF07,BPS07,BCL+08,LLT+esa08,LLT+spaa08,BCP09,GNS09,LLT+09]. For the non-clairvoyant setting, despite its practical importance, the progress is relatively limited. Only recently an online algorithm [LAPS] is known to be O(1)-competitive for minimizing (unweighted) flow time plus energy in the infinite speed model (i.e., T = ∞) [CEL+09,CEP09]. This paper makes two contributions to the non-clairvoyant scheduling. First, we resolve the open problem that the unweighted result of [LAPS] can be extended to the more realistic model with bounded maximum speed. Second, we show that another non-clairvoyant algorithm [WRR] is O(1)-competitive when weighted flow time is concerned. Note that [WRR] is not as efficient as [LAPS] for scheduling unweighted jobs as [WRR] has a much bigger constant hidden in its competitive ratio.

We investigate the relationship between the complexities of two models of randomized decision trees for read-once Boolean functions; namely, with the directional restriction and without it. A decision tree is directional if it reads a variable in a sub-formula, then it has to evaluate the sub-formula completely before reading another variable that appears in a different sub-formula. It was known that there is a read-once Boolean formula such that an optimal randomized decision tree to evaluate it is not directional. This was first pointed out by Saks and Wigderson [FOCS '86] and an explicit construction of such a formula was given by Vereshchagin [TCS '98]. In this paper, we conduct a systematic search for a certain class of functions and provide an explicit construction of a read-once Boolean formula f on n variables such that the cost of the optimal directional randomized decision tree for f is BigOmega(n^alpha) and the cost of the optimal randomized decision tree (without the directional restriction) for f is O(n^beta) with alpha-beta>0.0101. This is the largest known gap so far.

Mediators are third parties to whom the players in a game can delegate the task of choosing a strategy; a mediator forms a mediated equilibrium if delegating is a best response for all players. Mediated equilibria have more power to achieve outcomes with high social welfare than Nash or correlated equilibria, but less power than a fully centralized authority. Here we initiate the study of the power of mediation by introducing the mediation analogue of the price of stability—the ratio of the social cost of the best mediated equilibrium BME to that of the socially optimal outcome OPT. We focus on load-balancing games with social cost measured by weighted average latency. Even in this restricted class of games, BME can range from being as good as OPT to being no better than the best correlated equilibrium. In unweighted games BME achieves OPT; the weighted case is more subtle. Our main results are (1) a proof that the worst-case ratio BME=OPT is at least (1+sqrt(2))/2 ~= 1.2071 and at most 2 for linear-latency weighted load-balancing games, and that the lower bound is tight when there are two players; and (2) tight bounds on the worst-case BME=OPT for general-latency weighted load-balancing games. We give similarly detailed results for other natural social-cost functions. We also show a precise correspondence between the quality of mediated equilibria in a game G and the quality of Nash equilibria in the repeated game when G is played as the stage game. The proof of this correspondence is based on a close connection between mediated equilibria and the Folk Theorem from the economics literature.

This paper studies the one-way communication complexity of the subgroup membership problem, a classical problem closely related to basic questions in quantum computing. Here Alice receives, as input, a subgroup H of a finite group G; Bob receives an element y of G. Alice is permitted to send a single message to Bob, after which he must decide if his input y is an element of H. We establish the following bounds on the classical communication complexity of this problem in the bounded-error setting:

1. The problem can be solved with O( log |G|)-bit communication with the promise that H is normal.
2. The problem can be solved with O(dmax log |G|)-bit communication, where dmax is the maximum degree of an irreducible complex representation of G.
3. For any prime p not dividing |G|, the problem can be solved with O(log |G| + dmax log p)-bit communication, where dmax is the maximum degree of an irreducible Fp-representation of G.