Elad Verbin

SODA Conference 2012 Conference Paper

Lower bounds for number-in-hand multiparty communication complexity, made easy

• Jeff M. Phillips
• Elad Verbin
• Qin Zhang 0001

SODA Conference 2011 Conference Paper

The Streaming Complexity of Cycle Counting, Sorting by Reversals, and Other Problems

• Elad Verbin
• Wei Yu 0007

In this paper we introduce a new technique for proving streaming lower bounds (and one-way communication lower bounds), by reductions from a problem called the Boolean Hidden Hypermatching problem (BHH). BHH is a generalization of the well-known Boolean Hidden Matching problem, which was used by Gavinsky et al. to prove an exponential separation between quantum communication complexity and one-way randomized communication complexity. We are the first to introduce BHH, and to prove a lower bound for it. The hardness of the BHH problem is inherently one-way: it is easy to solve BHH using logarithmic two-way communication, but it requires √ n communication if Alice is only allowed to send messages to Bob, and not vice-versa. This one-wayness allows us to prove lower bounds, via reductions, for streaming problems and related communication problems whose hardness is also inherently one-way. By designing reductions from BHH, we prove lower bounds for the streaming complexity of approximating the sorting by reversal distance, of approximately counting the number of cycles in a 2-regular graph, and of other problems. For example, here is one lower bound that we prove, for a cycle-counting problem: Alice gets a perfect matching E A on a set of n nodes, and Bob gets a perfect matching E B on the same set of nodes. The union E A ∪ E B is a collection of cycles, and the goal is to approximate the number of cycles in this collection. We prove that if Alice is allowed to send o (√ n ) bits to Bob (and Bob is not allowed to send anything to Alice), then the number of cycles cannot be approximated to within a factor of 1. 999, even using a randomized protocol. We prove that it is not even possible to distinguish the case where all cycles are of length 4, from the case where all cycles are of length 8. This lower bound is “natively” one-way: With 4 rounds of communication, it is easy to distinguish these two cases.

FOCS Conference 2010 Conference Paper

The Coin Problem and Pseudorandomness for Branching Programs

• Joshua Brody
• Elad Verbin

The Coin Problem is the following problem: a coin is given, which lands on head with probability either 1/2 + β or 1/2 - β. We are given the outcome of n independent tosses of this coin, and the goal is to guess which way the coin is biased, and to answer correctly with probability ≥ 2/3. When our computational model is unrestricted, the majority function is optimal, and succeeds when β ≥ c/√n for a large enough constant c. The coin problem is open and interesting in models that cannot compute the majority function. In this paper we study the coin problem in the model of read-once width-w branching programs. We prove that in order to succeed in this model, β must be at least 1/(log n) Θ(ω). For constant w this is tight by considering the recursive tribes function, and for other values of w this is nearly tight by considering other read-once AND-OR trees. We generalize this to a Dice Problem, where instead of independent tosses of a coin we are given independent tosses of one of two m-sided dice. We prove that if the distributions are too close and the mass of each side of the dice is not too small, then the dice cannot be distinguished by small-width read-once branching programs. We suggest one application for this kind of theorems: we prove that Nisan's Generator fools width-w read-once regular branching programs, using seed length O (ω 4 log n log log n + log n log(1/ε)). For ω = ε = Θ(1), this seedlength is O (log n log log n). The coin theorem and its relatives might have other connections to PRGs. This application is related to the independent, but chronologically-earlier, work of Braverman, Rao, Raz and Yehudayoff.

STOC Conference 2010 Conference Paper

The limits of buffering: a tight lower bound for dynamic membership in the external memory model

• Elad Verbin
• Qin Zhang 0001

We study the dynamic membership (or dynamic dictionary) problem, which is one of the most fundamental problems in data structures. We study the problem in the external memory model with cell size b bits and cache size m bits. We prove that if the amortized cost of updates is at most 0.999 (or any other constant < 1), then the query cost must be (log b log n (n/m)), where n is the number of elements in the dictionary. In contrast, when the update time is allowed to be 1 + o (1), then a bit vector or hash table give query time O (1). Thus, this is a threshold phenomenon for data structures . This lower bound answers a folklore conjecture of the external memory community. Since almost any data structure task can solve membership, our lower bound implies a dichotomy between two alternatives: ( i ) make the amortized update time at least 1 (so the data structure does not buffer, and we lose one of the main potential advantages of the cache), or ( ii ) make the query time at least roughly logarithmic in n . Our result holds even when the updates and queries are chosen uniformly at random and there are no deletions; it holds for randomized data structures, holds when the universe size is O( n ), and does not make any restrictive assumptions such as indivisibility . All of the lower bounds we prove hold regardless of the space consumption of the data structure, while the upper bounds only need linear space. The lower bound has some striking implications for external memory data structures. It shows that the query complexities of many problems such as 1D-range counting, predecessor, rank-select, and many others, are all the same in the regime where the amortized update time is less than 1, as long as the cell size is large enough ( b = polylog ( n ) suffices). The proof of our lower bound is based on a new combinatorial lemma called the Lemma of Surprising Intersections (LOSI) which allows us to use a proof methodology where we first analyze the intersection structure of the positive queries by using encoding arguments, and then use statistical arguments to deduce properties of the intersection structure of all queries, even the negative ones. In most other data structure arguments that we know, it is difficult to argue anything about the negative queries. Therefore we believe that the LOSI and this proof methodology might find future uses for other problems.

FOCS Conference 2009 Conference Paper

Distance Oracles for Sparse Graphs

