Schedule for: 17w5147 - Communication Complexity and Applications, II

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the 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 tutorial-style talk on recent progress in various direct product theorems in communication complexity and related models, such as query complexity.

We study problems in randomized communication complexity when the protocol is only required to attain some small advantage over purely random guessing, i.e., it produces the correct output with probability at least epsilon greater than one over the codomain size of the function. Previously, Braverman and Moitra (STOC 2013) showed that the set-intersection function requires Θ(epsilon n) communication to achieve advantage epsilon. Building on this, we prove the same bound for several variants of set-intersection: (1) the classic “tribes” function obtained by composing with And (provided 1/epsilon is at most the width of the And), and (2) the variant where the sets are uniquely intersecting and the goal is to determine partial information about (say, certain bits of the index of) the intersecting coordinate.

TBD

In this talk we will discuss the challenges of, and some progress on, lower bounds on the communication complexity of functions in the natural multi-party peer-to-peer number-in-the-hand model. We will mostly discuss information theoretical tools and techniques to prove such lower bounds. Based on both published and ongoing work joint with Iordanis Kerenidis, Rotem Oshman, and Florent Urrutia.

Meet in the Corbett Hall Lounge 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!

It may be the only upper bound talk in the entire workshop! Just so that there will be something to prove lower bounds about !! Joint work with Yi Li and Qin Zhang.

We initiate the study of lower bounds for the median problem in the cell probe model. The algorithmic task is to maintain a subset of {1,2,....,m}, support insertion of elements and find the median of the set. Let $t_u,t_q,w$ denote the update time, the query time and the cell size of a data structure. We show that any data structure for the median problem must have $t_q \geq \Omega(m^(1/2(t_u+2))/(wt_u))$, when the updates are non-adaptive. An update is termed non-adaptive when locations of the cells accessed by the update algorithm is completely determined by the update value. For the predecessor search problem, we show that either $t_q \geq \Omega(\log m/(\log \log m + \log w))$ or $t_u \geq \Omega(m^(1/4(t_q+1)))$, when the queries are non-adaptive. This is joint work with Anup Rao.

The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. For any constant $\delta > 0$, we exhibit an $AC^0$ function of approximate degree $\Omega(n^{1-delta})$. This improves over the best previous lower bound of $\Omega(n^{2/3})$ due to Aaronson and Shi, and nearly matches the trivial upper bound of n that holds for any function. We accomplish this by giving a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. I will also describe a number of applications of this result to communication complexity and cryptography. This is joint work with Mark Bun.

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

First open problems session. Please sign up on blackboard for a five-minute slot to present an open problem you are currently excited about and would like to discuss over the next days, with other workshop attendees. There will be a followup session on Thursday.

This will be a tutorial-style talk, with a particular focus on the following result. For any n-bit boolean function $f$, we show that the randomized communication complexity of the composed function $f o g^n$, where $g$ is a small index gadget, is characterized by the randomized decision tree complexity of $f$. In particular, this means that many query complexity separations involving randomized models (e.g., classical vs. quantum) automatically imply analogous separations in communication complexity. Joint work with Toniann Pitassi and Thomas Watson.

In the recent years linear sketching has emerged as a powerful tool for approximate computing in settings with limited resources including distributed computation and streaming. It has been used in breakthrough results on graph and matrix processing, dimensionality reduction, etc. Strikingly, linear sketches have been shown to be optimal for dynamic stream processing under fairly mild assumptions. In this talk I will describe a new study of linear sketching that focuses on understanding the power of linear sketches based on parities (i.e. over $GF_2$, the field over two elements, as compared to the previous work that uses real arithmetic). I will illustrate various properties of such sketches using Fourier-analytic methods and tools from communication complexity. In particular, linear sketching over $GF_2$ turns out to be closely related to Fourier sparsity with respect to Lp-norms. Moreover, it can be shown to be (almost) optimal in streaming and distributed settings for data generated according to the uniform distribution. Joint work with Sampath Kannan (UPenn) and Elchanan Mossel (MIT).

