Seminars
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
Calendar
Search
Add a seminar

RSS
Forthcoming seminars




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:238

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/
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024