Constructing Reeb Graphs using Cylinder Maps

The Reeb graph of a scalar function represents the evolution of the topology of its level sets. In this video, we describe a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Arcs in the Reeb graph are computed in the second step using a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The algorithm is also able to handle non-manifold domains.

Joint Power Control, Scheduling and Routing for Multihop Energy Harvesting Sensor Networks

We study wireless multihop energy harvesting sensor networks employed for random field estimation. The sensors sense the random field and generate data that is to be sent to a fusion node for estimation. Each sensor has an energy harvesting source and can operate in two modes: Wake and Sleep. We consider the problem of obtaining jointly optimal power control, routing and scheduling policies that ensure a fair utilization of network resources. This problem has a high computational complexity. Therefore, we develop a computationally efficient suboptimal approach to obtain good solutions to this problem. We study the optimal solution and performance of the suboptimal approach through some numerical examples.

Algorithms for Colouring Random k-colourable Graphs

The k-colouring problem is to colour a given k-colourable graph with k colours. This problem is known to be NP-hard even for fixed k greater than or equal to 3. The best known polynomial time approximation algorithms require n(delta) (for a positive constant delta depending on k) colours to colour an arbitrary k-colourable n-vertex graph. The situation is entirely different if we look at the average performance of an algorithm rather than its worst-case performance. It is well known that a k-colourable graph drawn from certain classes of distributions can be ii-coloured almost surely in polynomial time. In this paper, we present further results in this direction. We consider k-colourable graphs drawn from the random model in which each allowed edge is chosen independently with probability p(n) after initially partitioning the vertex set into ii colour classes. We present polynomial time algorithms of two different types. The first type of algorithm always runs in polynomial time and succeeds almost surely. Algorithms of this type have been proposed before, but our algorithms have provably exponentially small failure probabilities. The second type of algorithm always succeeds and has polynomial running time on average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work as long as p(n) greater than or equal to n(-1+is an element of) where is an element of is a constant greater than 1/4.

A Cellular Array for Multivalued Logic Functions

An algebraic generalization of the well-known binary q-function array to a multivalued q-function array is presented. It is possible to associate tree-structure realizations for binary q-functions and multivalued q-functions. Synthesis of multivalued functions using this array is very simple

Easily Diagnosable Sequential Machines

This correspondence throws some light into the area of easily diagnosable machines. Given the behavior of a sequential machine in terms of a state table it explores the possibilities of designing a structure, that facilitates easy diagnosis of faults. The objective is achieved through structural decomposition which has already claimed to produce simpler physical realization.

Semi-Supervised Classification Using Sparse Gaussian Process Regression

Gaussian Processes (GPs) are promising Bayesian methods for classification and regression problems. They have also been used for semi-supervised learning tasks. In this paper, we propose a new algorithm for solving semi-supervised binary classification problem using sparse GP regression (GPR) models. It is closely related to semi-supervised learning based on support vector regression (SVR) and maximum margin clustering. The proposed algorithm is simple and easy to implement. It gives a sparse solution directly unlike the SVR based algorithm. Also, the hyperparameters are estimated easily without resorting to expensive cross-validation technique. Use of sparse GPR model helps in making the proposed algorithm scalable. Preliminary results on synthetic and real-world data sets demonstrate the efficacy of the new algorithm.

A maximal operator, Carleson's embedding, and tent spaces for vector-valued functions

