Schedule for: 22w5124 - Communication Complexity and Applications, III

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

The approximate degree of a Boolean function f:{0,1}^n -> {0,1} is the minimum degree of a real polynomial p that approximates f pointwise: |f(x)-p(x)| <= 1/3 for all x. For any delta>0, we construct DNF and CNF formulas of polynomial size with approximate degree Omega(n^{1-delta}), essentially matching the trivial upper bound of n. This fully resolves the approximate degree of constant-depth circuits (AC^0), a question that has seen extensive research over the past 10 years. Prior to our work, an Omega(n^{1-delta}) lower bound was known only for AC^0 circuits of depth that grows with 1/delta (Bun and Thaler, FOCS 2017). Furthermore, the DNF and CNF formulas that we construct are the simplest possible in that they have constant width. Our result gives the first near-linear lower bounds on the bounded-error communication complexity of polynomial-size DNF and CNF formulas in the challenging k-party number-on-the-forehead model and two-party quantum model: Omega(n/(4^k k^2))^{1-delta} and Omega(n^{1-delta}), respectively, where delta>0 is any constant. Our lower bounds are essentially optimal. Analogous to above, such lower bounds were previously known only for AC^0 circuits of depth that grows with 1/delta.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet in the PDC front desk for a guided tour of The Banff Centre campus.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

We provide the first separation in the approximation guarantee achievable by truthful and non-truthful algorithms for combinatorial auctions with polynomial communication. Specifically, we prove that any truthful mechanism guaranteeing a $(3/4-1/480)$-approximation for two buyers with XOS valuations over $m$ items requires $\exp(\Omega(m))$ communication, whereas a non-truthful algorithm by Dobzinski and Schapira [SODA 2006] and Feige [SICOMP 2009] is already known to achieve a $3/4$-approximation in $\poly(m)$ communication. We obtain our separation by proving that any {simultaneous} protocol ({not} necessarily truthful) which guarantees a $(3/4-1/480)$-approximation requires communication $\exp(\Omega(m))$. The taxation complexity framework of Dobzinski [FOCS 2016] extends this lower bound to all truthful mechanisms (including interactive truthful mechanisms).

The sign-rank of a sign matrix is the smallest rank of a real matrix with the same sign pattern. This fundamental notion arises naturally in areas as diverse as learning theory, discrete geometry and geometric graphs, communication complexity, circuit complexity, and the theory of Banach spaces. There are only three known methods for proving lower bounds on the sign-rank of explicit matrices: (i) Sign-rank is at least the VC-dimension; (ii) Forster's method, which states that sign-rank is at least the inverse of the largest possible average margin among the representations of the matrix by points and half-spaces; (iii) Sign-rank is at least a logarithmic function of the density of the largest monochromatic rectangle. We prove several results regarding the limitations of these methods. For example, we show that there exist matrices with polynomially large sign-rank for which none of these methods can provide a super-constant lower bound. We explore connections to other complexity measure and analytic parameters and in particular highlight a connection to some deep results in harmonic analysis. Finally, we propose numerous open problems, conjectures, and future research directions. The talk is based on several joint works with Tsun-Ming Cheung, Lianna Hambardzumyan, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao, Itai Zilberstein.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

In this talk we will describe some of our recent work giving new upper and lower bounds on the approximability of constraint satisfaction problems (CSPs) in the streaming and sketching settings. (Streaming algorithms process the input with small space, while sketching algorithms are restricted streaming algorithms that have additional composability requirements.) When the sketching algorithms are constrained to sub-polynomial space in the input length we get a fine dichotomy: CSP approximation problems on n variables are either solvable in polylogarithmic space or require at least sqrt(n) space. Our positive results show the broad applicability of what we call ``bias-based sketching algorithms'', and our negative results work by abstracting and significantly generalizing previous bounds for the Maximum Cut problem. We will also mention some partial extensions to streaming algorithms, linear space lower bounds, ordering CSPs. Based on joint works with Chi-Ning Chou, Sasha Golovnev, Noah Singer, Ameya Velingker and Santhoshini Velusamy.

