BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Erez Kantor

Erez Kantor contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingNetworking and Internet ArchitectureComputational GeometryInformation Theorymath.ITNumerical Analysis

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
7topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2015arXiv

Computing in Additive Networks with Bounded-Information Codes

This paper studies the theory of the additive wireless network model, in which the received signal is abstracted as an addition of the transmitted signals. Our central observation is that the crucial challenge for computing in this model is not high contention, as assumed previously, but rather guaranteeing a bounded amount of \emph{information} in each neighborhood per round, a property that we show is achievable using a new random coding technique. Technically, we provide efficient algorithms for fundamental distributed tasks in additive networks, such as solving various symmetry breaking problems, approximating network parameters, and solving an \emph{asymmetry revealing} problem such as computing a maximal input. The key method used is a novel random coding technique that allows a node to successfully decode the received information, as long as it does not contain too many distinct values. We then design our algorithms to produce a limited amount of information in each neighborhood in order to leverage our enriched toolbox for computing in additive networks.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Optimal competitiveness for the Rectilinear Steiner Arborescence problem

We present optimal online algorithms for two related known problems involving Steiner Arborescence, improving both the lower and the upper bounds. One of them is the well studied continuous problem of the {\em Rectilinear Steiner Arborescence} ($RSA$). We improve the lower bound and the upper bound on the competitive ratio for $RSA$ from $O(\log N)$ and $Ω(\sqrt{\log N})$ to $Θ(\frac{\log N}{\log \log N})$, where $N$ is the number of Steiner points. This separates the competitive ratios of $RSA$ and the Symetric-$RSA$, two problems for which the bounds of Berman and Coulston is STOC 1997 were identical. The second problem is one of the Multimedia Content Distribution problems presented by Papadimitriou et al. in several papers and Charikar et al. SODA 1998. It can be viewed as the discrete counterparts (or a network counterpart) of $RSA$. For this second problem we present tight bounds also in terms of the network size, in addition to presenting tight bounds in terms of the number of Steiner points (the latter are similar to those we derived for $RSA$).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Multi-Message Broadcast with Abstract MAC Layers and Unreliable Links

We study the multi-message broadcast problem using abstract MAC layer models of wireless networks. These models capture the key guarantees of existing MAC layers while abstracting away low-level details such as signal propagation and contention. We begin by studying upper and lower bounds for this problem in a {\em standard abstract MAC layer model}---identifying an interesting dependence between the structure of unreliable links and achievable time complexity. In more detail, given a restriction that devices connected directly by an unreliable link are not too far from each other in the reliable link topology, we can (almost) match the efficiency of the reliable case. For the related restriction, however, that two devices connected by an unreliable link are not too far from each other in geographic distance, we prove a new lower bound that shows that this efficiency is impossible. We then investigate how much extra power must be added to the model to enable a new order of magnitude of efficiency. In more detail, we consider an {\em enhanced abstract MAC layer model} and present a new multi-message broadcast algorithm that (under certain natural assumptions) solves the problem in this model faster than any known solutions in an abstract MAC layer setting.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Generalized Perron--Frobenius Theorem for Nonsquare Matrices

The celebrated Perron--Frobenius (PF) theorem is stated for irreducible nonnegative square matrices, and provides a simple characterization of their eigenvectors and eigenvalues. The importance of this theorem stems from the fact that eigenvalue problems on such matrices arise in many fields of science and engineering, including dynamical systems theory, economics, statistics and optimization. However, many real-life scenarios give rise to nonsquare matrices. A natural question is whether the PF Theorem (along with its applications) can be generalized to a nonsquare setting. Our paper provides a generalization of the PF Theorem to nonsquare matrices. The extension can be interpreted as representing client-server systems with additional degrees of freedom, where each client may choose between multiple servers that can cooperate in serving it (while potentially interfering with other clients). This formulation is motivated by applications to power control in wireless networks, economics and others, all of which extend known examples for the use of the original PF Theorem. We show that the option of cooperation between servers does not improve the situation, in the sense that in the optimal solution no cooperation is needed, and only one server needs to serve each client. Hence, the additional power of having several potential servers per client translates into \emph{choosing} the best single server and not into \emph{sharing} the load between the servers in some way, as one might have expected. The two main contributions of the paper are (i) a generalized PF Theorem that characterizes the optimal solution for a non-convex nonsquare problem, and (ii) an algorithm for finding the optimal solution in polynomial time.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Optimal competitiveness for Symmetric Rectilinear Steiner Arborescence and related problems