This thesis is concerned with the area of vector-valued Harmonic Analysis, where the central theme is to determine how results from classical Harmonic Analysis generalize to functions with values in an infinite dimensional Banach space. The work consists of three articles and an introduction. The first article studies the Rademacher maximal function that was originally defined by T. Hytönen, A. McIntosh and P. Portal in 2008 in order to prove a vector-valued version of Carleson's embedding theorem. The boundedness of the corresponding maximal operator on Lebesgue-(Bochner) -spaces defines the RMF-property of the range space. It is shown that the RMF-property is equivalent to a weak type inequality, which does not depend for instance on the integrability exponent, hence providing more flexibility for the RMF-property. The second article, which is written in collaboration with T. Hytönen, studies a vector-valued Carleson's embedding theorem with respect to filtrations. An earlier proof of the dyadic version assumed that the range space satisfies a certain geometric type condition, which this article shows to be also necessary. The third article deals with a vector-valued generalizations of tent spaces, originally defined by R. R. Coifman, Y. Meyer and E. M. Stein in the 80's, and concerns especially the ones related to square functions. A natural assumption on the range space is then the UMD-property. The main result is an atomic decomposition for tent spaces with integrability exponent one. In order to suit the stochastic integrals appearing in the vector-valued formulation, the proof is based on a geometric lemma for cones and differs essentially from the classical proof. Vector-valued tent spaces have also found applications in functional calculi for bisectorial operators. In the introduction these three themes come together when studying paraproduct operators for vector-valued functions. The Rademacher maximal function and Carleson's embedding theorem were applied already by Hytönen, McIntosh and Portal in order to prove boundedness for the dyadic paraproduct operator on Lebesgue-Bochner -spaces assuming that the range space satisfies both UMD- and RMF-properties. Whether UMD implies RMF is thus an interesting question. Tent spaces, on the other hand, provide a method to study continuous time paraproduct operators, although the RMF-property is not yet understood in the framework of tent spaces.

Effects of gender, and SLCO1B1 and CYP7A1 polymorphisms on plasma bile acids in humans and the pharmacokinetics of therapeutic ursodeoxycholic acid

Bile acids are important steroid-derived molecules essential for fat absorption in the small intestine. They are produced in the liver and secreted into the bile. Bile acids are transported by bile flow to the small intestine, where they aid the digestion of lipids. Most bile acids are reabsorbed in the small intestine and return to the liver through the portal vein. The whole recycling process is referred to as the enterohepatic circulation, during which only a small amount of bile acids are removed from the body via faeces. The enterohepatic circulation of bile acids involves the delicate coordination of a number of bile acid transporters expressed in the liver and the small intestine. Organic anion transporting polypeptide 1B1 (OATP1B1), encoded by the solute carrier organic anion transporter family, member 1B1 (SLCO1B1) gene, mediates the sodium independent hepatocellular uptake of bile acids. Two common SNPs in the SLCO1B1 gene are well known to affect the transport activity of OATP1B1. Moreover, bile acid synthesis is an important elimination route for cholesterol. Cholesterol 7α-hydroxylase (CYP7A1) is the rate-limiting enzyme of bile acid production. The aim of this thesis was to investigate the effects of SLCO1B1 polymorphism on the fasting plasma levels of individual endogenous bile acids and a bile acid synthesis marker, and the pharmacokinetics of exogenously administered ursodeoxycholic acid (UDCA). Furthermore, the effects of CYP7A1 genetic polymorphism and gender on the fasting plasma concentrations of individual endogenous bile acids and the bile acid synthesis marker were evaluated. Firstly, a high performance liquid chromatography-tandem mass spectrometry (HPLC-MS/MS) method for the determination of bile acids was developed (Study I). A retrospective study examined the effects of SLCO1B1 genetic polymorphism on the fasting plasma concentrations of individual bile acids and a bile acid synthesis marker in 65 healthy subjects (Study II). In another retrospective study with 143 healthy individuals, the effects of CYP7A1 genetic polymorphism and gender as well as SLCO1B1 polymorphism on the fasting plasma levels of individual bile acids and the bile acid synthesis marker were investigated (Study III). The effects of SLCO1B1 polymorphism on the pharmacokinetics of exogenously administered UDCA were evaluated in a prospective genotype panel study including 27 healthy volunteers (Study IV). A robust, sensitive and simple HPLC-MS/MS method was developed for the simultaneous determination of 16 individual bile acids in human plasma. The method validation parameters for all the analytes met the requirements of the FDA (Food and Drug Administration) bioanalytical guidelines. This HPLC-MS/MS method was applied in Studies II-IV. In Study II, the fasting plasma concentrations of several bile acids and the bile acid synthesis marker seemed to be affected by SLCO1B1 genetic polymorphism, but these findings were not replicated in Study III with a larger sample size. Moreover, SLCO1B1 polymorphism had no effect on the pharmacokinetic parameters of exogenously administered UDCA. Furthermore, no consistent association was observed between CYP7A1 genetic polymorphism and the fasting plasma concentrations of individual bile acids or the bile acid synthesis marker. In contrast, gender had a major effect on the fasting plasma concentrations of several bile acids and also total bile acids. In conclusion, gender, but not SLCO1B1 or CYP7A1 polymorphisms, has a major effect on the fasting plasma concentrations of individual bile acids. Moreover, the common genetic polymorphism of CYP7A1 is unlikely to influence the activity of CYP7A1 under normal physiological conditions. OATP1B1 does not play an important role in the in vivo disposition of exogenously administered UDCA.

