196 research outputs found
Improved Bounds for Bipartite Matching on Surfaces
No full textWe exhibit the following new upper bounds on the space complexity and the parallel complexity of the Bipartite Perfect Matching (BPM) problem for graphs of small genus:
(1) BPM in planar graphs is in UL (improves upon the SPL bound from Datta, Kulkarni, and Roy;
(2) BPM in constant genus graphs is in NL (orthogonal to the SPL bound from Datta, Kulkarni, Tewari, and Vinodchandran.;
(3) BPM in poly-logarithmic genus graphs is in NC; (extends the NC bound for O(log n) genus graphs from Mahajan and Varadarajan, and Kulkarni, Mahajan, and Varadarajan.
For Part (1) we combine the flow technique of Miller and Naor with the double counting technique of Reinhardt and Allender . For Part (2) and (3) we extend Miller and Naor's result to higher genus surfaces in the spirit of Chambers, Erickson and Nayyeri
Quantum Query Complexity of Subgraph Isomorphism and Homomorphism
No full textLet H be a (non-empty) graph on n vertices, possibly containing isolated vertices. Let f_H(G) = 1 iff the input graph G on n vertices contains H as a (not necessarily induced) subgraph. Let alpha_H denote the cardinality of a maximum independent set of H. In this paper we show: Q(f_H) = Omega( sqrt{alpha_H * n}), where Q(f_H) denotes the quantum query complexity of f_H.
As a consequence we obtain lower bounds for Q(f_H) in terms of several other parameters of H such as the average degree, minimum vertex cover, chromatic number, and the critical probability.
We also use the above bound to show that Q(f_H) = Omega(n^{3/4}) for any H, improving on the previously best known bound of Omega(n^{2/3}) [M. Santha/A. Chi-Chih Yao, unpublished manuscript]. Until very recently, it was believed that the quantum query complexity is at least square root of the randomized one. Our Omega(n^{3/4}) bound for Q(f_H) matches the square root of the current best known bound for the randomized query complexity of f_H, which is Omega(n^{3/2}) due to Groger. Interestingly, the randomized bound of Omega(alpha_H * n) for f_H still remains open.
We also study the Subgraph Homomorphism Problem, denoted by f_{[H]}, and show that Q(f_{[H]}) = Omega(n).
Finally we extend our results to the 3-uniform hypergraphs. In particular, we show an Omega(n^{4/5}) bound for quantum query complexity of the Subgraph Isomorphism, improving on the previously known Omega(n^{3/4}) bound. For the Subgraph Homomorphism, we obtain an Omega(n^{3/2}) bound for the same
Policies, implementation, and impact
No full textThis chapter pulls together the main findings from a broad policy perspective that draws upon lessons from policies pursued elsewhere and various initiatives in India. The vision that is constructed is unavoidably incomplete in some respects, but illuminates successes and failures in designing policies, and implementing them
Affluence, obesity, and non-communicable diseases in India
No full textAging, growing affluence, obesity, and NCDs are closely linked. This chapter examines these links using a nationwide household survey. Attention is given to complex health policy choices given the irreversibility of growing affluence, lifestyle changes and urbanization
Diets, malnutrition, and disease in India: An Overview
No full textThis chapter is an overview of different themes related to diets, malnutrition and non-communicable diseases in India. These include why calorie intake declined across different expenditure classes during 1993�2004; whether dietary diversification was associated with a reduction in calorie intake; what the factors are associated with eating out and its likely nutritional implications; whether a calorie share of the staples threshold could replace conventional calorie norms; whether poverty nutrition traps exist; whether child malnutrition is underestimated; links between aging, growing affluence, obesity and non-communicable diseases; why PDS has failed to fulfil its potential in terms of food security and a critique of the universal food subsidy enacted recently; and a policy perspective reflecting lessons from India and elsewhere and health policy challenges
Demand for nutrients in India, 1993-2004
No full textThe Deaton�Dreze (2009) explanation of a decline in calorie intake despite rapid economic growth in terms of lower calorie �requirements� is incomplete. This chapter fills this gap by taking into account the influences of food prices, growing affluence, urbanization and life-style changes and less strenuous activity levels. Insights into changing consumer preferences are given
Dietary transition in India: An analysis based on NSS data, 1993-2004
No full textOur study examines changes in diets over the period 1993-2004. Diets have shifted away from cereals towards higher consumption of fruits, vegetables, oils and livestock products. Using household data, reduced form demand relations are estimated for nine food commodities. Significant own and cross-price effects that vary over time are confirmed, as also income/expenditure effects. Over and above these effects, more sedentary life styles and less strenuous activity patterns played a significant role in shaping dietary patterns. While changes in life style and activity patterns are irreversible, an important policy insight is that food price stabilization and expansion of livelihood opportunities deserve greater attention
Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs
No full textWe present a Logspace Approximation Scheme (LSAS), i.e. an approximation algorithm for maximum matching in planar graphs (not necessarily bipartite) that achieves an approximation ratio arbitrarily close to one, using only logarithmic space. This deviates from the well known Baker's approach for approximation in planar graphs by avoiding the use of distance computation - which is not known to be in Logspace. Our algorithm actually works for any "recursively sparse" graph class which contains a linear size matching and also for certain other classes like bounded genus graphs.
The scheme is based on an LSAS in bounded degree graphs which are not known to be amenable to Baker's method. We solve the bounded degree case by parallel augmentation of short augmenting paths. Finding a large number of such disjoint paths can, in turn, be reduced to finding a large independent set in a bounded degree graph. The bounded degree assumption allows us to obtain a Logspace algorithm
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs
No full textWe present a deterministic way of assigning small (log bit) weights
to the edges of a bipartite planar graph so that the minimum weight
perfect matching becomes unique. The isolation lemma as described
in (Mulmuley et al. 1987) achieves the same for general graphs
using a randomized weighting scheme, whereas we can do it
deterministically when restricted to bipartite planar graphs. As a
consequence, we reduce both decision and construction versions of
the matching problem to testing whether a matrix is singular, under
the promise that its determinant is or , thus obtaining a
highly parallel SPL algorithm for bipartite planar graphs. This
improves the earlier known bounds of non-uniform SPL by (Allender
et al. 1999) and by (Miller and Naor 1995, Mahajan and
Varadarajan 2000). It also rekindles the hope of obtaining a
deterministic parallel algorithm for constructing a perfect
matching in non-bipartite planar graphs, which has been open for a
long time. Our techniques are elementary and simple
Calorie thresholds and undernutrition in India, 1993-2004
No full textUsing fixed calorie norms to measure undernutrition is suspect due to familiar reasons. Recent studies have proposed an approach that relies on a calorie share of staples threshold. Our analysis with Indian household data shows that such a measure is of limited interest and potentially misleading because it confines variation in calorie share to a measure of wealth. Since even the poor substitute in response to changes in food prices, calorie and income thresholds change, and, consequently, the estimates of undernourished. Thus, both the predictive accuracy of this measure and its descriptive richness leave a lot to be desired. The policy implications of our critique are significant, as not just livelihood expansion but also food price stabilisation are likely to mitigate undernutrition
- …
