In this paper, we propose two algorithms for identifying entry gates for Points of Interest (PoIs) using polygon representations of the PoIs (PoI polygons) and the Global Positioning System (GPS) trajectories of the Delivery Partners (DPs) obtained from their smartphones in the context of online food delivery platforms. PoIs include residential complexes, office complexes, and educational institutes where customers can order from. Identifying entry gates of PoIs helps avoid delivery hassles by routing the DPs to the nearest entry gates for customers within the PoIs. The DPs mark 'reached' on their smartphone applications when they reach the entry gate or the parking spot of the PoI. However, it is not possible to ensure compliance, and the 'reached' locations are dispersed throughout the PoI. The first algorithm is based on density-based clustering of GPS traces where the DPs mark 'reached'. The clusters that overlap with the PoI polygon as measured by a metric that we propose, namely Cluster Fraction in Polygon (CFIP), are declared as entry gate clusters. The second algorithm obtains the entry gate clusters as density-based clustering of intersections of GPS trajectories of the DPs with the PoI polygon edges. The entry gates are obtained as median centroids of the entry gate clusters for both the algorithms which are then snapped to the nearest polygon edge in the case of the first algorithm. We evaluate the algorithms for a few thousand PoIs across 9 large cities in India using appropriately defined precision and recall metrics. For single-gate PoIs, we obtain a mean precision of 84%, a mean recall of 77%, and an average haversine distance error of 14.7 meters for the first algorithm. For the second algorithm, the mean precision is the same as the first algorithm while the recall obtained is 78% and the average haversine distance error is 14.3 meters. The algorithmically identified gates were evaluated by manual validation. To the best of our knowledge, this is the first published work with metrics that solves for a ''last-last mile" entity of digital maps for India, i.e., the entry gates.

This paper deals with an abstraction of a unified problem of drug discovery and pathogen identification. Pathogen identification involves the identification of disease-causing biomolecules. Drug discovery involves finding chemical compounds, called lead compounds, that bind to pathogenic proteins and eventually inhibit the function of the protein. In this paper, the lead compounds are abstracted as inhibitors, pathogenic proteins as defectives, and the mixture of “ineffective” chemical compounds and non-pathogenic proteins as normal items. A defective could be immune to the presence of an inhibitor in a test. So, a test containing a defective is positive if it does not contain its “associated” inhibitor. The goal of this paper is to identify the defectives, inhibitors, and their “associations” with high probability, or in other words, learn the immune defectives graph (IDG) efficiently through group tests. We propose a probabilistic non-adaptive pooling design, a probabilistic two-stage adaptive pooling design, and decoding algorithms for learning the IDG. For the two-stage adaptive-pooling design, we show that the sample complexity of the number of tests required to guarantee recovery of the inhibitors, defectives, and their associations with high probability, i.e., the upper bound, exceeds the proposed lower bound by a logarithmic multiplicative factor in the number of items. To be precise, lower and upper bounds of Ω((r + d) log n + rd) and O(rd log n) tests, respectively, are identified for classifying r inhibitors and d defectives amongst n items, and identifying their associations. For the nonadaptive pooling design, we show that the upper bound (given by O((r + d)2log n) tests) exceeds the proposed lower bound (given by max{Q((r + d)logn + rd), Ω((r2/log r) log n), Ω(d2)} tests) by at most a logarithmic multiplicative factor in the number of items.

This paper abstracts the unified problem of drug discovery and pathogen identification as an inhibitor-defective classification problem and learning of “association pattern” between the inhibitors and defectives. We refer to the “association graph” between the inhibitors and defectives as the Immune-Defectives Graph (IDG). Here, the expression of a defective might be inhibited by a subset of the inhibitors rather than all the inhibitors as in the well-known 1-inhibitor model. A test containing a defective is positive iff it does not contain its associated inhibitor. The goal of this paper is to identify the defectives, inhibitors, and their “associations” with high probability, or in other words, learn the IDG using group tests. We propose a probabilistic non-adaptive pooling design, a probabilistic two-stage adaptive pooling design and decoding algorithms for learning the IDG. The sample complexity of the number of tests required for the proposed two-stage adaptive pooling design is shown to be close to the lower bound, while that for the proposed non-adaptive pooling design is close to the lower bound in the large inhibitor regime.