Three Dimensional Line-Clipping by Systematic Enumeration

Three dimensional clipping is a critical component of the 3D graphics pipeline. A new 3D clipping algorithm is presented in this paper. An efficient 2D clipping routine reported earlier has been used as a submodule. This algorithm uses a new classification scheme for lines of all possible orientations with respect to a rectangular parallelopiped view volume. The performance of this algorithm has been evaluated using exact arithmetic operation counts. It is shown that our algorithm requires less arithmetic operations than the Cyrus-Beck 3D clipping algorithm in all cases. It is also shown that for lines that intersect the clipping volume, our algorithm performs better than the Liang-Barsky 3D clipping algorithm.

Optimal scheduling of a processor executing a communication protocol stack

We consider the problem of optimally scheduling a processor executing a multilayer protocol in an intelligent Network Interface Controller (NIC). In particular, we assume a typical LAN environment with class 4 transport service, a connectionless network service, and a class 1 link level protocol. We develop a queuing model for the problem. In the most general case this becomes a cyclic queuing network in which some queues have dedicated servers, and the others have a common schedulable server. We use sample path arguments and Markov decision theory to determine optimal service schedules. The optimal throughputs are compared with those obtained with simple policies. The optimal policy yields upto 25% improvement in some cases. In some other cases, the optimal policy does only slightly better than much simpler policies.

Analyzing Cache Performance Bottlenecks of STM Applications and addressing them with Compiler's help

Software transactional memory (STM) is a promising programming paradigm for shared memory multithreaded programs as an alternative to traditional lock based synchronization. However adoption of STM in mainstream software has been quite low due to its considerable overheads and its poor cache/memory performance. In this paper, we perform a detailed study of the cache behavior of STM applications and quantify the impact of different STM factors on the cache misses experienced by the applications. Based on our analysis, we propose a compiler driven Lock-Data Colocation (LDC), targeted at reducing the cache overheads on STM. We show that LDC is effective in improving the cache behavior of STM applications by reducing the dcache miss latency and improving execution time performance.

NUcache: A Multicore Cache Organization Based on Next-Use Distance

In this work, we propose a new organization for the last level shared cache of a rnulticore system. Our design is based on the observation that the Next-Use distance, measured in terms of intervening misses between the eviction of a line and its next use, for lines brought in by a given delinquent PC falls within a predictable range of values. We exploit this correlation to improve the performance of shared caches in multi-core architectures by proposing the NUcache organization.

A non-cooperative game-theoretic approach to channel assignment in multi-channel multi-radio wireless networks

Channel assignment in multi-channel multi-radio wireless networks poses a significant challenge due to scarcity of number of channels available in the wireless spectrum. Further, additional care has to be taken to consider the interference characteristics of the nodes in the network especially when nodes are in different collision domains. This work views the problem of channel assignment in multi-channel multi-radio networks with multiple collision domains as a non-cooperative game where the objective of the players is to maximize their individual utility by minimizing its interference. Necessary and sufficient conditions are derived for the channel assignment to be a Nash Equilibrium (NE) and efficiency of the NE is analyzed by deriving the lower bound of the price of anarchy of this game. A new fairness measure in multiple collision domain context is proposed and necessary and sufficient conditions for NE outcomes to be fair are derived. The equilibrium conditions are then applied to solve the channel assignment problem by proposing three algorithms, based on perfect/imperfect information, which rely on explicit communication between the players for arriving at an NE. A no-regret learning algorithm known as Freund and Schapire Informed algorithm, which has an additional advantage of low overhead in terms of information exchange, is proposed and its convergence to the stabilizing outcomes is studied. New performance metrics are proposed and extensive simulations are done using Matlab to obtain a thorough understanding of the performance of these algorithms on various topologies with respect to these metrics. It was observed that the algorithms proposed were able to achieve good convergence to NE resulting in efficient channel assignment strategies.