In this work, we continue the examination of the role non-adaptivity plays in maintaining dynamic data structures, initiated by Brody and Larsen [BL15]}. We consider non-adaptive data structures for predecessor search in the w-bit cell probe model. Predecessor search is one of the most well-studied data structure problems. For this problem, using non-adaptivity comes at a steep price. We provide exponential cell probe complexity separations between (i) adaptive and non-adaptive data structures and (ii) non-adaptive and memoryless data structures for predecessor search. A classic adaptive data structure of van Emde Boas solves dynamic predecessor search in $O(\log \log m)$ probes. For dynamic data structures which make non-adaptive updates, we show the cell probe complexity is $O(min{ (log m)/(log(w/log m)$, $(n log m)/w) })$. We also give a nearly-matching $\Omega( min {(log m)/(log w)$, $(nlog m)/(w log w) })$ lower bound. We also give an $\Omega(m)$ lower bound for memoryless data structures. Our lower bound technique is tailored to non-adaptive (as opposed to memoryless) updates and might be of independent interest. Joint work with Joe Boninger and Owen Kephart.

TBD

In turnstile $l_0$ sampling, a vector x receives coordinate-wise updates, and during a query one must return a uniformly random element from support(x). Data structures solving this problem were first used as a subroutine to solve various dynamic graph streaming problems in (Ahn, Guha, McGregor SODA’12) and since then have been crucially used in seemingly every dynamic graph streaming problem studied across several papers (connectivity, k-connectivity, spanners, cut sparsifiers, spectral sparsifiers, minimum spanning tree, maximal matching, maximum matching, vertex cover, hitting set, b-matching, disjoint paths, k-colorable subgraph, several other maximum subgraph problems, densest subgraph, vertex and hyperedge connectivity, and approximating graph degeneracy, to name a few). If x is n-dimensional with poly(n)-bounded coordinates, (Jowhari, Saglam, Tardos PODS’11) gave an $\Omega(lg^2 n)$ bit space lower bound for data structures which fail with constant probability, and otherwise whose query responses are close to uniform in statistical distance. They also gave an upper bound with failure probability delta, which in fact gave $\Theta(lg(1/delta))$ uniform samples from the support, with space $O(lg^2 n lg(1/delta))$ bits. No lower bound was known in terms of delta. We prove that for any $l_0$ sampling data structure, the correct space complexity is $\Omega(max(k, lg(1/delta)) lg^2 n)$ bits to recover k samples from support(x) with failure probability delta. This is optimal for all settings of k, delta, and n (as long as the expression stays below, say, $n^{.99}$ -- there is always a trivial $O(n lg n)$ bit algorithm by storing x in memory). Furthermore, our lower bound holds even if the data structure is only required to output any k elements from the support, as opposed to nearly uniform ones. The previous lower bound did not hold against this weaker guarantee, despite that the fact that this weaker guarantee is actually all that is needed for most dynamic graph streaming applications. Furthermore, since our lower bound holds regardless of which support elements the data structure finds, it holds against l_p samplers for every p (or even other distributions). Our approach is loosely inspired by recent activity in adaptive data analysis and differential privacy and may be of independent interest. Joint work with Jakub Pachocki and Zhengyu Wang.

Part 1 of a two-part talk on the following paper. This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds. We introduce a new method for proving dynamic cell probe lower bounds and use it to prove a Ω̃ (log1.5n) lower bound on the operational time of a wide range of boolean data structure problems, most notably, on the query time of dynamic range counting over 𝔽2 ([Pat07]). Proving an ω(lgn) lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai Pătrașcu's obituary [Tho13]. This result also implies the first ω(lgn) lower bound for the classical 2D range counting problem, one of the most fundamental data structure problems in computational geometry and spatial databases. We derive similar lower bounds for boolean versions of dynamic polynomial evaluation and 2D rectangle stabbing, and for the (non-boolean) problems of range selection and range median. Our technical centerpiece is a new way of "weakly" simulating dynamic data structures using efficient one-way communication protocols with small advantage over random guessing. This simulation involves a surprising excursion to low-degree (Chebychev) polynomials which may be of independent interest, and offers an entirely new algorithmic angle on the "cell sampling" method of Panigrahy et al. [PTW10].

