#### List of Speakers

Piyush P Kurur(IMSc)
Sobhan Babu Chintapalli(IITB)
Ashish Tendulkar(IITB)
Ratul Mazumdar(IITB)
Saju Jude Dominic(IITG)
Ms. Alka(IITG)
Saketh Saurabh(CMI)
Viswanath Pulabaigari(IISc)
Siddhartha Tambat(IISc)
Basant Kumar Dwivedi(IITD)
Anup Gangwar(IITD)
Ms. R.Manimegalai(IITM)
Ms. Alpana Dubey(IITK)
Narottam Chand(IITR)
Ajey Kumar(IITR)
Sivaramakrishnan Sivasubramanian(TIFR)

Speaker : Piyush P Kurur
Institute : IMsc
Title : On the complexity of computing the Units group and Class group of
a number (Joint work with V. Arvind)
Abstract:
Given an algebraic number field K, let O_K denote the ring of integers of K. If [K:Q] is constant, we show that the problem of computing the group of units of the ring of integers of K is in the complexity class SPP. In particular we have a SPP algorithm for solution of Pell's equation. We also show that the poblem of testing whether a given ideal of O_K is prinicple is in SPP. Furthermore, assuming the GRH, the class number of K and a presentation for the class group of K can also be computed in SPP.

Speaker : Sobhan Babu Chintapalli
Institute : IITB
Title : Degree Conditions for Forests in Graphs
(Joint work with Prof. Ajit A. Diwan)
Abstract:
Let $F$ be a forest with $p$ vertices and $k$ components, and let $G$ be a graph with $n \ge p$ vertices and minimum degree at least $max\{ \frac{n-k}{2},p-k\}$. We prove that $G$ contains a spanning subdivision of $F$. If $H$ is any forest of order $n$ with $m$ edges, then any graph $G$ of order $\ge n$ $d(u)+d(v) \ge 2m-1$ for any two non-adjacent vertices $u,v$ contains $H$.

Speaker : Ashish Tendulkar
Institute : IITB
Title : Clustering of protein structural fragments reveals modular building block approach of nature.
Abstract:
Most of the genome sequencing projects are entering in the postgenomics phase, which deals with structure data. Protein structure information is more suitable than mere sequence for predicting its function. With more and more structure data being available, better algorithms are needed to predict the function of the protein with more efficiency and accuracy. The advancements in experimental structure determination are still inadequate to cater to the needs of rapid structure determination. In addition, it is simply not possible to experimentally determine structure of some proteins due to physical constrains. These limitations prompts the need for automatic structure prediction method simply based on amino acid sequence of protein. The structure prediction hinges on the knowledge of preference of a single or a group of amino acid residues to a specifc structures. To address the problem, the peptide fragment library is constructed from all the proteins in ASTRAL data set by clustering all possible overlapping octapeptides based on their structural similarity. The structure of each octapeptide is quantified using geometric invariants. Classic machine learning techniques are used to cluster the peptides. Similar approach is applied to predict important functional sites in proteins. The results include important functional sites in proteins, and clusters of octapeptides.

