Enav Weinreb

TCS Journal 2011 Journal Article

Partition arguments in multiparty communication complexity

• Jan Draisma
• Eyal Kushilevitz
• Enav Weinreb

Consider the “Number in Hand” multiparty communication complexity model, where k players holding inputs x 1, …, x k ∈ { 0, 1 } n communicate to compute the value f ( x 1, …, x k ) of a function f known to all of them. The main lower bound technique for the communication complexity of such problems is that of partition arguments: partition the k players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem. In this paper, we study the power of partition arguments. Our two main results are very different in nature: (i) For randomized communication complexity, we show that partition arguments may yield bounds that are exponentially far from the true communication complexity. Specifically, we prove that there exists a 3 -argument function f whose communication complexity is Ω ( n ), while partition arguments can only yield an Ω ( log n ) lower bound. The same holds for nondeterministiccommunication complexity. (ii) For deterministic communication complexity, we prove that finding significant gaps between the true communication complexity and the best lower bound that can be obtained via partition arguments, would imply progress on a generalized version of the “log-rank conjecture” in communication complexity. We also observe that, in the case of computing relations (search problems), very large gaps do exist. We conclude with two results on the multiparty “fooling set technique”, another method for obtaining communication complexity lower bounds.

STOC Conference 2009 Conference Paper

On the complexity of communication complexity

• Eyal Kushilevitz
• Enav Weinreb

FOCS Conference 2009 Conference Paper

The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection

• Eyal Kushilevitz
• Enav Weinreb

In this paper, we analyze the following communication complexity problem. It is a variant of the set-disjointness problem, denoted PDISJ log N, where each of Alice and Bob gets as an input a subset of [N] of size at most log N, with the promise that the intersection of the two subsets is of size at most 1. We provide an almost tight lower bound of ¿¿(log 2 N) on the deterministic communication complexity of the problem. The main motivation for studying this problem comes from the so-called "clique vs. independent-set" problem, introduced by Yannakakis (1988). Proving an ¿(log 2 N) lower bound on the communication complexity of the clique vs. independent-set problem for all graphs is a long standing open problem with various implications. Proving such a lower bound for random graphs is also open. In such a graph, both the cliques and the independent sets are of size O(log N) (and obviously their intersection is of size at most 1). Hence, our ¿¿(log 2 N) lower bound for PDISJ log N can be viewed as a first step in this direction. Interestingly, we note that standard lower bound techniques cannot yield the desired lower bound. Hence, we develop a novel adversary argument that may find other applications.

STOC Conference 2008 Conference Paper

Communication in the presence of replication

• Omer Barkol
• Yuval Ishai
• Enav Weinreb

We consider the following problem. Suppose that a big amount of data is distributed among several parties, so that each party misses only few pieces of data. The parties wish to perform some global computation on the data while minimizing the communication between them. This situation is common in many real-life scenarios. A naive solution to this problem is to first perform a synchronization step, letting one party learn all pieces of data, and then let this party perform the required computation locally. We study the question of obtaining better solutions to the problem, focusing mainly on the case of computing low-degree polynomials via non-interactive protocols. We present interesting connections between this problem and the well studied cryptographic problem of secret sharing. We use this connection to obtain nontrivial upper bounds and lower bounds using results and techniques from the domain of secret sharing. The relation with open problems from the area of secret sharing also provides evidence for the difficulty of resolving some of the questions we leave open.

STOC Conference 2006 Conference Paper

Private approximation of search problems

• Amos Beimel
• Paz Carmi
• Kobbi Nissim
• Enav Weinreb

Many approximation algorithms have been presented in the last decades for hard search problems. The focus of this paper is on cryptographic applications, where it is desired to design algorithms which do not leak unnecessary information. Specifically, we are interested in private approximation algorithms -- efficient algorithms whose output does not leak information not implied by the optimal solutions to the search problems. Privacy requirements add constraints on the approximation algorithms; in particular, known approximation algorithms usually leak a lot of information.For functions, [Feigenbaum et al., ICALP 2001] presented a natural requirement that a private algorithm should not leak information not implied by the original function. Generalizing this requirement to search problems is not straightforward as an input may have many different outputs. We present a new definition that captures a minimal privacy requirement from such algorithms -- applied to an input instance, it should not leak any information that is not implied by its collection of exact solutions . Although our privacy requirement seems minimal, we show that for well studied problems, as vertex cover and 3SAT, private approximation algorithms are unlikely to exist even for poor approximation ratios. Similar to [Halevi et al., STOC 2001], we define a relaxed notion of approximation algorithms that leak (little) information, and demonstrate the applicability of this notion by showing near optimal approximation algorithms for 3SAT that leak little information.

FOCS Conference 2003 Conference Paper

Separating the Power of Monotone Span Programs over Different Fields

• Amos Beimel
• Enav Weinreb

Monotone span programs are a linear-algebraic model of computation. They are equivalent to linear secret sharing schemes and have various applications in cryptography and complexity. A fundamental question is how the choice of the field in which the algebraic operations are performed effects the power of the span program. In this paper we prove that the power of monotone span programs over finite fields of different characteristics is incomparable; we show a super-polynomial separation between any two fields with different characteristics, answering an open problem of Pudlak and Sgall (1998). Using this result we prove a super-polynomial lower bound for monotone span programs for a function in uniform - /spl Nscr/; /spl Cscr/; /sup 2/ (and therefore in /spl Pscr/;), answering an open problem of Babai, Wigderson, and Gal (1999). Finally, we show that quasi-linear schemes, a generalization of linear secret sharing schemes introduced in Beimel and Ishai (2001), are stronger than linear secret sharing schemes. In particular, this proves, without any assumptions, that non-linear secret sharing schemes are more efficient than linear secret sharing schemes.