Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > POLYNOMIAL THRESHOLD FUNCTIONS:
Reports tagged with Polynomial threshold functions:
TR12-056 | 1st May 2012
Rocco Servedio, Li-Yang Tan, Justin Thaler

#### Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions

Revisions: 1

We study the challenging problem of learning decision lists attribute-efficiently, giving both positive and negative results.

Our main positive result is a new tradeoff between the running time and mistake bound for learning length-$k$ decision lists over $n$ Boolean variables. When the allowed running time is relatively high, our new ... more >>>

TR13-021 | 5th February 2013

#### Polynomial threshold functions and Boolean threshold circuits

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 ... more >>>

TR13-171 | 1st December 2013
Anindya De, Ilias Diakonikolas, Rocco Servedio

#### Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions

Let $g: \{-1,1\}^k \to \{-1,1\}$ be any Boolean function and $q_1,\dots,q_k$ be any degree-2 polynomials over $\{-1,1\}^n.$ We give a \emph{deterministic} algorithm which, given as input explicit descriptions of $g,q_1,\dots,q_k$ and an accuracy parameter $\eps>0$, approximates $\Pr_{x \sim \{-1,1\}^n}[g(\sign(q_1(x)),\dots,\sign(q_k(x)))=1]$
to within an additive $\pm \eps$. For any constant ... more >>>

TR13-172 | 1st December 2013
Anindya De, Ilias Diakonikolas, Rocco Servedio

#### Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions

We give a {\em deterministic} algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-$2$ polynomial threshold function. Given a degree-2 input polynomial $p(x_1,\dots,x_n)$ and a parameter $\eps > 0$, the algorithm approximates
$\Pr_{x \sim \{-1,1\}^n}[p(x) \geq 0]$
to within an additive $\pm \eps$ in ... more >>>

TR13-173 | 28th November 2013
Anindya De, Rocco Servedio

#### Efficient deterministic approximate counting for low degree polynomial threshold functions

We give a deterministic algorithm for
approximately counting satisfying assignments of a degree-$d$ polynomial threshold function
(PTF).
Given a degree-$d$ input polynomial $p(x_1,\dots,x_n)$ over $\mathbb{R}^n$
and a parameter $\epsilon > 0$, our algorithm approximates
$\mathbf{P}_{x \sim \{-1,1\}^n}[p(x) \geq 0]$
to within an additive $\pm \epsilon$ in time $O_{d,\epsilon}(1)\cdot ... more >>> TR14-009 | 21st January 2014 Alexander A. Sherstov #### Breaking the Minsky-Papert Barrier for Constant-Depth Circuits The threshold degree of a Boolean function$f$is the minimum degree of a real polynomial$p$that represents$f$in sign:$f(x)\equiv\mathrm{sgn}\; p(x)$. In a seminal 1969 monograph, Minsky and Papert constructed a polynomial-size constant-depth$\{\wedge,\vee\}$-circuit in$n$variables with threshold degree$\Omega(n^{1/3}).$This bound underlies ... more >>> TR15-147 | 8th September 2015 Alexander A. Sherstov #### The Power of Asymmetry in Constant-Depth Circuits The threshold degree of a Boolean function$f$is the minimum degree of a real polynomial$p$that represents$f$in sign:$f(x)\equiv\mathrm{sgn}\; p(x)$. Introduced in the seminal work of Minsky and Papert (1969), this notion is central to some of the strongest algorithmic and complexity-theoretic results for more >>> 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 >>> TR17-115 | 5th July 2017 Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket #### Hardness of learning noisy halfspaces using polynomial thresholds We prove the hardness of weakly learning halfspaces in the presence of adversarial noise using polynomial threshold functions (PTFs). In particular, we prove that for any constants$d \in \mathbb{Z}^+$and$\epsilon > 0$, it is NP-hard to decide: given a set of$\{-1,1\}$-labeled points in$\mathbb{R}^n\$ whether (YES Case) ... more >>>

ISSN 1433-8092 | Imprint