1 citations · 1 across the 3 of their papers we have counts for
3 papers
cs.CC2012★ 1 cited
Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings
Shiteng Chen, Elad Verbin, Wei Yu
In this paper we investigate the problem of building a static data structure that represents a string s using space close to its compressed size, and allows fast access to individu…
cs.CC2011
Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy
Jeff M. Phillips, Elad Verbin, Qin Zhang
In this paper we prove lower bounds on randomized multiparty communication complexity, both in the \emph{blackboard model} (where each message is written on a blackboard for all pl…
cs.DS2007
Sorting and Selection in Posets
Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel +2
Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study a more general setting, in which some pairs…