Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Lower Bounds for Linear Decision Trees with Bounded Weights
verfasst von : Kei Uchizawa, Eiji Takimoto
Erschienen in: SOFSEM 2015: Theory and Practice of Computer Science
Verlag: Springer Berlin Heidelberg
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
In this paper, we consider a linear decision tree such that a linear threshold function at each internal node has a bounded weight: the sum of the absolute values of its integer weights is at most
w
. We prove that if a Boolean function
f
is computable by such a linear decision tree of size (i.e., the number of leaves)
s
and rank
r
, then
f
is also computable by a depth-2 threshold circuit containing at most
s
(2
w
+ 1)
r
threshold gates with weight at most (2
w
+ 1)
r
+ 1
in the bottom level. Combining a known lower bound on the size of depth-2 threshold circuits, we obtain a 2
Ω(
n
/log
w
)
lower bound on the size of linear decision trees computing the Inner-Product function modulo 2, which improves on the previous bound
$2^{\sqrt{n}}$
if
$w=2^{o(\sqrt{n})}$
.