The problem of constructing optimal and near-optimal test sequences to diagnose
permanent faults in electronic and electromechanical systems is considered. The test …

The primary goal of this paper is to define and study the interactive information complexity of
functions. Let f (x, y) be a function, and suppose Alice is given x and Bob is given y …

Abstract We prove n^ 1+\varOmega (1/p)/p^ O (1) n 1+ Ω (1/p)/p O (1) lower bounds for the
space complexity of p-pass streaming algorithms solving the following problems on n-vertex …

We show that almost all known lower bound methods for communication complexity are also
lower bounds for the information complexity. In particular, we define a relaxed version of the …

We give exponentially small upper bounds on the success probability for computing the
direct product of any function over any distribution using a communication protocol. Let suc …

We show an exponential gap between communication complexity and information
complexity, by giving an explicit example for a communication task (relation), with …

We consider the communication complexity of some fundamental convex optimization
problems in the point-to-point (coordinator) and blackboard communication models. We …

Suppose each of k≤ no (1) players holds an n-bit number xi in its hand. The players wish to
determine if∑ i≤ kxi= s. We give a public-coin protocol with error 1% and communication O …

Abstract Recently, Rubinstein, Schramm, and Weinberg [ITCS'18] gave an algorithm for
finding an exact global minimum cut of undirected graphs in the cut-query model in which …

We show an exponential gap between communication complexity and information
complexity by giving an explicit example of a partial boolean function with information …