NDLI: The topology of wireless communication

Please wait, while we are loading the content...

The power of simple tabulation hashing

Quantum one-way communication can be exponentially stronger than classical communication

Cover times, blanket times, and majorizing measures

The equivalence of the random oracle model and the ideal cipher model, revisited

On optimal single-item auctions

Towards coding for maximum errors in interactive communication

Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm

Moser and tardos meet Lovász

Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs

An algorithm for the graph crossing number problem

The computational complexity of linear optics

Distributed verification and hardness of distributed approximation

An LLL-reduction algorithm with quasi-linear time complexity: extended abstract

Contraction decomposition in h-minor-free graphs and algorithmic applications

On the complexity of powering in finite fields

Mechanisms for (mis)allocating scientific credit

Don't rush into a union: take time to find your roots

Online bipartite matching with unknown distributions

K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance

Schaefer's theorem for graphs

Constant round non-malleable protocols using one way functions

Fast moment estimation in data streams in optimal space

Submodular function maximization via the multilinear relaxation and contention resolution schemes

Tight bounds for parallel randomized load balancing: extended abstract

Strong direct product theorems for quantum communication and query complexity

A general framework for graph sparsification

Separating succinct non-interactive arguments from all falsifiable assumptions

Optimal auctions with correlated bidders are easy

High-rate codes with sublinear-time decoding

Exact algorithms for solving stochastic games: extended abstract

A full derandomization of schöning's k-SAT algorithm

Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

Improved algorithms for min cut and max flow in undirected planar graphs

A quasipolynomial-time algorithm for the quantum separability problem

Linearizable implementations do not suffice for randomized distributed computation

NP-hardness of approximately solving linear equations over reals

A simpler algorithm and shorter proof for the graph minor decomposition

Almost settling the hardness of noncommutative determinant

Inner product spaces for MinSum coordination mechanisms

A unified framework for approximating and clustering data

Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs

Breaking the $k^{2}$ barrier for explicit RIP matrices

Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP

Constant-round non-malleable commitments from any one-way function

Subspace embeddings for the $L_{1}-norm$ with applications

Learning submodular functions

Social networks spread rumors in sublogarithmic time

An optimal lower bound on the communication complexity of gap-hamming-distance

Breaking $o(n^{1/2})-approximation$ algorithms for the edge-disjoint paths problem with congestion two

Limits of provable security from standard assumptions

An impossibility result for truthful combinatorial auctions with submodular valuations

From affine to two-source extractors via approximate duality

Dueling algorithms

Pseudorandom generators for combinatorial shapes

Analyzing network coding gossip made easy

Directed spanners via flow-based linear programs

Parallel repetition of entangled games

The topology of wireless communication

Black-box identity testing of depth-4 multilinear circuits

Multicut is FPT

Geometric complexity theory and tensor rank

Mechanism design with uncertain inputs: (to err is human, to forgive divine)

Approximate polytope membership queries

Almost tight bounds for reordering buffer management

Deterministic construction of a high dimensional $l_{p}$ section in $l_{1}^{n}$ for any p<2

Every property of hyperfinite graphs is testable

Secure computation with information leaking to an adversary

Near-optimal distortion bounds for embedding doubling spaces into $L_{1}$

Privately releasing conjunctions and the statistical query barrier

From convex optimization to randomized mechanisms: toward optimal combinatorial auctions

Correlation testing for affine invariant properties on $F_{p}^{n}$ in the high error regime

Pareto optimal solutions for smoothed analysts

Pseudorandom generators for group products: extended abstract

Optimal path search in small worlds: dimension matters

Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter

Fixed-parameter tractability of multicut parameterized by the size of the cutset

Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes

Santa Claus schedules jobs on unrelated machines

Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs

How to leak on key updates

From low-distortion norm embeddings to explicit uncertainty relations and efficient information locking

Privacy-preserving statistical estimation with optimal convergence rates

Finding topological subgraphs is fixed-parameter tractable

Near-optimal private approximation protocols via a black box transformation

The topology of wireless communication

Content Provider	ACM Digital Library
Author	Parter, Merav Kantor, Erez Peleg, David Lotker, Zvi
Abstract	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 reception map. In the SINR model, the resulting SINR diagram partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. SINR diagrams have been studied in [3] for the specific case where all stations use the same power. It is shown that the reception zones are convex (hence connected) and fat, and this is used to devise an efficient algorithm for the fundamental problem of point location. Here we consider the more general (and common) 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 for the non-uniform setting, as well as the theoretical challenge of understanding the geometry of SINR diagrams (e.g., the maximal number of connected components they might have). We achieve several results in both directions. We establish a form of weaker convexity in the case where stations are aligned on a line and use this to derive a tight bound on the number of connected components in this case. In addition, one of our key results concerns the behavior of a (d+1)-dimensional map, i.e., a map in one dimension higher than the dimension in which stations are embedded. Specifically, although the d-dimensional map might be highly fractured, drawing the map in one dimension higher "heals" the zones, which become connected (in fact hyperbolically 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. This is done through an analysis technique based on looking at the behavior of systems composed on lines of densely placed weak stations, as the number of stations tends to infinity, keeping their total transmission energy fixed. Finally, we turn to consider algorithmic applications, and propose a new variant of approximate point location.
Starting Page	383
Ending Page	392
Page Count	10
File Format	PDF MP4
ISBN	9781450306911
DOI	10.1145/1993636.1993688
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-06-06
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Wireless network Sinr
Content Type	Audio Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in