 Events |
|
| Seminars |
|
| Multimedia Archive |
|
|
|
 |
| UPCOMING SEMINARS |
|
Series: Department Seminar
Title: A Sensor Network System for Measuring Traffic Behavior in Road Work Zones - Speaker: Dr. Nigamanth Sridhar
Visiting Scientist - Date and Time: Friday, March 09, 2012, 4:00 PM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
In this talk, we present the design and implementation of a sensor network
system for monitoring the flow of traffic through temporary construction work zones.
As opposed to long-term work zones which are common on highways, short-term or
temporary work zones remain active for a few hours or a few days at most. As such,
instrumenting temporary work zones with monitoring equipment similar to those used
in long-term work zones is not practical. Yet, these temporary work zones present an
important problem in terms of crashes occurring in and around them. Our design for a
sensornet-based system for monitoring traffic is (a) inexpensive, (b) rapidly
deployable, and (c) requires minimal maintenance. We report on our experiences in
building this system, and with testing our system in live work zones in the
Cleveland area.
Host Faculty: Prof. K. Gopinath
| Series: Department Seminar
Title: Continuity in Scientific Visualization: - Speaker: Dr. Hamish Carr
Senior Lecturer
School of Computing
University of Leeds, UK - Date and Time: Tuesday, March 06, 2012, 11:00 AM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
Scientific computation is most commonly used to simulate continuous
phenomena. Scientific visualization, therefore, depends very heavily
on continuity in the mathematical models to be applied. Thus, not only
do good visualizations depend on good data, they depend on understanding
and reproducing the assumptions about continuity that underlie the
computation in the first place. Moreover, some implications of continuity
that are not part of conventional numerical analysis become increasingly
important when we attempt to present large-scale data to a human viewer.
One of the stages where this occurs is presenting a discrete representation
based on particles, voxels or meshes to the human eye. Since the human eye
expects visual continuity, it becomes important how continuity is reintroduced
after the computation. Another stage where this occurs is in topological
analysis - as data gets ever more massive, more sophisticated forms of
analysis are invoked, and these too depend on assumptions about continuity.
The presentation will therefore cover the fundamental role of continuity in
how we approach scientific visualization, some examples of where the choice
of models of continuity causes real difficulties, and a discussion of some
problems where the assumptions of continuity in visualization and analysis
are in tension with the assumptions of continuity in numerical simulation
Speaker Bio:
Hamish Carr completed his PhD at the University of British Columbia in May
2004 and has worked as a lecturer at University College Dublin and a
senior lecturer at the University of Leeds. His research interests include
scientific and medical visualization, computational geometry and topology,
computer graphics and geometric applications.
Host Faculty: Dr. Vijay Natarajan
| Series: Department Seminar
Title: Stackless Multi-threading in Small Embedded Systems - Speaker: Dr. Nigamanth Sridhar,
Visiting Scientist - Date and Time: Friday, March 02, 2012, 4:00 PM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
Programming support for multi-threaded applications on embedded
microcontroller platforms has attracted a considerable amount of research attention
in the recent years. This talk is focused on this problem, and presents UnStacked C,
a source-to-source transformation that can translate multithreaded programs into
stackless continuations. The transformation can support legacy code by not requiring
any changes to application code, and only modifications to the underlying threading
library. We describe the details of UnStacked C in the context of the TinyOS
operating system for wireless sensor network applications. We present a modified
implementation of the TOSThreads library for TinyOS, and show how existing
applications programmed using TOSThreads can be automatically transformed to use
stackless threads with only modifications in the build process. By eliminating the
need to allocate individual thread stacks and by supporting lazy thread preemption,
UnStacked C enables a considerable saving of memory used and power consumed,
respectively.
Host Faculty: Prof. K. Gopinath
| Series: Department Seminar
Title: Capturing Temporal Behavior in Contract-Based Specifications - Speaker: Dr. Nigamanth Sridhar,
Visiting Scientist - Date and Time: Friday, February 17, 2012, 4:00 PM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
Interrupt- and event-driven applications constitute an important system
class, with connections to desktop computing, embedded systems, and sensor networks.
We refer to this set of applications collectively as reactive systems. In this talk,
we present a specification idiom for documenting reactive system behavior.
Specifically, we discuss an approach to documenting split-phase operations ---
operations that involve a request, followed by a deferred out-of-context callback.
We derive the idiom by example using interfaces from the TinyOS library, a popular
component library for sensor network applications. We extend this specific example
to a broader discussion of specification idioms for reactive systems. We also
present details on how these specifications can be enforced at runtime using
monitoring infrastructure.
Host Faculty: Prof. K. Gopinath
| Series: Department Seminar
Title: Packet flow analysis in IP networks using data-flow analysis - Speaker: K. V. Raghavan
- Date and Time: Friday, February 17, 2012, 11:30 AM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
Static analysis (aka offline analysis) of a model of an IP network is
useful for understanding, debugging, and verifying packet flow properties
of the network. Data-flow analysis is a method that has typically been
applied to static analysis of programs. We propose a new,
data-flow based approach for static analysis of packet flows in networks.
We also investigate
an application of our analysis to the problem of inferring a high-level
policy from the network, which has been addressed in the past only for a single
router.
Speaker Bio:
K. V. Raghavan is an Assistant Professor in the Dept. of CSA, IISc. His research is in the areas
of program analysis, program verification, and software development tools.
| Series: Department Seminar
Title: Down the Rabbit Hole: Robust Proximity Search in Sublinear Space. - Speaker: Mr. Nirman Kumar
Computer Science Dept.
University of Ilinios, Urbana-Champaign - Date and Time: Wednesday, February 15, 2012, 4:00 PM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
For a set of n points in Re^d, and parameters k and eps, we present a
data structure that answers (1+eps)-approximate k nearest neighbor queries
in logarithmic time. Surprisingly, the space used by the data-structure is
otilde(n/k); that is, the space used is sublinear in the input size if k
is sufficiently large. Our approach provides a novel way to summarize
geometric data, such that meaningful proximity queries on the data can be
carried out using this sketch.
Host Faculty: Dr. Sathish Govindarajan
|
|
PAST SEMINARS |
|
Series: Department Seminar
Title: Fault Tolerance in Distributed Systems: A Coding-Theoretic Approach - Speaker: Mr. Bharath B
- Date and Time: Thursday, February 09, 2012, 4:15 PM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
Distributed systems are rapidly increasing in importance due to the
need for scalable computation on
huge volumes of data. This fact is reflected in many distributed
applications such as
Amazon?s cloud computing service, Google?s BigTable or Apache?s
Hadoop framework. Replication is the
prevalent solution for fault tolerance in these systems. This
solution, though simple, is wasteful in terms of both the
space and infrastructure costs required to host the backups. We
present a new paradigm to solve this
problem, broadly referred to as fusion, that combines the operational
efficiency of replication with
the space efficiency of coding theory. To make our techniques
generally applicable, we describe
fusion in two separate contexts: finite state machines and infinite
state machines.
For finite state machines, we present a polynomial time algorithm to
generate efficient backup machines. For
infinite state machines, we consider programs that host large data
structures such as linked
lists, stacks, vectors and maps. Using a combination of erasure codes
and selective replication, we
present an algorithm to generate efficient backup data structures. We
prove the minimality of our schemes and also provide experimental
results
that confirm the same. Finally, we present a fusion-based design for
fault
tolerance in two real world applications: Amazon?s key-value store,
Dynamo, and Google's Map Reduce
framework, that is much more efficient than the current
replication-based approach.
Speaker Bio:
Bharath B is a Ph.D student at University of Texas at Austin.
Host Faculty: Prof. Shalabh Bhatnagar
| Series: Ph.D. Colloquium
Title: Improving Memory Subsystem Performance through Performance Aware Prefetching and
Efficient Shared-Cache Management in Multi-Core Systems - Speaker: R. Manikantan
- Faculty Advisor: R. Govindarajan
- Date and Time: Friday, February 03, 2012, 4:00 PM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
With off-chip memory access taking 100's of processor cycles, getting data to the
processor in a timely fashion remains one of the key performance bottlenecks in
current systems. With increasing core counts, the problem of hiding the memory
access latency is likely to become even more critical. A combination of on-chip
caches and prefetchers is used to reduce the average off-chip memory access latency.
While a hierarchy of caches focus on exploiting locality by retaining useful data,
prefetchers complement them by attempting to hide the cache misses by initiating
data accesses early. Thus our focus in this thesis is on improving the memory system
performance through performance aware prefetching and efficient shared cache
management in multi-core systems.
It is well known that aggressive prefetching can harm performance due to increased
contention for memory bandwidth and cache pollution. Second, certain (static)
load/store instructions are known to be performance critical. But prefetchers treat
all loads/stores as equal. Further, enabling prefetching for all loads might dilute
the prefetch history. These motivate us to focus on a small subset of performance
critical loads. Our work identifies that a small number of static loads, referred to
as Loads Incurring Majority of Commit Stalls(LIMCOS), account for a majority of the
commit stalls in processors. We show that simple history based hardware called
classifiers can identify LIMCOS with high accuracy. In our first contribution,
Focused Prefetching, we use the classifiers to focus the prefetching efforts on
LIMCOS. This is achieved in a generic prefetcher-agnostic fashion by filtering the
history used by the prefetchers. Focused Prefetching improves performance in terms
of IPC by 9.8% for a set of memory intensive SPEC2000 workloads. This performance
gain is achieved along with a reduction in memory traffic and improved prefetch
accuracy.
Prefetchers rely on regularity in their training stream to predict and avoid future
misses. Typically the training stream is comprised of primary misses seen at the
cache level. We quantify the regularity present in the training stream using entropy
and study the impact on regularity by extending the training stream to include
secondary misses and accesses. We also consider triggering prefetches on secondary
misses. We find that the extended histories are more regular in general and it is
beneficial to trigger prefetches on secondary misses also. However, the best design
choice varies on a per-benchmark and prefetcher basis necessitating a dynamic
approach to identify the best prefetcher configuration. We propose an inexpensive
bloom filter based dynamic mechanism to identify the best performing prefetch design
point at run time. The adaptive scheme improves the IPC by 4.6% on average over a
baseline prefetcher along with a reduction in memory traffic requirements.
In the second part of the thesis, we focus on improving the performance of shared
caches in multi-core systems. Last level caches are affected by a lack of temporal
locality in the access stream as the locality gets filtered out by caches above it.
In the case of multi-cores, the interleaving of accesses from the various cores
further adds to the problem. To overcome this, we propose a PC-Centric Next-Use
Aware Cache Organization (NUcache) for shared caches in multi-cores. NUcache relies
on a cache organization with an ability to retain a subset of cache blocks longer.
This is achieved by a logical partitioning of the associative ways of a cache set
into MainWays and DeliWays. While all the blocks have access to the MainWays, blocks
that are accessed in the near future upon eviction (Next-Use of the block) are
candidates to be retained longer in the DeliWays to eliminate future misses. While
it is difficult to learn the next-use of each individual cache block, we make use of
the fact that a small number of PCs, referred to as delinquent PCs, bring in a
majority of the cache blocks. We learn the Next-Use characteristic of blocks brought
in by the delinquent PCs and use an intelligent cost-benefit based PC-selection
mechanism to identify the best set of delinquent PCs that should have access to the
DeliWays to maximize the cache hits. Performance evaluation reveals that NUcache
improves the performance over a baseline design by 9.6%, 30% and 33% respectively
for dual, quad and eight core workloads comprised of SPEC benchmarks. NUcache also
performed better than other state-of-the-art cache partitioning mechanisms.
The last part of the thesis deals with shared cache management in multi-core systems
to achieve different performance objectives. Explicitly controlling the shared cache
occupancy of competing applications is a flexible and practical way to achieve a
variety of high level performance goals like Quality of Service(QoS). Existing
solutions control cache occupancy at a coarser granularity, do not scale well to
large core counts and in some cases lack the flexibility to support a variety of
performance goals. To overcome this, we propose Probabilistic Shared Cache
Management (PriSM), a framework to manage the cache occupancy of different cores at
cache block granularity by controlling their eviction probabilities. The proposed
framework requires only simple hardware changes to implement, can scale to larger
core count and is flexible enough to support a variety of performance goals. We
demonstrate the flexibility of PriSM, by appropriately choosing the eviction
probabilities needed to achieve goals like hit-maximization, fairness and QOS. PriSM
with Hit-Maximization improves the performance by 18.4% over baseline LRU in a
sixteen core machine. PriSM-Fairness improves fairness over existing solutions by
23.3% along with a performance improvement of 19.0%.
| Series: M.Sc. (Engg) Colloquium
Title: Mechanisms and Algorithms for Allocation of Carbon
Reduction Units to Strategic Emitting Agents in a
Carbon Economy - Speaker: Udaya Lakshmi L
- Faculty Advisor: Y. Narahari
- Date and Time: Monday, January 30, 2012, 4:00 PM
- Venue: CSA Lecture Hall (Room No. 117, Ground Floor)
Abstract
Climate change and global warming represent issues of serious concern
and the whole world is actively engaged in initiating and undertaking
measures to mitigate the dangerous effects of these phenomena. In this
context, countries and global companies are now striving to reduce carbon
emissions as far as possible.
In this dissertation, we look at the problem of emission reduction from the
perspective of a global company which has many internal divisions and
strategic supply chain partners. The specific problem we address is that of
allocating a given target of carbon reduction units among the constituent
divisions and partners. To solve this problem in an optimal way, the
company needs to know the cost functions for emission reduction from the
different divisions and partners. Since the divisions and partners are
often autonomous entities and could exhibit strategic behaviour, the
company may not be able to elicit the cost functions truthfully. In this
dissertation, we use techniques from game theory and mechanism design to
elicit the cost functions truthfully and allocate emission reductions in a
way that divisions that participate satisfactorily in emission reductions
are amply rewarded and divisions which participate unsatisfactorily are
appropriately penalised. We propose two mechanisms which are
complementary; the first one is based on a forward auction and the
second one on a reverse auction. The proposed mechanisms trade off
three important properties namely incentive compatibility, allocative
efficiency, and budget balance.
| Series: M.Sc. (Engg) Colloquium
Title: An algorithmic characterization of polynomial
functions over Z_{p^n} - Speaker: Ashwin Guha
- Faculty Advisor: Ambedkar Dukkipati
- Date and Time: Friday, January 27, 2012, 3:30 PM
- Venue: CSA Multimedia Class (Room No. 252, First Floor)
Abstract
The problem of polynomial representability of functions is central to
many branches of mathematics. If the underlying set is a finite field,
every function can be represented as a polynomial. In this thesis we
consider polynomial representability over a special class of finite
rings, in particular, Z_{p^n}, where p is a prime and n is a positive
integer. This problem has been studied in literature and the two
notable results were given by Carlitz (1965) and Kempner (1921). While
the Kempner's method enumerates the set of distinct polynomial functions,
Carlitz provides a necessary and sufficient condition for a function
to be polynomial using Taylor series. Further, these results are
existential in
nature.
The aim of this thesis is to provide an algorithmic characterization,
given a prime p and a positive integer n, to determine whether a given
function over Z_{p^n} is polynomially representable or not. Note that one
can give an exhaustive search algorithm using the previous
results. Our characterization involves describing the set of
polynomial functions over Z_{p^n} with a 'suitable' generating set. We
make use of this result to give an non-exhaustive algorithm to
determine whether a given function over Z_{p^n} is polynomial
representable.
| Series: Ph.D. Thesis Defense
Title: Compiler transformations for improving the performance of software
transactional memory. - Speaker: Ms. Sandya Mannarswamy, PhD Engg. [ERP]
- Faculty Advisor: Prof. R. Govindarajan
- Date and Time: Friday, January 27, 2012, 11:30 AM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
Expressing synchronization using traditional lock based primitives has been found to be both error-prone and restrictive. Hence there has been considerable research work to develop scalable and programmer-friendly alternatives to lock-based synchronization. Atomic sections have been proposed as a programming idiom for expressing synchronization at a higher-level of abstraction than locks.
One way of supporting atomic sections in software is to rely on an underlying Software Transactional Memory (STM) implementation. While STM offers the promise of being a programming paradigm which is less error-prone and more programmer friendly compared to traditional lock-based synchronization, it also needs to be competitive in performance in order for it to be adopted in mainstream software. Unfortunately STMs do not meet the performance goals and are known to incur excessive performance overheads.
Prior work by other researchers and our performance analysis of STM applications show that conflicts and the resulting aborts are a major performance bottleneck for STM applications. Second we find that, supporting fine-grained optimistic concurrency can have significant impact on the cache behavior of applications running on STM and hence can adversely affect STM performance. Our systematic quantitative analysis of the cache behavior of STM applications as well as prior work on qualitative analysis of STM overheads show that cache overheads constitute a major performance bottleneck for STM applications. Hence in this thesis, we focus on addressing these two major STM performance bottlenecks.
Current STM implementations are typically application unaware in that they do not analyze the application and use that knowledge to improve the application performance on STM. Closer integration of transactions with the programming languages opens up the possibility of using compiler to analyze STM applications and using that knowledge to perform application code transformations to improve the application performance on STM automatically and in a manner transparent to the programmer. This motivated us to address the two major STM performance bottlenecks namely poor cache performance and performance penalty aborts due to aborts, by compiler transformations.
In order to pinpoint the cache bottlenecks of STM, we perform a detailed experimental evaluation of the cache behavior of STM applications and quantify the impact of the different STM factors on the cache misses experienced by the applications. We propose a set of compiler transformations targeted to address the cache performance bottlenecks identified by our analysis. Next we turn our attention to compiler analysis and transformations targeted at reducing the performance overheads due to transactional aborts, effectively utilizing the compiler's knowledge of the data access patterns of the application. Since not all applications are designed with optimistic concurrency in mind, real world applications typically contain certain atomic sections which are not amenable to STM's optimistic concurrency control and hence suffer from excessive transactional abort overheads. We propose two compiler techniques for handling such atomic sections.
Another major cause of transactional conflicts leading to unnecessary aborts is the uniform access tracking granularity tracking scheme employed by STM implementations. Using a single uniform access tracking granularity leads to poor lock assignment by STM. We propose techniques which use compiler's knowledge of an application to improve the application unaware lock assignment made by the STM. Last,as transactional abort overheads impact STM performance adversely, we propose a compiler based approach to reduce the transactional abort overheads by reconciling certain kinds of transactions instead of aborting them and then performing a complete re-execution. We show that our combined set of compiler transformations are effective in improving the performance of a set of STAMP benchmarks by reducing the execution time by 7.48% to 54.82%, aborts by 8.98% to 56.61% and the average D-cache miss latency by up to 33.51%.
| Series: Ph.D. Thesis Defense
Title: Simulation based methods for Optimization - Speaker: Mr. Vivek Kumar Mishra, Ph.D
- Faculty Advisor: Prof. Shalabh Bhatnagar
- Date and Time: Monday, January 23, 2012, 3:00 PM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
In many engineering problems, one is often interested in optimizing a parameterized performance objective. If the objective function is analytically known and its derivatives easily computable, then a number of methods such as gradient descent, Conjugate direction and quasi-Newton can be directly applied.
However in many real life problems belonging to a variety of disciplines such as neural networks, supply chain management, computer networks etc., only noisy observations of the objective function can be obtained. Besides, such observations are time/resource consuming. In many of these applications, the objective function corresponds to a long run average performance metric obtained from simulation. In such scenarios, often local search algorithms that perform incremental updates along descent directions are used. Different algorithms here differ in the way by which the descent direction is estimated. In one such approach that goes by the name of perturbation analysis (PA), one looks for ways to get a gradient estimate at any parameter value based on only one or a small number of simulation runs. However, PA type methods require constraining regularity assumptions on the process parameters and performance objectives. Finite difference stochastic approximation(FDSA) is another approach for simulation optimization problems. FDSA does not require the constraining regularity assumptions and is more universally applicable. A classical FDSA method is the Kiefer-Wolfowitz (K-W) finite difference algorithm. In a random directions version (Simultaneous Perturbation Stochastic Approximation (SPSA)) of K-W, all parameters are randomly perturbed together to obtain two function measurements that are then used to approximate the gradient. This results in huge savings in the number of function evaluations especially for higher dimensional problems. SPSA has been widely studied and is seen to perform well in general. Another algorithm based on random perturbations is the smoothed functional algorithm (SFA). Here one approximates the gradient of the objective function by a convolution of the same with a multivariate normal distribution. In this work we will focus on a variety of FDSA algorithms based on random perturbations and study their applications. In particular because of their scalability properties we will mainly concentrate on SPSA and SFA based algorithms.
PA and FDSA based algorithms were originally developed in the settings involving no functional constraints. In many real life problems we require optimization subject to constraints. For example, in communication networks, one is often interested in (say) maximizing the throughput of a connection subject to constraints on the quality of service (QoS) requirements. A constraint there could specify that the mean packet delay should be below a desired threshold such as a few milliseconds. Similarly another constraint could specify that the expected fraction of packets lost in transmission is below another threshold. We develop four algorithms for simulation based optimization under multiple inequality constraints. Both the cost and the constraint functions are considered to be long-run averages of certain state-dependent single-stage functions. We pose the problem in the simulation optimization framework by using the Lagrange multiplier method. Two of our algorithms estimate only the gradient of the Lagrangian while the other two estimate both the gradient and the Hessian of it. In the process, we also develop various new estimators for the gradient and Hessian. All our algorithms use two simulations each. Two of these algorithms are based on the smoothed functional (SF) technique while the other two are based on the simultaneous perturbation stochastic approximation (SPSA) method. We prove the convergence of our algorithms and show numerical experiments on a setting involving a network of queues. The Newton-based SF algorithm is seen to show the best overall performance.
A typical discrete parameter optimization problem can be expressed as finding a parameter value within a discrete set for which the parameterized objective function is minimized. In the setting that we consider, the objective is in fact a long run average performance metric. We present two efficient discrete parameter simulation optimization (DPSO) algorithms in this setting. One of these algorithms uses a smoothed functional approximation (SFA) procedure while the other is based on simultaneous perturbation stochastic approximation (SPSA). The use of SFA for DPSO had not been proposed previously in the literature. Further, both algorithms adopt an interesting technique of random projections that we present for the first time. We give a proof of convergence of our algorithms. Next, we present detailed numerical experiments on a problem of admission control with dependent service times. We consider two different settings involving parameter sets that have moderate and large sizes, respectively. On the first setting, we also show performance comparisons with the well-studied optimal computing budget allocation (OCBA) algorithm and also the equal allocation algorithm.
A stochastic differential equation(SDE) is a differential equation in which at least one of the terms is a stochastic process(usually a Brownian motion). Thus the solution of SDE itself is a stochastic process. SDEs are used to model diverse phenomena such as portfolio optimization, aerospace systems and wireless networks. We consider the problem of estimating the optimal parameter trajectory over a finite time interval in a parameterized SDE and propose a simulation based algorithm for this purpose. Towards this end, we consider a discretization of the SDE over finite time instants and reformulate the problem as one of finding an optimal parameter at each of these instants. A stochastic approximation algorithm based on the smoothed functional technique is adapted to this setting for finding the optimal parameter trajectory. A proof of convergence of the algorithm is presented and results of numerical experiments over two different settings are shown. The algorithm is seen to exhibit good performance. We also present extensions of our framework to the case of finding optimal parameterized feedback policies for controlled SDEs and present numerical results in this scenario as well.
Finally, we consider a parameterized SDE model of slotted Aloha with the retransmission probability as the associated parameter. We formulate the problem in finite and infinite horizon cost settings. In the first setting, we obtain an optimal parameter trajectory that prescribes the parameter to use at any given instant while in the second setting, we obtain an optimal time-invariant (scalar) parameter. Our algorithms are seen to exhibit good performance.
| Series: M.Sc. (Engg) Thesis Defense
Title: On the Complexity of Grobner Basis and Border Basis
Detection - Speaker: Mr. Prabhanjan Ananth, M.Sc Engg
- Faculty Advisor: Dr. Ambedkar Dukkipati
- Date and Time: Monday, January 23, 2012, 11:00 AM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
The theory of Grobner bases has garnered the interests of a large number of
researchers in computational algebra due to its applications not only in
mathematics but also in areas like control systems, robotics, cryptography
to name a few. It is well known that the computation of Grobner bases takes
time doubly exponential in the number of indeterminates rendering it
impractical in all but a few places. The current known algorithms for
Grobner bases depend on the term ordering over which Grobner bases is
computed. In this thesis, we study computational complexity of some problems
in computational ideal theory. We also study the algebraic formulation of
combinatorial optimization problems.
Gritzmann and Sturmfels (1993) posed the following question: Given a set of
generators, decide whether it is a Grobner bases with respect to some term
order. This problem, termed as the Grobner Basis Detection (GBD) problem,
was introduced as an application of Minkowski summand of polytopes. It was
shown by Sturmfels and Wiegelmann (1997) that GBD is NP-hard. We study the
problem for the case of zero-dimensional ideals and show that the problem is
hard even in this special case. We study the detection problem in the case
of border bases which are an alternative for Grobner bases in the case of
zero dimensional ideals. We propose the Border Basis Detection (BBD) problem
which is defined as follows: Given a set of generators of an ideal, decide
whether that set of generators is a border basis of the ideal with respect
to some order ideal. We show that BBD is NP-complete.
We also formulate the rainbow connectivity problem as a system of polynomial
equations such that solving the polynomial system yields a solution to it.
We give an alternate formulation of the rainbow connectivity problem as a
membership problem in polynomial ideals.
| Series: Department Seminar
Title: Can Proactive Cyber Forensics Improve Security of SCADA Systems? - Speaker: Narayanan Subramanian
Associate Professor of Computer Science and
Director of the Center for Petroleum Security Research
University of Texas at Tyler - Date and Time: Friday, January 13, 2012, 4:00 PM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
Supervisory Control and Data Acquisition (SCADA) systems have become part of our lives by controlling and monitoring critical infrastructures such as water supply, electricity grid, railway network, and oil and gas pipelines. SCADA systems include sophisticated hardware and software components that are increasingly being interconnected with corporate IT network for ease of operation and maintenance. This also exposes SCADA systems to external threats which affect their security - malware such as Stuxnet and NightDragon have affected SCADA systems and their operators worldwide. Risk assessments for security usually consider well known threats and mechanisms employed to counter those threats. When a security breach occurs cyber forensics is employed to analyze data to collect evidence against perpetrators. Cyber forensics is a rapidly evolving field of computer science that applies digital investigative techniques to unearth evidence of a cyber-crime. Cyber forensics has several specialties including desktop forensics, mobile forensics, and network forensics. Can we apply cyber forensics in a proactive manner and improve security of SCADA systems? In this lecture we address this issue and consider possible research directions.
Speaker Bio:
Narayanan Subramanian is an Associate Professor of Computer Science at the University of Texas at Tyler. He is also the Director of the Center for Petroleum Security Research. He obtained his Ph.D. in Computer Science from the University of Texas at Dallas. His research interests include software engineering, system engineering, and security engineering.
Host Faculty: Y.N. Srikant
| Series: Department Seminar
Title: Building complex structures and functions with DNA - Speaker: Mr. Nikhil Gopalkrishnan
Department of Computer Science
Duke University - Date and Time: Friday, January 13, 2012, 2:30 PM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
Self-assembly is a fundamental, pervasive natural phenomenon
that gives rise to complex structures and functions. It
describes processes in which a disordered system of components
form organized structures as a consequence of specific, local
interactions among the components themselves, without any
external direction. Biological self-assembled systems, evolved
over billions of years, are more intricate, more energy efficient
and more functional than anything researchers have currently
achieved at the nanoscale. A challenge for human designed
physical self-assembled systems is to catch up with mother
nature. In this talk, we argue, through examples of our
contributions in the field, that DNA is an apt material to
meet this challenge. I will present:
(1) Self-assembled nanostructures:
(a) A 3D DNA nanoscale container with the geometry of a regular
tetrahedron based on Rothemund's Origami technique and
(b) a microscale 3D DNA lattice based on a cross-shaped nanoscale
double decker DNA tile.
(2) Functionality engineered through strand displacement interactions:
(a) Novel protocols that allow for high fidelity hybridization
of a DNA strand to a target strand in the presence of noise in
the form of other strands in solution with sequence similar to
that of the target.
(b) Synthetic biochemical systems, termed meta-DNA systems,
consisting only of DNA nanostructures that capture the
properties and structure of DNA in biological systems. Our
work is reductive: we use simple DNA hybridization chemistry
to emulate more complex enzyme based DNA chemistry.
(3) Algorithmic constructs in the tile assembly model:
(a) Optimally concise tile sets for assembling fixed length
linear structures in a probabilistic tile assembly model.
(b) Optimally concise tile sets for assembling squares within
small errors.
Speaker Bio:
Nikhil Gopalkrishnan is a PhD candidate and James B. Duke Fellow at
the Duke Computer Science department working with Prof. John Reif. His
research interests are in self-assembly based models of computation,
computing with DNA molecules and experimental DNA self-assembly.
Nikhil has published papers in ICALP, SICOMP, Algorithmica, Journal of
the Royal Society Interface and DNA Computing & Molecular Programming.
He has also co-authored chapters in three books reviewing research in
his field.
Host Faculty: Dr. Vijay Natarajan
| Series: Department Seminar
Title: Abstract domains of affine relations - Speaker: Tushar Sharma
- Date and Time: Friday, January 13, 2012, 10:00 AM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
This paper considers some known abstract domains for
affine-relation analysis (ARA), along with several variants, and
studies how they relate to each other.
We show that the abstract domains of Muller-Ohm/Seidl (MOS) and
King/Sondergaard(KS) are, in general,
incomparable, but give sound interconversion methods. We also show
that the methods of King and Sondergaard can be applied without
bit-blasting while still using a bit-precise concrete semantic.
Speaker Bio:
Tushar Sharma is a graduate student at the University of Wisconsin, Madison,
working under Professor Thomas Reps. He is working on abstract
interpretation of programs that use machine integers (i.e., modulo arithmetic), using
relational domains.
Host Faculty: K. V. Raghavan
| Series: Department Seminar
Title: Bio-medicine at the single cell level with analysis of shapes and
structures - Speaker: Dr. Saumyadipta Pyne, Ph.D.
Faculty Track Research Scientist in Medical Oncology,
Dana-Farber Cancer Institute,
Harvard Medical School, Boston, USA. - Date and Time: Thursday, January 12, 2012, 4:00 PM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
Biomedicine at high-resolution single-cell level is made possible by
reliable characterization of the state-spaces of complex higher-level
networks such as in cell signaling or differentiation. High-dimensional
multi-parametric flow cytometry could be used to generate per cell data for
investigating such networks. The resulting high-throughput and multivariate
cytomic data however presents an array of unique modeling challenges for
which adequate analytical frameworks did not exist until recently. For the
most interesting applications of cytomics, such as in stem cell and cancer
studies, it is critically important to create new computational and
statistical techniques for characterizing the underlying biological
state-spaces with both precision and rigor.
To address this challenge, I constructed several new algorithms and
platforms for automated single cell multi-marker expression data analysis.
The platforms introduced novel statistical methodology in the form of
finite mixture models of multivariate skew t and skew normal probability
distributions that are fit with new and efficient Expectation-Maximization
algorithms. Such parametric models allow robust modeling against asymmetry
and outliers in data. The algorithms model clusters (or "cell populations")
with complex shapes and structures within each sample in high-dimensional
marker-space, and then employ graph matching for registration of the
corresponding cell populations across samples to enable comparison of
different phenotypes and time points. I introduced a variety of new
algorithms for non-Gaussian clustering, nonlinear regression based curve
clustering and modal landscape modeling, etc. to identify the individual
cell populations in samples in an unsupervised manner, and then classify
these in terms of their high-dimensional shapes and structures. The
platforms have opened up new possibilities for many biomedical
applications, and I shall illustrate with examples from stem cell systems
biology, cell signaling, and clinical studies.
Speaker Bio:
Dr. Saumyadipta Pyne is a Faculty Track Research Scientist in Department of
Medical Oncology at the Dana-Farber Cancer Institute of Harvard Medical
School in Boston, USA. Dr. Pyne is also an Associate with the Broad
Institute of MIT & Harvard in Cambridge, Mass. Dr. Pyne received
his PhD. from the State University of New York at Stony Brook and his
postdoctoral training at MIT where he did pioneering work in computational
cytomics. His research interests include different aspects of multivariate
and non-Gaussian data modeling for cancer cytomics and metabolomics,
with applications ranging from epidemiology to single cell analytics.
Host Faculty: Dr. Shivani Agarwal
| Series: Department Seminar
Title: It is just not an Interconnect - Speaker: Prof. Chita Das, Pennsylvania State University
- Date and Time: Tuesday, January 10, 2012, 2:30 PM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Host Faculty: Prof. T. Matthew Jacob
| Series: Department Seminar
Title: Learning to make predictions in networks - Speaker: Professor Charles Elkan,
Department of Computer Science and Engineering,
University of California, San Diego - Date and Time: Wednesday, December 21, 2011, 4:00 PM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
Many phenomena in social science and in biology are
represented naturally as graphs or networks. Typically, the relevant networks are only known incompletely, so a fundamental research question is how to infer missing information in a network, given all available known information. In this talk I will present a general method for learning from known nodes and edges in a graph to predict labels for other nodes and edges. The new method induces latent features to represent implicit properties of nodes, and combines the latent features with any available explicit features to make accurate predictions. The method is an extension and combination of matrix factorization and a log-linear model. For link prediction, the new method achieves state of the art accuracy over a wider range of datasets, from biology and from social science, than any previous method. (Joint work with Aditya Menon.)
Speaker Bio:
Dr. Charles Elkan is a professor in the Department of Computer Science and Engineering at the University of California, San Diego. In 1998/99 he was a visiting associate professor at Harvard University. Dr. Elkan is known for his research in machine learning, data mining, and computational biology; the MEME algorithm he
developed with his Ph.D. student Tim Bailey has been used in over 2000 published research projects in biology. Dr. Elkan has won several best paper awards and data mining contests, and some of his graduate students have become leaders at companies including Google, Yahoo, Zillow, and IBM, while others have held faculty positions at Columbia University, the University of Washington, and other universities inside and outside the U.S.
Host Faculty: Y. Narahari
| Series: Department Seminar
Title: Intent beyond Keywords: the future of Online Advertising - Speaker: Mr. Murthy Nukala
Chief Executive Officer, AdChemy - Date and Time: Wednesday, December 21, 2011, 11:00 AM
- Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract
The "Intent Web", the part of the web where Intent signals are detectable,
is the most valuable part of the web. For the past 10 years, this space has been
synonymous with "search by query". However, new modes of search such as mobile
applications, voice recognition and augmented reality are exploding --
these forms are "search by behavior". In my talk, I will explore the various models
and channels of online advertising, give an overview of the underlying systems,
and propose a new abstraction layer that is necessary for the
future of advertising against search and the Intent Web.
Speaker Bio:
Chief Executive Officer and Founder of AdChemy, Murthy is a veteran leader
of innovative, technology-driven businesses. He was the founder of Digital
Jones, which was acquired by Shopping.com, a $130 million company that was
the best-performing IPO of 2004. At Shopping.com, he held the position of
senior vice president of enterprise products overseeing the company's
strategic initiatives and businesses in that area. Murthy has also held
management positions at Composite Software and Sand Hill Group, where he
guided the firm's technology research agendas and investments.
Murthy holds a bachelor's degree in technology from the Indian Institute
of Technology, Madras; a master's degree in engineering from MIT; and an
MBA from Harvard University.
Host Faculty: Prof. Y. Narahari
|
|