• Christian Sommer 0001
• Elad Verbin
• Wei Yu 0007

Thorup and Zwick, in their seminal work, introduced the approximate distance oracle, which is a data structure that answers distance queries in a graph. For any integer k, they showed an efficient algorithm to construct an approximate distance oracle using space O(kn 1+1/k ) that can answer queries in time O(k) with a distance estimate that is at most ¿ = 2k-1 times larger than the actual shortest distance (this ratio is called the stretch). They proved that, under a combinatorial conjecture, their data structure is optimal in terms of space: if a stretch of at most 2k-1 is desired, then the space complexity is at least n 1+1/k. Their proof holds even if infinite query time is allowed: it is essentially an "incompressibility" result. Also, the proof only holds for dense graphs, and the best bound it can prove only implies that the size of the data structure is lower bounded by the number of edges of the graph. Naturally, the following question arises: what happens for sparse graphs? In this paper we give a new lower bound for approximate distance oracles in the cell-probe model. This lower bound holds even for sparse (polylog(n)-degree) graphs, and it is not an "incompressibility" bound: we prove a three-way tradeoff between space, stretch, and query time. We show that when the query time is t and the stretch is ¿, then the space S must be S ¿ n 1+¿(1/t¿) /lg n. This lower bound follows by a reduction from lopsided set disjointness to distance oracles, based on and motivated by recent work of Patrascu. Our results in fact show that for any high-girth regular graph, an approximate distance oracle that supports efficient queries for all subgraphs of G must obey this tradeoff. We also prove some lemmas that count sets of paths in high-girth regular graphs and high-girth regular expanders, which might be of independent interest.

SODA Conference 2009 Conference Paper

Sorting and selection in posets

• Constantinos Daskalakis
• Richard M. Karp
• Elchanan Mossel
• Samantha J. Riesenfeld
• Elad Verbin

Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study these problems in the context of partially ordered sets, in which some pairs of objects are incomparable. This generalization is interesting from a combinatorial perspective, and it has immediate applications in ranking scenarios where there is no underlying linear ordering, e. g. , conference submissions. It also has applications in reconstructing certain types of networks, including biological networks. Our results represent significant progress over previous results from two decades ago by Faigle and Turán. In particular, we present the first algorithm that sorts a width- w poset of size n with optimal query complexity O ( n ( w + log n )). We also describe a variant of Mergesort with query complexity and total complexity; an algorithm with the same query complexity was given by Faigle and Turán, but no efficient implementation of that algorithm is known. Both our sorting algorithms can be applied with negligible overhead to the more general problem of reconstructing transitive relations. We also consider two related problems: finding the minimal elements, and its generalization to finding the bottom k “levels”, called the k-selection problem. We give efficient deterministic and randomized algorithms for finding the minimal elements with O ( wn ) query and total complexity. We provide matching lower bounds for the query complexity up to a factor of 2 and generalize the results to the k -selection problem. Finally, we present efficient algorithms for computing a linear extension of a poset and computing the heights of all elements.

STOC Conference 2008 Conference Paper

On agnostic boosting and parity learning

• Adam Tauman Kalai
• Yishay Mansour
• Elad Verbin

The motivating problem is agnostically learning parity functions, i.e., parity with arbitrary or adversarial noise. Specifically, given random labeled examples from an *arbitrary* distribution, we would like to produce an hypothesis whose accuracy nearly matches the accuracy of the best parity function. Our algorithm runs in time 2 O(n/log n) , which matches the best known for the easier cases of learning parities with random classification noise (Blum et al, 2003) and for agnostically learning parities over the uniform distribution on inputs (Feldman et al, 2006).

TCS Journal 2007 Journal Article

A simpler analysis of Burrows–Wheeler-based compression

• Haim Kaplan
• Shir Landau
• Elad Verbin

In this paper, we present a new technique for worst-case analysis of compression algorithms which are based on the Burrows–Wheeler Transform. We mainly deal with the algorithm proposed by Burrows and Wheeler in their first paper on the subject [M. Burrows, D. J. Wheeler, A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, Palo Alto, California, 1994], called bw0. This algorithm consists of the following three essential steps: (1) Obtain the Burrows–Wheeler Transform of the text, (2) Convert the transform into a sequence of integers using the move-to-front algorithm, (3) Encode the integers using Arithmetic code or any order-0 encoding (possibly with run-length encoding). We achieve a strong upper bound on the worst-case compression ratio of this algorithm. This bound is significantly better than bounds known to date and is obtained via simple analytical techniques. Specifically, we show that for any input string s, and μ > 1, the length of the compressed string is bounded by μ ⋅ | s | H k ( s ) + log ( ζ ( μ ) ) ⋅ | s | + μ g k + O ( log n ) where H k is the k th order empirical entropy, g k is a constant depending only on k and on the size of the alphabet, and ζ ( μ ) = 1 1 μ + 1 2 μ + ⋯ is the standard zeta function. As part of the analysis, we prove a result on the compressibility of integer sequences, which is of independent interest. Finally, we apply our techniques to prove a worst-case bound on the compression ratio of a compression algorithm based on the Burrows–Wheeler Transform followed by distance coding, for which worst-case guarantees have never been given. We prove that the length of the compressed string is bounded by 1. 7286 ⋅ | s | H k ( s ) + g k + O ( log n ). This bound is better than the bound we give for bw0.

SODA Conference 2007 Conference Paper

Counting colors in boxes

• Haim Kaplan
• Natan Rubin
• Micha Sharir
• Elad Verbin