Speaker : Ratul Mazumdar
Institute : IITB
Title : Disseminating Dynamic Data with QoS Gurantee in Wide Area Network: A Practical Control Theoretic Approach.
Abstract :
Often, data used in on-line decision making (for example, in determining how to react to changes in process behavior, traffic flow control, etc.) is dynamic in nature and hence the timeliness of the data delivered to the decision making process becomes very important. The delivered data must conform to certain time or value based application specific inconsistency bounds. \eat { To illustrate, a user may be willing to receive sports scores and news information that may be out-of-sync by a few minutes with respect to the source, but may desire stronger coherency requirements on data items such as process control parameters.} A system designed to disseminate dynamic data can exploit user-specified coherency requirements by fetching and disseminating only those changes that are of interest to users and ignoring intermediate changes. But, the design of mechanisms for such data delivery is challenging given that dynamic data changes {\em rapidly} and {\em unpredictably}, the latter making it very hard to use simple prediction techniques. In this paper, we address these challenges. Specifically, we develop mechanisms to obtain timely and consistency-preserving updates for dynamic data by {\em pull}ing data from the source at strategically chosen points in time providing Quality of Service (QoS) Guarantee. Motivated by the need for practical system design, but using formal analytical techniques, we offer a systematic approach based on control-theoretic principles. Our solution is also unique from a control-theoretic perspective due to the presence of inherent non-linear system components and the dependence between the sampled time and sampled value. A proportional controller with dynamically changing tuning criteria and stochastic control theoretic based Linear Quadratic Gaussian (LQG) are used in this work as a means of deciding when to next refresh data from the source. Using real-world traces of real-time data we show the superior performance of our feedback-driven control-theoretic approach by comparing with (i) a previously proposed adaptive refresh technique and (ii) a new pattern matching technique. We also show that we can provide QoS guarantee in disseminating dynamic data using LQG control theoretic approach. We also develop a generic model to handle multiple queries involving multiple dynamic data items. Work to provide Quality of Service (QoS) Guranttee to handle multiple queries involving multiple dyanmic data items is left to the future.

Speaker : Saju Jude Dominic
Institute : IIT Guwahati
Title : The Random Buffer Tree
Abstract :
In this paper, we present a probabilistic self-balancing dictionary data structure for massive data sets, and prove expected amortized I/O-optimal bounds on the dictionary operations. We show how to use the structure as an I/O-optimal priority queue. The data structure, which we call as the random buffer tree, abstracts the properties of the random treap and the buffer tree. The random buffer tree immediately yields an I/O-optimal randomized algorithm for sorting numbers in external memory. We discuss heuristics to transform the random buffer tree into a self-adjusting data structure suitable for applications with skewed access patterns.

Speaker : Ms. Alka
Institute : IITG
Title : Two Fault-Containment Self-Stabilizing Spanning Tree Algorithm
Abstract :
A self-stabilization (1) system can automatically recover from arbitrary transient faults, and changes in the environment of the system, without any external intervention. A transient fault is one which instantaneously corrupts the states of one or more processses, but does not affect the program in anyway. In most of the existing distributed self-stabilizing protocols, recovery from even a small number of faults in the system is guaranteed, but takes a long time and is achieved only after spreading the fault in system.This limitation restricts the applicability of most self-stabilizing protocols in use. As a solution, the idea of fault-containment (2) has been suggested. Fault-containment is added to a self-stabilizing protocol to contain the effects of faults in the system. Adding of fault-containment to an existing self-stabilizing protocol necessitates more variables than in the original stabilizing algorithm. These variables store the information that helps in identifying the faulty node and, if the model is asynchronous, in synchronizing the execution of the nodes. In this work, we give a fault-containing self-stabilizing spanning tree protocol for one-fault and two-fault systems. Our model is the asynchronous shared memory model.We improve an earlier self-stabilizing spanning tree protocol designed by Chen,Yu,Huang(4) appropriately to derive the fault-containing protocol. We use the multiphase technique (3) for fault-containment. The advantages of the multiphase techniques are that verification is easier and extra variables required for synchronization are not needed. In the one fault case, we show that if we use the multiphase technique, the containment space needed is only four bits instead of the O(d) (where d is the maximum degree of a node in the graph) space in the earlier fault-containing self-stabilizing spanning tree algorithm. The two-fault case, to the best of our knowledge, has not been addressed before.

