On the complexity of finding stopping set size in Tanner Graphs

The problem of determining whether a Tanner graph for a linear block code has a stopping set of a given size is shown to be NT-complete.

Hardness of approximation results for the problem of finding the stopping distance in Tanner graphs

Tanner Graph representation of linear block codes is widely used by iterative decoding algorithms for recovering data transmitted across a noisy communication channel from errors and erasures introduced by the channel. The stopping distance of a Tanner graph T for a binary linear block code C determines the number of erasures correctable using iterative decoding on the Tanner graph T when data is transmitted across a binary erasure channel using the code C. We show that the problem of finding the stopping distance of a Tanner graph is hard to approximate within any positive constant approximation ratio in polynomial time unless P = NP. It is also shown as a consequence that there can be no approximation algorithm for the problem achieving an approximation ratio of 2(log n)(1-epsilon) for any epsilon > 0 unless NP subset of DTIME(n(poly(log n))).

On Finding the Natural Number of Topics with Latent Dirichlet Allocation: Some Observations

It is important to identify the ``correct'' number of topics in mechanisms like Latent Dirichlet Allocation(LDA) as they determine the quality of features that are presented as features for classifiers like SVM. In this work we propose a measure to identify the correct number of topics and offer empirical evidence in its favor in terms of classification accuracy and the number of topics that are naturally present in the corpus. We show the merit of the measure by applying it on real-world as well as synthetic data sets(both text and images). In proposing this measure, we view LDA as a matrix factorization mechanism, wherein a given corpus C is split into two matrix factors M-1 and M-2 as given by C-d*w = M1(d*t) x Q(t*w).Where d is the number of documents present in the corpus anti w is the size of the vocabulary. The quality of the split depends on ``t'', the right number of topics chosen. The measure is computed in terms of symmetric KL-Divergence of salient distributions that are derived from these matrix factors. We observe that the divergence values are higher for non-optimal number of topics - this is shown by a `dip' at the right value for `t'.

Population projection for Namibia 2011-2020 - With an estimation of the impact of HIV/AIDS

This study presents a population projection for Namibia for years 2011–2020. In many countries of sub-Saharan Africa, including Namibia, the population growth is still continuing even though the fertility rates have declined. However, many of these countries suffer from a large HIV epidemic that is slowing down the population growth. In Namibia, the epidemic has been severe. Therefore, it is important to assess the effect of HIV/AIDS on the population of Namibia in the future. Demographic research on Namibia has not been very extensive, and data on population is not widely available. According to the studies made, fertility has been shown to be generally declining and mortality has been significantly increasing due to AIDS. Previous population projections predict population growth for Namibia in the near future, yet HIV/AIDS is affecting the future population developments. For the projection constructed in this study, data on population is taken from the two most recent censuses, from 1991 and 2001. Data on HIV is available from HIV Sentinel Surveys 1992–2008, which test pregnant women for HIV in antenatal clinics. Additional data are collected from different sources and recent studies. The projection is made with software (EPP and Spectrum) specially designed for developing countries with scarce data. The projection includes two main scenarios which have different assumptions concerning the development of the HIV epidemic. In addition, two hypothetical scenarios are made: the first considering the case where HIV epidemic would never have existed and the second considering the case where HIV treatment would never have existed. The results indicate population growth for Namibia. Population in the 2001 census was 1.83 million and is projected to result in 2.38/2.39 million in 2020 in the first two scenarios. Without HIV, population would be 2.61 million and without treatment 2.30 million in 2020. Urban population is growing faster than rural. Even though AIDS is increasing mortality, the past high fertility rates still keep young adult age groups quite large. The HIV epidemic shows to be slowing down, but it is still increasing the mortality of the working-aged population. The initiation of HIV treatment in 2004 in the public sector seems to have had an effect on many projected indicators, diminishing the impact of HIV on the population. For example, the rise of mortality is slowing down.

Finding a Box Representation for a Graph in $O(n^2\Delta^2\ln n)$ time

An axis-parallel box in $b$-dimensional space is a Cartesian product $R_1 \times R_2 \times \cdots \times R_b$ where $R_i$ (for $1 \leq i \leq b$) is a closed interval of the form $[a_i, b_i]$ on the real line. For a graph $G$, its boxicity is the minimum dimension $b$, such that $G$ is representable as the intersection graph of (axis-parallel) boxes in $b$-dimensional space. The concept of boxicity finds application in various areas of research like ecology, operation research etc. Chandran, Francis and Sivadasan gave an $O(\Delta n^2 \ln^2 n)$ randomized algorithm to construct a box representation for any graph $G$ on $n$ vertices in $\lceil (\Delta + 2)\ln n \rceil$ dimensions, where $\Delta$ is the maximum degree of the graph. They also came up with a deterministic algorithm that runs in $O(n^4 \Delta )$ time. Here, we present an $O(n^2 \Delta^2 \ln n)$ deterministic algorithm that constructs the box representation for any graph in $\lceil (\Delta + 2)\ln n \rceil$ dimensions.

