Time lower bounds for parallel sorting on a mesh-connected processor array

Summary We prove that (1+6/2)n 2.22n is a time lower bound independent of indexing schemes for sorting n² items on an n × n mesh-connected processor array. We distinguish between indexing schemes by showing that there exists an indexing scheme which is provably worse than the snake-like row-major indexing for sorting. We also derive lower bounds for various indexing schemes. All these results are obtained by using the chain argument which we provide in this paper.A preliminary version of this paper was presented on the 3rd International Workshop on Parallel Computation and VLSI Theory, Corfu Island, Greece (June–July, 1988). Lect. Notes Comput. Sci. 319, 434–443 (1988)Research supported in part by the University of Kentucky research initiation award     

A nondeterministic space-time tradeoff for linear codes

We are interested in proving exponential lower bounds on the size of nondeterministic D-way branching programs computing functions in linear time, that is, in time at most kn for a constant k. Ajtai has proved such lower bounds for explicit functions over domains D of size about n, and Beame, Saks and Thathachar for functions over domains of size about k²². We prove an exponential lower bound ²Ω(n/ck) for an explicit function over substantially smaller domain D of size about k². Our function is a universal function of linear codes.     

Improved upper bounds on synchronizing nondeterministic automata

We show that i-directable nondeterministic automata can be i-directed with a word of length O(2ⁿ) for i=1,2, where n stands for the number of states. Since for i=1,2 there exist i-directable automata having i-directing words of length Ω(2ⁿ), these upper bounds are asymptotically optimal. We also show that a 3-directable nondeterministic automaton with n states can be 3-directed with a word of length , improving the previously known upper bound O(2ⁿ). Here the best known lower bound is .     

Lower Bounds for Dynamic Algebraic Problems

We consider dynamic evaluation of algebraic functions (matrix multiplication, determinant, convolution, Fourier transform, etc.) in the model of Reif and Tate; i.e., if f(x₁,…, x_n)=(y₁, …, y_m) is an algebraic problem, we consider serving online requests of the form “change input x_i to value v” or “what is the value of output y_i?” We present techniques for showing lower bounds on the worst case time complexity per operation for such problems. The first gives lower bounds in a wide range of rather powerful models (for instance, history dependent algebraic computation trees over any infinite subset of a field, the integer RAM, and the generalized real RAM model of Ben-Amram and Galil). Using this technique, we show optimal Ω(n) bounds for dynamic matrix–vector product, dynamic matrix multiplication, and dynamic discriminant and an Ω( ) lower bound for dynamic polynomial multiplication (convolution), providing a good match with Reif and Tate's O( ) upper bound. We also show linear lower bounds for dynamic determinant, matrix adjoint, and matrix inverse and an Ω( ) lower bound for the elementary symmetric functions. The second technique is the communication complexity technique of Miltersen, Nisan, Safra, and Wigderson which we apply to the setting of dynamic algebraic problems, obtaining similar lower bounds in the word RAM model. The third technique gives lower bounds in the weaker straight line program model. Using this technique, we show an Ω((log n)²/log log n) lower bound for dynamic discrete Fourier transform. Technical ingredients of our techniques are the incompressibility technique of Ben-Amram and Galil and the lower bound for depth-two superconcentrators of Radhakrishnan and Ta-Shma. The incompressibility technique is extended to arithmetic computation in arbitrary fields.     

B$$_\pi ^R$$-matrices and error bounds for linear complementarity problems

B-matrices form a subclass of P-matrices for which error bounds for the linear complementarity problem are known. It is proved that a bound involved in such problems is asymptotically optimal. \(B_\pi ^R\)-matrices form a subclass of P-matrices containing B-matrices. For the \(B_\pi ^R\)-matrices, error bounds for the linear complementarity problem are obtained. We also include illustrative examples showing the sharpness of these bounds.     

Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas

In this paper, we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds, we obtain lower bounds for these models.For depth-3 multilinear formulas, of size exp\({(n^\delta)}\), we give a hitting set of size exp\({\left(\tilde{O}\left(n^{2/3 + 2\delta/3}\right) \right)}\). This implies a lower bound of exp\({(\tilde{\Omega}(n^{1/2}))}\) for depth-3 multilinear formulas, for some explicit polynomial.For depth-4 multilinear formulas, of size exp\({(n^\delta)}\), we give a hitting set of size exp\({\left(\tilde{O}\left(n^{2/3 + 4\delta/3}\right) \right)}\). This implies a lower bound of exp\({(\tilde{\Omega}(n^{1/4}))}\) for depth-4 multilinear formulas, for some explicit polynomial.A regular formula consists of alternating layers of \({+,\times}\) gates, where all gates at layer i have the same fan-in. We give a hitting set of size (roughly) exp\({\left(n^{1- \delta}\right)}\), for regular depth-d multilinear formulas with formal degree at most n and size exp\({(n^\delta)}\), where \({\delta = O(1/{\sqrt{5}^d})}\). This result implies a lower bound of roughly exp\({(\tilde{\Omega}(n^{1/{\sqrt{5}^d}}))}\) for such formulas.We note that better lower bounds are known for these models, but also that none of these bounds was achieved via construction of a hitting set. Moreover, no lower bound that implies such PIT results, even in the white-box model, is currently known.Our results are combinatorial in nature and rely on reducing the underlying formula, first to a depth-4 formula, and then to a read-once algebraic branching program (from depth-3 formulas, we go straight to read-once algebraic branching programs).     

