Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > THRESHOLD FUNCTIONS:
Reports tagged with Threshold Functions:
TR96-004 | 18th January 1996
Shiva Chaudhuri, Jaikumar Radhakrishnan

#### Deterministic Restrictions in Circuit Complexity

We study the complexity of computing Boolean functions using AND, OR
and NOT gates. We show that a circuit of depth $d$ with $S$ gates can
be made to output a constant by setting $O(S^{1-\epsilon(d)})$ (where
$\epsilon(d) = 4^{-d}$) of its input values. This implies a
superlinear size lower bound ... more >>>

TR00-008 | 20th January 2000
Albert Atserias, Nicola Galesi, Ricard Gavaldà

#### Monotone Proofs of the Pigeon Hole Principle

We study the complexity of proving the Pigeon Hole
Principle (PHP) in a monotone variant of the Gentzen Calculus, also
known as Geometric Logic. We show that the standard encoding
of the PHP as a monotone sequent admits quasipolynomial-size proofs
in this system. This result is a consequence of ... more >>>

TR17-085 | 4th May 2017
Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang

#### Active classification with comparison queries

We study an extension of active learning in which the learning algorithm may ask the annotator to compare the distances of two examples from the boundary of their label-class. For example, in a recommendation system application (say for restaurants), the annotator may be asked whether she liked or disliked a ... more >>>

ISSN 1433-8092 | Imprint