• Upcoming
• Past

• Upcoming
• Past
• Add New Seminar

• List of Seminars

• Videos

Series: Department Seminar
Title: Verifying Periodic Real-Time Software

• Speaker: Dr. Sagar Chaki
• Date and Time: Monday, June 11, 2012, 4:00 PM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Real-Time Embedded Systems (RTESs) constitute an important sub-class of concurrent safety-critical software. In this talk, I will consider the problem of verifying functional correctness of periodic RTES, a popular variant of RTES that execute periodic tasks in an order determined by Rate Monotonic Scheduling (RMS). A computational model of a periodic RTES is a finite collection of terminating tasks that arrive periodically and must complete before their next arrival. I will present an approach -- developed in joint work with Arie Gurfinkel and Ofer Strichman -- for time-bounded verification of safety properties in periodic RTES. Our approach is based on sequentialization. Given an RTES C and a time-bound B, we construct (and verify) a sequential program S that over-approximates all executions of C up to time B, while respecting priorities and bounds on the number of preemptions implied by RMS. Our algorithm supports partial-order reduction, preemption locks, and priority locks. We implemented our approach for C programs, with properties specified via user-provided assertions. We evaluated our tool on several realistic examples, and were able to detect a subtle concurrency issue in a robot controller. I will conclude with a summary of ongoing work and future directions.

Speaker Bio:
Sagar Chaki is a senior Member of Technical Staff at the Software Engineering Institute at Carnegie Mellon University. He received a B.Tech in Computer Science & Engineering from the Indian Institute of Technology, Kharagpur in 1999, and a Ph.D. in Computer Science from Carnegie Mellon University in 2005. He works mainly on automating formal techniques for software analysis, but is generally interested in rigorous and automated approaches for improving software quality. He has developed several automated software verification tools, including two model checkers for C programs, MAGIC and Copper. He has co-authored over 40 peer reviewed publications. More details about Sagar and his current work are available at http://www.sei.cmu.edu/staff/chaki. An up to date list of his publications and a resume are available at http://www.contrib.andrew.cmu.edu/~schaki and http://www.contrib.andrew.cmu.edu/~schaki/resume.pdf.

Host Faculty: Aditya Kanade

Series: Ph.D. Thesis Defense
Title: Boxicity and Cubicity: A Study on Special Classes of Graphs

• Speaker: Mr. Rogers Mathew
• Faculty Advisor: Prof. Sunil Chandran
• Date and Time: Wednesday, May 30, 2012, 11:30 AM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Let F be a family of sets. A graph G(V,E) is an intersection graph of sets from F if there exists a function f:V(G) -> F such that (u,v) in E(G) <=> f(u) and f(v) have a nonempty intersection. An "interval graph" is an intersection graph of a family of closed intervals on the real line. Interval graphs find application in diverse fields ranging from DNA analysis to VLSI design.

An interval on the real line can be generalized to a "k dimensional box" or "k-box''. A k-box B=(R_1,R_2,...,R_k) is defined to be the Cartesian product R_1 x R_2 x ... x R_k, where each R_i is a closed interval on the real line. If each R_i is a unit length interval, we call B a "k-cube''. A graph G has a "k-box representation", if G is an intersection graph of a family of k-boxes in R^k. The minimum k such that G has a k-box representation is the "boxicity" of G (box(G)). Similarly, the "cubicity" of G (cub(G)) is the minimum integer k such that G has a k-cube representation.

The concepts of boxicity and cubicity were introduced by F.S. Roberts in 1969. Deciding whether the boxicity (or cubicity) of a graph is at most k is NP-complete even for a small positive integer k. Box representation of graphs finds application in niche overlap (competition) in ecology and to problems of fleet maintenance in operations research. Given a low dimensional box representation, some well known NP-hard problems become polynomial time solvable.

In this thesis, we present several upper bounds for boxicity and cubicity of special classes of graphs in terms of other graph parameters.

Our Work:

1. We show that, for a k-degenerate graph G, cub(G) is O(k log(n)). This bound is tight. We also give an efficient deterministic algorithm to construct an O(k log(n)) dimensional cube representation.

2. Crossing number of a graph G is the minimum number of crossing pairs of edges, over all drawings of G in the plane. We find a non-trivial relation between the boxicity of a graph and its crossing number.

3. Almost all graphs have cubicity O(d log n), where 'd' denotes the average degree.

4. Boxicity of a line graph with maximum degree D is O(D log(log(D))). We also prove a non-trivial lower bound for the boxicity of a d-dimensional hypercube.

5. Boxicity of a k-leaf power is at most k-1. For every k, there exist k-leaf powers whose boxicity is exactly k − 1. Since leaf powers are a subclass of strongly chordal graphs, this result implies that there exist strongly chordal graphs with arbitrarily high boxicity.

6. We give a constructive proof to show that there exist chordal bipartite graphs with arbitrarily high boxicity.

Series: M.Sc. (Engg) Colloquium
Title: Studies in Autonomic Management of Storage Systems

