Thursday, February 6 2020
14:00 - 15:00

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

Download as iCalendar