In this talk, we show a strong XOR lemma for bounded-round two-player randomized communication. For a function f:X×Y→{0,1}, the n-fold XOR function f^⊕n:X^n×Y^n→{0,1} maps n input pairs (x_1,...,x_n), (y_1,...,y_n) to the XOR of the n output bits f(x_1,y_1)⊕...⊕f(x_n, y_n). We prove that if every r-round communication protocols that computes f with probability 2/3 uses at least C bits of communication, then any r-round protocol that computes f^⊕n with probability 1/2+exp(-O(n)) must use n(r^{-O(r)}C-1) bits. When r is a constant and C is sufficiently large, this is Omega(nC) bits. It matches the communication cost and the success probability of the trivial protocol that computes the n bits f(x_i,y_i) independently and outputs their XOR, up to a constant factor in n. A similar XOR lemma has been proved for f whose communication lower bound can be obtained via bounding the discrepancy [Shaltiel03]. By the equivalence between the discrepancy and the correlation with 2-bit communication protocols, our new XOR lemma implies the previous result.

In distributed certification, we would like to certify that a distributed network has some desired property, e.g., it is connected, or the network nodes' internal states encode a valid spanning tree of the network. To this end, we store a certificate at each node, and the nodes can then interact with one another in order to decide whether to accept or reject the certificates. Our goal is to minimize the length of the certificates, the number of rounds the nodes spend interacting with one another, and the amount of communication. (No computational restrictions are assumed for the nodes.) In this talk I will discuss some recent research directions in the area of distributed certification, and several problems that remain open.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

We introduce and study the StreamingCycles problem, a random order streaming version of the Boolean Hidden Hypermatching problem that has been instrumental in streaming lower bounds over the past decade. In this problem the edges of a graph $G$, comprising $n/\ell$ disjoint length-$\ell$ cycles on $n$ vertices, are partitioned randomly among $n$ players. Every edge is annotated with an independent uniformly random bit, and the players' task is to output, for some cycle in $G$, the sum (modulo $2$) of the bits on its edges, after one round of sequential communication Our main result is an $\ell^{\Omega(\ell)}$ lower bound on the communication complexity of StreamingCycles, which is tight up to constant factors in the exponent. Applications of our lower bound for StreamingCycles include an essentially tight lower bound for component collection in (almost) random order graph streams, making progress towards a conjecture of Peng and Sohler [SODA'18] and the first exponential space lower bounds for random walk generation.

In recent years, there has been an explosion in the development of so-called ``lifting theorems'' which have led to the resolution of many long-standing open problems. The basic idea of a lifting theorem is simple: in order to prove a lower bound in a ``complicated'' object that we do not understand (for example, deterministic communication protocols), we will ``escalate'' the hardness from a ``simple'' system that we do understand (for example, decision trees) by taking a hard function f for the simple system and composing it with a specially chosen ``gadget function''. In many cases, it is possible to prove that the ``best'' possible strategy is to simulate the proof of the uncomposed function in the simple system (and thus lower bounds for the uncomposed function are ``escalated'' or ``lifted'' to lower bounds for the composed formula). While lifting theorems in communication complexity can be traced back to the work of Raz and McKenzie [RM99], recent developments have pushed these techniques to many new areas, and have shown how lifting is a flexible tool that allows quite finely tuned tradeoffs between different complexity parameters for a wide variety of models. In this talk, we give a survey of recent developments connecting communication complexity, circuit complexity, and proof complexity, and in particular connections with the complexity of total search problems. We will highlight several recent developments in the area and indicate some future directions.

Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}^n to {-1,1} and G in {AND_2, XOR_2}, the bounded-error quantum communication complexity of the composed function f o G equals O(Q(f) log n), where Q(f) denotes the bounded-error quantum query complexity of f. This is in contrast with the classical setting, where it is easy to show that R^{cc}(f o G) < 2 R(f), where R^{cc} and R denote bounded-error communication and query complexity, respectively. Chakraborty et al. (CCC'20) exhibited a total function for which the log n overhead in the BCW simulation is required. We improve upon their result in several ways. We show that the log n overhead is not required when f is symmetric, generalizing a result of Aaronson and Ambainis for the Set-Disjointness function (Theory of Computing'05). This upper bound assumes a shared entangled state, though for most symmetric functions the assumed number of entangled qubits is less than the communication and hence could be part of the communication. To prove this, we design an efficient distributed version of noisy amplitude amplification that allows us to prove the result when f is the OR function. In view of our first result, one may ask whether the log n overhead in the BCW simulation can be avoided even when f is transitive. We give a strong negative answer by showing that the log n overhead is still necessary for some transitive functions even when we allow the quantum communication protocol an error probability that can be arbitrarily close to 1/2. We also give, among other things, a general recipe to construct functions for which the log n overhead is required in the BCW simulation in the bounded-error communication model, even if the parties are allowed to share an arbitrary prior entangled state for free.