A fast algorithm for finding frequent episodes in event streams

Frequent episode discovery is a popular framework for mining data available as a long sequence of events. An episode is essentially a short ordered sequence of event types and the frequency of an episode is some suitable measure of how often the episode occurs in the data sequence. Recently,we proposed a new frequency measure for episodes based on the notion of non-overlapped occurrences of episodes in the event sequence, and showed that, such a definition, in addition to yielding computationally efficient algorithms, has some important theoretical properties in connecting frequent episode discovery with HMM learning. This paper presents some new algorithms for frequent episode discovery under this non-overlapped occurrences-based frequency definition. The algorithms presented here are better (by a factor of N, where N denotes the size of episodes being discovered) in terms of both time and space complexities when compared to existing methods for frequent episode discovery. We show through some simulation experiments, that our algorithms are very efficient. The new algorithms presented here have arguably the least possible orders of spaceand time complexities for the task of frequent episode discovery.

Some aids in the design of microstrip components II: Nomograms

Nomograms have been developed for coupled microstrips. With the help of these, it is possible to design various microstrip components. The design of a multiplexer using the directional filter is described and experimental results are given. Nomograms relating the even and odd mode impedances of coupled microstrip lines to the width to height rate and spacing to height ratio have been developed using the relations formulated by Schwarzmann. A multiplexer using directional filters is designed to operate with three channels at frequencies of 3÷3, 3÷4 and 3÷5 GHz and bandwidths of 10 MHz in each channel. Experimental results are given. The design specifications are satisfied reasonably well.

Aids in the design of microstrip components I: Getsinger's chart

Charts relating the capacitance to the width, spacing, thickness and height above the ground plane of coupled microstrips have been obtained. These are used to design hairpin line and hybrid hairpin line filters as well as multiplexers using microstrip comb line filters. The experimental results agree reasonably well with the design specifications. Getsinger's original charts for parallel coupled bars between parallel plates have been formulated for the microstrip case. Corresponding charts relating the capacitances to the width, spacing, thickness and height above the ground plane of coupled microstrips have been obtained. Examples of the use of these charts are shown in the design of hairpin lines and hybrid hairpin line filters as well as multiplexers using comb line filters. The hairpin line/hybrid hairpin line filters were designed to operate at a central frequency of 9÷5 GHz with 11 per cent bandwidth and 0÷5 dB ripple. The three filters constituting the comb line filters have center frequencies of 2÷4, 3÷0 and 3÷6 GHz. The components so designed were fabricated and tested. The dielectric used for the microstrip was teflon. Experimental curves for the attenuation (insertion loss) and VSWR are given. The design specifications arc satisfied quite well.

Finding India’s place in the Sun –Prospects for harnessing solar thermal energy

In this article, we describe our ongoing efforts in addressing the environment and energy challenges facing the world today. Tapping solar thermal energy seems to be the right choice for a country like India. We look at three solar-thermal technologies in the laboratory — water purification/distillation, Stirling engine, and air-conditioning/refrigeration.

On finding a set of healthy individuals from a large population

In this paper, we explore fundamental limits on the number of tests required to identify a given number of ``healthy'' items from a large population containing a small number of ``defective'' items, in a nonadaptive group testing framework. Specifically, we derive mutual information-based upper bounds on the number of tests required to identify the required number of healthy items. Our results show that an impressive reduction in the number of tests is achievable compared to the conventional approach of using classical group testing to first identify the defective items and then pick the required number of healthy items from the complement set. For example, to identify L healthy items out of a population of N items containing K defective items, when the tests are reliable, our results show that O(K(L - 1)/(N - K)) measurements are sufficient. In contrast, the conventional approach requires O(K log(N/K)) measurements. We derive our results in a general sparse signal setup, and hence, they are applicable to other sparse signal-based applications such as compressive sensing also.

The Lovasz θ function, SVMs and finding large dense subgraphs

