Communication complexity towards lower bounds on circuit depth

Karchmer, Raz, and Wigderson (1995) discuss the circuit depth complexity of n-bit Boolean functions constructed by composing up to d = log n/log log n levels of k = log n-bit Boolean functions. Any such function is in AC¹ . They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for this problem requires depth. This would separate AC¹ from NC¹. They recommend using the communication game characterization of circuit depth. In order to develop techniques for using communication complexity to prove circuit depth lower bounds, they suggest an intermediate communication complexity problem which they call the Universal Composition Relation. We give an almost optimal lower bound of dk—O(d ²(k log k)^1/2) for this problem. In addition, we present a proof, directly in terms of communication complexity, that there is a function on k bits requiring circuit depth. Although this fact can be easily established using a counting argument, we hope that the ideas in our proof will be incorporated more easily into subsequent arguments which use communication complexity to prove circuit depth bounds. Received: July 30, 1999.     

Complex polynomials and circuit lower bounds for modular counting

We study the power of constant-depth circuits containing negation gates, unbounded fan-in AND and OR gates, and a small number of MAJORITY gates. It is easy to show that a depth 2 circuit of sizeO(n) (wheren is the number of inputs) containingO(n) MAJORITY gates can determine whether the sum of the input bits is divisible byk, for any fixedk>1, whereas it is known that this requires exponentialsize circuits if we have no MAJORITY gates. Our main result is that a constant-depth circuit of size containingn ^o(1) MAJORITY gates cannot determine if the sum of the input bits is divisible byk; moreover, such a circuit must give the wrong answer on a constant fraction of the inputs. This result was previously known only fork=2. We prove this by obtaining an approximate representation of the behavior of constant-depth circuits by multivariate complex polynomials.     

Upper and lower bounds for some depth-3 circuit classes

We investigate the complexity of depth-3 threshold circuits with majority gates at the output, possibly negated AND gates at level two, and MOD _m gates at level one. We show that the fan-in of the AND gates can be reduced toO(logn) in the case wherem is unbounded, and to a constant in the case wherem is constant. We then use these upper bounds to derive exponential lower bounds for this class of circuits. In the unboundedm case, this yields a new proof of a lower bound of Grolmusz; in the constantm case, our result sharpens his lower bound. In addition, we prove an exponential lower bound if OR gates are also permitted on level two andm is a constant prime power.Dedicated to the memory of Roman Smolensky     

Parameter bounds evaluation of Wiener models with noninvertible polynomial nonlinearities

In this paper a three stage procedure is presented for deriving parameters bounds of SISO Wiener models when the nonlinear block is modeled by a possibly noninvertible polynomial and the output measurement errors are bounded. First, using steady-state input-output data, parameters of the nonlinear part are bounded by a tight orthotope. Then, given the estimated uncertain nonlinearity and the output measurements collected exciting the system with an input dynamic signal, bounds on the unmeasurable inner signal are computed. Finally, such bounds, together with noisy output measurements, are used for bounding the parameters of the linear block.     

Nonlinear integrals with polynomial kernel and its applications

Nonlinear integrals (NIs) are useful integration tools. It can get a set of virtual values by projecting original data onto a virtual space for classification purpose using NIs. The classical NIs implement projection along a line with respect to the features. But, in many cases, the linear projection cannot achieve good performance for classification or regression due to the limitation of the integrand. The linear function used for the integrand is just a special type of function with respect to the features. In this paper, we propose a nonlinear integrals with polynomial kernel (NIPK). A polynomial function with respect to the features is used as the integrand of NIs. It enables the projection to be along different types of curves to the virtual space so that the virtual values gotten by NIs can be better regularized and have higher separation power for classification. We use genetic algorithm to learn the fuzzy measures so that a larger solution space can be searched. To test the capability of the NIPK, we apply it to classification on several benchmark datasets and a bioinformatics project. Experiments show that there is evident improvement on performance for the NIPK compared to classical NIs. © 2011 Wiley Periodicals, Inc.     

Stronger uncertainty relations with improvable upper and lower bounds

