2015 | OriginalPaper | Buchkapitel
A Nonuniform Circuit Class with Multilayer of Threshold Gates Having Super Quasi Polynomial Size Lower Bounds Against NEXP
verfasst von : Kazuyuki Amano, Atsushi Saito
Erschienen in: Language and Automata Theory and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Recently, Williams [STOC ’14] proved a separation between
$$\mathsf {NEXP}$$
and
$$\mathsf {ACC}\circ \mathsf {THR}$$
, where an
$$\mathsf {ACC}\circ \mathsf {THR}$$
circuit has a single layer of threshold gates at the bottom and an
$$\mathsf {ACC}$$
circuit at the top. Two main ideas of his strategy are a closure property of circuit class and an algorithm for counting satisfying assignments of circuits.
In this paper, we show that this general scheme based on these two ideas can be applied for a certain class of circuits with
multi layer
of threshold gates. The circuit class we give has the symmetric gate at the top and poly-log layers of threshold gates to which an extra condition on the
dependency
is imposed. Two gates in a circuit are dependent, if the output of the one is always greater than or equal to the other one. An independent gate set is a set of gates in which two arbitrary gates are
$$not$$
dependent. We show that, if the size of a maximum independent gate set of each layer of threshold gates is at most
$$n^{\gamma }$$
for sufficiently small
$$\gamma >0$$
, then two key ingredients needed to apply his strategy can be established. Namely, (i) we can efficiently find a circuit in our class being equivalent to the AND of two input circuits in our class, and (ii) we can construct a faster than brute-force algorithm for counting satisfying assignments for this class by introducing a partial order to represent the dependency of gates. As a result, we give super quasi-polynomial size lower bounds for our class against
$$\mathsf {NEXP}$$
.