The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design and even in cybersecurity. We show that a DeMorgan circuit, that is, a Boolean AND, OR, NOT circuit with negations applied to only input variables, is hazard-free iff the circuit produces (purely syntactically) all prime implicants as well as all prime implicates of the Boolean function it computes. This extends to arbitrary DeMorgan circuits a classical result of Eichelberger [ IBM J. Res. Develop., 9 (1965), pp. 90--99] showing this property for circuits producing no terms containing a variable together with its negation. Via an amazingly simple proof, we also strengthen a recent result of Ikenmeyer et al. [ J. ACM, 66 (2019), 25]: not only do the complexities of hazard-free and monotone circuits for monotone Boolean functions coincide, but every minimal hazard-free circuit for a monotone Boolean function must be monotone. We also observe that hazard-free implementations of already very simple Boolean functions require a superpolynomial increase of circuit size and depth, such as, for example, the Boolean function which accepts a Boolean square matrix iff every row and every column has exactly one $1$. Finally, we show that the order of growth of the Shannon function of hazard-free circuits is the same as that of unrestricted circuits.

We prove the first, even superpolynomial, lower bounds on the size of tropical (min,+) and (max,+) circuits approximating given optimization problems. Many classical dynamic programming (DP) algorithms for optimization problems are pure in that they only use the basic $\min$, $\max$, $+$ operations in their recursion equations. Tropical circuits constitute a rigorous mathematical model for this class of algorithms. An algorithmic consequence of our lower bounds for tropical circuits is that the approximation powers of pure DP algorithms and greedy algorithms are incomparable. That pure DP algorithms can hardly beat greedy in approximation is long known. New in this consequence is that the converse also holds.

We consider Boolean circuits over {or, and, neg} with negations applied only to input variables. To measure the "amount of negation" in such circuits, we introduce the concept of their "negation width". In particular, a circuit computing a monotone Boolean function f(x_1,...,x_n) has negation width w if no nonzero term produced (purely syntactically) by the circuit contains more than w distinct negated variables. Circuits of negation width w=0 are equivalent to monotone Boolean circuits, while those of negation width w=n have no restrictions. Our motivation is that already circuits of moderate negation width w=n^{epsilon} for an arbitrarily small constant epsilon>0 can be even exponentially stronger than monotone circuits. We show that the size of any circuit of negation width w computing f is roughly at least the minimum size of a monotone circuit computing f divided by K=min{w^m,m^w}, where m is the maximum length of a prime implicant of f. We also show that the depth of any circuit of negation width w computing f is roughly at least the minimum depth of a monotone circuit computing f minus log K. Finally, we show that formulas of bounded negation width can be balanced to achieve a logarithmic (in their size) depth without increasing their negation width.

Many dynamic programming algorithms for discrete 0-1 optimization problems are just special (recursively constructed) tropical (min,+) or (max,+) circuits. A problem is homogeneous if all its feasible solutions have the same number of ones. Jerrum and Snir [J ACM 29 (1982), pp. 874--897] proved that tropical circuit complexity of homogeneous problems coincides with the monotone arithmetic circuit complexity of the corresponding polynomials. So, lower bounds on the monotone arithmetic circuit complexity of these polynomials yield lower bounds on the tropical complexity of the corresponding optimization problems. But the situation with nonhomogeneous problems is entirely different: here the gap between their tropical and arithmetic complexities can be even exponential. In this paper, we improve two classical lower bounds for monotone arithmetic circuits---Schnorr's bound and Hyafil--Valiant's bound---and use these improvements to derive general lower bounds for the tropical circuit complexity of nonhomogeneous optimization problems. In particular, we show that optimization problems, whose sets of feasible solutions are cover free, have large tropical complexity.

We consider the size of monotone circuits for quadratic Boolean functions, that is, disjunctions of length-2 monomials. Our motivation is that a good (linear in the number of variables) lower bound on the monotone circuit size for a certain type of quadratic function would imply a good (even exponential) lower bound on the general nonmonotone circuit size. To get more insight into the structure of monotone circuits for quadratic functions, we consider the so-called single level conjecture posed explicitly in the early 1990s. The conjecture claims that monotone single level circuits, that is, circuits which have only one level of AND gates, for quadratic functions are not much larger than arbitrary monotone circuits. In this paper we disprove the conjecture as follows: there exist quadratic functions whose monotone circuits have linear size but whose monotone single level circuits require almost quadratic size.

Our main result is a combinatorial lower bounds criterion for monotone circuits over the reals. We allow any unbounded fanin non-decreasing real-valued functions as gates. The only requirement is their "locality". Unbounded fanin AND and OR gates, as well as any threshold gate T/sub s//sup m/(x/sub 1/,...,x/sub m/) with small enough threshold value min{s,m-s+1}, are simplest examples of local gates. The proof is relatively simple and direct, and combines the bottlenecks counting approach of Haken with the idea of finite limit due to Sipser. Apparently this is the first combinatorial lower bounds criterion for monotone computations. It is symmetric and yields (in a uniform and easy way) exponential lower bounds.

We present a top-down lower bound method for depth 3 AND-OR-NOT circuits which is simpler than the previous methods and in some cases gives better lower bounds. In particular we prove that depth 3 AND-OR-NOT circuits that compute PARITY resp. MAJORITY require size at least 2/sup 0.618/ .../spl radic/n/ resp. 2/sup 0.849/.../spl radic/n/. This is the first simple proof of a strong lower bound by a top-down argument for non-monotone circuits.>