The Limits of Buffering: A Tight Lower Bound for Dynamic Membership in the External Memory Model

Autor: Qin Zhang, Elad Verbin

Publikováno v: STOC

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

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1496a1a1d44f678eaffdb2390f093f31
https://doi.org/10.1137/110842211

Surviving Rates of Graphs with Bounded Treewidth for the Firefighter Problem

Autor: Leizhen Cai, Yongxi Cheng, Yuan Zhou, Elad Verbin

Publikováno v: Cai, L, Cheng, Y, Verbin, E & Zhou, Y 2010, ' Surviving Rates of Graphs with Bounded Treewidth for the Firefighter Problem ', S I A M Journal on Discrete Mathematics, vol. 24, no. 4, pp. 1322-1335 . https://doi.org/10.1137/100791130

The firefighter problem is the following discrete-time game on a graph. Initially, a fire starts at a vertex of the graph. In each round, a firefighter protects one vertex not yet on fire, and then the fire spreads to all unprotected neighbors of the

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3b7b5c84a5afff0b772688fd09622fec
https://doi.org/10.1137/100791130

Sorting signed permutations by reversals, revisited

Autor: Haim Kaplan, Elad Verbin

Publikováno v: Journal of Computer and System Sciences. 70(3):321-341

The problem of sorting signed permutations by reversals (SBR) is a fundamental problem in computational molecular biology. The goal is, given a signed permutation, to find a shortest sequence of reversals that transforms it into the positive identity

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e54dc75c7db5b1a107fdfea8adc39239

Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy

Autor: Jeff M. Phillips, Qin Zhang, Elad Verbin

Publikováno v: Phillips, J, Verbin, E & Zhang, Q 2012, ' Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy ', The Annual A C M-S I A M Symposium on Discrete Algorithms. Proceedings, vol. 23, pp. 486-501 . < http://delivery.acm.org.ez.statsbiblioteket.dk:2048/10.1145/2100000/2095158/p486-phillips.pdf?ip=130.225.27.190&acc=ACTIVE%20SERVICE&CFID=163115493&CFTOKEN=91446070&__acm__=1356809475_fd9644b3144bb0145788980a11fea592 >

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 players to see) and (mainly) in the \emph{message-passing model}, where

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d5bde244c5ee3c6f80c7dca9d483a6c6
https://pure.au.dk/portal/da/publications/lower-bounds-for-numberinhand-multiparty-communication-complexity-made-easy(50a53703-6c08-42ca-a9eb-d2dc61f8cf7f).html

Approximating the Minmax Value of Three-Player Games within a Constant is as Hard as Detecting Planted Cliques

Autor: Elad Verbin, Kord Eickmeyer, Kristoffer Arnstfelt Hansen

Publikováno v: Algorithmic Game Theory ISBN: 9783642339950
SAGT

We consider the problem of approximating the minmax value of a multi-player game in strategic form. We argue that in three-player games with 0-1 payoffs, approximating the minmax value within an additive constant smaller than ξ/2, where $\xi = \frac

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::6d014f191461aa584c46453b3de3db82
https://doi.org/10.1007/978-3-642-33996-7_9