The log-rank conjecture is a longstanding open problem with multiple equivalent formulations in complexity theory and mathematics. In its linear-algebraic form, it asserts that the rank and partitioning number of a Boolean matrix are quasi-polynomially related. We propose a relaxed but still equivalent version of the conjecture based on a new matrix parameter, signed rectangle rank: the minimum number of all-1 rectangles needed to express the Boolean matrix as a $\pm 1$-sum. Signed rectangle rank lies between rank and partition number, and our main result shows that it is in fact equivalent to rank up to a logarithmic factor. Additionally, we extend the main result to tensors. This reframes the log-rank conjecture as: can every signed decomposition of a Boolean matrix be made positive with only quasi-polynomial blowup? As an application, we prove an equivalence between the log-rank conjecture and a conjecture of Lovett and Singer-Sudan on cross-intersecting set systems.

We prove that Boolean matrices with bounded $\gamma_{2}$-norm or bounded normalized trace norm must contain a linear-sized all-ones or all-zeros submatrix, verifying a conjecture of Hambardzumyan, Hatami, and Hatami. We also present further structural results about Boolean matrices of bounded $\gamma_{2}$-norm and discuss applications in communication complexity, operator theory, spectral graph theory, and extremal combinatorics. As a key application, we establish an inverse theorem for MaxCut. A celebrated result of Edwards states that every graph G with m edges has a cut of size at least $\frac{m}{2}+\frac{\sqrt{8 m+1}-1}{8}$, with equality achieved by complete graphs with an odd number of vertices. To contrast this, we prove that if the MaxCut of G is at most $\frac{m}{2}+O(\sqrt{m})$, then G must contain a clique of size $\Omega(\sqrt{m})$.

We prove that the class of communication problems with public-coin randomized constant-cost protocols, called BPP0, does not contain a complete problem. In other words, there is no randomized constant-cost problem Q ∈ BPP0, such that all other problems P ∈ BPP0 can be computed by a constant-cost deterministic protocol with access to an oracle for Q. We also show that the k-Hamming Distance problems form an infinite hierarchy within BPP0. Previously, it was known only that Equality is not complete for BPP0. We introduce a new technique, using Ramsey theory, that can prove lower bounds against arbitrary oracles in BPP0, and more generally, we show that k-Hamming Distance matrices cannot be expressed as a Boolean combination of any constant number of matrices which forbid large Greater-Than subproblems.

The seminal result of Kahn, Kalai and Linial shows that a coalition of O(n/(log n)) players can bias the outcome of any Boolean function {0,1}^n -> {0,1} with respect to the uniform measure. We extend their result to arbitrary product measures on {0,1}^n, by combining their argument with a completely different argument that handles very biased input bits. We view this result as a step towards proving a conjecture of Friedgut, which states that Boolean functions on the continuous cube [0,1]^n (or, equivalently, on {1,...,n}^n) can be biased using coalitions of o(n) players. This is the first step taken in this direction since Friedgut proposed the conjecture in 2004. Russell, Saks and Zuckerman extended the result of Kahn, Kalai and Linial to multi-round protocols, showing that when the number of rounds is o(log^* n), a coalition of o(n) players can bias the outcome with respect to the uniform measure. We extend this result as well to arbitrary product measures on {0,1}^n. The argument of Russell et al. relies on the fact that a coalition of o(n) players can boost the expectation of any Boolean function from epsilon to 1-epsilon with respect to the uniform measure. This fails for general product distributions, as the example of the AND function with respect to mu_{1-1/n} shows. Instead, we use a novel boosting argument alongside a generalization of our first result to arbitrary finite ranges.