Part 2 of a two-part talk on the following paper. This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds. We introduce a new method for proving dynamic cell probe lower bounds and use it to prove a Ω̃ (log1.5n) lower bound on the operational time of a wide range of boolean data structure problems, most notably, on the query time of dynamic range counting over 𝔽2 ([Pat07]). Proving an ω(lgn) lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai P\v{a}tra\c{s}cu's obituary [Tho13]. This result also implies the first ω(lgn) lower bound for the classical 2D range counting problem, one of the most fundamental data structure problems in computational geometry and spatial databases. We derive similar lower bounds for boolean versions of dynamic polynomial evaluation and 2D rectangle stabbing, and for the (non-boolean) problems of range selection and range median. Our technical centerpiece is a new way of "weakly" simulating dynamic data structures using efficient one-way communication protocols with small advantage over random guessing. This simulation involves a surprising excursion to low-degree (Chebychev) polynomials which may be of independent interest, and offers an entirely new algorithmic angle on the "cell sampling" method of Panigrahy et al. [PTW10].

We study the problem of compressing interactive communication to its information content I, defined as the amount of information that the participants learn about each other's inputs. We focus on the canonical setting where the participants' inputs are distributed independently and show how to compress the communication to O(I log2 I) bits, with no dependence on the original communication cost. This result essentially matches the well-known lower bound of Ω(I) and improves quadratically on previous work (Kol, STOC 2016). Our result complements the recent breakthrough of Ganor, Kol, and Raz (STOC 2014 and FOCS 2015), who show that one cannot achieve compression better than exp(Θ(I)) in the general case when the participants' inputs are dependent random variables.

This will be a tutorial-style talk on Information Theory and its applications in the theory of Extended Formulations

** Morteza Monemizadeh will Skype in remotely to give this talk. ** We study graph streaming problems. We transform known property testing algorithms into streaming ones. In particular, our main result is that for bounded degree graphs, any property that is constant-query testable in the adjacency list model can be tested with constant space in single-pass random order model. Our results are obtained by estimating the distribution of local neighborhoods of the vertices on a random order graph stream using constant space. We also apply this approach to constant time approximation algorithms in the adjacency list model and get single-pass random order streaming algorithms for all of them. For example, we get constant-space single-pass random order streaming algorithms for approximating the size of a maximum matching with additive error epsilon n (n is the number of nodes) . Our results are among the first known constant space graph streaming algorithms, while $\Omega(n)$ space is needed for many graph streaming problems and previous results typically use the semi-streaming model of $O(n poly log n)$ space. Joint work with S. Muthukrishnan, Pan Peng and Christian Sohler

I will talk about two recent works, one by [Anshu, Belovs, Ben-David, Goos, Jain, Kothari, Lee, Santha] and another by [Anshu, Ben-David, G., Jain, Kothari, Lee] which use “lookup functions” to get various separations in communication complexity.

In this talk I'll present our recent results on *Common Randomness Generation*, a very basic task where two parties have access to i.i.d. samples from a known source, and wish to generate many bits of randomness using limited (or no) communication with the largest possible agreement probability. Along the way, we'll see interesting connections to unbiased error-correcting codes, information complexity measures and communication with imperfectly shared randomness. Joint work with Badih Ghazi (MIT).

