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.

On a Novel Geometric Representation of Rotation

This paper presents a novel method of representing rotation and its application to representing the ranges of motion of coupled joints in the human body, using planar maps. The present work focuses on the viability of this representation for situations that relied on maps on a unit sphere. Maps on a unit sphere have been used in diverse applications such as Gauss map, visibility maps, axis-angle and Euler-angle representations of rotation etc. Computations on a spherical surface are difficult and computationally expensive; all the above applications suffer from problems associated with singularities at the poles. There are methods to represent the ranges of motion of such joints using two-dimensional spherical polygons. The present work proposes to use multiple planar domain “cube” instead of a single spherical domain, to achieve the above objective. The parameterization on the planar domains is easy to obtain and convert to spherical coordinates. Further, there is no localized and extreme distortion of the parameter space and it gives robustness to the computations. The representation has been compared with the spherical representation in terms of computational ease and issues related to singularities. Methods have been proposed to represent joint range of motion and coupled degrees of freedom for various joints in digital human models (such as shoulder, wrist and fingers). A novel method has been proposed to represent twist in addition to the existing swing-swivel representation.

Thermally induced phase separation in P alpha MSAN/PMMA blends in presence of functionalized multiwall carbon nanotubes: Rheology, morphology and electrical conductivity

The focus of this work is the evaluation and analysis of the state of dispersion of functionalized multiwall carbon nanotubes (CNTs), within different morphologies formed, in a model LCST blend (poly[(alpha-methylstyrene)-co-(acrylonitrile)]/poly(methyl-methacryla te), P alpha MSAN/PMMA). Blend compositions that are expected to yield droplet-matrix (85/15 P alpha MSAN/PMMA and 15/85 P alpha MSAN/PMMA, wt/wt) and co-continuous morphologies (60/40 P alpha MSAN/PMMA, wt/wt) upon phase separation have been combined with two types of CNTs; carboxylic acid functionalized (CNTCOOH) and polyethylene modified (CNTPE) up to 2 wt%. Thermally induced phase separation in the blends has been studied in-situ by rheology and dielectric (conductivity) spectroscopy in terms of morphological evolution and CNT percolation. The state of dispersion of CNTs has been evaluated by transmission electron microscopy. The experimental results indicate that the final blend morphology and the surface functionalization of CNT are the main factors that govern percolation. In presence of either of the CNTs, 60/40 P alpha MSAN/PMMA blends yield a droplet-matrix morphology rather than co-continuous and do not show any percolation. On the other hand, both 85/15 P alpha MSAN/PMMA and 15/85 P alpha MSAN/PMMA blends containing CNTPEs show percolation in the rheological and electrical properties. Interestingly, the conductivity spectroscopy measurements demonstrate that the 15/85 P alpha MSAN/PMMA blends with CNTPEs that show insulating properties at room temperature for the miscible blends reveal highly conducting properties in the phase separated blends (melt state) as a result of phase separation. By quenching this morphology, the conductivity can be retained in the blends even in the solid state. (C) 2011 Elsevier Ltd. All rights reserved.

Optimizing resolution of signals in a low-IF receiver

The resolution of the digital signal path has a crucial impact on the design, performance and the power dissipation of the radio receiver data path, downstream from the ADC. The ADC quantization noise has been traditionally included with the Front End receiver noise in calculating the SNR as well as BER for the receiver. Using the IEEE 802.15.4 as an example, we show that this approach leads to an over-design for the ADC and the digital signal path, resulting in larger power. More accurate specifications for the front-end design can be obtained by making SNRreg a function of signal resolutions. We show that lower resolution signals provide adequate performance and quantization noise alone does not produce any bit-error. We find that a tight bandpass filter preceding the ADC can relax the resolution requirement and a 1-bit ADC degrades SNR by only 1.35 dB compared to 8-bit ADC. Signal resolution has a larger impact on the synchronization and a 1-bit ADC costs about 5 dB in SNR to maintain the same level of performance as a 8-bit ADC.

Incremental natural-gradient actor-critic algorithms

We present four new reinforcement learning algorithms based on actor-critic and natural-gradient ideas, and provide their convergence proofs. Actor-critic rein- forcement learning methods are online approximations to policy iteration in which the value-function parameters are estimated using temporal difference learning and the policy parameters are updated by stochastic gradient descent. Methods based on policy gradients in this way are of special interest because of their com- patibility with function approximation methods, which are needed to handle large or infinite state spaces. The use of temporal difference learning in this way is of interest because in many applications it dramatically reduces the variance of the gradient estimates. The use of the natural gradient is of interest because it can produce better conditioned parameterizations and has been shown to further re- duce variance in some cases. Our results extend prior two-timescale convergence results for actor-critic methods by Konda and Tsitsiklis by using temporal differ- ence learning in the actor and by incorporating natural gradients, and they extend prior empirical studies of natural actor-critic methods by Peters, Vijayakumar and Schaal by providing the first convergence proofs and the first fully incremental algorithms.

