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.

A survey on compressed domain video analysis techniques

Image and video analysis requires rich features that can characterize various aspects of visual information. These rich features are typically extracted from the pixel values of the images and videos, which require huge amount of computation and seldom useful for real-time analysis. On the contrary, the compressed domain analysis offers relevant information pertaining to the visual content in the form of transform coefficients, motion vectors, quantization steps, coded block patterns with minimal computational burden. The quantum of work done in compressed domain is relatively much less compared to pixel domain. This paper aims to survey various video analysis efforts published during the last decade across the spectrum of video compression standards. In this survey, we have included only the analysis part, excluding the processing aspect of compressed domain. This analysis spans through various computer vision applications such as moving object segmentation, human action recognition, indexing, retrieval, face detection, video classification and object tracking in compressed videos.

A Perspective on Computer Assisted Assessment Techniques for Short Free-Text Answers

Computer Assisted Assessment (CAA) has been existing for several years now. While some forms of CAA do not require sophisticated text understanding (e.g., multiple choice questions), there are also student answers that consist of free text and require analysis of text in the answer. Research towards the latter till date has concentrated on two main sub-tasks: (i) grading of essays, which is done mainly by checking the style, correctness of grammar, and coherence of the essay and (ii) assessment of short free-text answers. In this paper, we present a structured view of relevant research in automated assessment techniques for short free-text answers. We review papers spanning the last 15 years of research with emphasis on recent papers. Our main objectives are two folds. First we present the survey in a structured way by segregating information on dataset, problem formulation, techniques, and evaluation measures. Second we present a discussion on some of the potential future directions in this domain which we hope would be helpful for researchers.

Comparison of Matching Pursuit Algorithm with Other Signal Processing Techniques for Computation of the Time-Frequency Power Spectrum of Brain Signals

Signals recorded from the brain often show rhythmic patterns at different frequencies, which are tightly coupled to the external stimuli as well as the internal state of the subject. In addition, these signals have very transient structures related to spiking or sudden onset of a stimulus, which have durations not exceeding tens of milliseconds. Further, brain signals are highly nonstationary because both behavioral state and external stimuli can change on a short time scale. It is therefore essential to study brain signals using techniques that can represent both rhythmic and transient components of the signal, something not always possible using standard signal processing techniques such as short time fourier transform, multitaper method, wavelet transform, or Hilbert transform. In this review, we describe a multiscale decomposition technique based on an over-complete dictionary called matching pursuit (MP), and show that it is able to capture both a sharp stimulus-onset transient and a sustained gamma rhythm in local field potential recorded from the primary visual cortex. We compare the performance of MP with other techniques and discuss its advantages and limitations. Data and codes for generating all time-frequency power spectra are provided.

Nano-hardness Techniques and Its Applications in Mechanical Property Measurements for Surface Engineering

结合纳米硬度技术测量各类薄膜和块体材料表层的纳米压痕硬度、弹性模量、断裂韧性、膜厚、微结构的弯曲变形,采用纳米划痕硬度技术测量各类薄膜和块体材料的粗糙度、临界附着力、摩擦系数、划痕横剖面.纳米硬度计是检测材料表层微米乃至几十纳米力学性能的先进仪器,可广泛应用于表面工程中的质量检测.

Flexible representations of dynamics are used in object manipulation.

To manipulate an object skillfully, the brain must learn its dynamics, specifying the mapping between applied force and motion. A fundamental issue in sensorimotor control is whether such dynamics are represented in an extrinsic frame of reference tied to the object or an intrinsic frame of reference linked to the arm. Although previous studies have suggested that objects are represented in arm-centered coordinates [1-6], all of these studies have used objects with unusual and complex dynamics. Thus, it is not known how objects with natural dynamics are represented. Here we show that objects with simple (or familiar) dynamics and those with complex (or unfamiliar) dynamics are represented in object- and arm-centered coordinates, respectively. We also show that objects with simple dynamics are represented with an intermediate coordinate frame when vision of the object is removed. These results indicate that object dynamics can be flexibly represented in different coordinate frames by the brain. We suggest that with experience, the representation of the dynamics of a manipulated object may shift from a coordinate frame tied to the arm toward one that is linked to the object. The additional complexity required to represent dynamics in object-centered coordinates would be economical for familiar objects because such a representation allows object use regardless of the orientation of the object in hand.

Evaluation of manufacturing techniques for a minifluidics demonstrator system

A multi-disciplinary team based at Heriot-Watt University and other Universities has been set up to tackle the design and manufacturing of lab-on-a-chip for industries as one of the demonstrators of the EPSRC Grand Challenge project "3D-Mintegration". The team focuses on the analysis of foetal genetic material extracted from maternal blood as a smart alternative to invasive prenatal testing such as amniocentesis. The first module of the microsystem envisaged achieves a separation of blood cells from plasma. This system permits the testing of different manufacturing techniques.

Evaluation of termination techniques for 4H-SiC PiN diodes and trench JFETs

An investigation concerning suitable termination techniques for 4H-SiC trench JFETs is presented. Field plates, p+ floating rings and junction termination extension techniques are used to terminate 1.2kV class PiN diodes. The fabricated PiN diodes evaluated here have a similar design to trench JFETs. Therefore, the conclusions for PiN diodes can be applied to JFET structures as well. Numerical simulations are also used to illustrate the effect of the terminations on the diodes' blocking mode behaviour.

Comparison of relative flexoelectric coefficients measured by different techniques

While it is well known that it is possible to determine the effective flexoelectric coefficient of nematic liquid crystals using hybrid cells [1], this technique can be difficult due to the necessity of using a D.C. field. We have used a second method[2], requiring an A.C. field, to determine this parameter and here we compare the two techniques. The A.C. method employs the linear flexoelectrically induced linear electro-optic switching mechanism observed in chiral nematics. In order to use this second technique a chiral nematic phase is induced in an achiral nematic by the addition of a small amount of chiral additive (∼3% concentration w/w) to give helix pitch lengths of typically 0.5-1.0 μm. We note that the two methods can be used interchangeably, since they produce similar results, and we conclude with a discussion of their relative merits.

Parasitic feedthrough cancellation techniques for enhanced electrical characterization of electrostatic microresonators

Capacitive parasitic feedthrough is an impediment that is inherent to all electrically interfaced micron scale resonant devices, resulting in increased challenges to their integration in more complex circuits, particularly as devices are scaled to operate at higher frequencies for RF applications. In this paper, a technique to cancel the undesirable effects of capacitive feedthrough that was previously proposed is here developed for an on-chip implementation. The method reported in this paper benefits from the simplicity of its implementation, and its effectiveness is demonstrated in this paper. This technique is demonstrated for two disk-plate resonators that have been excited in the wine glass mode at 5.4 MHz, though applicable to almost any electrically interfaced resonator. Measurements of the electrical transmission from these resonators show that the magnitude of the frequency response of the system is enhanced by up to 19 dB, while the phase is found to shift through a full 180° about the resonant frequency. This method is proposed as a useful addition to other techniques for enhancing the measured response of electrostatic micromechanical resonators. © 2009 Elsevier B.V. All rights reserved.