Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > POLYNOMIAL REPRESENTATIONS OF BOOLEAN FUNCTIONS:
Reports tagged with polynomial representations of Boolean functions:
TR09-098 | 9th October 2009
Alexander A. Sherstov

#### The intersection of two halfspaces has high threshold degree

Revisions: 1

The threshold degree of a Boolean function
$f\colon\{0,1\}\to\{-1,+1\}$ is the least degree of a real
polynomial $p$ such $f(x)\equiv\mathrm{sgn}\; p(x).$ We
construct two halfspaces on $\{0,1\}^n$ whose intersection has
threshold degree $\Theta(\sqrt n),$ an exponential improvement on
previous lower bounds. This solves an open problem due to Klivans
(2002) and ... more >>>

TR10-025 | 24th February 2010
Alexander A. Sherstov

#### Optimal bounds for sign-representing the intersection of two halfspaces by polynomials

The threshold degree of a function
$f\colon\{0,1\}^n\to\{-1,+1\}$ is the least degree of a
real polynomial $p$ with $f(x)\equiv\mathrm{sgn}\; p(x).$ We
prove that the intersection of two halfspaces on
$\{0,1\}^n$ has threshold degree $\Omega(n),$ which
matches the trivial upper bound and completely answers
a question due to Klivans (2002). The best ... 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 >>>

TR18-207 | 5th December 2018
Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan

#### On the Probabilistic Degree of OR over the Reals

We study the probabilistic degree over reals of the OR function on $n$ variables. For an error parameter $\epsilon$ in (0,1/3), the $\epsilon$-error probabilistic degree of any Boolean function $f$ over reals is the smallest non-negative integer $d$ such that the following holds: there exists a distribution $D$ of polynomials ... more >>>

TR19-013 | 31st January 2019
Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami

#### CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo $M$, for various choices of the modulus $M$. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2SAT, HornSAT, ... more >>>

ISSN 1433-8092 | Imprint