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.
  4. Some perfect matchings and perfect half-integral matchings in NC by Raghav Kulkarni, Meena Mahajan, and Kasturi R. Varadarajan.
    5 September 2008.
    We show that for any class of bipartite graphs which is closed under edge deletion and where the number of perfect matchings can be counted in NC, there is a deterministic NC algorithm for finding a perfect matching. In particular, a perfect matching can be found in NC for planar bipartite graphs and K_{3,3}-free bipartite graphs via this approach. A crucial ingredient is part of an interior-point algorithm due to Goldberg, Plotkin, Shmoys and Tardos. An easy observation allows this approach to handle regular bipartite graphs as well.

    We show, by a careful analysis of the polynomial time algorithm due to Galluccio and Loebl, that the number of perfect matchings in a graph of small O(log n) genus can be counted in NC. So perfect matchings in small genus bipartite graphs can also be found via this approach.

    We then present a different algorithm for finding a perfect matching in a planar bipartite graph. This algorithm is substantially different from the algorithm described above, and also from the algorithm of Miller and Naor, which predates the approach of Goldberg et al. and tackles the same problem. Our new algorithm extends to small genus bipartite graphs, but not to K_{3,3}-free bipartite graphs. We next show that a non-trivial extension of this algorithm allows us to compute a vertex of the fractional perfect matching polytope (such a vertex is either a perfect matching or a half-integral matching) in NC, provided the graph is planar or small genus but not necessarily bipartite, and has a perfect matching to begin with. This extension rekindles the hope for an NC-algorithm to find a perfect matching in a non-bipartite planar graph.

  5. The phase transition in exact cover by Vamsi Kalapala and Cris Moore.
    October 1, 2008
    We study EC3, a variant of Exact Cover which is equivalent to Positive 1-in-3 SAT. Random instances of EC3 were recently used as benchmarks for simulations of an adiabatic quantum algorithm. Empirical results suggest that EC3 has a transition from satisfiability to unsatisfiability when the ratio r of clauses to variables exceeds some treshold r* = 0.62 +- 0.01. Usong the method of differential equations, we show that iff r is less than or equal to 0.546, then with high probability a random instance of EC3 is satisfiable. Combined with previous results this limits the location of the treshold, assuming it exists, to the range 0.546 < r* < 0.644.
  6. Efficient Fully-Simulatable Oblivious Transfer by Yehuda Lindell.
    December 2, 2008
    Oblivious transfer, first introduced by Rabin, is one of the basic building blocks of cryptographic protocols. In an oblivious transfer (or more exactly, in its 1-out-of-2 variant), one party known as the sender has a pair of messages and the other party, known as the receiver, obtains one of them. Somewhat paradoxically, the receiver obtains exactly one of the messages (and learns nothing of the other), and the sender does not know which of the messages the receiver obtained. Due to its importance as a building block for secure protocols, the efficiency of oblivious transfer protocols has been extensively studied. However, to date, there are almost no known oblivious transfer protocols that are secure in the presence of malicious adversaries under the real/ideal model simulation paradigm (without using general zero-knowledge proofs). Thus, efficient protocols that reach this level of security are of great interest. In this paper we present efficient oblivious transfer protocols that are secure according to the ideal/real model simulation paradigm. We achieve constructions under the DDH, Nth residuosity, and quadratic residuosity assumptions, as well as under the assumption that homomorphic encryption exists.
  7. Simultaneous Communication Protocols with Quantum and Classical Messages by Dmitry Gavinsky, Oded Regev, and Ronald de Wolf
    December 28, 2008
    We study the simultaneous message passing (SMP) model of communication complexity, for the case where one party is quantum and the other is classical. We show that in an SMP protocol that computes some function with the first party sending q qubits and the second sending c classical bits, the quantum message can be replaced by a randomized message of O(qc) classical bits, as well as by a deterministic message of O(q c \log q) classical bits. Our proofs rely heavily on earlier results due to Scott Aaronson. In particular, our results imply that quantum-classical protocols need to send Omega(sqrt{n/ log n}) bits/qubits to compute EQUALITY on n-bit strings, and hence are not significantly better than classical-classical protocols (and are much worse than quantum-quantum protocols such as quantum fingerprinting). This essentially answers a recent question of Wim van Dam. Our results also imply, more generally, that there are no superpolynomial separations between quantum-classical and classical-classical SMP protocols for functional problems. This contrasts with the situation for relational problems, where exponential gaps between quantum-classical and classical-classical SMP protocols are known. We show that this surprising situation cannot arise in purely classical models: there, an exponential separation for a relational problem can be converted into an exponential separation for a functional problem.
[] Volume 2007 Abstracts
[back] Volume 2007 [back] Published articles
[CJCTS home]

Janos Simon