There has been a flurry of recent literature studying streaming algorithms for which the input stream is chosen adaptively by a black-box adversary who observes the output of the streaming algorithm at each time step. However, these algorithms fail when the adversary has access to the internal state of the algorithm, rather than just the output of the algorithm.

We consider a simple model of imprecise comparisons: there exists some δ > 0 such that when a subject is given two elements to compare, if the values of those elements (as perceived by the subject) differ by at least δ, then the comparison will be made correctly; when the two elements have values that are within δ, the outcome of the comparison is unpredictable. This model is inspired by both imprecision in human judgment of values and also by bounded but potentially adversarial errors in the outcomes of sporting tournaments. Our model is closely related to a number of models commonly considered in the psychophysics literature where δ corresponds to the Just Noticeable Difference (JND) unit or difference threshold . In experimental psychology, the method of paired comparisons was proposed as a means for ranking preferences among n elements of a human subject. The method requires performing all ( n 2 ) comparisons, then sorting elements according to the number of wins. The large number of comparisons is performed to counter the potentially faulty decision-making of the human subject, who acts as an imprecise comparator. We show that in our model the method of paired comparisons has optimal accuracy, minimizing the errors introduced by the imprecise comparisons. However, it is also wasteful because it requires all ( n 2 ). We show that the same optimal guarantees can be achieved using 4 n 3/2 comparisons, and we prove the optimality of our method. We then explore the general tradeoff between the guarantees on the error that can be made and number of comparisons for the problems of sorting, max-finding, and selection. Our results provide strong lower bounds and close-to-optimal solutions for each of these problems.

For each natural number d we consider a finite structure Md whose universe is the set of all 0,1-sequence of length n=2d, each representing a natural number in the set {0,1,...,2n-1} in binary form. The operations included in the structure are the four constants 0,1,2n-1,n, multiplication and addition modulo 2n, the unary function min{2x, 2n-1}, the binary functions ⌊ x/y⌋ (with ⌊ x/0 ⌋ =0), max(x,y), min(x,y), and the boolean vector operations, vee,- defined on 0,1 sequences of length n, by performing the operations on all components simultaneously. These are essentially the arithmetic operations that can be performed on a RAM, with wordlength n, by a single instruction. We show that there exists an ε>0 and a term (that is, an algebraic expression) F(x,y) built up from the mentioned operations, with the only free variables x,y, such that if Gd(y), d=0,1,2,..., is a sequence of terms, and for all d=0,1,2,..., Md models ∀ x, [Gd(x)-> ∃ y, F(x,y)=0], then for infinitely many integers d, the depth of the term Gd, that is, the maximal number of nestings of the operations in it, is at least ε (log d)1/2 = ε (log log n)1/2.

For each natural number d we consider a finite structure md whose universe is the set of all 0,1-sequence of length n=2d, each representing a natural number in the set [0,1,...,2n-1] in binary form. The operations included in the structure are the four constants 0,1,2n-1,n, multiplication and addition modulo 2n, the unary function min[2x, 2n-1], the binary functions ⌊ x/y⌋ (with ⌊ x/0 ⌋ =0), max(x,y), min(x,y), and the boolean vector operations ∧,∨,- defined on 0,1 sequences of length n by performing the operations on all components simultaneously. These are essentially the arithmetic operations that can be performed on a RAM, with wordlength n, by a single instruction. We show that there exists a term (that is, an algebraic expression) F(x,y) built up from the mentioned operations, with the only free variables x,y, such that for all terms G(y), which is also built up from the mentioned operations, the following holds. For infinitely many positive integers d, there exists an a ∈ md such that the following two statements are not equivalent: (i) md |= ∃ x, F(x,a), (ii) md models G(a)=0. In other words, the question whether an existential statement, depending on the parameter a ∈ md is true or not, cannot be decided by evaluating an algebraic expression at a.