The Lovasz θ function of a graph, is a fundamental tool in combinatorial optimization and approximation algorithms. Computing θ involves solving a SDP and is extremely expensive even for moderately sized graphs. In this paper we establish that the Lovasz θ function is equivalent to a kernel learning problem related to one class SVM. This interesting connection opens up many opportunities bridging graph theoretic algorithms and machine learning. We show that there exist graphs, which we call SVM−θ graphs, on which the Lovasz θ function can be approximated well by a one-class SVM. This leads to a novel use of SVM techniques to solve algorithmic problems in large graphs e.g. identifying a planted clique of size Θ(n√) in a random graph G(n,12). A classic approach for this problem involves computing the θ function, however it is not scalable due to SDP computation. We show that the random graph with a planted clique is an example of SVM−θ graph, and as a consequence a SVM based approach easily identifies the clique in large graphs and is competitive with the state-of-the-art. Further, we introduce the notion of a ''common orthogonal labeling'' which extends the notion of a ''orthogonal labelling of a single graph (used in defining the θ function) to multiple graphs. The problem of finding the optimal common orthogonal labelling is cast as a Multiple Kernel Learning problem and is used to identify a large common dense region in multiple graphs. The proposed algorithm achieves an order of magnitude scalability compared to the state of the art.

Lovasz theta function, SVMs and Finding Dense Subgraphs

In this paper we establish that the Lovasz theta function on a graph can be restated as a kernel learning problem. We introduce the notion of SVM-theta graphs, on which Lovasz theta function can be approximated well by a Support vector machine (SVM). We show that Erdos-Renyi random G(n, p) graphs are SVM-theta graphs for log(4)n/n <= p < 1. Even if we embed a large clique of size Theta(root np/1-p) in a G(n, p) graph the resultant graph still remains a SVM-theta graph. This immediately suggests an SVM based algorithm for recovering a large planted clique in random graphs. Associated with the theta function is the notion of orthogonal labellings. We introduce common orthogonal labellings which extends the idea of orthogonal labellings to multiple graphs. This allows us to propose a Multiple Kernel learning (MKL) based solution which is capable of identifying a large common dense subgraph in multiple graphs. Both in the planted clique case and common subgraph detection problem the proposed solutions beat the state of the art by an order of magnitude.

Finding hidden females in a crowd: Mate recognition in fig wasps

Multi-species mating aggregations are crowded environments within which mate recognition must occur. Mating aggregations of fig wasps can consist of thousands of individuals of many species that attain sexual maturity simultaneously and mate in the same microenvironment, i.e, in syntopy, within the close confines of an enclosed globular inflorescence called a syconium - a system that has many signalling constraints such as darkness and crowding. All wasps develop within individual galled flowers. Since mating mostly occurs when females are still confined within their galls,, male wasps have the additional burden of detecting conspecific females that are ``hidden'' behind barriers consisting of gall walls. In Ficus racemosa, we investigated signals used by pollinating fig wasp males to differentiate conspecific females from females of other syntopic fig wasp species. Male Ceratosolen fusciceps could detect conspecific females using cues from galls containing females, empty galls, as well as cues from gall volatiles and gall surface hydrocarbons. In many figs, syconia are pollinated by single foundress wasps, leading to high levels of wasp inbreeding due to sibmating. In F. racemosa, as most syconia contain many foundresses, we expected male pollinators to prefer non-sib females to female siblings to reduce inbreeding. We used galls containing females from non-natal figs as a proxy for non-sibs and those from natal figs as a proxy for sibling females. We found that males preferred galls of female pollinators from natal figs. However, males were undecided when given a choice between galls containing non-pollinator females from natal syconia and pollinator females from non-natal syconia, suggesting olfactory imprinting by the natal syconial environment. (C) 2013 Elsevier Masson SAS. All rights reserved.

On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties

We study the problem of finding small s-t separators that induce graphs having certain properties. It is known that finding a minimum clique s-t separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221-232, 1985), while for example the problems of finding a minimum s-t separator that induces a connected graph or forms an independent set are fixed-parameter tractable when parameterized by the size of the separator (Marx et al. in ACM Trans. Algorithms 9(4): 30, 2013). Motivated by these results, we study properties that generalize cliques, independent sets, and connected graphs, and determine the complexity of finding separators satisfying these properties. We investigate these problems also on bounded-degree graphs. Our results are as follows: Finding a minimum c-connected s-t separator is FPT for c=2 and W1]-hard for any ca parts per thousand yen3. Finding a minimum s-t separator with diameter at most d is W1]-hard for any da parts per thousand yen2. Finding a minimum r-regular s-t separator is W1]-hard for any ra parts per thousand yen1. For any decidable graph property, finding a minimum s-t separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree. Finding a connected s-t separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless .