Monday, April 20th, 2015

9:30 am10:45 am

Although we understand how to send single messages in a way that is resilient to errors, the interactive setting is much less understood. In this introductory talk, we will define the problem of correcting errors in interactive communication (first considered by Schulman), and outline the plan for the rest of the tutorial.

Several recent works will be discussed:

  1. The definition and construction of tree-codes (first used by Schulman to give a solution to this problem)
  2. A way to use tree codes to recover from errors [Braverman-Rao]
  3. Applications. How to recover from short-circuit errors in circuits [Kalai-Lewko-Rao], how to embed any graph metric into l1 [Lee-Mesmay-Moharrami]
  4. A candidate explicit construction of tree codes [Moore-Schulman]
11:15 am11:45 am

In profoundly influential works, Shannon and Huffman show that if Alice wants to send a message X to Bob, it's sufficient for her to send roughly H(X) bits (in expectation), where H denotes Shannon's entropy function. In other words, the message X can be compressed to roughly H(X) bits, the information content of the message. Can one prove similar results in the interactive setting, where Alice and Bob engage in an interactive communication protocol?

We show the first gap between communication complexity and information complexity, by giving an explicit example of a boolean function with information complexity O(k), and distributional communication complexity > 2^k. This shows that a communication protocol cannot always be compressed to its internal information, answering (the standard formulation of) the above question in the negative. By a result of Braverman, our example gives the largest possible gap.

By a result of Braverman and Rao, our example gives the first gap between communication complexity and amortized communication complexity, implying that strong direct sum does not hold for distributional communication complexity, answering a long standing open problem.

Joint work with Anat Ganor and Ran Raz.

11:45 am12:15 pm

We prove a parallel repetition theorem for general games with value tending to 0. We also give alternate proofs for the parallel repetition theorems of Dinur & Steurer, Holenstein and Rao. Parallel repetition theorems fall in the category of hardness amplification results and have a lot of applications in theoretical computer science, including hardness of approximation. Our proofs heavily rely on information theory but only use basic properties of mutual information such as chain rule. I will give a high level overview of our proof focussing on the role of information theory. This is joint work with Mark Braverman.

1:30 pm2:00 pm

We present a general problem that we call Functional Aggregate Queries (or FAQs), which as special cases includes frequently asked questions in CSPs, PGMs, Databases, Logic and Matrix Operations. The problem is to compute sums of products of functions over semi-rings. We present a single simple algorithm to solve this general problem that in addition to re-proving a bunch of known results (e.g. our algorithm specialized to computing DFT results in the FFT) also proves new results in counting CSPs with quantification and exact probabilistic inferences in probabilistic graphical model (PGMs).

Our algorithm has its origin in algorithms designed to compute the natural join query. The natural join query is a fundamental operation in relational database systems (RDBMs). It has been optimized for over 40 years in commercial RDBMs but surprisingly, we only recently have an optimal understanding of the worst-case complexity of computing the join query. This talk will present an information theoretic proof of an optimal worst-case bound on output size of any join query using Shearer's lemma (due to Atserias, Grohe and Marx, 2009) and our algorithmic proof of the same result from 2012. Based on joint works with Abo Khamis, Ngo, Nguyen, Porat and Re.

2:00 pm2:30 pm

We consider the problem of estimating the value of max cut in a graph in the streaming model of computation.

At one extreme, there is a trivial $2$-approximation for this problem that uses only $O(\log n)$ space, namely, count the number of edges and output half of this value as the estimate for max cut value. On the other extreme, if one allows $\tilde{O}(n)$ space, then a near-optimal solution to the max cut value can be obtained by storing an $\tilde{O}(n)$-size sparsifier that essentially preserves the max cut. An intriguing question is if poly-logarithmic space suffices to obtain a non-trivial approximation to the max-cut value (that is, beating the factor $2$). It was recently shown that the problem of estimating the size of a maximum matching in a graph admits a non-trivial approximation in poly-logarithmic space.

Our main result is that any streaming algorithm that breaks the $2$-approximation barrier requires $\tilde{\Omega}(\sqrt{n})$ space even if the edges of the input graph are presented in random order. Our result is obtained by exhibiting a distribution over graphs which are either bipartite or $\frac{1}{2}$-far from being bipartite, and establishing that $\tilde{\Omega}(\sqrt{n})$ space is necessary to differentiate between these two cases. Thus as a direct corollary we obtain that $\tilde{\Omega}(\sqrt{n})$ space is also necessary to test if a graph is bipartite or $\frac{1}{2}$-far from being bipartite.