Lifting theorems have played a key role in many recent breakthrough results in communication complexity. A typical lifting theorem translates the query complexity of a Boolean function f to the communication complexity of a function f o g obtained by composing f with an inner function g. Most lifting theorems work for any Boolean function f and depend upon the pseudo-random properties of the inner function g known as the gadget. The main parameter of efficiency in lifting theorems is the input size of the inner function g. Obtaining lifting theorems for constant-sized gadgets would give us breakthrough results and a nearly complete understanding of lifting phenomena; current techniques are far from achieving this goal. The main barrier is whether such “nice” pseudo-random properties exists for typically used gadgets when their input length is relatively small compared to the outer function f. A well-known gadget is the Index function. In recent work, Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, and Jiapeng Zhang improved the size of the index gadget in the deterministic query to communication lifting to almost linear by building on the recent breakthrough improvements in the sunflower lemma. They also stated a conjecture about pseudo-random properties of the Index gadget, which is essential in further improvements in gadget size using the existing techniques. In recent work (manuscript in preparation), we prove that the conjecture is false for the index gadget when the range of Alice’s inputs m is smaller than log n. We also show that for specific structured protocols solving f o Index (protocols where Bob is only allowed to communicate parities of his input), we can obtain deterministic query to communication lifting theorems with gadget size $O(1)$. Our results suggest that we need new tools and techniques if we have to improve the gadget size in the query to communication lifting beyond log n for Index gadget. But it leaves open the possibility of non-trivial improvements in the gadget size from linear to almost logarithmic using existing techniques. Joint work with Paul Beame

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

Online learning with expert advice is a fundamental problem of sequential prediction. In this problem, the algorithm has access to a set of n "experts" who make predictions on each day. The goal on each day is to process these predictions, and make a prediction with the minimum cost. After making a prediction, the algorithm sees the actual outcome on that day, updates its state, and then moves on to the next day. An algorithm is judged by how well it does compared to the best expert in the set. The classical algorithm for this problem is the multiplicative weights algorithm. Variations of this algorithm have been applied to and optimized for a broad range of problems, including boosting an ensemble of weak-learners in machine learning, and approximately solving linear and semi-definite programs. However, every application, to our knowledge, relies on storing weights for every expert, and uses Omega(n) memory. There is little work on understanding the memory required to solve the online learning with expert advice problem (or run standard sequential prediction algorithms, such as multiplicative weights) in natural streaming models, which is important when the number of experts, as well as the number of days on which the experts make predictions, is large. We initiate the study of the learning with expert advice problem in the streaming setting, and show lower and upper bounds. Our lower bound for i.i.d., random order, and adversarial order streams uses a novel masking technique and distributional detection communication game to show a smooth trade-off for regret versus memory. Our upper bounds in adversarial and random-order streams show ways to run standard sequential prediction algorithms in rounds on small "pools" of experts, thus reducing the necessary memory. For random-order streams, we show that our upper bound is tight up to low order terms. Joint work with Vaidehi Srinivas, Ziyu (Neil) Xu, and Samson Zhou

The 3SUM-Indexing problem was introduced as a data structure version of the 3SUM problem, with the goal of proving strong conditional lower bounds for static data structures via reductions. Ideally, the conjectured hardness of 3SUM-Indexing should be replaced by an unconditional lower bound. Unfortunately, we are far from proving this, with the strongest current lower bound being a logarithmic query time lower bound by Golovnev et al. from STOC'20. Moreover, their lower bound holds only for non-adaptive data structures and they explicitly asked for a lower bound for adaptive data structures. In this talk, we present precisely such a lower bound against adaptive data structures. Joint work with Eldon Chung.

Hambardzumyan, Hatami and Hatami defined blocky rank showed that it is connected to communication complexity and operator theory. We describe additional connections to circuit complexity and combinatorics, and we prove upper and lower bounds on blocky rank in various contexts. Joint ongoing project with Daniel Avraham.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

In the graph steaming model, the edges of a graph are presented one by one in an arbitrary order and the algorithms can make one or a limited number of sequential passes over this stream, while using a limited memory to process the graph. In this talk, we will survey the current landscape of multi-pass graph streaming lower bounds, including several recent advances and mention some fundamental problems that are still widely open in this area.