This talk will begin with tutorial-style material, and then focus on the following result. $1+\Omega(1)$ Approximation to MAX-CUT Requires Linear Space. We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. We show that there exists a constant $\e_* > 0$ such that any randomized streaming algorithm that computes a $(1+\e_*)$-approximation to MAX-CUT requires $\Omega(n)$ space on an $n$ vertex graph. By contrast, there are algorithms that produce a $(1+\e)$-approximation in space $O(n/\e^2)$ for every $\e > 0$. Our result is the first linear space lower bound for the task of approximating the max cut value and partially answers an open question from the literature~\cite{Ber67}. The prior state of the art ruled out $(2-\epsilon)$-approximation in $\tilde{O}(\sqrt{n})$ space or $(1+\e)$-approximation in $n^{1-O(\e)}$ space, for any $\epsilon > 0$. Previous lower bounds for the MAX-CUT problem relied, in essence, on a lower bound on the communication complexity of the following task: Several players are each given some edges of a graph and they wish to determine if the union of these edges is $\e$-close to forming a bipartite graph, using one-way communication. The previous works proved a lower bound of $\Omega(\sqrt{n})$ for this task when $\e=1/2$, and $n^{1-O(\e)}$ for every $\e>0$, even when one of the players is given a candidate bipartition of the graph and the graph is promised to be bipartite with respect to this partition or $\e$-far from bipartite. This added information was essential in enabling the previous analyses but also yields a weak bound since, with this extra information, there is an $n^{1-O(\e)}$ communication protocol for this problem. In this work, we give an $\Omega(n)$ lower bound on the communication complexity of the original problem (without the extra information) for $\e=\Omega(1)$ in the three-player setting. Obtaining this $\Omega(n)$ lower bound on the communication complexity is the main technical result in this paper. We achieve it by a delicate choice of distributions on instances as well as a novel use of the convolution theorem from Fourier analysis combined with graph-theoretic considerations to analyze the communication complexity. Joint work with Sanjeev Khanna, Madhu Sudan and Ameya Velingker

Unlike estimating the norm of a vector in a stream, the memory required for estimating the norm of a matrix is less understood. Of interest is estimating the Schatten p-norm of an n x n matrix A, which is the p-norm of the vector of singular values of A. I'll discuss a number of works in this direction, which nearly resolve the memory required of the algorithm in certain cases, such as when A has O(n) non-zero entries, when the algorithm is required to be a linear sketch and p > 2, or when the algorithm is required to be an embedding. The techniques are sometimes based on communication complexity, and sometimes more direct arguments tailored for linear sketches. I'll also discuss the main remaining open questions. Based on works with Yi Li and Huy Nguyen (Soda '14, Stoc '16, Random '16, arXiv '17)

I will describe recent work on the multi-party (number-in-hand) communication complexity of property testing in graphs, particularly testing triangle-freeness. I will also discuss open problems in this area arising from distributed computing. Based on joint work with Orr Fischer and Shay Gershtein.

This session will be devoted to short talks (about 5 min each) for quick announcements of very recent or upcoming results that fit the general theme of the workshop. Slides optional. Please sign up on the blackboard to reserve a slot.

We give new lower bounds for multi-party communication problems based on the basic Equality predicate, but incorporating strong promises. These promises make our bounds stronger than what was known before. We also give some applications of these bounds to data stream problems. In particular, we obtain strong space/approximation tradeoffs showing that for deterministic algorithms, even loose estimations of some basic statistics of an input stream require large, even linear, amounts of space. This work is joint with Sagar Kale (Dartmouth).

For any integers $d, n \geq 2$ and $1/({\min\{n,d\}})^{0.4999} <\eps<1$, we show the existence of a set of $n$ vectors $X\subset \R^d$ such that any embedding $f:X\rightarrow \R^m$ satisfying $$ \forall x,y\in X,\ (1-\eps)\|x-y\|_2^2 \le \|f(x)-f(y)\|_2^2 \le (1+\eps)\|x-y\|_2^2 $$ must have $$ m = \Omega(\eps^{-2} \lg n). $$ This lower bound matches the upper bound given by the Johnson-Lindenstrauss lemma [JL’84]. Furthermore, our lower bound holds for nearly the full range of $\eps$ of interest, since there is always an isometric embedding into dimension $\min\{d, n\}$ (either the identity map, or projection onto $span(X)$). Previously such a lower bound was only known to hold against linear maps $f$, and not for such a wide range of parameters $\eps, n, d$ [LN’16]. The best previously known lower bound for general $f$ was $m = \Omega(\eps^{-2}\lg n/\lg(1/\eps))$ [W’74,A’03], which is suboptimal for any $\eps = o(1)$.

A second session on open problems, perhaps with a focus on following up on some of the problems presented in Monday's open problems session. Ideally, discussions over the course of the workshop would have led to the formulation of some new open problems that we can talk about at this time.

Based on joint works with Michael Langberg, Shi Li, Jaikumar Radhakrishnan and Atri Rudra.

Abstract TBD

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.