Deterministic load balancing and dictionaries in the parallel disk model Berger, Mette; Hansen, Esben Rune; Pagh, Rasmus ...
ACM Symposium on Parallel Algorithms and Architectures: Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures; 30 July-02 Aug. 2006,
07/2006
Conference Proceeding
We consider deterministic dictionaries in the parallel disk model, motivated by applications such as file systems. Our main results show that if the number of disks is moderately large (at least ...logarithmic in the size of the universe from which keys come), performance similar to the expected performance of randomized dictionaries can be achieved. Thus, we may avoid randomization by extending parallelism. We give several algorithms with different performance tradeoffs. One of our main tools is a deterministic load balancing scheme based on expander graphs, that may be of independent interest. Our algorithms assume access to certain expander graphs "for free". While current explicit constructions of expander graphs have suboptimal parameters, we show how to get near-optimal expanders for the case where the amount of data is polynomially related to the size of internal memory.
We consider the question of constructing cryptographic pseudorandom generators (PRGs) in NC0, namely ones in which each bit of the output depends on just a constant number of input bits. Previous ...constructions of such PRGs were limited to stretching a seed of n bits to n + o(n) bits. This leaves open the existence of a PRG with a linear (let alone superlinear) stretch in NC0. In this work we study this question and obtain the following main results:
1. We show that the existence of a linear-stretch PRG in NC0 implies non-trivial hardness of approximation results without relying on PCP machinery. In particular, that Max 3SAT is hard to approximate to within some constant.
2. We construct a linear-stretch PRG in NC0 under a specific intractability assumption related to the hardness of decoding “sparsely generated” linear codes. Such an assumption was previously conjectured by Alekhnovich 1.
We note that Alekhnovich directly obtains hardness of approximation results from the latter assumption. Thus, we do not prove hardness of approximation under new concrete assumptions. However, our first result is motivated by the hope to prove hardness of approximation under more general or standard cryptographic assumptions, and the second result is independently motivated by cryptographic applications.
Given a finite group G by its multiplication table, we give a deterministic polynomial-time construction of a directed O(log|G|) degree Cayley expander for G. Our construction exploits the connection ...between rapid mixing random walks and spectral expansion. Our main group-theoretic tool is Erdős-Rényi sequences. We give a similar construction of O(log|G|) degree undirected Cayley expanders for G, which is an alternative proof of Wigderson and Xiao’s derandomization WX08 of the Alon-Roichman randomized construction.
In this chapter we will discuss some extremal properties of error-correcting codes. We will also use expander graphs to construct very easily decodable codes.
The aim of this article is to discuss some of the notions and applications of random walks on finite graphs, especially as they apply to random graphs. In this section we give some basic definitions, ...in Section 2 we review applications of random walks in computer science, and in Section 3 we focus on walks in random graphs.
In the previous chapters, we have already seen constructions of asymptotically good codes of good rate over both large alphabets (the AG-codes from Chapter 6) and the binary alphabet (the ...concatenated codes from Chapter 8), that are efficiently list decodable up to a “maximum” possible radius.
The problem of minimizing the number of service ports of a central facility which serves a number of users subject to some constraints is addressed. At any time, a set of at most s users may want to ...use the facility, and one user can be connected to each port at a given time. It is assumed that there are direct communication links from users to service ports, with at most d links incident at a single service port. This problem maps to the graph-theoretic problem of minimizing the number of outputs of a bipartite graph with n inputs, such the degree of each output node is at most d and every set of k<or=s inputs is joined collectively to at least k different outputs. This minimum is denoted by f(n, s, d). A linear programming formulation is also given.< >
PDF
