Lower bounds on the OBDD size of two fundamental functions' graphs

Ordered Binary Decision Diagrams (OBDDs) are a data structure for Boolean functions which supports many useful operations. Among others it finds applications in CAD, model checking, and symbolic graph algorithms. Nevertheless, many simple functions are known to have exponential OBDD size with respect to their number of variables. In order to investigate the limits of symbolic graph algorithms which work on OBDD-represented graph instances, it is useful to have simply-structured graphs whose OBDD representation has exponential size. Therefore, we consider two fundamental functions with exponential lower bounds on their OBDD size and transfer these results to their corresponding graphs. Concretely, we consider the Indirect Storage Access function and the Hidden Weighted Bit function.     

Efficient polynomial time algorithms computing industrial-strength primitive roots

E. Bach, following an idea of T. Itoh, has shown how to build a small set of numbers modulo a prime p such that at least one element of this set is a generator of Z/pZ. E. Bach suggests also that at least half of his set should be generators. We show here that a slight variant of this set can indeed be made to contain a ratio of primitive roots as close to 1 as necessary. In particular we present an asymptotically algorithm providing primitive roots of p with probability of correctness greater than 1−? and several O(logα(p)), α?5.23, algorithms computing “Industrial-strength” primitive roots.     

A decidable characterization of the classes between lintime and exptime

A language is defined by closure under safe iteration and under a new form of safe diagonalization that, unlike other forms of diagonalization used in literature to define sub-recursive hierarchies, is constructive and decidable. By counting the nesting levels of these schemes, an ordinal is assigned to each program. This yields a hierarchy Tα(α<ωω) that singles-out the complexity classes DTIMEF(ncnd+e) for all c,d,e?0.     

Range mode and range median queries in constant time and sub-quadratic space

Given a list of n items and a function defined over sub-lists, we study the space required for computing the function for arbitrary sub-lists in constant time.For the function mode we improve the previously known space bound O(n²/logn) to O(n²loglogn/log²n) words.For median the space bound is improved to O(n²loglog²n/log²n) words from O(n²⋅log(k)n/logn), where k is an arbitrary constant and log(k) is the iterated logarithm.     

String matching with simple devices

With the help of a general simulation technique of deterministic finite two-way multi-head automata by automata with blind heads we show O(n²/logn) to be an upper time bound on string matching. This result is tight by a previously known lower bound.     

Parallel algorithms for some functions of two convex polygons

Let P andQ be two convex,n-vertex polygons. We consider the problem of computing, in parallel, some functions ofP andQ whenP andQ are disjoint. The model of parallel computation we consider is the CREW-PRAM, i.e., it is the synchronous shared-memory model where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing). We show that a CREW-PRAM havingn ^1/k processors can compute the following functions in O(k¹⁺) time: (i) the common tangents betweenP andQ, and (ii) the distance betweenP andQ (and hence a straight line separating them). The positive constant can be made arbitrarily close to zero. Even with a linear number of processors, it was not previously known how to achieve constant time performance for computing these functions. The algorithm for problem (ii) is easily modified to detect the case of zero distance as well.This research was supported by the Office of Naval Research under Grants N00014-84-K-0502 and N00014-86-K-0689, and the National Science Foundation under Grant DCR-8451393, with matching funds from AT&T.     

Cryptography and cryptographic protocols

We survey the paradigms, approaches and techniques used to conceptualize, define and provide solutions to natural cryptographic problems. We start by presenting some of the central tools (e.g., computational difficulty, pseudorandomness, and zero-knowledge proofs), and next turn to the treatment of encryption and signature schemes. We conclude with an extensive treatment of secure cryptographic protocols both when executed in a stand-alone manner and when many sessions of various protocols are concurrently executed and controlled by an adversary. The survey is intended for researchers in distributed computing, and assumes no prior familiarity with cryptography.Received: June 2001, Accepted: July 2002,     