Speaker : Saketh Saurabh
Institute : CMI
Title : Efficient fixed parameter tractable algorithms for undirected feedback vertex set. (Joint work with Dr. V raman and Dr. C R Subramanian)
Abstract :
Feedback Vertex Set (FVS) problem is among the six classical NP complete problems. Given an undirected graph G=(V,E), FVS F is a minimum cardinality subset of V such that it contains at least one vertex from every cycle in G. It has been studied quite extensively and an approximation algorithm of factor 2 is known. But in real life many a time we need an exact solution and one way to cope with this is to use parametrized complexity. In the framework of parameterized complexity, a problem with input size n and an integer parameter k is fixed parameter tractable (FPT) if there exists an algorithm to solve the problem in O(f(k)n^{O(1)}) time where f is any function of k. Such an algorithm is quite useful in practice for small ranges of k (against a naive n^{k+O(1)}) algorithm. We have given the best known FPT algorithm for the decision version of the FVS problem. This is a O(max{6^{k},(4 log k +3)^{k}}.n^{\omega}) algorithm for testing whether an undirected graph on n vertices has FVS of size at most k. Here n^{\omega} is the complexity of the most efficient matrix multiplication.

Speaker : Viswanath Pulabaigari
Institute : IISc
Title : A fast and efficient nearest neighbor classifier with constant classification time.
Abstract:
The nearest neighbor classifier (NNC) is a popular non-parametric classifier. It is a simple classifier with no design phase and shows good performance. Important factors affecting the efficiency and performance of NNC are (i) memory required to store the training set, (ii) classification time required to search the nearest neighbor of a given test pattern, and (iii) due to the curse of dimensionality it becomes severely biased when the dimensionality of the data is high with finite samples. In this paper we propose (i) a novel pattern synthesis technique to increase the density of patterns in the input feature space which can reduce the curse of dimensionality effect, (ii) a compact representation of the training set to reduce the memory requirement, (iii) a weak approximate nearest neighbor classifier which has constant classification time, and (iv) an ensemble of the approximate nearest neighbor classifiers where the individual classifier's decisions are combined based on the majority vote. The ensemble has constant classification time upperbound and according to empirical results, it shows good classification accuracy. A comparison based on empirical results is shown between our approaches and other related classifiers.

Speaker : Siddhartha Tambat
Institute : IISc
Title :Characterizing the Phase Behaviour of SPEC CPU 2000 Benchmarks
Abstract:
Memory performance has become a major bottleneck for current microprocessors due to the widening speed gap between processor and main memory. To avoid large performance losses due to long memory access delays, processors rely on a hierarchy of caches. Unfortunately, on-chip caches are not always effective due to latency, power, and transistor budget constraints. To at least partially overcome the limitations of caches, data can be prefetched into the cache. Prefetching can be initiated in either hardware or software. Compared to software prefetching, hardware prefetchers have the advantage of runtime information availability. Typically, hardware prefetchers rely on capturing specific repeating patterns observed in memory reference streams by using tables to record history information related to data accesses. For example, stride prefetchers target load instructions that stride through the address space. Although they are simple, conventional stride prefetchers store prefetch history inefficiently resulting in cache pollution and memory bandwidth contention due to useless prefetches. In this paper, with the aim of using table history more effectively, we characterize the time varying behaviour of entries which issue useful prefetches. Using algorithms from machine learning, we show that this behaviour exhibits phases and that different sets of a small number of entries that generate useful prefetches are active in different phases of the program. Overall, our results suggest that a carefully tuned phase-based stride prefetcher can effectively use a small amount of history (16--128 entries) to improve both prefetch accuracy and coverage.

Speaker : Basant Kumar Dwivedi
Institute: IITD
Title : Estimation of Communication Overheads for Shared Memory Application Specific Multiprocessors
Abstract:
In this paper, we present an analytical approach to estimate the contention for the shared resources such as shared bus and shared memory in System on Chip (SoC) heterogeneous multiprocessor architectures with non-uniform memory accesses. Our approach takes into account the re-submissions of the access requests appearing due to contention. We have also modeled the effect of arbitration policy more accurately. The experimental results show very good correspondence between estimation and simulation. Our approach can be effectively used to evaluate a particular mapping of application onto the heterogeneous multiprocessor architectures.

