Satisfiability and Derandomization for Small Polynomial Threshold Circuits

Valentine Kabanets and Zhenjian Lu


Abstract

A polynomial threshold function (PTF) is defined as the sign of a polynomial $p\colon\{0,1\}^n\to\mathbb{R}$. A PTF circuit is a Boolean circuit whose gates are PTFs. We study the problems of exact and (promise) approximate counting for PTF circuits of constant depth.


Versions