Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PTF CIRCUITS:
Reports tagged with PTF circuits:
TR17-026 | 17th February 2017
Valentine Kabanets, Daniel Kane, Zhenjian Lu

#### A Polynomial Restriction Lemma with Applications

A polynomial threshold function (PTF) of degree $d$ is a boolean function of the form $f=\mathrm{sgn}(p)$, where $p$ is a degree-$d$ polynomial, and $\mathrm{sgn}$ is the sign function. The main result of the paper is an almost optimal bound on the probability that a random restriction of a PTF is ... more >>>

TR18-162 | 16th September 2018
Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan

#### A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates

We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit $C$ made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to $C$ in significantly better than ... more >>>

ISSN 1433-8092 | Imprint