Search

We consider probabilistic circuits working over the real numbers, and using arbitrary semialgebraic functions of bounded description complexity as gates. In particular, such circuits can use all arithmetic operations +, -, x, /, optimization operations min and max, conditional branching (if-then-else), and many more. We show that probabilistic circuits using any of these operations as gates can be simulated by deterministic circuits with only about a quadratical blowup in size. A not much larger blow up in circuit size is also shown when derandomizing approximating circuits. The algorithmic consequence, motivating the title, is that randomness cannot substantially speed up dynamic programming algorithms., 25 pages, 1 table

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.

Many discrete minimization problems, including various versions of the shortest path problem, can be efficiently solved by dynamic programming (DP) algorithms that are “pure” in that they only perform basic operations, as min, max, +, but no conditional branchings via if-then-else in their recursion equations. It is known that any pure ( min ⁡ , + ) DP algorithm solving the minimum weight spanning tree problem on undirected n-vertex graphs must perform at least 2 Ω ( n ) operations. We show that this problem can be solved by a pure ( min ⁡ , max ⁡ , + ) DP algorithm performing only O ( n 3 ) operations. The algorithm is essentially a ( min ⁡ , max ⁡ ) algorithm: addition operations are only used to output the final values. The presence of both min and max operations means that now DP algorithms can sort: this explains the title of the paper.

Many dynamic programming algorithms for discrete 0-1 optimizationproblems are "pure" in that their recursion equations only use min/max and addition operations, and do not depend on actual input weights. The well-known greedy algorithm of Kruskal solves the minimum weight spanning tree problem on $n$-vertex graphs using only $O(n^2\log n)$ operations. We prove that any pure DP algorithm for this problem must perform $2^{\Omega(\sqrt{n})}$ operations. Since the greedy algorithm can also badly fail on some optimization problems, easily solvable by pure DP algorithms, our result shows that the computational powers of these two types of algorithms are incomparable., Comment: The first structural claim of the Forest lemma (that the sets of vertices in the connected components of all forests from one side must be the same) in the previous version is just wrong. We now use entirely different arguments to prove a slightly weaker version of the numerical claim of the Forest lemma. The resulting lower bound is weaker, but still exponential

A completion of an m-by-n matrix A with entries in {0,1,*} is obtained by setting all *-entries to constants 0 or 1. A system of semi-linear equations over GF(2) has the form Mx=f(x), where M is a completion of A and f:{0,1}^n --> {0,1}^m is an operator, the i-th coordinate of which can only depend on variables corresponding to *-entries in the i-th row of A. We conjecture that no such system can have more than 2^{n-c\cdot mr(A)} solutions, where c>0 is an absolute constant and mr(A) is the smallest rank over GF(2) of a completion of A. The conjecture is related to an old problem of proving super-linear lower bounds on the size of log-depth boolean circuits computing linear operators x --> Mx. The conjecture is also a generalization of a classical question about how much larger can non-linear codes be than linear ones. We prove some special cases of the conjecture and establish some structural properties of solution sets., 22 pages, to appear in: J. Comput.Syst.Sci.

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.

A boolean circuit represents an n by n(0,1)-matrix A if it correctly computes the linear transformation y→=Ax→ over GF(2) on all n unit vectors. If we only allow linear boolean functions as gates, then some matrices cannot be represented using fewer than Ω(n2/lnn) wires. We first show that using non-linear gates one can save a lot of wires: any matrix can be represented by a depth-2 circuit with O(nlnn) wires using multilinear polynomials over GF(2) of relatively small degree as gates. We then show that this cannot be substantially improved: If any two columns of an n by n(0,1)-matrix differ in at least d rows, then the matrix requires Ω(dlnn/lnlnn) wires in any depth-2 circuit, even if arbitrary boolean functions are allowed as gates.

We are interested in proving exponential lower bounds on the size of nondeterministic D-way branching programs computing functions f:D^n->{0,1} 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 2^2^^^k. We prove an exponential lower bound 2^@W^(^n^/^c^^^k^) for an explicit function over substantially smaller domain D of size about 2^k. Our function is a universal function of linear codes.