Assume that Alice is running a program P on a RAM, and an adversary Bob would like to get some information about the input or output of the program. At each time, during the execution of P, Bob is able to see the addresses of the memory cells involved in the instruction which is executed and the name of the instruction. In addition to this, at certain times, Bob can even see the contents of all of the memory cells involved in the instruction. We will call a time when this happens a compromised time. Bob can choose the compromised times in an adaptive way, that is, immediately before the instruction at time t is executed, Bob, using all of the information at his disposal, can decide whether time t will be compromised or not. The only restriction on his choice is, that among m consecutive instructions there can be at most ε m whose time is compromised, where ε>0 is a small constant. We show that if m= c⌊ log n ⌋, where c>0 is a large constant, then for each program P, using n memory cells and time T=O(poly(n)), Alice can construct a functionally equivalent program P', such that the probability that Bob gets any nontrivial information about the input of P is negligible, and the time and space requirements of P' grows, compared to P, only by a factor of poly(log n). We assume that the program P' gets its input in an encoded form, namely each input bit b is encoded by a random 0,1-sequence of length m whose parity is b. The output bits must be encoded by P' in a similar way.

ithmic increase in the time and space requirements is possible on a probabilistic (coin flipping) RAM without using any cryptographic assumptions. The simulation will fail with a negligible probability. If n memory locations are used, then the probability of failure is at most n-log n. Pippenger and Fischer has shown in 1979, see [7], that a Turing machine with one-dimensional tapes, performing a computation of length n can be simulated on-line by an oblivious Turing machine with two dimensional tapes, in time O(n log n), where a Turing machine is oblivious if the movements of it heads as a function of time are independent of its input. For RAMs the notion of obliviousness was defined by Goldreich in 1987 in [2], and he proved a simulation theorem about it. A RAM is oblivious if the distribution of its memory access pattern, which memory cells are accessed at which time, is independent of the program running on the RAM, provided that the time used by the program is fixed. That is, an adversary watching the memory access will not know anything about the program running on the machine apart from its total time. Ostrovsky, improving Goldreich's theorem, has shown in 1990, see [4], [5], [3], that a RAM using n memory cells can a be simulated by an oblivious RAM with a random oracle (where the random bits can be accessed repeatedly) so that the increase of the space and time requirement is only about a factor of ln (Goldreich's factor was about exp[(log n)1/2]). In both cases the oblivious RAM with a random oracle, can be replaced, by an oblivious probabilistic (coin-flipping) RAM, provided that we accept some unproven cryptographic assumptions, e.g., the existence of a one-way function. In this paper we show that simulation with an oblivious, coin-flipping RAM, with only a factor of ln increase in time and space requirements, is possible, even without any cryptographic assumptions.

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(nlog n). This is true with the assumption that all of the participants in the cryptosystem share O(n2log n) random bits which has 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 nc-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 a randomized diophantine approximation problem related to a well-known theorem of Dirichlet.

We formulate a conjecture which describes all of the polynomial time computable (p. t. c. ) functions f with domain(f)=lattice n, range(f) ⊆ lattice m, m ≤ nc, where latticen is the set of lattices in Rn with determinant 1. A former conjecture, the 0-1-conjecture, of the author states that all 0,1-valued functions defined on latticen are constant almost everywhere. Since the n-dimensional lattices as Abelian groups are pairwise isomorphic we can say that, according to this conjecture, the value of a p. t. c. 0,1-function may depend only on the algebraic structure of the lattice and not on the metric defined on it. The new conjecture generalizes this statement for functions where the value is also a lattice. As a typical example we can think of the function f(L)=L′, where L′ is the dual of L. When both the domain and the range of the functions are n-dimensional lattices with determinants 1 then, according to the conjecture, every p. c. t. functions are either constant or identical almost everywhere to f(L)=AL, or f(L)=AL′, where A is a suitably chosen linear transformation with determinant one.There is a striking analogy between the new conjecture and theorems describing the uniquely definable functions which assign for each n-dimensional vectorspace an m-dimensional vectorspace. These theorems are closely related to questions about the Axiom of Choice. In this analogy polynomial time computation corresponds to definability (in set theory) and lattices to finite dimensional vectorspaces.

