Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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