The quantum superposition principle is used to establish improved upper and lower bounds for the Maccone–Pati uncertainty inequality, which is based on a “weighted-like” sum of the variances of observables. Our bounds include free parameters that not only guarantee nontrivial bounds but also effectively control the bounds’ tightness. Significantly, these free parameters depend on neither the state nor the observables. A feature of our method is that any nontrivial bound can always be improved. In addition, we generalize both bounds to uncertainty relations with multiple (three or more) observables, maintaining the uncertainty relations’ tightness. Examples are given to illustrate our improved bounds.     

Model checking expected time and expected reward formulae with random time bounds

In this paper, we extend CSL (continuous stochastic logic) with an expected time and an expected reward operator, both of which are parameterized by a random terminal time. With the help of such operators we can state, for example, that the expected sojourn time in a set of goal states within some generally distributed delay is at most (at least) some time threshold. In addition, certain performance measures of systems which contain general distributions can be calculated with the aid of this extended logic. We extend the efficient model checking of CTMCs against the logic CSL developed by Katoen et al. [1] to cater for the new operator. Our method involves precomputing a family of mixed Poisson expected sojourn time coefficients for a range of random variables which includes Pareto, uniform and gamma distributions, but otherwise carries the same computational cost as calculating CSL until formulae.     

Lower time bounds for integer programming with two variables

In this paper an elementary version of the integer programming problem is considered, namely that of deciding whether a given triangle in the plane contains a point with integer coordinates. We prove two lower bounds for the number of operations necessary to solve this problem: (i) Ω(p) steps are necessary if operations from {+, -,%,, ?} are admissible, (ii) Ω(log p) steps are necessary if operations from {+, -, ?·?, ?} are admissible. Here, p denotes the binary length of the input and ?·? denotes the floor function. New techniques are necessary for relating the bounds to the length of the input—known methods only yield uniform bounds assuming all real inputs to be allowed—and for handling the floor function which prevents us from applying the well-known algebraic arguments.The best known algorithm is due to H.W. Lenstra, Jr. (preprint) and needs O(p) steps over {+, -, 1, %, ?·?, ?} (P. van Emde Boas, 1984).     

Stable duplicate-key extraction with optimal time and space bounds

Summary We consider the problem of transforming a list L of records sorted on some key into two sublists L ₁ and L ₂ where, for each distinct key in L, L ₁ contains the first record of L that possesses the key and L ₂ contains all records of L with duplicate keys. We desire that our duplicate-key extraction algorithm perform the transformation in place and be stable (that is, records within each sublist must obey the original order given by L). This operation is useful in database and related file processing environments whenever only distinct keys need be considered. Moreover, stability in extraction insures that L can be efficiently restored at a later time with a stable merge of L ₁ and L ₂. Any procedure for performing duplicate-key extraction on a list of size n must require at least O(n) time and O(1) extra space, although the obvious algorithm for achieving either bound alone violates the other bound. We design a stable algorithm, using block-rearrangement techniques, and show that it is optimal in the theoretical sense that it achieves both lower bounds simultaneously. We also prove that its worst-case number of key comparisons and record exchanges sum to no more than 6 n, suggesting that the algorithm has practical application as well.A preliminary version of a portion of this paper [HL1] was presented at the 24th Annual Allerton Conference on Communication, Control and Computing held in Monticello, Illinois, in October, 1986This author's research has been supported in part by the Washington State University Graduate Research Assistantship ProgramThis author's research has been supported in part by the National Science Foundation under grants ECS-8403859 and MIP-8603879, and by the Office of Naval Research under contract N0001488-K-0343     

Frobenius-Chebyshev polynomial approximations with a priori error bounds for nonlinear initial value differential problems

In this paper, we present a method for approximating the solution of initial value ordinary differential equations with a priori error bounds. The method is based on a Chebyshev perturbation of the original differential equation together with the Frobenius method for solving the equation. Chebyshev polynomials in two variables are developed. Numerical results are presented.     

Calculation of simplicial depth estimators for polynomial regression with applications

