|
|
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/
|
|