Shiva Chaudhuri, Jaikumar Radhakrishnan

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

Albert Atserias, Nicola Galesi, Ricard GavaldÃ

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

Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang

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