RUS  ENG
Full version
SEMINARS



Threshold gates on the set $\{1,2\}$ and threshold circuits

V. V. Podolskii

Abstract: We study the complexity of computing Boolean functions on general Boolean domains by polynomial threshold functions (PTFs). A typical example of a general Boolean domain is $\{1,2\}^n$ . We are mainly interested in the length (the number of monomials) of PTFs, with their degree and weight being of secondary interest. We show that PTFs on general Boolean domains are tightly connected to depth two threshold circuits.
This is a joint work with Kristoffer Hansen, http://eccc.hpi-web.de/report/2013/021/


© Steklov Math. Inst. of RAS, 2024