Speaker : Anup Gangwar
Institute : IITD
Title : Evaluating Inter-cluster Communication in Clustered VLIW Architectures
Abstract :
VLIW processors have started gaining acceptance in the embedded systems domain. However, monolithic register file VLIW processors with a large number of functional units are not viable. This is because of the need for a large number of ports to support FU requirements, which makes them expensive and extremely slow. A simple solution is to break up this register file into a number of small register files with a subset of FUs connected to it. These architectures are termed as clustered VLIW processors. In this talk we first build a case for clustered VLIW processors with more than four clusters. We show that traditional media applications have more ILP than is currently believed. We next provide a classification of the inter-cluster interconnection design space, and show that a large part of this design-space is currently unexplored. Finally using our performance evaluation methodology, we evaluate a subset of this design space and show that the most commonly used type of interconnection, RF-to-RF, fails to meet achievable performance by as much as 80%, while certain other types of interconnections can lower this gap to as much as 38%. We also establish that this behavior is heavily application dependent. Finally, based on our results, we propose a new interconnection network which on the average is likely to be more efficient than those currently used in both research as well as commercial domains.

Institute : IITD
Title : A multi-agent framework based on communication and concurrency.
Abstract :
The general title of my project is "Verification and Semantics" and specifically I am working on the "Semantics and Verification of Agent Programming Languages". In a multi-agent system that consists of various agents, each agent program communicates with other agents through an agent communication language (ACL), to fulfill it's goals. Two most popular ACLs are being used are KQML, and FIPA-ACL. FIPA-ACL has message types like inform(f) to inform some other agent that formula f holds, and request(a) to request an agent to do action a. It also includes other message types for various purposes. Semantics of these operators are defined by a language called SL, which is a quantified multi modal logic and includes BDI (Belief, Desire, and Intention respectively) modalities. BDI agents today have been received more attention in the literature. The problem of agent communication verification is to check whether agents that use an specific ACL, conform with its semantics or not, i.e. when an agent sends a message(it is also called communicative act) to other agent, whether it satisfies the semantics of the message or not. For example when agent i sends message inform(a) to agent j, it has to conform with the semantics of inform message or simply satisfy the preconditions of the message, defined in the ACL.
In my research, we define a framework for agent programming and communication. We use CCS as agent programming language, and extend it with some primitive communicative acts (message types) from FIPA-ACL. The communicative acts(CA) that we use, are inform(f) and request(a). The semantics of these communicative acts are defined in the FIPA specifications. We define the semantics of proposed language (which we call ECCS) in terms of Structural Operational Semantics(SOS). Then we introduce a variant version of CTL logic (which we call ACTL), to define the specifications of agent systems, which must be satisfied by agents. Finally we write a model checking algorithm to verify the correctness of programs in satisfying defined specifications.

Speaker : R.Manimegalai
Institute : IITM
Title : MemMap-pd: Performance Driven Technology Mapping Algorithm for FPGAs with Embedded Memory Arrays
Abstract :
Modern day Field Programmable Gate Arrays (FPGA) include in addition to Look-up Tables, reasonably big configurable Embedded Memory Blocks (EMB) to cater to the on-chip memory requirements of systems/applications mapped on them. While mapping applications on to such FPGAs, some of the EMBs may be left unused. This paper presents a methodology to utilise such unused EMBs as large look-up tables to map multi-output combinational sub-circuits of the application, with depth minimisation as the main objective along with area minimisation in terms of the number of LUTs used. Depth minimisation is an important goal while mapping performance driven circuits. Experimental results show that our proposed methodology, when employed on popular benchmark circuits, leads to upto 14% reduction in depth with comparable reduction in area.

Institute : IITM
Title : Extracting Schema from Ontologies (Joint work with Dr. P Sreenivasa Kumar)
Abstract:
Migrating to semantic web is going to be a fairly tough task for the current web sites. There is a need to adhere to the standard vocabulary realized through the ontologies. It is hard to expect web site authors to understand the intricacies of ontology development, for that matter even the formal description of an ontology. Ontology development and maintenance being the forte of domain experts and knowledge engineers, there has to be some means of presenting knowledge contained in ontology in a form that can easily be used by the web site authors. It would be useful if one could capture the essentials of domain specifications of an ontology in a schema language such that the web page authors could employ them in their job. This paper presents a translation scheme that translates OWL ontologies into XML Schema. At the end, we have arrived at some suggestions for language enhancement of XML Schema.

