RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
Forthcoming seminars
Seminar calendar
List of seminars
Archive by years
Register a seminar

Search
RSS
Forthcoming seminars





You may need the following programs to see the files








Kolmogorov seminar on computational complexity and descriptive complexity
April 1, 2013 16:45–18:25, Moscow
 


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

V. V. Podolskii

Number of views:
This page:117

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/

SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Contact us:
 Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020