Chicago Journal of Theoretical Computer Science

Volume 2011 Abstracts

  1. Non-clairvoyant Scheduling for Weighted Flow Time and Energy on Speed Bounded Processors by Sze-Hang Chan, Tak-Wah Lam, Lap-Kei Lee, Hing-Fung Ting, and Peng Zhang.
    May 5, 2011.

    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.

  2. k-Cographs are Kruskalian by Ling-Ju Hung and Ton Kloks.
    May 6, 2011.
    A class of graphs is Kruskalian if Kruskal's theorem on a well-quasi-ordering of finite trees provides a finite characterization in terms of forbidden induced subgraphs. Let k be a natural number. A graph is a k-cograph if its vertices can be colored with colors from the set {1,...,k} such that for every nontrivial subset of vertices W there exists a partition W_1,W_2 of W into nonempty subsets such that either no vertex of W_1 is adjacent to a vertex of W_2 or, such that there exists a permutation pi of k elements such that vertices with color i in W_1 are adjacent exactly to the vertices with color pi(i) in W_2, for all i in {1, ... k}. We prove that k-cographs are Kruskalian. We show that k-cographs have bounded rankwidth and that they can be recognized in O(n^3) time.

  3. On Directed vs. General Randomized Decision Tree Complexity fo Read-Once Formulas by Kazuyuki Amano.
    May 6, 2011.

    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.

  4. Notes on Large Angle Crossing Graphs by Vida Dumjovič, Joachim Gudmundsson, Pat Morin and Thomas Wolle.
    May 6, 2011.
    A geometric graph G is an a angle crossing (alpha AC) graph if every pair of crossing edges in G cross at an angle of at least alpha. The concept of right angle crossing (RAC) graphs alpha = pi/2) was recently introduced by Didimo et al. [10]. It was shown that any RAC graph with n vertices has at most 4n-10 edges and that there are infinitely many values of n for which there exists a RAC graph with n vertices and 4n-10 edges. In this paper, we give upper and lower bounds for the number of edges in alphaAC graphs for all 0 < alpha < pi/2.

  5. Mediated Equilibria in Load-Balancing Games by Joshua R. Davis, David Linden-Nowell, Alexa Sharp and Tom Wexler.
    November 6, 2011.

    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.

  6. The One-Way Communication Complexity of Subgroup Membership by Scott Aaronson, François Le Gall, Alexander Russell and Seiichiro Tani.
    December 20, 2011.

    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.

[] Volume 2010 Abstracts
[back] Volume 2011 [back] Published articles
[CJCTS home]

Janos Simon