3 citations · 12 across the 19 of their papers we have counts for
14 papers · 1 filter
Distributed Testing of Graph Isomorphism in the CONGEST model
Reut Levi, Moti Medina
In this paper we study the problem of testing graph isomorphism (GI) in the CONGEST distributed model. In this setting we test whether the distributive network, , is isomorphi…
Small Hazard-free Transducers
Johannes Bund, Christoph Lenzen, Moti Medina
Ikenmeyer et al. (JACM'19) proved an unconditional exponential separation between the hazard-free complexity and (standard) circuit complexity of explicit functions. This raises th…
Graph Ranking and the Cost of Sybil Defense
Gwendolyn Farach-Colton, Martin Farach-Colton, Leslie Ann Goldberg +5
Ranking functions such as PageRank assign numeric values (ranks) to nodes of graphs, most notably the web graph. Node rankings are an integral part of Internet search algorithms, s…
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…
Non-Local Probes Do Not Help with Graph Problems
Mika Göös, Juho Hirvonen, Reut Levi +2
This work bridges the gap between distributed and centralised models of computing in the context of sublinear-time graph algorithms. A priori, typical centralised models of computi…
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…
Improved Approximation for Orienting Mixed Graphs
Iftah Gamzu, Moti Medina
An instance of the maximum mixed graph orientation problem consists of a mixed graph and a collection of source-target vertex pairs. The objective is to orient the undirected edges…
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…