• Speaker: Mr. Pankaj Pipada
• Faculty Advisor: Prof. K. Gopinath
• Date and Time: Thursday, May 17, 2012, 3:00 PM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Autonomic management is important in storage systems and the space of autonomics in storage systems is vast. Such autonomic management systems can employ a variety of techniques depending upon the specific problem. In this thesis, we first take an algorithmic approach towards reliability enhancement and then we use learning along with a reactive framework to facilitate storage optimization for applications.

We study how the reliability of non-repairable systems can be improved through automatic reconfiguration of their XOR-coded structure. To this regard we propose to increase the fault tolerance of non-repairable systems by reorganizing the system, after a failure is detected, to a new XOR-code with a better fault tolerance. As errors can manifest during reorganization due to whole reads of multiple submodules, our framework takes them into account and models such errors as based on access intensity (ie. BER - bit error rate). We present and evaluate the reliability of an example storage system with and without reorganization.

Motivated by the critical need for automating various aspects of data management in virtualized data centers, we study the specific problem of automatically implementing Virtual Machine (VM) migration in a dynamic environment according to some pre-set policies. This is a problem that requires automated identification of various workloads and their execution environments running inside virtual machines in a non-intrusive manner. To this end we propose AuM (for Autonomous Manager)that has the capability to learn workloads by aggregating variety of information obtained from network traces of storage protocols. We use state of the art Machine Learning tools, namely Multiple Kernel learning, to aggregate information and show that AuM is indeed very accurate in identifying workloads, their execution environments and is also successful in following user set policies very closely for the VM migration tasks.

Storage infrastructure in large-scale cloud data center environments must support applications with diverse, time-varying data access patterns while observing the quality of service. To meet service level requirements in such heterogeneous application phases, storage management needs to be phase-aware and adaptive, i.e., identify specific storage access patterns of applications as they occur and customize their handling accordingly. We build LoadIQ, an online application phase detector for networked (file and block)storage systems. In a live deployment, LoadIQ analyzes traces and emits phase labels learnt online. Such labels could be used to generate alerts or to trigger phase-specific system tuning.

Series: Ph.D. Colloquium
Title: Power Efficient Last Level Cache for Chip-Multicores

• Speaker: Aparna Mandke
• Faculty Advisor: Y.N. Srikant and Bharadwaj Amrutur
• Date and Time: Tuesday, May 15, 2012, 4:00 PM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The number of cores and on-chip cache size have been increasing in chip multicores (CMPs), thanks to advances in technology. As a result, leakage power dissipated in the on-chip cache has become a major contributing component of the power dissipated in the memory subsystem. In this thesis, we explore various techniques to switch-off the over-allocated cache so as to reduce leakage power consumed by it.

Past studies for leakage power reduction techniques have focused on smaller uniform access latency primary caches, with a single application executing on a uniprocessor. In this thesis, we consider large caches inter-connected using an on-chip network on CMPs. Such a cache offers non-uniform access latency to different cores present on the CMP. Hence, it is called as a Non-Uniform Cache Architecture (NUCA). The concurrently executing multiple threads and NUCA cache make leakage power optimization on CMPs a challenging problem. We first propose a new method to estimate the working set size of an application(s) executing on a CMP. We use this method to adapt associativity of NUCA caches on tiled CMPs. Our algorithm uses information available locally in each tile. This enables the technique to scale with the number of cores present on a CMP.

We also propose the remap strategy in which farther L2 slices are mapped to nearer L2 slices. The mapped L2 slices are switched-off. Apart from reducing leakage power consumption in L2 slices, it also saves execution time in some applications. Next, we determine the maximum energy-delay savings possible with the remap strategy using genetic algorithms. We formulate the near-optimal remap configuration determination problem as a energy-delay minimization problem.

Leakage power optimization policies can be applied to static or dynamic NUCA policies. However, the characteristics of an application decide the suitability of the cache access policy. Hence, we propose indices to quantify data sharing properties of an application. We use these indices to predict suitability of a cache access policy for an application.

Speaker Bio:
Aparna Mandke is a PhD student in the department of Computer Science and Automation.

Host Faculty: Y.N. Srikant

Series: Professor Priti Shankar Memorial Lecture Series
Title: My work with Prof. Priti Shankar and its impact on my Professional Life

• Speaker: Dr. B.S. Adiga, TCS
• Date and Time: Friday, May 11, 2012, 5:00 PM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The talk is about application of Elliptic curve based cryptography for sensor networks which essentially use mobile phones as nodes. The speaker gives a detailed description of his work with Prof Priti Shankar during 1980s regarding the application of Pseudo-Mersenne/ Fermat numbers and Fermat Number Theoretic Transforms in developing fast algorithms for long integer multiplication and modular reduction. These concepts have been further developed by Paar and Baily of Wooster Polytechnic USA under the frame work of Optimum Extension Fields (OEF). At present OEFs have been drafted into 1363 Standards on Elliptic Curve Cryptography. The talk is intended to give impetus to further research in this area.

