| Title | : | Comparator Circuits over Finite Bounded Posets |
| Speaker | : | Balagopal Komarath (IITM) |
| Details | : | Tue, 23 Jun, 2015 3:00 PM @ BSB 361 |
| Abstract: | : | Comparator circuit model was originally introduced by Mayr and
Subramanian (1992) (and further studied by Cook, Filmus and Le (2012))
to capture problems which are not known to be P-complete but still not
known to admit efficient parallel algorithms. The class CC is the
complexity class of problems many-one logspace reducible to the
Comparator Circuit Value Problem and we know that NL is contained in
CC which is inturn contained in P. Cook, Filmus and Le (2012) showed
that CC is also the class of languages decided by polynomial size
comparator circuits.
We study generalizations of the comparator circuit model that work over fixed finite bounded posets. We observe that there are universal comparator circuits even over arbitrary fixed finite bounded posets. Building on this, we show that general (resp. skew) comparator circuits of polynomial size over fixed finite distributive lattices characterizes CC (resp. L). Complementing this, we show that general comparator circuits of polynomial size over arbitrary fixed finite lattices exactly characterizes P and that when the comparator circuit is skew they characterize NL. In addition, we show a characterization of the class NP by a family of polynomial sized comparator circuits over fixed {em finite bounded posets}. These results generalize the results by Cook, Filmus and Le (2012) regarding the power of comparator circuits. As an aside, we consider generalizations of Boolean formulae over arbitrary lattices. We show that Spira's theorem (1971) can be extended to this setting as well and show that polynomial sized Boolean formulae over finite fixed lattices capture exactly NC^1. Our results indicate potential new approaches towards solving the problems P vs CC and NL vs L using lattice theoretic methods. |
