Search

We prove a general lower bound on the size of switching-and-rectifier networks over any semiring of zero characteristic, including the ( min ? , + ) semiring. Using it, we show that the classical dynamic programming algorithm of Bellman, Ford and Moore for the shortest s-t path problem is optimal, if only Min and Sum operations are allowed.

Khrapchenko’s classical lower bound n2 on the formula size of the parity function f can be interpreted as designing a suitable measure of sub-rectangles of the combinatorial rectangle f−1(0)×f−1(1). Trying to generalize this approach we arrived at the concept of convex measures. We prove the negative result that convex measures are bounded by O(n2) and show that several measures considered for proving lower bounds on the formula size are convex. We also prove quadratic upper bounds on a class of measures that are not necessarily convex.

We propose an information-theoretic approach to proving lower bounds on the size of branching programs. The argument is based on Kraft type inequalities for the average amount of uncertainty about (or entropy of) a given input during the various stages of computation. The uncertainty is measured by the average depth of so-called ‘splitting trees’ for sets of inputs reaching particular nodes of the program.We first demonstrate the approach for read-once branching programs. Then, we introduce a strictly larger class of so-called ‘balanced’ branching programs and, using the suggested approach, prove that some explicit Boolean functions cannot be computed by balanced programs of polynomial size. These lower bounds are new since some explicit functions, which are known to be hard for most previously considered restricted classes of branching programs, can be easily computed by balanced branching programs of polynomial size.

A method for obtaining lower bounds on the contact circuit complexity of explicitly defined Boolean functions is given. It appears as one of possible concretizations of a more general “convolutional” approach to the lower bounds problem worked out by the author in 1984 [12]. The method is based on an appropriate notion of “inner information” or “entropy” of finite objects (circuits, Boolean functions, etc.). Lower bounds on the complexity are obtained by means of entropy-preserving embeddings of circuits into the more restricted ones. This allows to prove in a uniform and easy way that contact circuits, which are local in a sense that the function computed by a subcircuit weakly depends on the whole circuit, require 2 Ω(√n) or even 2 Ω( n log n ) contacts to compute some explicitly defined n -argument Boolean functions from NP.

The replication number of a branching program is the minimum number R such that along every accepting computation at most R variables are tested more than once; the sets of variables re-tested along different computations may be different. For every branching program, this number lies between 0 (read-once programs) and the total number n of variables (general branching programs). The best results so far were exponential lower bounds on the size of branching programs with R=o(n/logn). We improve this to [email protected][email protected] for a constant @e>0. This also gives an alternative and simpler proof of an exponential lower bound for ([email protected])n time branching programs for a constant @e>0. We prove these lower bounds for quadratic functions of Ramanujan graphs.

Already 30 years ago, Chvátal has shown that some instances of the zero-one knapsack problem cannot be solved in polynomial time using a particular type of branch-and-bound algorithms based on relaxations of linear programs together with some rudimentary cutting-plane arguments as bounding rules. We extend this result by proving an exponential lower bound in a more general class of branch-and-bound and dynamic programming algorithms which are allowed to use memoization and arbitrarily powerful bound rules to detect and remove subproblems leading to no optimal solution.