It is well known that the interference alignment (IA) based transmission scheme proposed by Jafar and Shamai achieves the 4M over 3 sum-degrees of freedom (DoF) of the twotransmitter, two-receiver multiple-input multiple-output (MIMO) X-Network with M antennas at each node, referred to as the (2 × 2, M) X-Network. The Jafar-Shamai scheme assumes the availability of “global” channel-state-information at the transmitter (CSIT). “Local” CSIT based transmission schemes that couple IA with space-time block codes (STBC) in order to achieve the sum-DoF of the (2 × 2, M) X-Network are known specifically for M = 2; 3; 4. Further, these schemes have been proven to guarantee a diversity gain of M when finite-sized input constellations are employed. In this paper, an explicit transmission scheme that achieves the 4M over 3 sum-DoF of the (2 × 2, M) X-Network, for arbitrary M, is presented. The proposed scheme needs only local CSIT unlike the Jafar-Shamai scheme. In addition, it is shown analytically that the proposed scheme guarantees a diversity gain of M + 1 when finite-sized input constellations are employed.

Group testing with inhibitors (GTI) introduced by Farach at al. is studied in this paper. There are three types of items, d defectives, r inhibitors and n−d−r normal items in a population of n items. The presence of any inhibitor in a test can prevent the expression of a defective. For this model, we propose a probabilistic non-adaptive pooling design with a low complexity decoding algorithm. We show that the sample complexity of the number of tests required for guaranteed recovery with vanishing error probability using the proposed algorithm scales as T = O(d log n) and equation in the regimes r = O(d) and d = o(r) respectively. In the former regime, the number of tests meets the lower bound order while in the latter regime, the number of tests is shown to exceed the lower bound order by a log r over d multiplicative factor. The decoding complexity of the proposed decoding algorithm scales as O(nT).

Interference alignment is known to achieve the maximum sum DoF of 4M/3 in the 2 × 2 X-Network (i.e., two-transmitter (Tx) two-receiver (Rx) X-Network) with M antennas at each node, as demonstrated by Jafar and Shamai. Recently, an Alamouti code based transmission scheme, which we call the Li-Jafarkhani-Jafar (LJJ) scheme, was proposed for the 2×2 X-Network with two antennas at each node. This scheme achieves a sum degrees of freedom (DoF) of 8/3 and also a diversity gain of two with fixed finite constellation inputs. This work first proposes a new STBC for a three transmit antenna single user MIMO system. Building on this STBC, we extend the LJJ scheme to the 2×2 X-Network with three antennas at each node. As in the LJJ scheme and unlike the Jafar-Shamai scheme, only local channel knowledge is assumed at each Tx. It is shown that the proposed scheme achieves the maximum possible sum DoF of 4. A diversity gain of 3 is also guaranteed when fixed finite constellation inputs are used.