A fast algorithm for calculating the simplicial depth of a single parameter vector of a polynomial regression model is derived. Additionally, an algorithm for calculating the parameter vectors with maximum simplicial depth within an affine subspace of the parameter space or a polyhedron is presented. Since the maximum simplicial depth estimator is not unique, l₁ and l₂ methods are used to make the estimator unique. This estimator is compared with other estimators in examples of linear and quadratic regression. Furthermore, it is shown how the maximum simplicial depth can be used to derive distribution-free asymptotic α-level tests for testing hypotheses in polynomial regression models. The tests are applied on a problem of shape analysis where it is tested how the relative head length of the fish species Lepomis gibbosus depends on the size of these fishes. It is also tested whether the dependency can be described by the same polynomial regression function within different populations.     

Minimal-cost network flow problems with variable lower bounds on arc flows

The minimal-cost network flow problem with fixed lower and upper bounds on arc flows has been well studied. This paper investigates an important extension, in which some or all arcs have variable lower bounds. In particular, an arc with a variable lower bound is allowed to be either closed (i.e., then having zero flow) or open (i.e., then having flow between the given positive lower bound and an upper bound). This distinctive feature makes the new problem NP-hard, although its formulation becomes more broadly applicable, since there are many cases where a flow distribution channel may be closed if the flow on the arc is not enough to justify its operation. This paper formulates the new model, referred to as MCNF-VLB, as a mixed integer linear programming, and shows its NP-hard complexity. Furthermore, a numerical example is used to illustrate the formulation and its applicability. This paper also shows a comprehensive computational testing on using CPLEX to solve the MCNF-VLB instances of up to medium-to-large size.     

On time bounds, the work-time scheduling principle, and optimalityfor BSR

Constant time solutions for many applications have been obtained on BSR, but some theoretical problems on BSR (broadcasting with selective reduction) that raised when BSR was proposed have not been solved. Three of them are: 1) No lower bound for any problem on BSR is known except trivial constant time, 2) is there any improvement with nonconstant BSR time but still better than the lower bound for CRCW?, and 3) how to characterize problems for which BSR achieves constant time performance. In this paper, we have solved these three problems. For Problem 1, a lower bound on BSR is shown for any computational problem with an optimal sequential solution. An efficient sorting algorithm answers the second problem. A necessary condition is given for the third problem. The work-time (WT) scheduling principle and optimality for BSR are also introduced for investigating the BSR performance when the number of processors available, p, is different from the input size, n, of problems     

Prediction of multivariate chaotic time series with local polynomial fitting

To improve the prediction accuracy of complex multivariate chaotic time series, a novel scheme formed on the basis of multivariate local polynomial fitting with the optimal kernel function is proposed. According to Takens Theorem, a chaotic time series is reconstructed into vector data, multivariate local polynomial regression is used to fit the predicted complex chaotic system, then the regression model parameters with the least squares method based on embedding dimensions are estimated,and the prediction value is calculated. To evaluate the results, the proposed multivariate chaotic time series predictor based on multivariate local polynomial model is compared with a univariate predictor with the same numerical data. The simulation results obtained by the Lorenz system show that the prediction mean squares error of the multivariate predictor is much smaller than the univariate one, and is much better than the existing three methods. Even if the last half of the training data are used in the multivariate predictor, the prediction mean squares error is smaller than that of the univariate predictor.     

Translational lemmas,polynomial time,and (log n)j-space

Translational lemmas are stated in a general framework and then applied to specific complexity classes. Necessary and sufficient conditions are given for every set accepted by a Turing acceptor which operates in linear or polynomial time to be accepted by a Turing acceptor which operates in space (log n)^j for some j ? 1.     

Duality in polynomial models with some applications to geometric control theory

Duality is studied in the context of polynomial models for linear systems. The output injection group, the dual of the feedback group, is studied and a polynomial characterization of (C, A)-invariant subspaces as well as of the maximal reachability subspaces contained in kerCis given.     

Preemptive open shop scheduling with multiprocessors: polynomial cases and applications

This paper addresses a multiprocessor generalization of the preemptive open-shop scheduling problem. The set of processors is partitioned into two groups and the operations of the jobs may require either single processors in either group or simultaneously all processors from the same group. We consider two variants depending on whether preemptions are allowed at any fractional time points or only at integer time points. We reduce the former problem to solving a linear program in strongly polynomial time, while a restricted version of the second problem is solved by rounding techniques. Applications to course scheduling and hypergraph edge coloring are also discussed.