An infinite stream consists of iid samples from an unknown and arbitrary discrete distribution. You want to additively estimate the entropy of this distribution. But you are impatient and forgetful: how long do you need to observe the stream given that you only have a constant amount of memory? The talk presents a new upper bound improving upon previous work by Acharya et al. (NeurIPS 2019). This is joint work with Maryam Aliakbarpour, Jelani Nelson, and Erik Waingarten.

We give a direct product theorem for the entanglement-assisted interactive quantum communication complexity of an l-player predicate V. In particular we show that for a distribution p that is product across the input sets of the l players, the success probability of any entanglement-assisted quantum communication protocol for computing n copies of V, whose communication is o(log(eff∗(V,p))⋅n), goes down exponentially in n. Here eff∗(V,p) is a distributional version of the quantum efficiency or partition bound introduced by Laplante, Lerays and Roland (2014), which is a lower bound on the distributional quantum communication complexity of computing a single copy of V with respect to p. As an application of our result, we show that it is possible to do device-independent quantum key distribution (DIQKD) without the assumption that devices do not leak any information after inputs are provided to them. We analyze the DIQKD protocol given by Jain, Miller and Shi (2017), and show that when the protocol is carried out with devices that are compatible with n copies of the Magic Square game, it is possible to extract Ω(n) bits of key from it, even in the presence of O(n) bits of leakage. Our security proof is parallel, i.e., the honest parties can enter all their inputs into their devices at once, and works for a leakage model that is arbitrarily interactive, i.e., the devices of the honest parties Alice and Bob can exchange information with each other and with the eavesdropper Eve in any number of rounds, as long as the total number of bits or qubits communicated is bounded. Talk based on: arXiv:2106.04299, FOCS 2021.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

In this talk we will discuss dimension-free relations between basic communication and query complexity measures and various matrix norms. Dimension-free relations are inequalities that bound a parameter as a function of another parameter without dependency on the number of input bits. This is in contrast to the more common framework in communication complexity where poly-logarithmic dependencies are tolerated. Dimension-free bounds are closely related to structural results, where one seeks to describe the structure of Boolean matrices and functions that have ``low complexity''. We prove such bounds for several communication and query complexity measures as well as various matrix and operator norms. We also propose several conjectures, and establish connections to graph theory, operator theory, and harmonic analysis. The talk is based on joint work with Hamed Hatami and Pooya Hatami.

In the reliable transmission problem, a sender, Alice, wishes to transmit a bit-string x to a remote receiver, Bob, over a binary channel with adversarial noise. The solution to this problem is to encode x using an error-correcting code. As it is long known that the distance of binary codes is at most 1/2, reliable transmission is possible only if the channel corrupts (flips) at most a 1/4-fraction of the communicated bits. We revisit the reliable transmission problem in the two-way setting, where both Alice and Bob can send bits to each other. Our main result is the construction of two-way error-correcting codes that are resilient to a constant fraction of corruptions strictly larger than 1/4. Moreover, our code has a constant rate and requires Bob to only send one short message. Curiously, our new two-way code requires a fresh perspective on classical error-correcting codes: While classical codes have only one distance guarantee for all pairs of codewords (i.e., the minimum distance), we construct codes where the distance between a pair of codewords depends on the ``compatibility'' of the messages they encode. We also prove that such codes are necessary for our results. Joint work with Gillat Kol, Raghuvansh R. Saxena, and Zhijun Zhang

The Exactly-N problem in the number-on-forehead setting asks k players, who can individually see all but one of the inputs, if the inputs add to N. In their paper first studying this problem, Chandra, Furst, and Lipton showed a deep connection between protocols for Exactly-N and the construction of large sets with no length-k arithmetic progressions (denoted k-AP-free sets). Their proof is existential and does not construct an explicit protocol. Linial, Pitassi, and Shraibman gave an explicit protocol for the case of k=3 that matches Behrend's construction of large 3-AP-free sets. In this work, we give an explicit protocol for k>3 that matches the asymptotic behavior of Rankin's construction of large k-AP-free sets, which generalizes Behrend's construction. This is ongoing work with Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, and Adi Shraibman.

The recent counterexample to the Log-Approximate-Rank Conjecture created a hard Boolean function that was the sum of simple Boolean functions. While this was sufficient to refute the LARC, it was not enough to settle two interesting questions: 1) What is the best upper bound on randomized communication complexity in terms of approximate rank? And 2) What about the Log-Approximate-Nonnegative-Rank Conjecture? In this talk we will see some potential functions that could make progress on these questions and that raise interesting challenges along the way.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

5-day workshop participants are welcome to use BIRS facilities (TCPL ) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 11AM.