Alladi Ramakrishnan Hall

Lower Bounds for Natural Algorithms

Balagopal Komarath

Saarland University, Germany

In this talk, we will look at a project that
explores the power and limitations of some "natural"
algorithms, called Hazard-free complexity.


A hazard-free circuit is a Boolean circuit that is
guaranteed to work reliably even in the presence of
unstable values. A special value u is used to denote all
unstable values. For example, a hazard-free circuit for the
three input majority function should output 1 when 1, 1, u
is given as input because the output is 1 irrespective of
whether the unstable value is actually a 0 or a 1. Huffman
(1957) showed that all Boolean functions have hazard-free
circuits of size O(n.3^n) and asked whether an exponential
blow-up in size is necessary for Boolean functions that
have polynomial size circuits. Clearly, this computational
model is "natural" due to real-world constraints.

We (IKLLMS 2019) show that there are Boolean functions that
have polynomial size circuits (small complexity) but no
polynomial size hazard-free circuits (large hazard-free
complexity). We show that hazard-free complexity of Boolean
functions is a generalization of monotone complexity. i.e.,
both measures coincide for monotone functions and
hazard-free complexity is defined for all functions. This
allows us to use monotone complexity lower bounds to prove
hazard-free complexity lower bounds for non-monotone
functions as well.

We also show that:

(a) There are efficient constructions for hazard-free
circuits when the number of unstable values in the input
is small.

(b) Detecting hazards requires almost 3^n time assuming
the strong exponential time hypothesis, even when the
inputs are depth four formulas (KS 2020, unpublished).

(c) Detecting hazards in depth two formulas is easy (KS
2020, unpublished).