Kernelization complexity of possible winner and coalitional manipulation problems in voting

In the POSSIBLE WINNER problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the POSSIBLE WINNER problem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge 10]. In this paper, we settle this open question for many common voting rules. We show that the POSSIBLE WINNER problem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that includes the Borda voting rule does not admit a polynomial kernel with the number of candidates as the parameter. We show however that the COALITIONAL MANIPULATION problem which is an important special case of the POSSIBLE WINNER problem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the POSSIBLE WINNER problem is harder than the COALITIONAL MANIPULATION problem since the COALITIONAL MANIPULATION problem admits a polynomial kernel whereas the POSSIBLE WINNER problem does not admit a polynomial kernel. (C) 2015 Elsevier B.V. All rights reserved.

Analysis of Rectangular Folded-Waveguide Millimeter-Wave Slow-wave Structures using Conformal Transformations

An analysis of rectangular folded-waveguide slow-wave structure was developed using conformal mapping technique through Schwarz's polygon transformation and closed form expressions for the lumped capacitance and inductance per period of the slow-wave structure were derived in terms of the physical dimensions of the structure, incorporating the effects of the beam hole in the lumped parameters. The lumped parameters were subsequently interpreted for obtaining the dispersion and interaction impedance characteristics of the structure. The analysis was benchmarked for two typical millimeter-wave structures, one operating in Ka-band and the other operating in Q-band, against measurement and 3D electromagnetic modeling using MAFIA.

An adaptive decomposition method for video

Scalable video coding (SVC) is an emerging standard built on the success of advanced video coding standard (H.264/AVC) by the Joint video team (JVT). Motion compensated temporal filtering (MCTF) and Closed loop hierarchical B pictures (CHBP) are two important coding methods proposed during initial stages of standardization. Either of the coding methods, MCTF/CHBP performs better depending upon noise content and characteristics of the sequence. This work identifies other characteristics of the sequences for which performance of MCTF is superior to that of CHBP and presents a method to adaptively select either of MCTF and CHBP coding methods at the GOP level. This method, referred as "Adaptive Decomposition" is shown to provide better R-D performance than of that by using MCTF or CRBP only. Further this method is extended to non-scalable coders.

A landscape approach to conservation of birds

Landscape ecology as a discipline in science is rather young. However its principles appear promising in outlining conservation strategies including a wide range of organisms, particularly birds. Birds due to their mobility use a variety of environmental resources, especially habitats. However, currently these habitats are only available in patches over most of the tropical world. Further whatever is left is under constant human pressure. This paper, therefore, addresses this problem and suggests means of dealing with it using the landscape approach as outlined by landscape ecology. The landscape approach starts with the realization that patches of habitats are open and interact with one another. Corridors of trees along roads, hedgerows and canals in a landscape can aid in the movement of species. Hence the landscape approach considers patches of habitats as interacting elements in the large matrix of the landscape. The landscape approach also integrates concepts. It puts together often debated issues such as whether to preserve maximum species diversity, to maximize representativeness, or to preserve only the valuable species. Based on a case study of the Uttara Kannada district in Karnataka, these oft-opposing views and complications can be dealt with practically and synthesized into a conservation strategy far the diverse avifauna of the Western Chats.

A large conductance Ca2+-activated K+ channel in alpha T3-1 pituitary gonadotrophs

The Ca2+-activated K+ channel in endocrine cells is responsible for membrane hyperpolarization and rhythmic firing of action potentials. The probability of opening of this channel is sensitive to intracellular-free Ca2+ concentration. In this study we have identified one such large conductance Ca2+-activated K+ channel in alpha T3-1 pituitary gonadotroph cell. This channel is ohmic with a unit conductance of 170 pS in symmetrical KCl (135 mM) and its current reverses near zero millivolts. When more than one channel is present in the patch membrane they open and close independent of each other, exhibiting no cooperativity between them as expected of a binomial distribution. The regulatory mechanism of this channel in modulating hormone secretion from alpha T3-1 gonadotroph cells is indicated.

Class of linear time-varying discrete systems

A class of linear time-varying discrete systems is considered, and closed-form solutions are obtained in different cases. Some comments on stability are also included.

Determinant: Old algorithms, new insights (Extended Abstract)

In this paper we approach the problem of computing the characteristic polynomial of a matrix from the combinatorial viewpoint. We present several combinatorial characterizations of the coefficients of the characteristic polynomial, in terms of walks and closed walks of different kinds in the underlying graph. We develop algorithms based on these characterizations, and show that they tally with well-known algorithms arrived at independently from considerations in linear algebra.

Ultrafast photoinduced enhancement of nonlinear optical response in 15-atom gold clusters on indium tin oxide conducting film

We show that the third order optical nonlinearity of 15-atom gold clusters is significantly enhanced when in contact with indium tin oxide (ITO) conducting film. Open and close aperture z-scan experiments together with non-degenerate pump-probe differential transmission experiments were done using 80 fs laser pulses centered at 395 nm and 790 nm on gold clusters encased inside cyclodextrin cavities. We show that two photon absorption coefficient is enhanced by an order of magnitude as compared to that when the clusters are on pristine glass plate. The enhancement for the nonlinear optical refraction coefficient is similar to 3 times. The photo-induced excited state absorption using pump-probe experiments at pump wavelength of 395 nm and probe at 790 nm also show an enhancement by an order of magnitude. These results attributed to the excited state energy transfer in the coupled gold cluster-ITO system are different from the enhancement seen so far in charge donor-acceptor complexes and nanoparticle-conjugate polymer composites.

Crevasses detection in Himalayan glaciers using ground-penetrating radar

Identification and mapping of crevasses in glaciated regions is important for safe movement. However, the remote and rugged glacial terrain in the Himalaya poses greater challenges for field data collection. In the present study crevasse signatures were collected from Siachen and Samudra Tapu glaciers in the Indian Himalaya using ground-penetrating radar (GPR). The surveys were conducted using the antennas of 250 MHz frequency in ground mode and 350 MHz in airborne mode. The identified signatures of open and hidden crevasses in GPR profiles collected in ground mode were validated by ground truthing. The crevasse zones and buried boulder areas in a glacier were identified using a combination of airborne GPR profiles and SAR data, and the same have been validated with the high-resolution optical satellite imagery (Cartosat-1) and Survey of India mapsheet. Using multi-sensor data, a crevasse map for Samudra Tapu glacier was prepared. The present methodology can also be used for mapping the crevasse zones in other glaciers in the Himalaya.