52 citations · 106 across the 21 of their papers we have counts for
17 papers · 1 filter
Prefix Filter: Practically and Theoretically Better Than Bloom
Tomer Even, Guy Even, Adam Morrison
Many applications of approximate membership query data structures, or filters, require only an incremental filter that supports insertions but not deletions. However, the design sp…
A Dynamic Space-Efficient Filter with Constant Time Operations
Ioana Oriana Bercea, Guy Even
A dynamic dictionary is a data structure that maintains sets of cardinality at most from a given universe and supports insertions, deletions, and membership queries. A filter a…
A Space-Efficient Dynamic Dictionary for Multisets with Constant Time Operations
Ioana Oriana Bercea, Guy Even
We consider the dynamic dictionary problem for multisets. Given an upper bound on the total cardinality of the multiset (i.e., including multiplicities) at any point in time, t…
Upper Tail Analysis of Bucket Sort and Random Tries
Ioana O. Bercea, Guy Even
Bucket Sort is known to run in expected linear time when the input keys are distributed independently and uniformly at random in the interval . The analysis holds even when…
Fully-Dynamic Space-Efficient Dictionaries and Filters with Constant Number of Memory Accesses
Ioana O. Bercea, Guy Even
A fully-dynamic dictionary is a data structure for maintaining sets that supports insertions, deletions and membership queries. A filter approximates membership queries with a one-…
Survivable Network Design for Group Connectivity in Low-Treewidth Graphs
Parinya Chalermsook, Syamantak Das, Guy Even +2
In the Group Steiner Tree problem (GST), we are given a (vertex or edge)-weighted graph on vertices, a root vertex and a collection of groups $\{S_i\}_{i\in[h]}:…
Minimal Controllability of Conjunctive Boolean Networks is NP-Complete
Eyal Weiss, Michael Margaliot, Guy Even
Given a conjunctive Boolean network (CBN) with state-variables, we consider the problem of finding a minimal set of state-variables to directly affect with an input so that the…
Competitive Path Computation and Function Placement in SDNs
Guy Even, Moti Medina, Boaz Patt-Shamir
We consider a task of serving requests that arrive in an online fashion in Software-Defined Networks (SDNs) with network function virtualization (NFV). Each request specifies an ab…
A Constant Approximation Algorithm for Scheduling Packets on Line Networks
Guy Even, Moti Medina, Adi Rosén
In this paper we improve the approximation ratio for the problem of scheduling packets on line networks with bounded buffers, where the aim is that of maximizing the throughput. Ea…
Sublinear Random Access Generators for Preferential Attachment Graphs
Guy Even, Reut Levi, Moti Medina +1
We consider the problem of sampling from a distribution on graphs, specifically when the distribution is defined by an evolving graph model, and consider the time, space and random…
Better Online Deterministic Packet Routing on Grids
Guy Even, Moti Medina, Boaz Patt-Shamir
We consider the following fundamental routing problem. An adversary inputs packets arbitrarily at sources, each packet with an arbitrary destination. Traffic is constrained by link…
Online Packet-Routing in Grids with Bounded Buffers
Guy Even, Moti Medina
We present deterministic and randomized algorithms for the problem of online packet routing in grids in the competitive network throughput model \cite{AKOR}. In this model the netw…
Best of Two Local Models: Local Centralized and Local Distributed Algorithms
Guy Even, Moti Medina, Dana Ron
We consider two models of computation: centralized local algorithms and local distributed algorithms. Algorithms in one model are adapted to the other model to obtain improved algo…
A Nonmonotone Analysis with the Primal-Dual Approach: online routing of virtual circuits with unknown durations
Guy Even, Moti Medina
We address the question of whether the primal-dual approach for the design and analysis of online algorithms can be applied to nonmonotone problems. We provide a positive answer by…
Hitting Sets Online and Unique-Max Coloring
Guy Even, Shakhar Smorodinsky
We consider the problem of hitting sets online. The hypergraph (i.e., range-space consisting of points and ranges) is known in advance, and the ranges to be stabbed are input one-b…
Online Multi-Commodity Flow with High Demands
Guy Even, Moti Medina
This paper deals with the problem of computing, in an online fashion, a maximum benefit multi-commodity flow (\ONMCF), where the flow demands may be bigger than the edge capacities…
Multi-Hop Routing and Scheduling in Wireless Networks in the SINR model
Guy Even, Yakov Matsri, Moti Medina
We present an algorithm for multi-hop routing and scheduling of requests in wireless networks in the \sinr\ model. The goal of our algorithm is to maximize the throughput or maximi…