Scaling of program functionality

The distribution of fitness values (landscapes) of programs tends to a limit as the programs get bigger. We use Markov chain convergence theorems to give general upper bounds on the length of programs needed for convergence. How big programs need to be to approach the limit depends on the type of the computer they run on. We give bounds (exponential in N, N log N and smaller) for five computer models: any, average or amorphous or random, cyclic, bit flip and four functions (AND, NAND, OR and NOR). Programs can be treated as lookup tables which map between their inputs and their outputs. Using this we prove similar convergence results for the distribution of functions implemented by linear computer programs. We show most functions are constants and the remainder are mostly parsimonious. The effect of ad-hoc rules on genetic programming (GP) are described and new heuristics are proposed. We give bounds on how long programs need to be before the distribution of their functionality is close to its limiting distribution, both in general and for average computers. The computational importance of destroying information is discussed with respect to reversible and quantum computers. Mutation randomizes a genetic algorithm population in generations. Results for average computers and a model like genetic programming are confirmed experimentally.     

Lower bounds for minimizing total completion time in a two-machine flow shop

For the -hard problem of scheduling n jobs in a two-machine flow shop so as to minimize the total completion time, we present two equivalent lower bounds that are computable in polynomial time. We formulate the problem by the use of positional completion time variables, which results in two integer linear programming formulations with O(n ²) variables and O(n) constraints. Solving the linear programming relaxation renders a very strong lower bound with an average relative gap of only 0.8% for instances with more than 30 jobs. We further show that relaxing the formulation in terms of positional completion times by applying Lagrangean relaxation yields the same bound, no matter which set of constraints we relax.     

Separating complexity classes related to bounded alternating ω-branching programs

We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of -branching programs, : , a semiring homomorphism, that generalizes ordinary branching programs, -branching programs [M2] andMOD _p-branching programs [DKMW].Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating -branching programs we are able to separate the corresponding complexity classesN _ba ,co-N _{ba ba} , andMOD _p - _ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.     

<Emphasis Type="Italic">hp</Emphasis>-Version <Emphasis Type="Italic">a priori</Emphasis> Error Analysis of Interior Penalty Discontinuous Galerkin Finite Element Approximations to the Biharmonic Equation

We consider the symmetric formulation of the interior penalty discontinuous Galerkin finite element method for the numerical solution of the biharmonic equation with Dirichlet boundary conditions in a bounded polyhedral domain in . For a shape-regular family of meshes consisting of parallelepipeds, we derive hp-version a priori bounds on the global error measured in the L² norm and in broken Sobolev norms. Using these, we obtain hp-version bounds on the error in linear functionals of the solution. The bounds are optimal with respect to the mesh size h and suboptimal with respect to the degree of the piecewise polynomial approximation p. The theoretical results are confirmed by numerical experiments, and some practical applications in Poisson–Kirchhoff thin plate theory are presented.     

Convergence of MUSCL Relaxing Schemes to the Relaxed Schemes for Conservation Laws with Stiff Source Terms

We consider the convergence and stability property of MUSCL relaxing schemes applied to conservation laws with stiff source terms. The maximum principle for the numerical schemes will be established. It will be also shown that the MUSCL relaxing schemes are uniformly l ¹- and TV-stable in the sense that they are bounded by a constant independent of the relaxation parameter , the Lipschitz constant of the stiff source term and the time step t. The Lipschitz constant of the l ¹ continuity in time for the MUSCL relaxing schemes is shown to be independent of and t. The convergence of the relaxing schemes to the corresponding MUSCL relaxed schemes is then established.     

Implementing Shared Memory on Mesh-Connected Computers and on the Fat-Tree

