Based on the recent breakthrough of Huang (2019), we show that for any total Boolean
function f, deg (f)= O (adeg (f)^ 2): The degree of f is at most quadratic in the approximate …

For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we
show that a gadget-composed version of F is hard to refute in any proof system whose lines …

The purpose of this article is to initiate a systematic study of dimension-free relations
between basic communication and query complexity measures and various matrix norms. In …

We obtain the first true size-space trade-offs for the cutting planes proof system, where the
upper bounds hold for size and total space for derivations with constantsize coefficients, and …

Given an m× n binary matrix M with| M|= p· mn (where| M| denotes the number of 1 entries),
define the discrepancy of M as disc (M)= max X⊂[m], Y⊂[n]|| M [X× Y]|-p| X|·| Y||. Using …

In this paper we study the problem of multiclass classification with a bounded number of
different labels $ k $, in the realizable setting. We extend the traditional PAC model to a) …

The log-rank conjecture states that the communication complexity of a boolean matrix A is
bounded by a polynomial in the log of the rank of A. Equivalently, it says that the chromatic …

We survey lower-bound results in complexity theory that have been obtained via newfound
interconnections between propositional proof complexity, boolean circuit complexity, and …

Let f:{0, 1} n→{0, 1} be a boolean function, and let f∧(x, y)= f (x∧ y) denote the AND-function
of f, where x∧ y denotes bit-wise AND. We study the deterministic communication …

We exhibit an unambiguous-DNF (disjunctive normal form) formula that requires conjunctive
normal form width, which is optimal up to logarithmic factors. As a consequence, we get a …