Speaker Bio:
Dr. B.S. Adiga received his PhD from CSA, IISc under the guidance of Prof. Priti Shankar. He was a Scientist at National Aerospace Laboratory, Bangalore for 21 years from 1975 to 1996. He was a Principal Scientific Officer at Motorola India Electronics, Bangalore for 5 years from 1996 to 2001 and at Philips Innovation Center, Bangalore for 5 years from 2001 to 2006. He is currently an Advisor at TCS Innovation Labs, Bangalore. He is also a Visiting Professor of IIT Bombay from 2007. His area of research includes Signal Processing, Error Control Coding, Cryptography and Super Computing.

Series: Department Seminar
Title: Entrepreneurship as a Career Option

• Speaker: Mr Ravi Trivedi (CSA Alumnus)
                 Principal Officer
                 Southeast Interactive Technology Funds
• Date and Time: Friday, May 11, 2012, 3:30 PM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The talk will focus on choosing Entrepreneurship as a career option, and delves into the nuances before and after one makes the choice. The talk will highlight best practices, and present a framework to think about how to reach this decision, and what to do when want to do your startup.

Outline of topics that will be discussed in the talk: a) Why, When, Who, Thoughts and Pros/Cons on entrepreneurship b) Making the Leap c) Types of startups d) First Steps: Founding Team, Idea, Building Product, Selling your Product e) Fund raising f) Work life balance as a founder

Speaker Bio:
Ravi works as a Principal at Southeast Interactive Technology Funds, an early stage technology venture capital fund. He runs Srijan Capital, a seed stage fund to make angel investments and incubate startups in India. He is a charter member of TiE Bangalore, and likes to work in trenches with passionate entrepreneurs. At Southeast, apart from investments, his experience includes running and growing a B2C E-commerce startup.

Before Southeast, Ravi worked as equity analyst with Banc of America Securities, where he participated in covering companies over $120B in market capitalization. He was part of the team that was ranked runners up in the Alpha Hedge Fund Research rankings.

Ravi started his career as a software engineer at Hewlett Packard and has global cross-functional experience in leading and managing technology businesses. He has worked in marketing, consulting and engineering functions at Hewlett Packard. Ravi co-authored the book Web Services Security, and was HP's representative in few web services standards.

Ravi completed his MBA from Duke University, Fuqua School of Business and has a Masters in Computer Science from Computer Science and Automation, Indian Institute of Science, Bangalore.

Host Faculty: Prof. Y. Narahari

Series: Department Seminar
Title: System Software for Cloud Computing

• Speaker: Dr. Dilma da Silva,
                 IBM TJ Watson Research Center
• Date and Time: Thursday, May 03, 2012, 4:00 PM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Cloud Computing has gone from being perceived as "IT fad of the moment" to being considered a revolutionary approach to deliver computing services that is changing several aspects of the computer industry. In this talk we analyze cloud computing from the perspective of system software, exploring how this new model impacts current practices in operating systems and distributed computing. We identify a set of exciting research opportunities in resource management for cloud computing and discuss how cloud computing itself affects the way we carry out research projects

