Chicago Journal of Theoretical Computer Science

Volume 2008 Abstracts

  1. A Priority-Based Model of Routing by Barak Farzad, Neil Olver, and Adrian Vetta.
    5 February 2008.
    We consider a priority-based selfish routing model, where agents may have different priorities on a link. An agent with higher priority on a link can traverse it with smaller delay or cost than an agent with lower priority. This general framework can be used to model a number of different problems. The strctural propeties that lead to inefficiencies in routing choices appear different in this priority based model compared to the classical model. In particular, in parallel link networks with nonatomic agents, the price of anarchy is exactly one in the priority based model; that is, selfish behavior leads to optimal routing. In contrast, in the standard model the worst possible price of anarchy can be achieved in a simple two-link network. For multi-commodity networks, selfish routing does lead to inefficiencies in the priority-based model. We present tight bounds on the price of anarchy for such networks. Specifically, in the nonatomic case the worst-case price of anarchy is exactly (d+1)^(d+1) for polynomial latency functions of degree d (hence 4 for linear cost functions). For atomic games, the worst-case price of anarchy is exactly 3+2sqrt(2) in the weighted case, and exactly 17/3 in the unweighted case. An upper bound of O(2^d d^d ) is also shown for polynomial functions in the atomic case, although this is not tight. Our framework (and results) also generalise to include models similar to congestion games.
  2. Representing Hard Lattices with O(nlogn) Bits by Miklos Ajtai.
    12 May 2008.
    We present a variant of the Ajtai-Dwork public-key cryptosystem where the size of the public-key is only O(nlog n) bits and the encrypted text/clear text ratio is also O(nlogn). This is true with the assumption that all of the participants in the cryptosystem share O(n*n*log n) random bits which have to be picked only once and the users of the cryptosystem get them e.g. together with the software implementing the protocol. The public key is a random lattice with an n^c-unique nonzero shortest vector, where the constant c>1/2 can be picked arbitrarily close to 1/2, and we pick the lattice according to a distribution described in the paper. We do not prove a worst-case average-case equivalence but the security of the system follows from the hardness of an average-case diophantine approximation problem related to a well-known theorem of Dirichlet.
  3. Syntactic Characterizations of Polynomial Time Optimization Classes by Prabhu Manyem.
    22 May 2008.
    The characterization of important complexity classes by logical descriptions has been an important and prolific area of Descriptive complexity. However, the central focus of the research has been the study of classes like P, NP, L and NL, corresponding to decision problems (e.g. the characterization of NP by Fagin [Fag74] and of P by Gradel [E. 91]). In contrast, optimization problems have received much less attention. Optimization problems corresponding to the NP class have been characterized in terms of logic expressions by Papadimitriou and Yannakakis, Panconesi and Ranjan, Kolaitis and Thakur, Khanna et al, and by Zimand. In this paper, we attempt to characterize the optimization versions of P via expressions in second order logic, many of them using universal Horn formulae with successor relations. These results nicely complement those of Kolaitis and Thakur [KT94] for polynomially bounded NP-optimization problems. The polynomially bounded versions of maximization and minimization problems are treated first, and then the maximization problems in the Ònot necessarily polynomially boundedÓ class.
[] Volume 2007 Abstracts
[back] Volume 2007 [back] Published articles
[CJCTS home]

Janos Simon