The algebraic formulation for linear network coding in acyclic networks with the links having integer delay is well known. Based on this formulation, for a given set of connections over an arbitrary acyclic network with integer delay assumed for the links, the output symbols at the sink nodes, at any given time instant, is a Fpm-linear combination of the input symbols across different generations, where Fpm denotes the field over which the network operates (p is prime and m is a positive integer). We use finite-field discrete Fourier transform to convert the output symbols at the sink nodes, at any given time instant, into a Fpm-linear combination of the input symbols generated during the same generation without making use of memory at the intermediate nodes. We call this as transforming the acyclic network with delay into n-instantaneous networks (n is sufficiently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (nontransform) approach if and only if there exists a network code satisfying sink demands in the transform approach. When the zero-interference conditions are not satisfied, we propose three precoding-based network alignment (PBNA) schemes for three-source three-destination multiple unicast network with delays (3-S 3-D MUN-D) termed as PBNA using transform approach and time-invariant local encoding coefficients (LECs), PBNA using time-varying LECs, and PBNA using transform approach and block time-varying LECs. We derive sets of necessary and sufficient conditions under which throughputs close to n' + 1/2n' + 1, n'/2n'+ 1, and n'/2n'+ 1 are achieved for the three source-destination pairs in a 3-S 3-D MUN-D employing PBNA using transform approach and time-invariant LECs, and PBNA using transform approach and block time-varying LECs, where n' is a positive integer. For PBNA using time-varying LECs, we obtain a sufficient condition under which a throughput demand of n1/n, n2/n, and n3/n can be met for the three source-destination pairs in a 3-S 3-D MUN-D, where n1, n2, and n3are positive integers less than orequal to the positive integer n. This condition is also necessary when n1+ n3= n1+ n2= n where n1≥ n2≥ n3.

A transmission scheme based on the Alamouti code, which we call the Li-Jafarkhani-Jafar (LJJ) scheme, was recently proposed for the 2 × 2 X-network [i.e., two-transmitter (Tx) two-receiver X-network] with two antennas at each node. This scheme was claimed to achieve a sum degrees of freedom (DoF) of 8/3 and also a diversity gain of two when fixed finite constellations are employed at each Tx. Furthermore, each Tx required the knowledge of only its own channel unlike the Jafar-Shamai scheme which required global CSIT to achieve the maximum possible sum DoF of 8/3. In this paper, we extend the LJJ scheme to the 2 × 2 X-network with four antennas at each node. The proposed scheme also assumes only local channel knowledge at each Tx. We prove that the proposed scheme achieves the maximum possible sum DoF of 16/3. In addition, we also prove that, using any fixed finite constellation with appropriate rotation at each Tx, the proposed scheme achieves a diversity gain of at least four.

This paper considers linear precoding for the constant channel-coefficient K-user MIMO Gaussian interference channel (MIMO GIC) where each transmitter-i (Tx-i) requires the sending of diindependent complex symbols per channel use that take values from fixed finite constellations with uniform distribution to receiver-i (Rx-i) for i=1,2,..., K. We define the maximum rate achieved by Tx-i using any linear precoder as the signal-to-noise ratio (SNR) tends to infinity when the interference channel coefficients are zero to be the constellation constrained saturation capacity (CCSC) for Tx-i. We derive a high-SNR approximation for the rate achieved by Tx-i when interference is treated as noise and this rate is given by the mutual information between Tx-i and Rx-i, denoted as I[Xi;Yi]. A set of necessary and sufficient conditions on the precoders under which [IXi; Yi] tends to CCSC for Tx-i is derived. Interestingly, the precoders designed for interference alignment (IA) satisfy these necessary and sufficient conditions. Furthermore, we propose gradient-ascent-based algorithms to optimize the sum rate achieved by precoding with finite constellation inputs and treating interference as noise. A simulation study using the proposed algorithms for a three-user MIMO GIC with two antennas at each node with di=1 for all i and with BPSK and QPSK inputs shows more than 0.1-b/s/Hz gain in the ergodic sum rate over that yielded by precoders obtained from some known IA algorithms at moderate SNRs.

A transmission scheme based on the Alamouti code, which we call the Li-Jafarkhani-Jafar (LJJ) scheme, was recently proposed for the 2×2 X Network (i.e., two-transmitter (Tx) two-receiver (Rx) X Network) with two antennas at each node. This scheme was claimed to achieve a sum degrees of freedom (DoF) of 8 over 3 and also a diversity gain of two when fixed finite constellations are employed at each Tx. Furthermore, each Tx required the knowledge of only its own channel unlike the Jafar-Shamai scheme which required global CSIT to achieve the maximum possible sum DoF of 8 over 3. In this paper, we extend the LJJ scheme to the 2 × 2 X Network with four antennas at each node. The proposed scheme also assumes only local channel knowledge at each Tx. We prove that the proposed scheme achieves the maximum possible sum DoF of 16 over 3. In addition, we also prove that, using any fixed finite constellation with appropriate rotation at each Tx, the proposed scheme achieves a diversity gain of at least four.

This paper considers linear precoding for constant channel-coefficient K-User MIMO Gaussian Interference Channel (K-MIMO GIC) where each transmitter-i (Tx-i) requires to send diindependent complex symbols per channel use that take values from fixed finite constellations with uniform distribution to receiver-i (Rx-i), for i = 1, 2, ..., K. The maximum rate achieved by Tx-i as the signal to noise ratio (SNR) tends to infinity, using any linear precoder, when the interference channel-coefficients are zero is termed as Constellation Constrained Saturation Capacity (CCSC) for Tx-i. In this paper, we derive a high SNR approximation for the rate achieved by Tx-i when interference is treated as noise, which is given by the mutual information between Tx-i and Rx-i, denoted by I[Xi;Yi] where, Xidenotes the symbols generated at Tx-i before precoding and Yidenotes the symbols received at the antennas of Rx-i. Based on this high SNR approximation, we derive a set of necessary and sufficient conditions on the precoders under which I[Xi;Yi] tends to CCSC for Tx-i. Interestingly, the precoders that achieve interference alignment (IA) satisfy these necessary and sufficient conditions. However, finding precoders that achieve IA is known to be NP-hard in general whereas, the precoders that satisfy the derived necessary and sufficient conditions are easy to find for any given channel-coefficients. Further, we propose a gradient-ascent based algorithm to optimize the sum-rate achieved by precoding with finite constellation inputs and treating interference as noise. Simulation study for a 3-MIMO GIC with di= 1, for all i, equipped with two antennas at each node and QPSK inputs shows an improvement of 1.07 bits/sec/Hz in the ergodic sum-rate using the precoders obtained from the proposed algorithm over the precoders that achieve IA, at SNR = -2 dB.

A transform approach to network coding was introduced by Bavirisetti et al. (arXiv:1103.3882v4 [cs.IT]) as a tool to view wireline networks with delays as k-instantaneous networks, for some large k. When the local encoding kernels (LEKs) of the network are varied with every time block of length k > 1, the network is said to use block time varying LEKs. In this work, we propose a Precoding Based Network Alignment (PBNA) scheme based on transform approach and block time varying LEKs for three-source three-destination multiple unicast network with delays (3-S 3-D MUN-D). In a recent work, Meng et al. (arXiv:1202.3405v1 [cs.IT]) reduced the infinite set of sufficient conditions for feasibility of PBNA in a three-source three-destination instantaneous multiple unicast network as given by Das et al. (arXiv:1008.0235v1 [cs.IT]) to a finite set and also showed that the conditions are necessary. We show that the conditions of Meng et al. are also necessary and sufficient conditions for feasibility of PBNA based on transform approach and block time varying LEKs for 3-S 3-D MUN-D.

In this work, interference alignment for a class of Gaussian interference networks with general message demands, having line of sight (LOS) channels, at finite powers is considered. We assume that each transmitter has one independent message to be transmitted and the propagation delays are uniformly distributed between 0 and (L - 1) (L >; 0). If receiver-j, j ∈{1,2,..., J}, requires the message of transmitter-i, i ∈ {1, 2, ..., K}, we say (i, j) belongs to a connection. A class of interference networks called the symmetrically connected interference network is defined as a network where, the number of connections required at each transmitter-i is equal to ctfor all i and the number of connections required at each receiver-j is equal to crfor all j, for some fixed positive integers ctand cr. For such networks with a LOS channel between every transmitter and every receiver, we show that an expected sum-spectral efficiency (in bits/sec/Hz) of at least K/(e+c1-1)(ct+1) (ct/ct+1)ctlog2 (1+min(i, j)∈c|hi, j|2P/WN0) can be achieved as the number of transmitters and receivers tend to infinity, i.e., K, J →∞ where, C denotes the set of all connections, hijis the channel gain between transmitter-i and receiver-j, P is the average power constraint at each transmitter, W is the bandwidth and N0W is the variance of Gaussian noise at each receiver. This means that, for an LOS symmetrically connected interference network, at any finite power, the total spectral efficiency can grow linearly with K as K, J →∞. This is achieved by extending the time domain interference alignment scheme proposed by Grokop et al. for the k-user Gaussian interference channel to interference networks.

The algebraic formulation for linear network coding in acyclic networks with each link having an integer delay is well known. Based on this formulation, for a given set of connections over an arbitrary acyclic network with integer delay assumed for the links, the output symbols at the sink nodes at any given time instant is a Fq-linear combination of the input symbols across different generations, where Fqdenotes the field over which the network operates. We use finite-field discrete Fourier transform (DFT) to convert the output symbols at the sink nodes at any given time instant into a Fq-linear combination of the input symbols generated during the same generation. We call this as transforming the acyclic network with delay into n-instantaneous networks (n is sufficiently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (non-transform) approach if and only if there exists a network code satisfying sink demands in the transform approach. Furthermore, assuming time invariant local encoding kernels, we show that the transform method can be employed to achieve half the rate corresponding to the individual source-destination mincut (which are assumed to be equal to 1) for some classes of three-source three-destination multiple unicast network with delays using alignment strategies when the zero-interference condition is not satisfied.

In the two-user Gaussian Strong Interference Channel (GSIC) with finite constellation inputs, it is known that relative rotation between the constellations of the two users enlarges the Constellation Constrained (CC) capacity region. In this paper, a metric for finding the approximate angle of rotation to maximally enlarge the CC capacity is presented. It is shown that for some portion of the Strong Interference (SI) regime, with Gaussian input alphabets, the FDMA rate curve touches the capacity curve of the GSIC. Even as the Gaussian alphabet FDMA rate curve touches the capacity curve of the GSIC, at high powers, with both the users using the same finite constellation, we show that the CC FDMA rate curve lies strictly inside the CC capacity curve for the constellations BPSK, QPSK, 8-PSK, 16-QAM and 64-QAM. It is known that, with Gaussian input alphabets, the FDMA inner-bound at the optimum sum-rate point is always better than the simultaneous-decoding inner-bound throughout the Weak Interference (WI) regime. For a portion of the WI regime, it is shown that, with identical finite constellation inputs for both the users, the simultaneous-decoding inner-bound enlarged by relative rotation between the constellations can be strictly better than the FDMA inner-bound.

The concept of interference alignment when extended to three-source three-destination instantaneous multiple unicast network for the case where, each source-destination pair has a min-cut of 1 and zero-interference conditions are not satisfied, is known to achieve a rate of half for every source-destination pair under certain conditions. This was called network alignment. We generalize this concept of network alignment to three-source three-destination multiple unicast (3S-3D-MU) networks with delays, without making use of memory at the intermediate nodes (i.e., nodes other than the sources and destinations) and using time varying Local Encoding Kernels (LEKs). This achieves half the rate corresponding to the individual source-destination min-cut for some classes of 3S-3D-MU network with delays which do not satisfy the zero-interference conditions.

The capacity region of the 3-user Gaussian Interference Channel (GIC) with mixed strong-very strong interference was established in [1]. The mixed strong-very strong interference conditions considered in [1] correspond to the case where, at each receiver, one of the interfering signals is strong and the other is very strong. In this paper, we derive the capacity region of K-user (K ≥ 3) Discrete Memoryless Interference Channels (DMICs) with a mixed strong-very strong interference. This corresponds to the case where, at each receiver one of the interfering signals is strong and the other (K - 2) interfering signals are very strong. This includes, as a special case, the 3-user DMIC with mixed strong-very strong interference. The proof is specialized to the 3-user GIC case and hence an alternative derivation for the capacity region of the 3-user GIC with mixed strong-very strong interference is provided.