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 …

We show a power 2.5 separation between bounded-error randomized and quantum query
complexity for a total Boolean function, refuting the widely believed conjecture that the best …

For any n-bit boolean function f, we show that the randomized communication complexity of
the composed function fog n, where g is an index gadget, is characterized by the …

We prove that any two-pass graph streaming algorithm for the st reachability problem in n-
vertex directed graphs requires near-quadratic space of n 2-o (1) bits. As a corollary, we also …

For a constant ϵ, we prove a (N) lower bound on the (randomized) communication
complexity of ϵ-Nash equilibrium in two-player N x N games. For n-player binary-action …

We construct a simple and total Boolean function F= f○ XOR on 2 n variables that has only
O (√ n) spectral norm, O (n 2) approximate rank, and O (n 2.5) approximate nonnegative …

We study algorithms for solving three problems on strings. These are sorting of n strings of
length k,“the Most Frequent String Search Problem”, and “searching intersection of two …

We show that deterministic communication complexity can be superlogarithmic in the
partition number of the associated communication matrix. We also obtain near-optimal …

Lifting theorems are theorems that relate the query complexity of a function f:{0,1\}^n→{0,1\}
to the communication complexity of the composed function f∘g^n for some “gadget” …

Abstract Recently, Rubinstein, Schramm, and Weinberg [ITCS'18] gave an algorithm for
finding an exact global minimum cut of undirected graphs in the cut-query model in which …