#### 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).

Done