Institute : IITK
Title : A Decomposition Method for Support Vector Clustering
Abstract :
In this paper we look at how to apply the decomposition method for Support Vector Clustering (SVC) and compare its performance with that of non-decomposition methods which solves quadratic programming problem using traditional techniques. Decomposition is one of the major methods for solving SVMs and is known for its efficiency. SVC is a novel clustering method that uses SVM approach. SVC problem is formulated as a quadratic optimization with constrains to come up with clusters. When applying SVC to large data sets traditional ways of solving quadratic programming problem require huge memory and computational time. This is where application of decomposition method excel. Thus this paper discusses about applying decomposition method to SVC. We applied this method on a few benchmark data sets and results show an improvement in performance in terms of memory requirements and training time.

Speaker : Alpana Dubey
Institute : IITK
Title : Extracting Grammar from Programs
Abstract :
Many tools for software analysis and software engineering require the grammar of the source code programs. However, most legacy applications are written in the languages which have minor variations from the standard language. Normally we have grammar of the standard language. But the grammar of dialects are frequently unavailable. This paper presents some of the attempts of grammar extraction from programs. Furthermore it suggests a new technique for grammar extraction. The new technique is explored and some initial observations are given.

Speaker : Narottam Chand
Institute : IITR
Title : Energy Efficient Cache Invalidation for Mobile Clients
Abstract :
Caching at mobile client is an important technique for improving the performance in wireless data dissemination. It can reduce the number of requests sent by the client to the server, reduce the server load, shorten the query latency and increase the data availability. Battery energy and limited bandwidth are two major constraints imposing challenges to the realization of caching at mobile clients. Once caching is used, a cache invalidation strategy is needed to ensure that the data objects cached in a mobile client are consistent with those stored in the server. We propose an invalidation report (IR) based caching strategy named cache directory (CD), which facilitates clients to selectively tune to the portions of the report. To minimize uplink requests, this approach broadcasts all the recently updated data objects that are cached. Query latency and energy consumption are used as major performance metrics. Due to reduced number of uplink requests and selective tuning of the mobile client to the broadcast channel, the CD strategy conserves the precious and limited client energy. Simulations are used to evaluate the effect of data update rates and it has been found that compared to previous IR based algorithms, the proposed strategy provides an improvement in terms of query latency and energy consumption.

Speaker : Ajey Kumar
Institute : IITR
Title : Location Dependent Data Caching in Mobile Environment
Abstract :
Advent of high-speed wireless network and popularity of portable devices have fueled the development of mobile computing. Mobile location\226dependent information services (LDISs) are gaining interest in recent years. They can provide traffic reports, travel information, emergency information, nearest-neighbor queries, etc. In these services, data values depend on their locations. Caching frequently accessed data on mobile clients can help in saving bandwidth and improving system performance. Since, client location changes constantly, location-dependent data may become obsolete due to clients movement across the network. In this paper, we will present a comprehensive survey of location models, location dependent queries, and location-dependent cache invalidation and replacement policies. The fundamental techniques underlying the proposed approaches will be identified and classified along various dimensions.

Speaker : Sivaramakrishnan Sivasubramanian
Institute : TIFR
Title : A multiprocessor scheduling problem
Abstract :
We consider the problem of scheduling a set of $n$ jobs on $m$ machines where every job has to run on {\it all} the machines. The objective is to minimize the total completion times of all the jobs. We provide an approximation algorithm that produces a solution that costs at most twice the optimum. We also show that there is a constant $\epsilon >0$ such that unless $\cP = \cNP$, no polynomial-time algorithm can produce a solution that is at most a factor $1 + \epsilon$ of the optimum.