We consider unbounded fanin depth-2 circuits with arbitrary boolean functions as gates. We define the entropy of an operator f:{0,1}n →{0,1}m as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f. Our main result is that every depth-2 circuit for f requires at least entropy(f) wires. This is reminiscent of a classical lower bound of Nechiporuk on the formula size, and gives an information-theoretic explanation of why some operators require many wires. We use this to prove a tight estimate Θ(n 3) of the smallest number of wires in any depth-2 circuit computing the product of two n by n matrices over any finite field. Previously known lower bound for this operator was Ω(n 2log n).

We consider the analog of the P versus NP ∩ co-NP question for the classical two-party communication protocols where polynomial time is replaced by poly-logarithmic communication: if both a boolean function f and its negation ¬ f have small (poly-logarithmic in the number of variables) nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition model of communication this question was answered by Aho, Ullman and Yannakakis in 1983: here P = NP ∩ co-NP.We show that in the best partition model of communication the situation is entirely different: here P is a proper subset even of RP ∩ co-RP. This, in particular, resolves an open question raised by Papadimitriou and Sipser in 1982.

We study k-partition communication protocols, an extension of the standard two-party best-partition model to k input partitions. The main results are as follows. 1. A strong explicit hierarchy on the degree of non-obliviousness is established by proving that, using k + 1 partitions instead of k may decrease the communication complexity from Θ (n) to Θ(log k). 2. Certain linear codes are hard for k-partition protocols even when k may be exponentially large (in the input size). On the other hand, one can show that all characteristic functions of linear codes are easy for randomized OBDDs. 3. It is proved that there are subfunctions of the triangle-freeness function and the function ⊕ CLIQUE 3,n that are hard for multi-partition protocols. As an application, strongly exponential lower bounds on the size of nondeterministic read-once branching programs for these functions are obtained, solving an open problem of Razborov [Proceedings of the eighth FCT, LNCS 529, Springer, 1991, pp. 47-60].

We show that an explicit sequence of monotone functions fn : {0, 1}n → {0, 1}m (m ≤ n) can be computed by Boolean circuits with polynomial (in n) number of And, Or and Not gates, but every such circuit must use at least log n - O(log log n) Not gates. This is almost optimal because results of Markov [J. ACM 5 (1958) 331] and Fisher [Lecture Notes in Comput. Sci., Vol. 33, Springer, 1974, p. 71] imply that, with only small increase of the total number of gates, any circuit in n variables can be simulated by a circuit with at most ⌈log(n + 1)⌉ Not gates.

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.

We show that recognizing the K3-freeness and K4-freeness of graphs is hard, respectively, for two-player nondeterministic communication protocols using exponentially many partitions and for nondeterministic syntactic read-r times branching programs.The key ingredient is a generalization of a colouring lemma, due to Papadimitriou and Sipser, which says that for every balanced red—blue colouring of the edges of the complete n-vertex graph there is a set of εn2 triangles, none of which is monochromatic, such that no triangle can be formed by picking edges from different triangles. We extend this lemma to exponentially many colourings and to partial colourings.

Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower bounds arguments for tropical circuits, and hence, for dynamic programs., Corrected reduction to arithmetic circuits (holds only for multilinear polynomials, now Sect. 4). Solved Open Problem 3 about Min/Max gaps (now Lemma 10). Added lower bounds for the depth of tropical circuits (Sect. 15)

It is known that if a Boolean function f in n variables has a DNF and a CNF of size $ \le N $ then f also has a (deterministic) decision tree of size exp(O(log n log2 N)). We show that this simulation cannot be made polynomial: we exhibit explicit Boolean functions f that require deterministic trees of size exp $ (\Omega({\rm log^2} N)) $ where N is the total number of monomials in minimal DNFs for f and ¬f. Moreover, we exhibit new examples of explicit Boolean functions that require deterministic read-once branching programs of exponential size whereas both the functions and their negations have small nondeterministic read-once branching programs. One example results from the Bruen—Blokhuis bound on the size of nontrivial blocking sets in projective planes: it is remarkably simple and combinatorially clear. Other examples have the additional property that f is in AC0.

