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.
Speaker : Jamshid Bagherzadeh
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.
Speaker : Sujatha R Upadhyaya
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.
Speaker : Vijaya V Saradhi
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.