Speaker Bio:
Dilma da Silva is a researcher at the IBM T. J. Watson Research Center, in New York. She manages the Advanced Operating Systems group and is also Principal Investigator in the Exascale Collaboratory in Ireland. She received her Ph.D in Computer Science from Georgia Tech in 1997. Prior to joining IBM, she was an Assistant Professor at University of Sao Paulo, Brazil. Her research in operating systems addresses the need for scalable and customizable system software. Her current focus is on cloud computing. She is an ACM Distinguished Scientist and ACM Distinguished Speaker. She has published more than 70 technical papers. Dilma is a member of the board of CRA-W (Computer Research Association's Committee on the Status of Women in Computing Research), of the CDC (Coalition for Diversifying Computing), a co-founder of the Latinas in Computing group, and treasurer/secretary for ACM SIGOPS. More information is available at www.research.ibm.com/people/d/dilma

Host Faculty: Prof. K. Gopinath

Series: M.Sc. (Engg) Colloquium
Title: Scalable Quota Management for High performance Computing.

• Speaker: Mr. B.S. Amarnath, M.Sc Engg.
• Faculty Advisor: Prof. K. Gopinath
• Date and Time: Monday, April 30, 2012, 4:00 PM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Quotas are used in file systems to control use of available storage resources. When a large scientific application is run on a large cluster, quotas are essential to avoid catastrophic failures of other long running applications or itself due to lack of disk space. Quota management also contributes to system noise which can decrease the application throughput of High-Performance Computing (HPC) applications due to interrupts, barriers, or messages exchanged in a large cluster. In a digital cash model, quotas are tracked and enforced by a single quota server that issues cryptographically signed vouchers. Clients use these vouchers to allocate storage on any available object storage devices. The storage servers are able to ensure that clients do not use more storage than they are allowed using, in our model, only time-insensitive asynchronous communication with the quota server. The scheme does not require synchronized clocks and is able to recover from client and server failures. It is also resilient to transient failures of the various components including network connectivity. In previous work, the above scheme was evaluated using simulation; this work also used moving average window to perform prediction of the size of quotas to be requested from the quota server when replenishing quota. In this work, we investigate the quota management approach based on the digital cash model on Ceph, a peta-byte capable file system. We also use an ensemble based prediction algorithm to track a client’s needs for storage; this is especially important with bursty requests that characterize large scientific applications. While the quota management algorithm is scalable, the prediction algorithm further reduces the number of messages to the quota server, reducing jitter. We have evaluated our algorithm on two scientific applications, a fluid dynamics code and a micro magnetic simulation, and report on the reduction of messages for the digital cash model with and without the ensemble based prediction algorithm.

Series: Department Seminar
Title: Performance models for distributed query languages

• Speaker: Kaushik Rajan
• Date and Time: Friday, April 20, 2012, 4:00 PM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Programming models such as MapReduce, HIVE, FlumeJava and DryadLINQ are popular models for expressing data intensive computations that run on a large cluster of machines. These models provide a simple declarative language that programmers can use to exploit the computational power of a large distributed system without having to deal with the vagaries of distribution such as failures, synchronization, messaging and storage. However, this level of abstraction comes at a cost - the inability to understand, predict and debug performance. We propose a performance modeling approach for predicting execution time of distributed computations expressed in these models. Our modeling approach uses a novel combination of analytical white box models used to model parallelism and resource contention across the cluster, and empirically generated black box models used for parts of the system that are hard to model analytically. We evaluate the models using several real world applications. We find that the models can accurately predict execution time to within 1- 13% of actual execution times across the benchmark. We demonstrate the usefulness of the model in identifying performance bottlenecks, both during design and while debugging performance problems.Title : Performance models for distributed query languages

Speaker Bio:
Kaushik Rajan is a member of the Rigorous Software Engineering group at Microsoft Research India. He is broadly interested in the areas of computer architecture, static analysis and programming languages. His current research focus is on providing language support for programming multi-cores and distributed systems. He completed his PhD from the Indian Institute of Science, Bangalore.

Host Faculty: R. Govindarajan

Series: Department Seminar
Title: Control of Sample Complexity and Regret in Bandits using Fractional Moments

• Speaker: Prof. B. Ravindran
• Date and Time: Tuesday, April 17, 2012, 4:00 PM
• Venue: CSA Multimedia Class (Room No. 252, First Floor)

Abstract
One key facet of learning through reinforcements is the dilemma between exploration to find profitable actions and exploitation to act optimal according to the observations already made. We analyze this explore/exploit situation on Bandit problems in stateless environments. We propose a family of learning algorithms for bandit problems based on fractional expectation of rewards acquired. The algorithms can be controlled to behave optimal with respect to sample complexity or regret, through a single parameter. The family of algorithms is theoretically shown to contain an algorithm that has very competitive sample complexity compared to the state-of-the-art; as well as an algorithm that achieves optimal regret. Experimental results support these theoretical findings and the algorithms perform substantially better than state-of-the-art techniques in regret reduction like UCB-Revisited and other standard approaches.

Speaker Bio:
Dr. B. Ravindran is an Associate Professor in the Department of Computer Science and Engineering at the Indian Institute of Technology Madras. He obtained his PhD in Computer Science from University of Massachusetts, Amherst. His current research interests span the broader area of machine learning, ranging from Spatio-temporal abstractions in Reinforcement Learning to social network analysis and Data & Text Mining. Much of his current work is directed toward understanding interactions and learning from them. He served as the program co-chair for PAKDD 2010 and regularly serves on the program committee of premier conferences. He has co-authored several research papers, including the chapter on reinforcement learning in the Handbook of Neural Computation published by the Oxford University Press. He is a consultant for several start-up’s as well as research labs such as Ericsson R&D and General Motors, India Science Lab.

Host Faculty: Dr. Shivani Agarwal

Series: M.Sc. (Engg) Colloquium
Title: Sentiment-Driven Topic Analysis of Song Lyrics

• Speaker: Mr. Govind Sharma, MSc. Engg.
• Faculty Advisor: Prof. M. Narasimha Murty
• Date and Time: Tuesday, April 17, 2012, 10:30 AM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Sentiment Analysis is an area of Computer Science that deals with the impact a document makes on a user. In case of text documents, sentiments are delivered using words. The very field is further sub-divided into Opinion Mining and Emotion Analysis, the latter of which is the basis for the present work. Work on songs is aimed at building affective interactive applications such as music recommendation engines. In the recent past, a considerable amount of work has been done on music analysis which looks at both lyrics and melody for such applications. Using song lyrics, we are interested in both supervised and unsupervised analyses, each of which has its own pros and cons.

For an unsupervised analysis (clustering), we use a standard probabilistic topic model called Latent Dirichlet Allocation (LDA). It mines topics from songs, which are nothing but probability distributions over the vocabulary of words. Some of the topics seem sentiment-based, motivating us to continue with this approach. We evaluate our clusters using a gold dataset collected from an apt website and get positive results. This approach would be useful in the absence of a supervisor dataset.

In another part of our work, we argue the inescapable existence of implied supervision in terms of the term-weighing scheme used, the distance metric used, and to analyse the topics (clusters) returned. Further, we have also used explicit supervision in terms of a training dataset for a classifier to learn sentiment specific classes. This analysis helps reduce dimensionality and improve classification accuracy. We get excellent dimensionality reduction using Support Vector Machines for feature selection. We also study different term-weighing schemes (binary, tfidf, etc.) and distance metrics (Euclidean, cosine similarity, etc.) to find apt ones for sentiment analysis.

Series: Ph.D. Colloquium
Title: Weighted Average Based Clock Synchronization Protocols for Wireless Sensor Networks

• Speaker: Mr. Amulya Ratna Swain, PhD
• Faculty Advisor: Prof. R.C. Hansdah
• Date and Time: Monday, April 16, 2012, 4:00 PM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Wireless Sensor Networks (WSNs) consist of a large number of resource constrained sensor nodes equipped with various sensing devices which can monitor events in the real world. There are various applications such as environmental monitoring, target tracking, forest fire detection, etc., which require clock synchronization among the sensor nodes with certain accuracy. However, a major constraint in the design of clock synchronization protocols in WSNs is that sensor nodes of WSNs have limited energy and computing resources. Clock synchronization process in the WSNs is carried out at each sensor node either synchronously, i.e., periodically during the same real-time interval, which we call synchronization phase, or asynchronously, i.e., independently without worrying about what other nodes are doing for clock synchronization. A disadvantage of asynchronous clock synchronization protocols is that they require the sensor nodes to remain awake all the time. Therefore, they cannot be integrated with any sleep-wakeup scheduling scheme of sensor nodes, which is a major technique to reduce energy consumption in WSNs. On the other hand, synchronous clock synchronization protocols can be easily integrated with the synchronous sleep-wakeup scheduling scheme of sensor nodes, and at the same time, they can provide support to achieve sleep-wakeup scheduling of sensor nodes. Essentially, there are two ways to synchronize the clocks of a WSN, viz. internal clock synchronization and external clock synchronization. The existing approaches to internal clock synchronization in WSNs are mostly hop-by-hop in nature which is difficult to maintain. There are also many application scenarios where external clock synchronization is the only option to synchronize the clocks of a WSN. Besides, it is also desired that the internal clock synchronization protocol used is fault-tolerant to message loss and node failures. Moreover, when the external source fails or reference node fails, the external clock synchronization protocol should revert back to internal clock synchronization protocol with/without using any reference node. Towards this goal, we propose three fully distributed synchronous clock synchronization protocols, called IEFCS/EFCS, IWICS/WICS, and IWECS/WECS, for WSNs that make use of peer-to-peer approach and provide both external and internal clock synchronization. These three protocols are dynamically interchangeable depending upon the availability of external source or reference nodes. We have analyzed these protocols for bounds on synchronization error, and shown that the synchronization error is always upper bounded. We have evaluated the performance of these protocols through simulation and experimental studies and shown that the synchronization accuracy achieved by these protocols is of the order of a few clock ticks even in very large networks. The proposed protocols make use of estimated drift rate to provide logical time from the physical clock value at any instant and at the same time ensure the monotonicity of logical time even though physical clock is updated at the end of each synchronization phase. We have also proposed an energy aware routing protocol with sleep scheduling which can be integrated with the proposed clock synchronization protocols to reduce energy consumption in WSNs further.

Series: Ph.D. Thesis Defense
Title: Scaling Context-Sensitive Points-to Analysis.

• Speaker: Mr. Rupesh Nasre, PhD
• Faculty Advisor: Prof. R. Govindarajan
• Date and Time: Monday, April 16, 2012, 11:00 AM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Pointer analysis is one of the key static analyses during compilation. The efficiency of several compiler optimizations and transformations depends directly on the scalability and precision of the underlying pointer analysis. Recent advances still lack an efficient and scalable context-sensitive inclusion-based pointer analysis. In this work, we propose four novel techniques to improve the scalability of context-sensitive points-to analysis for C/C++ programs.

First, we develop an efficient way of storing the approximate points-to information using a multi-dimensional bloom filter (multibloom). By making use of fast hash functions and exploiting the spatial locality of the points-to information, our multibloom-based points-to analysis offers significant savings in both analysis time and memory requirement. Since the representation never resets any bit in the multibloom, no points-to information is ever lost; and the analysis is sound, though approximate. This allows a client to trade off a minimal amount of precision but gain huge savings in memory requirement. By making use of multiple random and independent hash functions, the algorithm also achieves high precision and runs, on an average, 2x faster than Andersen's points-to analysis. Using Mod/Ref analysis as a client, we illustrate that the precision is above 98% of that of Andersen's analysis.

Second, we devise a sound randomized algorithm that processes a group of constraints in a less precise but efficient manner and the remaining constraints in a more precise manner. By randomly choosing different groups of constraints across different runs, the analysis results in different points-to information, each of which is guaranteed to be sound. By joining the results of a few runs, the analysis obtains an approximation that is very close to the one obtained by the more precise analysis and still proves efficient in terms of analysis time. We instantiate our technique to develop a randomized context-sensitive points-to analysis. By varying the level of randomization, a client of points-to analysis can trade off minimal precision (less than 5%) for large gain in efficiency (over 50% reduction in analysis time). We also develop an adaptive version of the randomized algorithm that carefully varies the randomization across different runs to achieve maximum benefit in terms of analysis time and precision without pre-setting the randomization percentage and the number of runs.

Third, we transform the points-to analysis problem into finding a solution to a system of linear equations. By making novel use of prime factorization, we illustrate how to transform complex points-to constraints into a set of linear equations and transform the solution back as a points-to solution. We prove that our algorithm is sound and show that our technique is 1.8x faster than Andersen's analysis for large benchmarks.

Finally, we observe that the order in which points-to constraints are processed plays a vital role in the algorithm efficiency. We prove that finding an optimal ordering to compute the fixed-point solution is NP-Hard. We then propose a greedy heuristic based on the amount of points-to information computed by a constraint to prioritize the constraints. This results in a dynamic ordering of the constraint evaluation which, in turn, results in skewed evaluation of constraints where each constraint is evaluated repeatedly and different number of times in a single iteration. Our prioritized analysis achieves, on an average, an improvement of 33% over Andersen's points-to analysis.

We illustrate that our algorithms help in scaling the state-of-the-art pointer analyses. We also believe that the techniques developed would be useful for other program analyses and transformations.

Series: Ph.D. Colloquium
Title: Algorithms for General-Sum Stochastic Games and Service Systems

• Speaker: H.L.Prasad
• Faculty Advisor: Prof. Shalabh Bhatnagar
• Date and Time: Friday, April 13, 2012, 3:00 PM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The field of stochastic games has been actively pursued over the last seven decades because of several of its important applications in oligopolistic economics. In the past, zero-sum stochastic games have been modelled and solved for Nash equilibria using the standard techniques of Markov decision processes. General-sum stochastic games on the contrary have posed difficulty as they cannot be reduced to Markov decision processes. Over the past few decades the quest for algorithms to compute Nash equilibria in general-sum stochastic games has intensified and several important algorithms such as stochastic tracing procedure [Herings and Peeters, 2004], NashQ [Hu and Wellman, 2003], FFQ [Littman, 2001], etc., and their generalised representations such as the optimization problem formulations for various reward structures [Filar and Vrieze, 2004] have been proposed. However, they suffer from either lack of generality or are intractable for even medium sized problems or both. In our venture towards algorithms for stochastic games, we start with a non-linear optimization problem and then design a simple gradient descent procedure for the same. Though this procedure gives the Nash equilibrium for a sample problem of terrain exploration, we observe that, in general, it need not be true. We characterize the necessary conditions and define KKT-N point. KKT-N points are those KKT points which corresponding to Nash equilibrium. Thus, for a simple gradient based algorithm to guarantee convergence to Nash equilibrium, all KKT points of the optimization problem need to be KKT-N points which restricts the applicability of such algorithms.

We then take a step back and start looking at better characterization of those points of the optimization problem which correspond to Nash equilibria of the underlying game. As a result of this exploration, we derive two sets of necessary and sufficient conditions. The first set, KKT-SP conditions, is inspired from KKT conditions itself and is obtained by breaking down the main optimization problem into several sub-problems and then applying KKT conditions to each one of those sub-problems. The second set, SG-SP conditions, is simplified set of conditions which characterize those Nash points more compactly. Using both KKT-SP and SG-SP conditions, we propose three algorithms, OFF-SGSP, ON-SGSP and DON-SGSP, respectively, which we show provide Nash equilibrium strategies for general-sum discounted stochastic games. Here OFF-SGSP is an off-line algorithm while ON-SGSP and DON-SGSP are on-line algorithms. In particular, we believe that DON-SGSP is the first decentralized on-line algorithm for general-sum discounted stochastic games. We show that both our on-line algorithms are computationally efficient. In fact, we show that DON-SGSP is not only applicable for multi-agent scenarios but is also directly applicable for single-agent case, i.e., MDPs (Markov Decision Processes).

Second part of the talk focuses on formulating and solving the problem of minimizing the labour-cost in service systems. We define the setting of service systems and then model the labour-cost problem as a constrained Markov-cost process. This Markov process is parametrized by number of workers in various shifts and with various skill levels. With number of workers as optimization variables, we provide a detailed formulation of a constrained optimization problem where the objective is the expected long-run average of single-stage labour-costs, and the main set of constraints are expected long-run average of aggregate SLAs (Service Level Agreements). For this constrained optimization problem, we provide two stochastic optimization algorithms, SASOC-SF-N and SASOC-SF-C, which use smoothed functional approaches to estimate gradient and do gradient descent in the aforementioned constrained optimization problem. SASOC-SF-N uses Gaussian distribution for smoothing while SASOC-SF-C uses Cauchy distribution for the same. SASOC-SF-C is the first Cauchy based smoothing algorithm which requires a fixed number (two) of simulations independent of the number of optimization variables. We show that these algorithms provide an order of better performance than existing industrial standard tool, OptQuest. We also show that SASOC-SF-C gives overall better performance.

Series: Department Seminar
Title: Epsilon-nets and its Relatives

• Speaker: Dr. Saurabh Ray
• Date and Time: Friday, April 13, 2012, 11:30 AM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Epsilon nets and approximations are among the most fundamental notions of sampling. For a given set system and a parameter $epsilon$, an $epsilon$-net is a transveral for the sets of size at least $epsilon n$, $n$ being the size of the ground set. The idea originated in the context of learning theory and was introduced by Haussler and Welzl in 1987. With a delicate use of random sampling, they showed that any set system of finite VC dimension has an $epsilon$-net of small size independent of the size of the set system - and moreover a random sample of this size is an $epsilon$-net with high probability. Epsilon nets are now an important tool that has found applications in many areas including computational geometry, approximation algorithms, discrepancy theory and statistics. Very simple and deterministic constructions were found by Matousek in 1991. Deterministic algorithms for computing $epsilon$-nets have turned them into a general tool for divide & conquer and for derandomization - many of the sophisticated data structures and algorithms are based on $epsilon$-nets. They power tools like cuttings and simplicial partitions that are among the finest algorithmic tools in geometry. Besides algorithmic applications, they have have been used for the proof of other combinatorial results. Recent research on Epsilon nets and related problems has revealed further connections to other areas of mathematics.

In this talk I will give an introduction to $epsilon$-nets and the various related problems that I have worked on. I will describe my results on the construction of $epsilon$-nets, related geometric set cover problems, enumeration problems and weak $epsilon$-nets.

Speaker Bio:
Saurabh Ray received his Ph.D in Computer Science from Universität des Saarlandes,Saarbrücken, Germany in 2009 and is currently a Postdoc at Max-Plank Institut für Informatik, Saarbrücken, Germany. His interests are in Algorithms, Discrete and Computational Geometry, Geometric Optimization.

Host Faculty: Shalabh Bhatnagar

Series: Ph.D. Colloquium
Title: Reeb Graphs: Computation, Visualization and Applications

• Speaker: Mr. D. Harish, Ph.D
• Faculty Advisor: Dr. Vijay Natarajan
• Date and Time: Thursday, April 12, 2012, 11:30 AM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Level sets are extensively used for the visualization of scalar fields. The Reeb graph of a scalar function tracks the evolution of the topology of its level sets. It is obtained by mapping each connected component of a level set to a point. The Reeb graph and its loop-free version called the contour tree serve as an effective user interface for selecting meaningful level sets and for designing transfer functions for volume rendering. It also finds several other applications in the field of scientific visualization.

In this thesis, we focus on designing algorithms for efficiently computing the Reeb graph of scalar functions and using the Reeb graph for effective visualization of scientific data. We have developed three algorithms to compute the Reeb graph of PL functions defined over manifolds and non-manifolds in any dimension. The first algorithm efficiently tracks the connected components of the level set and has the best known theoretical bound on the running time. The second algorithm, utilizes an alternate definition of Reeb graphs using cylinder maps, is simple to implement and efficient in practice. The third algorithm aggressively employs the efficient contour tree algorithm and is efficient both theoretically, in terms of the worst case running time, and practically, in terms of performance on real-world data. This algorithm has the best performance among existing methods and computes the Reeb graph at least an order of magnitude faster than other generic algorithms.

We describe a scheme for controlled simplification of the Reeb graph and two different graph layout schemes that help in the effective presentation of Reeb graphs for visual analysis of scalar fields. We also employ the Reeb graph in four different applications -- surface segmentation, spatially-aware transfer function design, visualization of interval volumes, and interactive exploration of time-varying data.

Finally, we introduce the notion of topological saliency that captures the relative importance of a topological feature with respect to other features in its local neighborhood. We integrate topological saliency with Reeb graph based methods and demonstrate its application to visual analysis of features.

Series: Department Seminar
Title: Automated verification of cryptographic protocols

• Speaker: Dr. Rohit Chadha
• Date and Time: Wednesday, April 11, 2012, 3:00 PM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The widespread use of internet has raised serious concerns of privacy and trust. In order to address these concerns, cryptographic protocols are widely used. A cryptographic protocol is a distributed program that uses cryptographic primitives to ensure security over an untrusted network. However, the �design of cryptographic protocols has proven to be error-prone and several errors have been found. Thus, �there is a need for building scalable tools for automatically verifying security of cryptographic protocols. The complexity of cryptographic protocols as well as the desired security guarantees presents unique challenges to verification of cryptographic protocols. We illustrate these challenges within the context of� verifying game-based and equivalence-based properties of cryptographic properties.

Speaker Bio:
Rohit Chadha obtained his bachelor's degree in 1997 from Indian Institute of Technology, Delhi� and his PhD in 2003 from� University of Pennsylvania. His thesis was on formally specifying and analyzing contract signing protocols. Since his doctoral studies, Rohit has held research positions at Univ of Sussex, Instituto Superior Tecnico and University of Illinois, Urbana Champaign. He joined INRIA in 2009 and is associated with� Laboratoire Sp�cification et V�rification, ENS Cachan. His primary research interests are in the areas of logic and automata theory and their applications to verification of security infrastructure.

Host Faculty: Shalabh Bhatnagar

Series: Department Seminar
Title: Decision Making in Intensive Care: Melding the Art of Medicine and Statistical/Machine Learning Techniques in Critical Care

• Speaker: Dr. Sampath Sriram
                 [Professor & Head Department of Critical Care Medicine
                 St. John's Medical College, Bangalore]
• Date and Time: Tuesday, April 10, 2012, 4:00 PM
• Venue: CSA Multimedia Class (Room No. 252, First Floor)

Abstract
Hypothetico-deductive techniques in diagnosis, principles of basic numerical analysis in prognosis and evidence based approaches in therapy will be explained. The use of techniques of numerical evidence synthesis like meta-analyses will be discussed. The use of statistical techniques like logistic regression methods and machine learning methods in critical care medicine with future applications from large datasets will be explored. The task of identifying frugal data collection techniques which leads to economic endpoints will be explored.

Speaker Bio:
Dr. Sampath Sriram is currently Professor and Head in the Department of Critical Care Medicine at St. John's Medical College, Bangalore. He received his MBBS and MD from Christian Medical College, Vellore. He has has been recognized for his research at St. John's and has served as a consultant in the Intensive Care Unit at Alice Springs Hospital in Australia. His interests include prediction models, nosocomial infection, and quality control.

Host Faculty: Dr. Shivani Agarwal

Series: Department Seminar
Title: Pre-orders for Reasoning about Stability of Hybrid Systems

• Speaker: Pavithra Prabhakar
• Date and Time: Tuesday, April 10, 2012, 3:30 PM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Pre-orders between processes, such as simulation, have played a central role in the verification and analysis of discrete state systems. Logical characterizations of such pre-orders have enabled the analysis of the correctness of a system by analyzing an abstraction of the system. In this talk, we discuss whether a similar approach is feasible for verifying stability properties of hybrid systems.

We investigate pre-orders for reasoning about stability. We show that stability is not invariant under the canonical notion of equivalence for reasoning about discrete systems, namely, bisimulation. We present new definitions which suffice to preserve two notions of stability, namely, Lyapunov and asymptotic stability, and argue that the definitions are useful in the approximation based analysis of stability of hybrid systems.

Speaker Bio:
Pavithra Prabhakar obtained her PhD at University of Illinois at Urbana-Champaign and is currently a post-doctoral fellow at the Center for Mathematics of Information at Caltech.

Host Faculty: Deepak D'Souza

Series: Department Seminar
Title: Functional encryption systems from hard lattice problems

• Speaker: Shweta Agrawal
• Date and Time: Tuesday, April 10, 2012, 11:30 AM
• Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
�Data security challenges faced in the modern world demand functionality from encryption systems that traditional public key cryptography falls far short in delivering.�

Take the example of cloud computing, a paradigm which allows users to outsource their data storage and computing needs to a powerful third party server such as Amazon. Though such a service is very useful, users may be reluctant to trust third party servers with sensitive data. Organizations utilizing these services must also ensure that their clients are secure from each other. At the same time, meaningful functionality must be provided. For example a server storing medical data might be required to grant users access to certain useful functions computed on the entire user database, such as the success rate of some medication for a given disease, while making sure that individual medical privacy is not compromised.

To address these emerging needs, a new paradigm of encryption was recently put forward �� Functional Encryption. In functional encryption, a user's secret key can be associated with its holder's credentials, while the ciphertext can be associated with an access policy.�We may ask that decryption succeed if and only if the credentials satisfy the access policy.

I will describe several special cases of functional encryption that we have constructed -- systems for the identity function (identity based encryption or IBE), threshold function (fuzzy IBE) and linear functions. I will describe ongoing work to provide a general framework for these constructions and challenges faced in supporting more general functions.�The technical tool we use in these constructions is the worst-case hardness of lattice problems. Lattices have traditionally been used in cryptography for breaking cryptosystems and their use in building cryptosystems is surprising and elegant.

Speaker Bio:
Shweta Agrawal received her Ph.D from UT Austin in May 2011 and is currently a Postdoc at UCLA. Her interests are in Cryptography, Information Theory and Coding Theory.

Host Faculty: Shalabh Bhatnagar