On limits on the computational power of data-accumulating algorithms

In the data-accumulating paradigm, inputs arrive continuously in real time, and the computation terminates when all the already received data are processed before another datum arrives. Previous research states that a constant upper bound on the running time of a successful algorithm within this paradigm exists only for particular forms of the data arrival law. This contradicts our recent conjecture that those problems that are solvable in real time are included in the class of logarithmic space-bounded computations. However, we prove that such an upper bound does exist in fact in both the parallel and sequential cases and for any polynomial arrival law, thus strengthening the mentioned conjecture. Then, we analyze an example of a non-continuous data arrival law. We find similar properties for the sorting algorithm under such a law, namely the existence of an upper bound on the running time, suggesting that such properties do not depend on the form of the arrival law.     

Fast parallel recognition of LR language suffixes

It is shown that suffix recognition for deterministic context-free languages can be done on a PRAM multi-processor within the upper complexity bounds of the graph reachability problem.     

Top-down lower bounds for depth-three circuits

We present a top-down lower bound method for depth-three , , ¬-circuits which is simpler than the previous methods and in some cases gives better lower bounds. In particular, we prove that depth-three , , ¬-circuits that compute parity (or majority) require size at least , respectively). This is the first simple proof of a strong lower bound by a top-down argument for non-monotone circuits.     

Quantum lower bounds for the Goldreich-Levin problem

At the heart of the Goldreich-Levin theorem is the problem of determining an n-bit string a by making queries to two oracles, referred to as IP (inner product) and EQ (equivalence). The IP oracle, on input x, returns a bit that is biased towards a⋅x (the modulo two inner product of a with x) in the following sense. For a random x, the probability that IP(x)=a⋅x is at least . The EQ oracle, on input x, returns a bit specifying whether or not x=a. It has been shown that a quantum algorithm can solve this problem with O(1/?) IP and EQ queries, whereas any classical algorithm requires Ω(n/?²) such queries. Also, the quantum algorithm requires only O(n/?) auxiliary one- and two-qubit gates in addition to its queries. We show that the above quantum algorithm is optimal in terms of both EQ and IP queries. Specifically, Ω(1/?) EQ queries are necessary, and Ω(1/?) IP queries are necessary if the number of EQ queries is .     

Vertex rankings of chordal graphs and weighted trees

In this paper we consider the vertex ranking problem of weighted trees. We show that this problem is strongly NP-hard. We also give a polynomial-time reduction from the problem of vertex ranking of weighted trees to the vertex ranking of (simple) chordal graphs, which proves that the latter problem is NP-hard. In this way we solve an open problem of Aspvall and Heggernes. We use this reduction and the algorithm of Bodlaender et al.'s for vertex ranking of partial k-trees to give an exact polynomial-time algorithm for vertex ranking of a tree with bounded and integer valued weight functions. This algorithm serves as a procedure in designing a PTAS for weighted vertex ranking problem of trees with bounded weight functions.     

A fixed-parameter tractable algorithm for matrix domination

Matrix domination is the NP-complete problem of determining whether a given {0,1} matrix contains a set of k non-zero entries that are in the same row or same column as all other non-zero entries. Using a kernelization and search tree approach, we show the problem to be fixed-parameter tractable with running time .     

Monotone separations for constant degree polynomials

We prove a separation between monotone and general arithmetic formulas for polynomials of constant degree. We give an example of a polynomial C in n variables and degree k which is computable by a homogeneous arithmetic formula of size O(k²n²), but every monotone formula computing C requires size (n/kc)^Ω(logk), with c∈(0,1). Since the upper bound is achieved by a homogeneous arithmetic formula, we also obtain a separation between monotone and homogeneous formulas, for polynomials of constant degree.     

关于矩阵张量积计算的研究

利用矩阵张量积有关理论,讨论了矩阵张量积的计算问题,分析了算法的复杂性,并研究了并行算法及计算复杂性问题。