We present deterministic upper and lower bounds on the slowdown required to simulate an (n, m)-PRAM on a variety of networks. The upper bounds are based on a novel scheme that exploits the splitting and combining of messages. This scheme can be implemented on an n-node d-dimensional mesh (for constant d) and on an n-leaf pruned butterfly and attains the smallest worst-case slowdown to date for such interconnections, namely, O(n^1/d(log(m/n))^1-1/d) for the d-dimensional mesh (with constant d) and O( ) for the pruned butterfly. In fact, the simulation on the pruned butterfly is the first PRAM simulation scheme on an area-universal network. Finally, we prove restricted and unrestricted lower bounds on the slowdown of any deterministic PRAM simulation on an arbitrary network, formulated in terms of the bandwidth properties of the interconnection as expressed by its decomposition tree.     

Randomization and the computational power of analytic and algebraic decision trees

We introduce a new powerful method for provinglower bounds onrandomized anddeterministic analytic decision trees, and give direct applications of our results towards some concrete geometric problems. We design alsorandomized algebraic decision trees for recognizing thepositive octant in ⁿ or computing MAX in ⁿ in depth log ^O(1) n. Both problems are known to have linear lower bounds for the depth of any deterministic analytic decision tree recognizing them. The mainnew (andunifying) proof idea of the paper is in the reduction technique of the signs oftesting functions in a decision tree to the signs of theirleading terms at the specially chosen points. This allows us to reduce the complexity of adecision tree to the complexity of a certainBoolean circuit.     

An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography

In this paper, we present an efficient and general algorithm for decomposing multivariate polynomials of the same arbitrary degree. This problem, also known as the Functional Decomposition Problem (FDP), is classical in computer algebra. It is the first general method addressing the decomposition of multivariate polynomials (any degree, any number of polynomials). As a byproduct, our approach can be also used to recover an ideal I from its kth power I^k. The complexity of the algorithm depends on the ratio between the number of variables (n) and the number of polynomials (u). For example, polynomials of degree four can be decomposed in , when this ratio is smaller than . This work was initially motivated by a cryptographic application, namely the cryptanalysis of 2R⁻ schemes. From a cryptographic point of view, the new algorithm is so efficient that the principle of two-round schemes, including 2R⁻ schemes, becomes useless. Besides, we believe that our algorithm is of independent interest.     

New Approximation Bounds for Lpt Scheduling

We provide new bounds for the worst case approximation ratio of the classic Longest Processing Time (Lpt) heuristic for related machine scheduling (Q||C _max?). For different machine speeds, Lpt was first considered by Gonzalez et al. (SIAM J. Comput. 6(1):155–166, 1977). The best previously known bounds originate from more than 20 years back: Dobson (SIAM J. Comput. 13(4):705–716, 1984), and independently Friesen (SIAM J. Comput. 16(3):554–560, 1987) showed that the worst case ratio of Lpt is in the interval (1.512,1.583), and in (1.52,1.67), respectively. We tighten the upper bound to $1+\sqrt{3}/3\approx1.5773We provide new bounds for the worst case approximation ratio of the classic Longest Processing Time (Lpt) heuristic for related machine scheduling (Q||C _max). For different machine speeds, Lpt was first considered by Gonzalez et al. (SIAM J. Comput. 6(1):155–166, 1977). The best previously known bounds originate from more than 20 years back: Dobson (SIAM J. Comput. 13(4):705–716, 1984), and independently Friesen (SIAM J. Comput. 16(3):554–560, 1987) showed that the worst case ratio of Lpt is in the interval (1.512,1.583), and in (1.52,1.67), respectively. We tighten the upper bound to 1+?3/3 ? 1.57731+\sqrt{3}/3\approx1.5773 , and the lower bound to 1.54. Although this improvement might seem minor, we consider the structure of potential lower bound instances more systematically than former works. We present a scheme for a job-exchanging process, which, repeated any number of times, gradually increases the lower bound. For the new upper bound, this systematic method together with a new idea of introducing fractional jobs, facilitated a proof that is surprisingly simple, relative to the result. We present the upper-bound proof in parameterized terms, which leaves room for further improvements.     

The Parallel Complexity of Graph Canonization Under Abelian Group Action

We study the problem of computing canonical forms for graphs and hypergraphs under Abelian group action and show tight complexity bounds. Our approach is algebraic. We transform the problem of computing canonical forms for graphs to the problem of computing canonical forms for associated algebraic structures, and we develop parallel algorithms for these associated problems.

1. In our first result we show that the problem of computing canonical labelings for hypergraphs of color class size 2 is logspace Turing equivalent to solving a system of linear equations over the field $\mathbb {F} _{2}$ . This implies a deterministic NC ² algorithm for the problem.
2. Similarly, we show that the problem of canonical labeling graphs and hypergraphs under arbitrary Abelian permutation group action is fairly well characterized by the problem of computing the integer determinant. In particular, this yields deterministic NC ³ and randomized NC ² algorithms for the problem.