We present optimal competitive algorithms for two interrelated known problems involving Steiner Arborescence. One is the continuous problem of the Symmetric Rectilinear Steiner Arborescence (SRSA), studied by Berman and Coulston. A very related, but discrete problem (studied separately in the past) is the online Multimedia Content Delivery (MCD) problem on line networks, presented originally by Papadimitriu, Ramanathan, and Rangan. An efficient content delivery was modeled as a low cost Steiner arborescence in a grid of network*time they defined. We study here the version studied by Charikar, Halperin, and Motwani (who used the same problem definitions, but removed some constraints on the inputs). The bounds on the competitive ratios introduced separately in the above papers are similar for the two problems: O(log N) for the continuous problem and O(log n) for the network problem, where N was the number of terminals to serve, and n was the size of the network. The lower bounds were Omega(sqrt{log N}) and Omega(sqrt{log n}) correspondingly. Berman and Coulston conjectured that both the upper bound and the lower bound could be improved. We disprove this conjecture and close these quadratic gaps for both problems. We first present an O(sqrt{log n}) deterministic competitive algorithm for MCD on the line, matching the lower bound. We then translate this algorithm to become a competitive optimal algorithm O(sqrt{log N}) for SRSA. Finally, we translate the latter back to solve MCD problem, this time competitive optimally even in the case that the number of requests is small (that is, O(min{sqrt{log n},sqrt{log N}})). We also present a Omega(sqrt[3]{log n}) lower bound on the competitiveness of any randomized algorithm. Some of the techniques may be useful in other contexts.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

SINR Diagram with Interference Cancellation

In this paper we study the reception zones of a wireless network in the SINR model with receivers that employ \emph{interference cancellation} (IC), a technique that allows a receiver to decode interfering signals, and \emph{cancel} them from the received signal in order to decode its intended message. We first derive some important topological properties of the diagram describing the reception zones and their connections to \emph{high-order Voronoi diagrams} and other related geometric objects. We then discuss the computational issues that arise when seeking an efficient description of the zones. Our main fundamental result states that although potentially there are exponentially many possible cancellation orderings (and consequently reception cells), in fact there are much fewer nonempty such cells. We prove a (tight) linear bound on the number of cells and provide a polynomial time algorithm to describe the diagram. Moreover, we introduce a novel measure, referred to as the \emph{Compactness Parameter}, which influences the tightness of our bounds. We then utilize the properties established for reception diagrams to devise a logarithmic time algorithm for answering \emph{point-location} queries for networks with IC.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Topology of Wireless Communication

In this paper we study the topological properties of wireless communication maps and their usability in algorithmic design. We consider the SINR model, which compares the received power of a signal at a receiver against the sum of strengths of other interfering signals plus background noise. To describe the behavior of a multi-station network, we use the convenient representation of a \emph{reception map}. In the SINR model, the resulting \emph{SINR diagram} partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. We consider the general case where transmission energies are arbitrary (or non-uniform). Under that setting, the reception zones are not necessarily convex or even connected. This poses the algorithmic challenge of designing efficient point location techniques as well as the theoretical challenge of understanding the geometry of SINR diagrams. We achieve several results in both directions. We establish a form of weaker convexity in the case where stations are aligned on a line. In addition, one of our key results concerns the behavior of a $(d+1)$-dimensional map. Specifically, although the $d$-dimensional map might be highly fractured, drawing the map in one dimension higher "heals" the zones, which become connected. In addition, as a step toward establishing a weaker form of convexity for the $d$-dimensional map, we study the interference function and show that it satisfies the maximum principle. Finally, we turn to consider algorithmic applications, and propose a new variant of approximate point location.

0 citations0 reviewsNo code linkedOpen access