We study the discrepancy of the following communication problem. Alice receives a halfplane, and Bob receives a point in the plane, and their goal is to determine whether Bob’s point belongs to Alice’s halfplane. This communication task corresponds to determining whether x₁y₁+y₂ ≥ x₂, where the first player knows (x₁,x₂) and the second player knows (y₁,y₂). Denoting n = m³, we show that when the inputs are chosen from [m] × [m²], the communication discrepancy of the above problem is O(n^{-1/6} log^{3/2} n). On the other hand, through the connections to the notion of hereditary discrepancy by Matoušek, Nikolov, and Tawler (IMRN 2020) and a classical result of Matoušek (Discrete Comput. Geom. 1995), we show that the communication discrepancy of every set of n points and n halfplanes is at least Ω(n^{-1/4} log^{-1} n).

In an influential paper, Linial and Shraibman (STOC '07) introduced the factorization norm as a powerful tool for proving lower bounds against randomized and quantum communication complexities. They showed that the logarithm of the approximate γ₂-factorization norm is a lower bound for these parameters and asked whether a stronger lower bound that replaces approximate γ₂ norm with the γ₂ norm holds. We answer the question of Linial and Shraibman in the negative by exhibiting a 2ⁿ×2ⁿ Boolean matrix with γ₂ norm 2^Ω(n) and randomized communication complexity O(log n). As a corollary, we recover the recent result of Chattopadhyay, Lovett, and Vinyals (CCC '19) that deterministic protocols with access to an Equality oracle are exponentially weaker than (one-sided error) randomized protocols. In fact, as a stronger consequence, our result implies an exponential separation between the power of unambiguous nondeterministic protocols with access to Equality oracle and (one-sided error) randomized protocols, which answers a question of Pitassi, Shirley, and Shraibman (ITSC '23). Our result also implies a conjecture of Sherif (Ph.D. thesis) that the γ₂ norm of the Integer Inner Product function (IIP) in dimension 3 or higher is exponential in its input size.

In a recent article, Alon, Hanneke, Holzman, and Moran (FOCS '21) introduced a unifying framework to study the learnability of classes of partial concepts. One of the central questions studied in their work is whether the learnability of a partial concept class is always inherited from the learnability of some "extension" of it to a total concept class. They showed this is not the case for PAC learning but left the problem open for the stronger notion of online learnability. We resolve this problem by constructing a class of partial concepts that is online learnable, but no extension of it to a class of total concepts is online learnable (or even PAC learnable).