We also show that for any $\epsilon > 0$, any streaming algorithm that obtains a $(1 + \epsilon)$-approximation to the max cut value when edges arrive in adversarial order requires $n^{1 - O(\epsilon)}$ space, implying that $\Omega(n)$ space is necessary to obtain an arbitrarily good approximation to the max cut value.

2:30 pm3:00 pm

I will survey some of the recent lower bounds for extended formulations, with an emphasis on the underlying techniques, and the parallels to the techniques used in lower bounds for communication complexity.

3:30 pm4:00 pm

We continue the study of welfare maximization in unit-demand (matching) markets, in a distributed information model where agent?s valuations are unknown to the central planner, and therefore communication is required to determine an efficient allocation. Dobzinski, Nisan and Oren (STOC?14) showed that if the market size is n, then r rounds of interaction (with logarithmic bandwidth) suffice to obtain an n^{1/(r+1)}-approximation to the optimal social welfare. In particular, this implies that such markets converge to a stable state (constant approximation) in time logarithmic in the market size.

We obtain the first multi-round lower bound for this setup. We show that even if the allowable per- round bandwidth of each agent is n?(r), the approximation ratio of any r-round (randomized) protocol is no better than ?(n^{1/5^{r+1}}, implying an ?(log log n) lower bound on the rate of convergence of the market to equilibrium.

Our construction and techniques may be of interest to round-communication tradeoffs in the more general setting of combinatorial auctions, for which the only known lower bound is for simultaneous (r = 1) protocols [DNO14].

4:00 pm4:30 pm

Over 50 years ago R. Gallager used the probabilistic method to show that good codes exist with parity check matrix that has constant row and column sums. I will present a proof and speak about some possible approaches to the search for improved bounds.

Tuesday, April 21st, 2015

9:30 am10:45 am

This talk is concerned with the design of coding schemes for interactive communication that are computationally efficient and can tolerate optimal rates. We show that list decodable coding schemes are a key ingredient for achieving both goals.

We give a general black-box reduction which reduces unique decoding, in various settings, to list decoding while preserving computational efficiency. In particular, we give the first computational efficient non-adaptive protocol tolerating the optimal 1/4 error rate. We also define adaptive protocols and show that, given a list decoder, adaptive coding schemes can tolerate a higher error rate of 2/7, which is optimal.

As a second ingredient we show how to boost the computational and communication efficiency of any list decoder to become near linear. Put together with the list decoder of Braverman and Effremenko (see day 4) this leads to coding schemes with optimal error tolerance, constant rate, and near linear computational complexity for all settings considered.

This talk is based on joint work with Mohsen Ghaffari (STOC'14,FOCS'14) and Madhu Sudan (FOCS'14).

11:15 am11:45 am

Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Recently, Ganor et al. [2014] provided such a separation in the distributional setting for a specific input distribution µ. We show that in the nondistributional setting, the relative discrepancy bound they defined is, in fact, smaller than the information complexity, and hence it cannot be used to separate information and communication complexity. In addition, in the distributional case, we provide an equivalent linear program formulation for relative discrepancy and relate it to variants of the partition bound, resolving also an open question regarding the relation of the partition bound and information complexity. Last, we prove the equivalence between the adaptive relative discrepancy and the public-coin partition bound, which implies that the logarithm of the adaptive relative discrepancy bound is quadratically tight with respect to communication.

11:45 am12:15 pm

We study internal compression of communication protocols to their internal entropy, which is the entropy of the transcript from the players' perspective. We provide two internal compression schemes with error. One of a protocol of Fiege et al.\ for finding the first difference between two strings. The second and main one is an internal compression with error $\eps > 0$ of a protocol with internal entropy $H^{int}$ and communication complexity $C$ to a protocol with communication at most order $(H^{int}/\eps)^2 \log(\log(C))$.

This immediately implies a similar compression to the internal information of public coin protocols, which exponentially improves over previously known public coin compressions in the dependence on $C$. It further shows that in a recent protocol of Ganor, Kol and Raz, it is impossible to move the private randomness to be public without an exponential cost. No such example was previously known.

Joint work with Balthazar Bauer (ENS Lyon) and Amir Yehudayoff (Technion).

1:30 pm2:00 pm

In profoundly influential works, Shannon and Huffman show that if Alice wants to send a message X to Bob, it's sufficient for her to send roughly H(X) bits (in expectation), where H denotes Shannon's entropy function. In other words, the message X can be compressed to roughly H(X) bits, the information content of the message. Can one prove similar results in the interactive setting, where Alice and Bob engage in an interactive communication protocol?

We show the first gap between communication complexity and information complexity, by giving an explicit example of a boolean function with information complexity O(k), and distributional communication complexity > 2^k. This shows that a communication protocol cannot always be compressed to its internal information, answering (the standard formulation of) the above question in the negative. By a result of Braverman, our example gives the largest possible gap.

By a result of Braverman and Rao, our example gives the first gap between communication complexity and amortized communication complexity, implying that strong direct sum does not hold for distributional communication complexity, answering a long standing open problem.

Joint work with Anat Ganor and Ran Raz.

2:00 pm2:30 pm

Distributed computing is a natural application domain for communication complexity: the typical distributed system has multiple participants, each with only a partial view of the global state of the system, and the players must communicate to achieve some shared goal. Communication is often the most important resource, because its cost is usually orders-of-magnitude greater than the cost of local computation.

In this talk we describe how two-party information complexity can be extended to the multi-party setting, and how it has recently been used to obtain strong lower bounds. We point out that several nice properties of the two-party model unfortunately do not carry over to multi-party communication, so new notions are necessary.

2:30 pm3:00 pm

Consider the problem of packing Hamming balls of a given relative radius subject to the constraint that they cover any point of the ambient Hamming space with multiplicity at most $L$. For odd $L\ge 3$ an asymptotic upper bound on the rate of any such packing is proven. Resulting bound improves the best known bound (due to Blinovsky'1986) for rates below a certain threshold. Method is a superposition of the linear-programming idea of Ashikhmin, Barg and Litsyn (that was used previously to improve the estimates of Blinovsky for $L=2$) and a Ramsey-theoretic technique of Blinovsky. As an application it is shown that for all odd $L$ the slope of the rate-radius tradeoff is zero at zero rate.

3:30 pm4:00 pm

Sparse (or small) set disjointness is the communication game where Alice and Bob are given each a set of size k in a larger universe and they are to find out if the two sets are disjoint. The randomized communication complexity of this problem is was found by Hastad and Wigderson ('97, '07): it is O(k). In this joint result with Mert Saglam we improve their O(log k) round protocol to a log* k round protocol of the same complexity and find an optimal tradeoff between the length and the number of rounds: to solve the sparse set disjointness problem in an r*>

A major advantage of our protocols is that we find the intersection of the two sets exactly and do not only decide whether it is empty. For the lower bound we use a new isoperimetric inequality.

4:00 pm4:30 pm

I'll briefly describe a handful of computational models that I often see being used in large-data analysis. As far as I know, these models have not been analyzed from a theoretical perspective. The goal is to give theorists an overview of these models in the hope that it may spark some exciting new methods for proving lower bounds (or better yet, upper bounds). Examples include the Millwheel model, the "parameter server" model, etc.

Wednesday, April 22nd, 2015

9:30 am10:45 am

Ran Raz: We will talk about the interactive channel capacity of a noisy channel: the minimal ratio between the communication complexity of a problem over a non-noisy channel, and the communication complexity of the same problem over the noisy channel (where the communication complexity tends to infinity).

We will discuss a lower bound for communication complexity over the binary symmetric channel, that shows a separation between interactive and non-interactive channel capacity (for small enough error rate).


Bernhard Haeupler: This talk presents a new, natural, and extremely easy way to achieve coding schemes for interactive communication that avoids the use of tree-codes and leads to the first coding scheme with good communication rate against adversarial noise.

The protocol essentially consist of both parties having their original conversation as-is (without any coding), interspersed only by short exchanges of hash values.  When hash values do not match, the parties backtrack. We feel the protocol gives the simplest explanation for how and why interactive coding schemes for adversarial noise are possible.

Our coding scheme achieves a communication rate of 1 - Theta(sqrt{eps log log 1/eps}) evenoutperforming the rate achieved for random noise achieved by a coding scheme of [Kol, Raz, STOC13]. For random, oblivious, or computationally bounded noise the communication rate becomes 1 - Theta(sqrt{eps}). Despite their odd form we conjecture these error rates to be optimal in their respective settings.

This talk is based on the FOCS'14 paper "Interactive Channel Capacity Revisited".

 

11:15 am11:45 am

The Beckner - Bonami inequality was first imported to the scene of theoretical computer science and analytical combinatorics in the famou KKL (Kahn-Kalai-Linial) paper. Since, it has become a cornerstone of discrete Fourier analysis, and has had great influence (no pun intended) and numerous and diverse applications. Roughly, the inequality compares one norm of a real function f on {0,1}^n with a different norm of Tf, where T is an averaging operator. Not surprisingly, the averaging produces a "smoother" function, and this is captured by the comparison.

A slightly different interpretation is that the inequality bounds the correlation between a vector chosen from a given distribution and a noisy version of it. In this talk we will prove such a version of the inequality using an information theoretic approach.

Previous information theoretic proofs of the dual version of the inequality were given by Friedgut-Rodl, and Blais-Tan, but it seems that the current proof is unrelated.

11:45 am12:15 pm

In 1979 Yao published a paper that started the field of communication complexity and asked, in particular, what was the randomized complexity of the Equality function in the Simultaneous Message Passing (SMP) model. The tight lower bound was given only in 1996 by Newman and Szegedy.

In this work we develop a new lower bound method for analyzing the complexity of Equality in SMP.

Our technique allows us to obtain the the following new results:

  • It allows to show a tight lower bound for the quantum-classical case.
  • It leads to tight lower bounds for both Equality and its complement in all non-deterministic versions of quantum-classical SMP, where Merlin may also be quantum. Previous methods do not seem to work in this case.

Our characterization leads to tight trade-offs between the message lengths needed for players Alice, Bob, Merlin, not just the maximum message length among them, and highlights that the complement of Equality is easier than Equality in the case of classical proofs, but not for quantum proofs.

Along the way, we give tight analysis of a new quantum communication primitive, where a honest classical and an untrusted quantum party help a third party to obtain an approximate copy of a quantum state.

1:30 pm2:00 pm

Consider the problem of packing Hamming balls of a given relative radius subject to the constraint that they cover any point of the ambient Hamming space with multiplicity at most $L$. For odd $L\ge 3$ an asymptotic upper bound on the rate of any such packing is proven. Resulting bound improves the best known bound (due to Blinovsky'1986) for rates below a certain threshold. Method is a superposition of the linear-programming idea of Ashikhmin, Barg and Litsyn (that was used previously to improve the estimates of Blinovsky for $L=2$) and a Ramsey-theoretic technique of Blinovsky. As an application it is shown that for all odd $L$ the slope of the rate-radius tradeoff is zero at zero rate.

2:00 pm2:30 pm

In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game G with optimal winning probability 1−α and its repeated version Gn (in which n games are played together, in parallel), can the players use strategies that are substantially better than ones in which each game is played independently? This question is relevant in physics for the study of correlations and plays an important role in computer science in the context of complexity and cryptography. In this work the case of multiplayer non-signalling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For complete-support games (games where all possible combinations of questions have non-zero probability to be asked) with any number of players we prove a threshold theorem stating that the probability that non-signalling players win more than a fraction 1−α+β of the n games is exponentially small in nβ2, for every 0≤β≤α. For games with incomplete support we derive a similar statement, for a slightly modified form of repetition. The result is proved using a new technique, based on a recent de Finetti theorem, which allows us to avoid central technical difficulties that arise in standard proofs of parallel repetition theorems.

2:30 pm3:00 pm

"Kernelization" is an influential paradigm for attacking hard computational problems. Kernelization reductions efficiently preprocess their input to “shrink” it to a smaller, equivalent one. This can be a valuable first step before applying exhaustive-search techniques.

After giving the basic framework of kernelization, I’ll describe my contribution to a line of works showing limits to the power of kernelization for many NP problems (under complexity-theoretic assumptions). To this end, I show that if such problems have a sufficiently strong kernelization reduction, the information bottleneck in the reduction can be exploited to give proofs of unsatisfiability for Boolean formulas.

Based on: [A. Drucker, New Limits to Classical and Quantum Instance Compression. FOCS’12]

3:30 pm4:00 pm

We give improved parallel repetition theorems for multiplayer, one-round games with entangled players, when the inputs to the players are uncorrelated. We do so by exploiting a novel connection between communication protocols and quantum parallel repetition, first explored by Chailloux and Scarpa: by taking advantage of fast quantum protocols for distributed search, we show that for this class of games (called free games), the entangled value of the n-fold repetition decays as (1 - eps^{3/2})^{\Omega(n/s)}, where 1 - eps is the entangled value of the original game, and s is the output alphabet size.

In contrast, the best known parallel repetition theorem for free games (due to Barak, et al.) in the classical setting is that the n-fold repetition value is bounded by (1 -eps^2)^{\Omega(n/s)}, suggesting the possibility of a separation between the behavior of quantum and classical games under parallel repetition.

Our proof takes advantage of the Aaronson-Ambainis quantum search protocol, and a general theorem of Nayak and Salzman that bounds the ability of parties to convey classical messages using two-way quantum communication. No prior knowledge of quantum information will be assumed.

Joint work with Kai-Min Chung and Xiaodi Wu.

4:00 pm4:30 pm

While most current high-throughput DNA sequencing technologies generate short reads with low error rates, emerging sequencing technologies generate long reads with high error rates. A basic question of interest is the tradeoff between read length and error rate in terms of the information needed for the perfect assembly of the genome. Using an adversarial erasure error model, we make progress on this problem by establishing a critical read length, as a function of the genome and the error rate, above which perfect assembly is guaranteed. For several real genomes, we verify that this critical read length is not significantly greater than the read length required for perfect assembly from reads without errors.

Thursday, April 23rd, 2015

9:30 am10:45 am

Klim Efremenko: In this talk we show that any protocol can be encoded, with a constant rate, into a list-decodable protocol which is resilient to a noise rate of up to 1/2, and that this is tight.  Using our list-decodable construction, we study a more nuanced model of noise where the adversary can corrupt up to a fraction alpha of Alice's communication and up to a fraction beta  of Bob's communication. We use list-decoding in order to fully characterize the region of pairs (alpha, beta) for which unique decoding with a constant rate is possible. This region  turns out to be quite unusual in its shape.
 


Ran Gelles: We will discuss the task of multiparty computation performed over networks (of arbitrary topology) in the presence of random noise. We will set the model and survey several coding schemes which plot an interesting relation between the specific topology and the rate of the coding scheme.  Specifically, we will discuss a scheme by Rajagopalan and Schulman whose rate is O(1/log (d+1)), where d is the maximal degree of connectivity in the network. Additionally, we will discuss a recent scheme by Alon, Braverman, Efremenko, Gelles and Haeupler which achieves a constant rate O(1) for a large family of topologies including complete graphs and random graphs with n vertices and degrees n^{\Omega(1)}.

11:15 am11:45 am

Information theory is a powerful tool to analyze the behavior of communication systems. However, its applicability goes far beyond this and more recently many important problems in Theoretical Computer Science as well as Optimization have been addressed by means of Information Theory. We provide a new framework for establishing strong lower bounds on the nonnegative rank of matrices by means of common information, a notion previously introduced in Wyner [1975]. Common information is a natural lower bound for the nonnegative rank of a matrix and by combining it with various distance estimations we can bound the extension complexity of various polytopes of interest.

11:45 am12:15 pm

Additive number theory contains a number of so-called "sumset inequalities" that relate the cardinalities of various finite subsets of an abelian group G, for instance, the sumset A+A and the difference set A-A of a finite subset A of G. We explore probabilistic analogues of such results, showing for instance that for independent, identically distributed random variables X and X’ that are discrete and take values in an abelian group G, the entropies of X+X' and X-X' strongly constrain each other. We also discuss statements analogous to the entropy power inequality (which is well known for R^n) that can be made for specific discrete groups of interest such as the integers and finite cyclic groups. Some of our results have extensions to general locally compact abelian groups, and applications to probability theory, combinatorics, information theory, and convex geometry. Based on (multiple) joint works with Ioannis Kontoyiannis (Athens), Jiange Li (Delaware), Liyao Wang (Yale), and Jaeoh Woo (Yale).

1:30 pm2:00 pm

The Beckner - Bonami inequality was first imported to the scene of theoretical computer science and analytical combinatorics in the famou KKL (Kahn-Kalai-Linial) paper. Since, it has become a cornerstone of discrete Fourier analysis, and has had great influence (no pun intended) and numerous and diverse applications. Roughly, the inequality compares one norm of a real function f on {0,1}^n with a different norm of Tf, where T is an averaging operator. Not surprisingly, the averaging produces a "smoother" function, and this is captured by the comparison.

A slightly different interpretation is that the inequality bounds the correlation between a vector chosen from a given distribution and a noisy version of it. In this talk we will prove such a version of the inequality using an information theoretic approach.

Previous information theoretic proofs of the dual version of the inequality were given by Friedgut-Rodl, and Blais-Tan, but it seems that the current proof is unrelated.

2:00 pm2:30 pm

We study the complexity of parallelizing streaming algorithms (or equivalently, branching programs). If M(f) denotes the minimum average memory required to compute a function f(x1,x2,...,xn) how much memory is required to compute f on k independent streams that arrive in parallel? We show that when the inputs (updates) are sampled independently from some domain and M(f)=(n), then computing the value of f on k streams requires average memory at least knM(f).

Our results are obtained by defining new ways to measure the information complexity of streaming algorithms. We define two such measures: the \emph{transitional} and \emph{cumulative} information content. We prove that any streaming algorithm with transitional information content I can be simulated using average memory (n(I+1)). On the other hand, if every algorithm with cumulative information content I can be simulated with average memory (I+1), then computing f on k streams requires average memory at least (k(M(f)−1)).

Joint work with Anup Rao.

2:30 pm3:00 pm

We consider the following scenario motivated by the rise of cloud computing. A client needs to process a massive stream of data, arriving online, but is unable to store even a small fraction of the data. It outsources the processing to a commercial cloud computing service, but is unwilling to blindly trust answers returned by this service. How can we design a suitable communication protocol that allows the server to not just provide the desired answer but prove to the client that the answer is correct?

This general question has been the subject of several recent research works. In this talk we shall focus on one particular problem of great practical interest: Nearest Neighbour Search. Our main protocol allows a client to find, with proof (in the above sense) the nearest neighbour to a query point in a stream of data points, while storing barely more than a constant number of points. In fact, the protocol we design is considerably more general, allowing us to solve many other data streaming problems, and leading to a rich theory within communication complexity, known as Arthur-Merlin communication. The talk will outline this theory broadly.

Based on joint work with Cormode, McGregor, Thaler, and Venkatasubramanian.

3:30 pm4:00 pm

The sensitivity conjecture is a major outstanding foundational problems about boolean functions is the sensitivity conjecture. In one of its many forms, it asserts that the degree of a boolean function (i.e. the minimum degree of a real polynomial that interpolates the function) is bounded above by some fixed power of its sensitivity (which is the maximum vertex degree of the graph defined on the inputs where two inputs are adjacent if they differ in exactly one coordinate and their function values are different). We propose an attack on the sensitivity conjecture in terms of a novel two-player communication game. A strong enough lower bound on the cost of this game would imply the sensitivity conjecture.

To investigate the problem of bounding the cost of the game, three natural (stronger) variants of the question are considered. For two of these variants, protocols are presented that show that the hoped for lower bound does not hold. These protocols satisfy a certain monotonicity property, and (in contrast to the situation for the two variants) we show that the cost of any monotone protocol satisfies a strong lower bound.

This is joint work with Justin Gilmer and Michal Koucký.

4:00 pm4:30 pm

We show that deterministic communication complexity can be superlogarithmic in the partition number of the associated communication matrix. We also obtain near-optimal deterministic lower bounds for the clique vs. independent set problem, which in particular yields new lower bounds for the log-rank conjecture. These results follow from a simple adaptation of a communication-to-query simulation theorem of Raz and McKenzie, together with lower bounds for the analogous query complexity classes.

Joint work with Mika Goos and Thomas Watson.

Friday, April 24th, 2015

10:00 am10:30 am

The sensitivity conjecture is a major outstanding foundational problems about boolean functions is the sensitivity conjecture. In one of its many forms, it asserts that the degree of a boolean function (i.e. the minimum degree of a real polynomial that interpolates the function) is bounded above by some fixed power of its sensitivity (which is the maximum vertex degree of the graph defined on the inputs where two inputs are adjacent if they differ in exactly one coordinate and their function values are different). We propose an attack on the sensitivity conjecture in terms of a novel two-player communication game. A strong enough lower bound on the cost of this game would imply the sensitivity conjecture.

To investigate the problem of bounding the cost of the game, three natural (stronger) variants of the question are considered. For two of these variants, protocols are presented that show that the hoped for lower bound does not hold. These protocols satisfy a certain monotonicity property, and (in contrast to the situation for the two variants) we show that the cost of any monotone protocol satisfies a strong lower bound.

This is joint work with Justin Gilmer and Michal Koucký.

11:00 am11:30 am

I'll discuss various tools for proving lower bounds in the message passing communication model, where there are k players each with an input who speak to each other in a point-to-point communication network, with the goal being to solve a function of their inputs while minimizing total communication. I'll mostly focus on several recent works in which the servers try to estimate the number of distinct elements on the union of their datasets, though I'll also discuss results for graph problems, linear-algebraic problems, and other statistical problems.

This is based on joint works with Yi Li, Xiaoming Sun, Chengu Wang, and Qin Zhang.

11:30 am12:00 pm

We prove first n^(1+\Omega(1)) lower bounds for the space complexity of multipass streaming algorithms for problems such as maximum matching, shortest path, and directed connectivity. More precisely, if the number of passes is a constant p, we show that these problems require n^(1+\Omega(1/p)) space. Prior to our result, it was known that they need Omega(n^2) space in one pass, but no n^(1+\Omega(1)) lower bound was known for any p >= 2.

Our results follow from a communication complexity lower bound for a communication game in which the players hold two graphs on the same set of vertices. The task of the players is to find out whether the sets of vertices at distance exactly p+1 from a specific vertex intersect. The game requires a significant amount of communication only if the players are forced to speak in a specific difficult order. This is reminiscent of lower bounds for communication problems such as indexing and pointer chasing. Among other things, our line of attack requires proving an information cost lower bound for a decision version of the classic pointer chasing problem and a direct sum type theorem for the disjunction of several instances of this problem.

Joint work with Venkatesan Guruswami.

1:30 pm2:00 pm

We consider the point-to-point message passing model of communication in which there are k processors with individual private inputs, each n-bit long. Each processor is located at the node of an underlying undirected graph and has access to private random coins. An edge of the graph is a private channel of communication between its endpoints. The processors have to compute a given function of all their inputs by communicating along these channels. While this model has been widely used in distributed computing, strong lower bounds on the amount of communication needed to compute simple functions have just begun to appear. In this talk, we will see a tight lower bound of Ω(kn) on the communication needed for computing the Tribes function, when the underlying graph is a star of k + 1 nodes that has k leaves with inputs and a center with no input. Lower bound on this topology easily implies comparable bounds for others. These lower bounds are obtained by building upon the recent information theoretic techniques of Braverman et.al ([BEO+13], FOCS’13) and combining it with the earlier work of Jayram, Kumar and Sivakumar ([JKS03], STOC’03). This approach yields information complexity bounds that is of independent interest.

Joint work with Sagnik Mukhopadhyay.

2:00 pm2:30 pm

In 2010, Impagliazzo and Kabanets gave a proof of the Chernoff bound which is "more combinatorial" than the usual one using the Bernstein trick. We will discuss their proof, and discuss when it is easier to use. As an example, we discuss a setting in which it gives a stronger bound one the concentration of the value of a polynomial than previously known.

Joint work with Jan Hazla [STACS 2015]

2:30 pm3:00 pm

We study the relationship between communication and information in 2-party communication protocols when the information is asymmetric. If I_A denotes the number of bits of information revealed by the first party, I_B denotes the information revealed by the second party, and C is the number of bits of communication in the protocol, we show that 

-- one can simulate the protocol using order  I_A + C^{3/4} I_B^{1/4} log C  bits of communication,
-- one can simulate the protocol using order I_A  2^{O(I_B)} bits of communication

The first result gives the best known bound on the complexity of a simulation when I_A >> I_B ,C^{3/4}. The second gives the best known bound when I_B << log C. In addition we show that if a function is computed by a protocol with asymmetric information complexity, then the inputs must have a large, nearly monochromatic rectangle of the right dimensions, a fact that is useful for proving lower bounds on lopsided communication problems.

This is joint work with Anup Rao.

3:30 pm4:00 pm

This talk will highlight the role of geometry in proving information complexity lower bounds. We illustrate this paradigm by considering some classical problems in communication complexity with applications to data stream and sketching lower bounds.

4:00 pm4:30 pm

The information complexity of a function f is the minimum amount of information Alice and Bob need to exchange to compute the function f. We provide an algorithm for approximating the information complexity  of an arbitrary function f to within any additive error epsilon>0. In the process, we give the first explicit upper bound on the rate of convergence of the information complexity of f when restricted to b-bit protocols to the (unrestricted) information complexity of f.

Joint work with Jon Schneider.