Schnorr's algorithm for finding an approximation for the shortest nonzero vector in an n dimensional lattice depends on a parameter k. He proved that for a fixed k ≤ n his algorithm (block 2k-reduction) provides a lattice vector whose length is greater than the length of a shortest nonzero vector in the lattice by at most a factor of (4k2) n/k. (The time required by the algorithm depends on k.) We show that if k=o(n), this bound on the performance of Schnorr's algorithm cannot be improved (apart from a constant factor in the exponent), namely there is a lattice and a basis so that if they are given as an input to the algorithm then the resulting approximating factor of the output is at least k e n/k. (For larger integers k if Schnorr's algorithm runs in polynomial time then we have already a polynomial time algorithm for finding the shortest nonzero vector.) We also solve an open problem formulated by Schnorr about the the Korkine-Zolotareff lattice constants αk. We show that his upper bound αk ≤ k1 + ln k is the best possible apart from a constant factor in the exponent. We prove a similar result about his upper bound βk≤ 4k2, where βk is another lattice constant with an important role in Schnorr's analysis of his algorithm.

We present a 2/sup O(n)/ time Turing reduction from the closest lattice vector problem to the shortest lattice vector problem. Our reduction assumes access to a subroutine that solves SVP exactly and a subroutine to sample short vectors from a lattice, and computes a (1+/spl epsi/)-approximation to CVP As a consequence, using the SVP algorithm from (Ajtai et al., 2001), we obtain a randomized 2[O(1+/spl epsi//sup -1/)n] algorithm to obtain a (1+/spl epsi/)-approximation for the closest lattice vector problem in n dimensions. This improves the existing time bound of O(n!) for CVP achieved by a deterministic algorithm in (Blomer, 2000).

We formulate a conjecture about random n-dimensional lattices with a suitable distribution. The conjecture says that every polynomial time computable property of a random lattice holds with a probability either close to 0 or close to 1. Accepting the conjecture we get a large class of hard lattice problems. We describe an analogy between our conjecture and a set theoretical axiom, which cannot be proved in ZFC. This axiom says that there exists a nontrivial /spl sigma/-additive 0 - 1 measure defined on the set of all subsets of some set S.

Memory checking is the task of checking the correctness of a sequence of "store" and "retrieve" operations. The operations are performed in a large unreliable memory. A checker using a much smaller but completely reliable memory tries to decide whether they were executed correctly. M. Blum, W. Evans, P. Gemmel, S. Kannan and M. Naor, has shown in 1991 that the off-line checking of a sequence of memory operations concerning a RAM consisting of n registers can be done, in a probabilistic sense, by a checker using only O(log n) reliable memory and a constant number of RAM operation per each "store" and "retrieve" operations (with log n word length), moreover no unproven cryptographic assumptions are needed in the proof. The probability of error will be polynomially small in n. The solution however requires the checker to store some extra information in the unreliable memory, that is, the checking protocol is invasive. (In this solution the time of each "store" operation must be stored together with the data and must be supplied to the checker at the time of the corresponding retrieve operation.) In this paper we prove that off-line memory checking, in the sense described above, is necessarily invasive, even if we make the problem somewhat easier for the checker to exclude trivial counter-examples. We show that even if the checker is allowed to read a constant number of registers from the large memory after each "store" or "retrieve" instruction, off-line non-invasive memory checking is not possible. Moreover for the case when the invasiveness consists of storing some extra information together with each piece of data and retrieving it together with the data we give a quantitative lower bound on the amount of extra "invasive" information stored in the memory. Namely, if the checker has O(log n) memory and the probability of error is polynomially small than the "invasiveness" of the mentioned method of [5] is optimal upto a constant factor. With other words the total number of extra bits that must be written in the memory is at least εT log T, where T is the number of store and retrieve operations. In the lower bounds we do not restrict the computational power of the checker at all, in fact we only assume that the checker is an n-way branching program with O(log n) bits of memory.

Inversions are used as a fundamental quantity to measure the sortedness of data, to evaluate different ranking methods for databases, and in the context of rank aggregation. Considering the volume of the data sets in these applications, the data stream model [16, 2] is a natural setting to design efficient algorithms. We obtain a suite of space-efficient streaming algorithms for approximating the number of inversions in a permutation to within a factor of ffl. The best space bound we achieve for this problem is O(log n log log n) through a deterministic algorithm. In contrast, we derive an \\Omega\\Gamma n) lower bound for randomized exact computation for this problem; thus approximation is essential. For the more general problem of approximating the number of inversions between two permutations, we obtain a randomized O( p n log n)-space algorithm. For approximating the number of inversions in a general list, we give a randomized O( p n log 2 n)-space two-pass algorithm. In contrast, we derive \\Omega\\Gamma n) lower bounds for deterministic approximate computation for these problems; thus randomization is essential. All our algorithms use only O(log n) time per data item. Our result for approximating the number of inversions in a permutation is unique and surprising in the following aspect: all of the existing streaming algorithms require randomization in a crucial way, whereas our algorithms are deterministic! 1

The subject of this article is differential compression , the algorithmic task of finding common strings between versions of data and using them to encode one version compactly by describing it as a set of changes from its companion. A main goal of this work is to present new differencing algorithms that (i) operate at a fine granularity (the atomic unit of change), (ii) make no assumptions about the format or alignment of input data, and (iii) in practice use linear time, use constant space, and give good compression. We present new algorithms, which do not always compress optimally but use considerably less time or space than existing algorithms. One new algorithm runs in O ( n ) time and O (1) space in the worst case (where each unit of space contains [log n ] bits), as compared to algorithms that run in O ( n ) time and O ( n ) space or in O ( n 2 ) time and O (1) space. We introduce two new techniques for differential compression and apply these to give additional algorithms that improve compression and time performance. We experimentally explore the properties of our algorithms by running them on actual versioned data. Finally, we present theoretical results that limit the compression power of differencing algorithms that are restricted to making only a single pass over the data.

We present a randomized 2^{O(n)} time algorithm to compute a shortest non-zero vector in an n-dimensional rational lattice. The best known time upper bound for this problem was 2^{O(n\log n)} first given by Kannan [7] in 1983. We obtain several consequences of this algorithm for related problems on lattices and codes, including an improvement for polynomial time approximations to the shortest vector problem. In this improvement we gain a factor of log log n in the exponent of the approximating factor.

In the classical secretary problem, n objects from an ordered set arrive in random order, and one has to accept k of them so that the final decision about each object is made only on the basis of its rank relative to the ones already seen. Variants of the problem depend on the goal: either maximize the probability of accepting the best k objects, or minimize the expectation of the sum of the ranks (or powers of ranks) of the accepted objects. The problem and its generalizations are at the core of tasks with a large data set, in which it may be impractical to backtrack and select previous choices. Optimal algorithms for the special case of k = 1 are well known. Partial solutions for the first variant with general k are also known. In contrast, an explicit solution for the second variant with general k has not been known. It seems that the fact that the expected sum of powers of the ranks of selected items is bounded as n tends to infinity has been known to follow from standard results. We derive our results by obtaining explicit algorithms. For each $z \geq 1$, the resulting expected sum of the zth powers of the ranks of the selected objects is at most $k^{z + 1}/(z + 1) + C(z) \cdot k^{z + 0.5}\log k$, where log k \equiv \max\{1, \log_2 k\}$, whereas the best possible value at all is k z + 1/(z + 1) + O(k z ). Our methods are very intuitive and apply to some generalizations. We also derive a lower bound on the trade-off between the probability of selecting the best object and the expected rank of the selected object.

We prove that for all positive integer k and for all sufficiently small /spl epsiv/>0 if n is sufficiently large then there is no Boolean (or 2-way) branching program of size less than 2/sup em/ which for all inputs X/spl sube/{0, 1, ..., n-1} computes in time kn the parity of the number of elements of the set of all pairs (x,y) with the property x/spl isin/X, y/spl isin/X, x0 is an absolute constant and n is sufficiently large with respect to /spl delta/.

Our computational model is a random access machine with n read only input registers each containing c log n bits of information and a read and wile memory.We measure the time by the number of accesses to the input registers.We show thal for all k there is an E > 0 so that if n is sufficiently large then the elements distinctness problem cannot be solved in time kn with en bits of read and wile memory.that is.there is no machine with this values of the parameters which decides whether there are two different input registers whose contents are identical.Intmduction.One of the main goals of complexity theory is the separation of non-deterministic and deterministic computation.We solve the problem for random access machines with certain restrictions on the size of their working memory.Although the restrictions are strong, the working memory must be smaller than the input.still.under certain circumstances this computational model is realistic as we will explain later.Our seacrh problem.as described in the abstract is the element distinctness problem.that is.we have to decide whether there are different input registers with identical contents.We also show that there is a simple decision problem that can be solved in constant time (actually in IWO steps) using non-deterministic computation, while there is no deterministic linear time algorithm with enlogn bits read and write memory which solves the problem.More precisely if we allow kn time for some fixed constant k, then there is an 6 > 0 so that the problem cannot be solved with in log n bits of read and write memory if n is sufficiently large.The decision problem is the following: "Find two different input registers, so that the Hamming distance of their contents is at most i c log n".i can be replaced by any fixed 0 < 7 < 4 if c is sufficiently loge with respect to 7. We actually show that the promise problem : "decide whether all occurring Hamming dist'ances are greater than ($ -r)c log n

It is a well-known result of Fagin that the complexity class NP coincides with the class of problems expressible in existential second-order logic (El), which allows sentences consisting of a string of existential second-order quantifiers followed by a first-order formula.Monadic NP is the class of problems expressible in monadic Cl, i.e., Xi with therestriction that the second-order quantifiers are all unary, and hence range only over sets (as opposed to ranging over, say, binary relations), For example, the property of a graph being 3colorable belongs to monadic NP, because 3colorability can be expressed by saying that there exists three sets of vertices such that each vertex is in exactly one of the sets and no two vertices in the same set are connected by an edge.Unfortunately, monadicNPis notarobustclass, inthatitisnotclosed under first-order quantification.We define closed monadic NP to be the closure of monadic NP under first-order quanthlcation and existential unary second-order quantification.Thus, closed monadic NP differs from monadic NP in that we allow the possibility of arbitrary interleavings of tirstorder qunntifiers among the existential unary second-order quantifiers, We show that closed monadic NP is a natural, rich, and robust subclass of NP.As evidence for its richness, we show that not only is it a proper extension of monadic NP, but that it contains properties not in various other extensions of monadic NP.In particular, we show that closed monadic NP contnins an undirected graph property not in the closure of monadic NP under first-order quantification and Boolean operations, Our lower-boundproofsrequire a number of new game-theoretic techniques.*The full vcrnlon of this pnpcr, including proofs, can be obtaioed from: hltp://v/wv~,nlmadcn,ibm.comlcs/people/ 'This is xcessible from the finite model theory home page ut httpz~/speedy.informatkwth-aachen.dcAVWW~.html.

Abstract We present a probabilistic public key cryptosystem which is secure unless the worst case of the following lattice problem can be solved in polynomial time: "Find the shortest nonzero vector in an n dimensional lattice L where the shortest vector v is unique in the sense that any other vector whose length is at most nckvk is parallel to v."

. We give a random class of lattices in Z n so that, if there is a probabilistic polynomial time algorithm which finds a short vector in a random lattice with a probability of at least 1 2 then there is also a probabilistic polynomial time algorithm which solves the following three lattice problems in every lattice in Z n with a probability exponentially close to one. (1) Find the length of a shortest nonzero vector in an n-dimensional lattice, approximately, up to a polynomial factor. (2) Find the shortest nonzero vector in an n-dimensional lattice L where the shortest vector v is unique in the sense that any other vector whose length is at most n c kvk is parallel to v, where c is a sufficiently large absolute constant. (3) Find a basis b 1 ; :::; b n in the n-dimensional lattice L whose length, defined as max n i=1 kb i k, is the smallest possible up to a polynomial factor. A large number of the existing techniques of cryptography include the generation of a specific ins...

It is shown that for any fixed number of variables, linear-programming problems with n linear inequalities can be solved deterministically by n parallel processors in sublogarithmic time. The parallel time bound (counting only the arithmetic operations) is $O((\log \log n)^d )$, where d is the number of variables. In the one-dimensional case, this bound is optimal. If we take into account the operations needed for processor allocation, the time bound is $O((\log \log n)^{d + c} )$, where c is an absolute constant.

In the classical secretary problem, n objects from an ordered set arrive in random order, and one has to accept k of them so that the final decision about each object is made only on the basis of its rank relative to the ones already seen. Variants of the problem depend on the goal: either maximize the probability of accepting the best k objects, or minimize the expectation of the sum of the ranks (or powers of ranks) of the accepted objects. The problem and its generalizations are at the core of tasks with a large data set, in which it may be impractical to backtrack and select previous choices. Optimal algorithms for the special case of k=1 are well known. Partial solutions for the first variant with general k are also known. In contrast, an explicit solution for the second variant with general k has not been known; even the question of whether or not the expected sum of powers of the ranks of selected items tends to infinity with n has been unresolved. We answer these open questions by obtaining explicit algorithms. For each z/spl ges/1, the resulting expected sum of the zth powers of the ranks of the selected objects is at most k/sup z+1//(z+1)+C(z)/spl middot/k/sup z+0.5/log k, whereas the best possible value at all is k/sup z+1//(z+1)+O(k/sup z/). Our methods are very intuitive and apply to some generalizations. We also derive a lower bound on the trade-off between the probability of selecting the best object and its expected rank.

We introduce a theory of competitive analysis for distributed algorithms. The first steps in this direction were made in the seminal papers of Y. Bartal et al. (1992), and of B. Awerbuch et al. (1992), in the context of data management and job scheduling. In these papers, as well as in other subsequent sequent work, the cost of a distributed algorithm is compared to the cost of an optimal global-control algorithm. In this paper we introduce a more refined notion of competitiveness for distributed algorithms, one that reflects the performance of distributed algorithms more accurately. In particular, our theory allows one to compare the cost of a distributed on-line algorithm to the cost of an optimal distributed algorithm. We demonstrate our method by studying the cooperative collect primitive, first abstracted by M. Saks, N. Shavit, and H. Woll (1991). We provide the first algorithms that allow processes to cooperate to finish their work in fewer steps. Specifically, we present two algorithms (with different strengths), and provide a competitive analysis for each one.>

No abstract available.

If p is a prime and n is a positive integer then the mod p counting principle for n (CPp,n ) is the following statement: there are no two equivalence relations @ and @ on a set A of size n with the following properties: (a) each class of@ cent ains exactly p elements, and (b) each class of IO with one exception contains exactly p elements, the exceptional class contains 1 element.We will always assume that p is constant and n is sufficiently large.If we associate Boolean variables x ~, b, ya, b with all pairs formed from the elements of A then CPP,n can be expressed as a Boolean formula of constant depth and polynomial size.(We may think that a@b iff xa, h = 1, aQb iff Ya,b = 1.)This formula is a tautology.We show that if p, q are distinct primes then there is no constant depth polynomial (in n) size Frege proof of CF'P,n even if we are allowed to use CF'q,n as an axiom schema.(We get the axiom schema from C'Pg,n by replacing in every possible way the variables in G'pq,n by constant depth polynomial size fromulae formed from the variables used in the Frege proof.This schema says the if we define the partitions 0, W in an arbi-

Given a graph G on n nodes the authors say that a graph T on n + k nodes is a k-fault tolerant version of G, if one can embed G in any n node induced subgraph of T. Thus T can sustain k faults and still emulate G without any performance degradation. They show that for a wide range of values of n, k and d, for any graph on n nodes with maximum degree d there is a k-fault tolerant graph with maximum degree O(kd). They provide lower bounds as well: there are graphs G with maximum degree d such that any k-fault tolerant version of them has maximum degree at least Ω(d√k)

The authors investigate the asymptotic efficiency of certain combinatorial networks called halvers, which are basic building blocks of many parallel algorithms. They improve the efficiency of halvers in terms of their depth. The novelty is the use of combinatorial circuits whose basic units are k-sorter switches.>

It is shown that for any fixed number of variables, the linear programming problems with n linear inequalities can be solved deterministically by n parallel processors in sub-logarithmic time. The parallel time bound is O((log log n)d) where d is the number of variables. In the one-dimensional case this bound is optimal.

Abstract Although it is known that reachability in undirected finite graphs can be expressed by an existential monadic second-order sentence, our main result is that this is not the case for directed finite graphs (even in the presence of certain “built-in” relations, such as the successor relation). The proof makes use of Ehrenfeucht-Fraïssé games, along with probabilistic arguments. However, we show that for directed finite graphs with degree at mostk, reachability is expressible by an existential monadic second-order sentence.

The relation between the expressive power of datalog and that of first-order languages, is clarified. It is then proved that every first-order expressible datalog query is bounded. A form of compactness theorem for finite structure implied by this result is examined, and counterexamples to natural generalizations of the above result are given.>

This paper presents a comparison sorting algorithm for the abstract CROW PRAM parallel computer model. The algorithm sorts n input values using n processors and runs in time $O(\log n/\log \log n)$ on the average, assuming that all permutations of the input are equally likely.

The pigeonhole principle for n is the statement that there is no one-to-one function between a set of size n and a set of size n-1. This statement can be formulated as an unlimited-fan-in constant depth polynomial-size Boolean formula PHP/sub n/ in n(n-1) variables, PHP/sub n/ can be proved in the propositional calculus; that is, a sequence of Boolean formulas can be given so that each one is either an axiom of the propositional calculus or a consequence of some of the previous ones according to an inference rule of the propositional calculus, the last one being PHP/sub n/. The main result is that the pigeonhole principle cannot be proved in this way if the size of the proof (the total number or symbols of the formulas in the sequence) is polynomial in n and each formula is constant-depth (unlimited-fan-in), polynomial size and contains only the variables of PHP/sub n/.>

It is shown that for directed graphs, reachability can not be expressed by an existential monadic second-order sentence. The proof makes use of Ehrenfeucht-Fraisse games, along with probabilistic. However, it is shown that for directed graphs with degree at most k, reachability is expressible by an existential monadic second-order sentence. One reason for the interest in the main result is that while there is considerable empirical evidence (in terms of the efficiency of algorithms that have been discovered) that reachability in directed graphs is 'harder' than reachability in undirected graphs, this is the first proof in a precise technical sense that this is so.>

We present an algorithm which in n3(log n)3 time constructs a 3- regular expander graph on n vertices. In each step we substitute a pair of edges of the graph by a new pair of edges so that the total number of cycles of length s = [c log n] decreases (for some fixed absolute constant c). When we reach a local minimum in the number of cycles of length s the graph is an expander. The proof is completely elementary, we use only the basic results about the eigenvalues and eigenvectors of symmetric matrices.

In this paper we show that a wide class of probabilistic algorithms can be simulated by deterministic algorithms. Namely if there is a test in LOGSPACE so that a random sequence of length (log n)2 / log log n passes the test with probability at least 1/n then a deterministic sequence can be constructed in LOGSPACE which also passes the test. It is important that the machine performing the test gets each bit of the sequence only once. The theorem remains valid if both the test and the machine constructing the satisfying sequence have access to the same oracle of polynomial size.

In connection with the least fixed point operator the following question was raised: Suppose that a first-order formula P ( P ) is (semantically) monotone in a predicate symbol P on finite structures. Is P ( P ) necessarily equivalent on finite structures to a first-order formula with only positive occurrences of P ? In this paper, this question is answered negatively. Moreover, the counterexample naturally gives a uniform sequence of constant-depth, polynomial-size, monotone Boolean circuits that is not equivalent to any (however nonuniform) sequence of constant-depth, polynomial-size, positive Boolean circuits.

The first result concerns branching programs having width (log n) °{*).We give an fl(n log n~ log log n) lower bound for the size of such branching programs computing almost any symmetric Boolean fnnction and in particular the following explicit fnnction: "the sum of the input variables is a quadratic residue mod p" where p is any given prime between n 1/4 and n 1/3.This is a strengthening of previous nonlinear lower bounds obtained by Chandra, Furst, Lipton and by Pudlgk.We mention that by iterating our method the result can be further strengthened to lfl(nlog n).The second result is a C" lower bound for read-onceonly branching programs computing an explicit Boolean function.For n = (~), the function computes the parity of the number of triangles in a graph on v vertices.This improves previous exp(cx/n ) lower bounds for other graph functions by Wegener and Z£k.The result implies a linear lower bound for the space complexity of this Boolean function on "eraser machines", i.e. machines that erase each input bit immediately after having read it.

We show that in the deterministic comparison model for parallel computation, n processors can select the k th smallest item from a set of n numbers in O(loglogn) parallel time.With this result all comparison tasks (selection, merging, sorting), now have upper and lower bounds of the same order in both random and deterministic models.

We explicitly construct, for every integer n and ε ≫ 0, a family of functions (psuedo-random bit generators) fn,ε:{0,1}nε → {0,1}n with the following property: for a random seed, the pseudorandom output "looks random" to any polynomial size, constant depth, unbounded fan-in circuit. Moreover, the functions fn,ε themselves can be computed by uniform polynomial size, constant depth circuits. Some (interrelated) consequences of this result are given below. 1) Deterministic simulation of probabilistic algorithms. The constant depth analogues of the probabilistic complexity classes RP and BPP are contained in the deterministic complexity classes DSPACE(nε) and DTIME(2nε) for any ε ≫ 0. 2) Making probabilistic constructions deterministic. Some probablistic constructions of structures that elude explicit constructions can be simulated in the above complexity classes. 3) Approximate counting. The number of satisfying assignments to a (CNF or DNF) formula, if not too small, can be arbitrarily approximated in DSPACE(nε) and DTIME(2nε), for any ε ≫ 0. We also present two results for the special case of depth 2 circuits. They deal, respectively, with finding a satisfying assignment and approximately counting the number of assignments. For example, for 3-CNF formulas with a fixed fraction of satisfying assignmemts, both tasks can be performed in polynomial time!

Article Free Access Share on A theorem on probabilistic constant depth Computations Authors: Miklos Ajtai View Profile , Michael Ben-Or View Profile Authors Info & Claims STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computingDecember 1984 Pages 471–474https://doi.org/10.1145/800057.808715Online:01 December 1984Publication History 55citation507DownloadsMetricsTotal Citations55Total Downloads507Last 12 Months22Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The complexity of priority queue operations is analyzed with respect to the cell probe computational model of A. Yao. A method utilizing families of hash functions is developed which permits priority queue operations to be implemented in constant worst case time provided that a size constraint is satisfied. The minimum necessary size of a family of hash functions for computing the rank function is estimated and contrasted with the minimum size required for perfect hashing.

The purpose of this paper is to describe a sorting network of size 0(n log n) and depth 0(log n).