We introduce the model of conservative one-way multiparty complexity and prove lower and upper bounds on the complexity of pointer jumping.¶ The pointer jumping function takes as its input a directed layered graph with a starting node and k layers of n nodes, and a single edge from each node to one node from the next layer. The output is the node reached by following k edges from the starting node. In a conservative protocol, the ith player can see only the node reached by following the first i–1 edges and the edges on the jth layer for each j > i. This is a restriction of the general model where the ith player sees edges of all layers except for the ith one. In a one-way protocol, each player communicates only once in a prescribed order: first Player 1 writes a message on the blackboard, then Player 2, etc., until the last player gives the answer. The cost is the total number of bits written on the blackboard.¶Our main results are the following bounds on k-party conservative one-way communication complexity of pointer jumping with k layers:¶ (1) A lower bound of order \(\Omega(n/k^2)\) for any \(k = O(n^{1/3-\varepsilon})\).¶(2) Matching upper and lower bounds of order \(\Theta(n\,{\rm log}^{(k-1)}n)\) for \(k\,{\rm\le\,log^\ast}\,n\).

We consider depth-3 unbounded fanin threshold circuits. Gates are usual threshold functions T k n which compute 1 iff at least k of the inputs are equal to 1; the minimum min k , n − k + 1 is the threshold value of this gate. We show that the function T k n cannot be computed by a small depth-3 threshold circuit with threshold values of its gates much smaller than k .

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\(2^{0.618...\sqrt n } (or 2^{0.849...\sqrt n } \), respectively). This is the first simple proof of a strong lower bound by a top-down argument for non-monotone circuits.

Motivated by its relation to the length of cutting plane proofs for the Maximum Biclique problem, we consider the following communication game on a given graph G, known to both players. Let K be the maximal number of vertices in a complete bipartite subgraph of G, which is not necessarily an induced subgraph if G is not bipartite. Alice gets a set A of vertices, and Bob gets a disjoint set B of vertices such that |A|+|B|>K. The goal is to find a nonedge of G between A and B. We show that O(\log n) bits of communication are enough for every n-vertex graph., 10 pages. Theorem 1 in the previous version holds only for bipartite graphs, the non-bipartite case remains open. I now separate the bipartite and non-bipartite cases (by switching from independent sets to cliques, hence a new title). Some new open problems as well as references are added

We have already seen that communication complexity of relations captures the depth of circuits. Protocols in this case are trying to solve search problems. In this chapter we consider the communication complexity of decision problems.

The communication complexity of boolean functions is an information theoretic measure of their complexity. Besides its own importance, this measure is closely related to the computational complexity of functions: it corresponds to the smallest depth of circuits computing them. Thus, this measure can be used to prove circuit lower bounds. Communication complexity is appealing not only for its elegance and relation to circuit complexity, but also because its study involves the application of diverse tools from algebra, combinatorics and other fields of mathematics.

We show that the characteristic functions of linear codes are exponentially hard for the model of oblivious read-once branching programs with parity accepting mode, known also as Parity OBDDs. The proof is extremely simple, and employs a particular combinatorial property of linear codes—their universality.

We introduce the model of conservative one-way multiparty complexity and prove lower and upper bounds on the complexity of pointer jumping.

By the complexity of a graph we mean the minimum number of union and intersection operations needed to obtain the whole set of its edges starting from stars. This measure of graphs is related to the circuit complexity of boolean functions.We prove some lower bounds on the complexity of explicitly given graphs. This yields some new lower bounds for boolean functions, as well as new proofs of some known lower bounds in the graph-theoretic framework. We also formulate several combinatorial problems whose solution would have intriguing consequences in computational complexity.

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.