Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: circuit complexity

Sortuj według:

Ogranicz wyniki do:

On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models

Ghosal Purnata, Raghavendra Rao B. V.

Fundamenta Informaticae

2020

Vol. 177, nr 1

69--93

We consider the problem of obtaining parameterized lower bounds for the size of arithmetic circuits computing polynomials with the degree of the polynomial as the parameter. We consider the following special classes of multilinear algebraic branching programs: 1) Read Once Oblivious Branching Programs (ROABPs), 2) Strict interval branching programs, 3) Sum of read once formulas with restricted ordering. We obtain parameterized lower bounds (i.e., nΩ(t(k)) lower bound for some function t of k ) on the size of the above models computing a multilinear polynomial that can be computed by a depth four circuit of size g (k)n0(1) for some computable function g. Further, we obtain a parameterized separation between ROABPs and read-2 ABPs. This is obtained by constructing a degree k polynomial that can be computed by a read-2 ABP of small size such that the rank of the partial derivative matrix under any partition of the variables is large.

A Note on a priori Estimations of Classification Circuit Complexity

Albrecht A.A., Chashkin A.V., Iliopoulos C.S., Kasim-Zade O.M., Lappas G., Steinhöfel K.K.

Fundamenta Informaticae

2010

Vol. 104, nr 3

201-217

The paper aims at tight upper bounds on the size of pattern classification circuits that can be used for a priori parameter settings in a machine learning context. The upper bounds relate the circuit size S(C) to n_L := .log_2mL., where mL is the number of training samples. In particular, we show that there exist unbounded fan-in threshold circuits with less than (a) [formula] gates for unbounded depth, (b) SL [formula] gates for small bounded depth, where in both cases all mL samples are classified correctly. We note that the upper bounds do not depend on the length n of input (sample) vectors. Since n_L << n in real-world problem settings, the upper bounds return values that are suitable for practical applications. We provide experimental evidence that the circuit size estimations work well on a number of pattern classification tasks. As a result, we formulate the conjecture that [formula] gates are sufficient to achieve a high generalization rate of bounded-depth classification circuits.