Optimizing Multimedia Experience in a Thin Client Environment for a Resource Constrained Processor

In this paper, we study how TCP and UDP flows interact with each other when the end system is a CPU resource constrained thin client. The problem addressed is twofold, 1) the throughput of TCP flows degrades severely in the presence of heavily loaded UDP flows 2) fairness and minimum QoS requirements of UDP are not maintained. First, we identify the factors affecting the TCP throughput by providing an in-depth analysis of end to end delay and packet loss variations. The results obtained from the first part leads us to our second contribution. We propose and study the use of an algorithm that ensures fairness across flows. The algorithm improves the performance of TCP flows in the presence of multiple UDP flows admitted under an admission algorithm and maintains the minimum QoS requirements of the UDP flows. The advantage of the algorithm is that it requires no changes to TCP/IP stack and control is achieved through receiver window control.

WCET Estimation for Executables in the Presence of Data Caches

This paper describes techniques to estimate the worst case execution time of executable code on architectures with data caches. The underlying mechanism is Abstract Interpretation, which is used for the dual purposes of tracking address computations and cache behavior. A simultaneous numeric and pointer analysis using an abstraction for discrete sets of values computes safe approximations of access addresses which are then used to predict cache behavior using Must Analysis. A heuristic is also proposed which generates likely worst case estimates. It can be used in soft real time systems and also for reasoning about the tightness of the safe estimate. The analysis methods can handle programs with non-affine access patterns, for which conventional Presburger Arithmetic formulations or Cache Miss Equations do not apply. The precision of the estimates is user-controlled and can be traded off against analysis time. Executables are analyzed directly, which, apart from enhancing precision, renders the method language independent.

Analog/RF Built-in-Self-Test Subsystem for a Mobile Broadcast Video Receiver in 65-nm CMOS

A built-in-self-test (BIST) subsystem embedded in a 65-nm mobile broadcast video receiver is described. The subsystem is designed to perform analog and RF measurements at multiple internal nodes of the receiver. It uses a distributed network of CMOS sensors and a low bandwidth, 12-bit A/D converter to perform the measurements with a serial bus interface enabling a digital transfer of measured data to automatic test equipment (ATE). A perturbation/correlation based BIST method is described, which makes pass/fail determination on parts, resulting in significant test time and cost reduction.

An Actor-Critic Algorithm for Finite Horizon Markov Decision Processes

We develop a simulation based algorithm for finite horizon Markov decision processes with finite state and finite action space. Illustrative numerical experiments with the proposed algorithm are shown for problems in flow control of communication networks and capacity switching in semiconductor fabrication.

A Simultaneous Deterministic Perturbation Actor-Critic Algorithm with an Application to Optimal Mortgage Refinancing

We develop a simulation-based, two-timescale actor-critic algorithm for infinite horizon Markov decision processes with finite state and action spaces, with a discounted reward criterion. The algorithm is of the gradient ascent type and performs a search in the space of stationary randomized policies. The algorithm uses certain simultaneous deterministic perturbation stochastic approximation (SDPSA) gradient estimates for enhanced performance. We show an application of our algorithm on a problem of mortgage refinancing. Our algorithm obtains the optimal refinancing strategies in a computationally efficient manner

Hydrothermal synthesis of CdTe QDs: Their luminescence quenching in the presence of bio-molecules and observation of bistable memory effect in CdTe QD/PEDOT:PSS heterostructure

We report one-pot hydrothermal synthesis of nearly mono-disperse 3-mercaptopropionic acid capped water-soluble cadmium telluride (CdTe) quantum dots (QDs) using an air stable Te source. The optical and electrical characteristics were also studied here. It was shown that the hydrothermal synthesis could be tuned to synthesize nano structures of uniform size close to nanometers. The emissions of the CdTe QDs thus synthesized were in the range of 500-700 nm by varying the duration of synthesis. The full width at half maximum (FWHM) of the emission peaks is relatively narrow (40-90 nm), which indicates a nearly uniform distribution of QD size. The structural and optical properties of the QDs were characterized by transmission electron microscopy (TEM), photoluminescence (PL) and Ultraviolet-visible (UV-Vis) spectroscopy. The photoluminescence quenching of CdTe QDs in the presence of L-cysteine and DNA confirms its biocompatibility and its utility for biosensing applications. The room temperature current-voltage characteristics of QD film on ITO coated glass substrate show an electrically induced switching between states with high and low conductivities. The phenomenon is explained on the basis of charge confinement in quantum dots. (C) 2011 Elsevier B.V. All rights reserved.