Department of Computer Science and Automation Department of Computer Science and Automation, IISc, Bangalore, India Indian Institute of Science
HOME | ABOUT US | PEOPLE | RESEARCH | ACADEMICS | FACILITIES | EVENTS / SEMINARS | NEWS | CONTACT US

UPCOMING SEMINARS

Series: Ph.D. Thesis Defense
Title: Interplay of Incentives and Computation in Social Choice

  • Speaker: Mr. Rohit Vaish
                   Ph.D Student
                   Dept. of CSA
  • Faculty Advisor: Dr. Siddharth Barman
  • Date and Time: Friday, October 26, 2018, 2:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Social choice is the science of collective decision-making, spanning a wide variety of problems such as voting, matching, and fair division. Two key factors govern the success of any social choice procedure: (1) the availability of the right set of incentives to the participating agents, and (2) computational efficiency. This thesis examines the interplay between incentives and computation in three fundamental problems in social choice: fair division, voting, and matching.

--Our work in fair division provides a computationally efficient algorithm for dividing a set of discrete resources among a set of agents in a fair and economically efficient manner. Prior to our work, the only known way of achieving such an outcome was via solving a computationally intractable optimization problem. Thus, we use the ease of computation to make incentives possible.

--In contrast to fair division, our work in voting uses the difficulty of computation to achieve the desired incentives. In particular, we study the problem of strategic voting in a general model of elections, and show that finding a manipulative vote can be computationally hard, thus ensuring truthful voter behavior.

--Finally, our work in matching studies the classical problem of two-sided stable matching. Here, we accept the fact that the agents will act strategically, and yet we are able to guarantee desirable social outcomes.

Video Archive Go Top

 

Series: M.Sc. (Engg) Thesis Defense
Title: Adaptively Secure Primitives in the Random Oracle Model

  • Speaker: Mr. Pratik Sarkar
                   M.Sc (Engg)student
                   Dept. of CSA
  • Faculty Advisor: Dr. Arpita Patra
  • Date and Time: Monday, October 22, 2018, 9:30 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Adaptive security embodies one of the strongest notions of security that allows an adversary to corrupt parties at any point during protocol execution and gain access to its internal state. Since it models real life situations such as “hacking”, efficient adaptively-secure multiparty computation (MPC) protocols are desirable. Such protocols demand primitives such as zero knowledge (ZK), oblivious transfer (OT) and commitment schemes that are adaptively-secure as building blocks. Efficient realizations of these primitives have been found to be challenging, especially in the no erasure model. We make progress in this direction and provide efficient constructions that are Universally-Composable in the random oracle model. The study of efficient ZK protocols for non-algebraic statements has seen rapid progress in recent times, relying on the techniques from secure computation. Our primary contribution in ZK lies in constructing efficient constant round ZK protocols from garbled circuits that are adaptively-secure, with communication linear in the size of the statement. We begin by showing that the practically efficient ZK protocol of Jawurek et al. (CCS 2013) is adaptively-secure when the underlying OT satisfies a mild adaptive security guarantee. We gain adaptive security with little to no overhead over the static case. A conditional verification technique is then used to obtain a three-round adaptively secure zero-knowledge argument in the non-programmable non-observable random oracle model. We present the first round optimal framework for building an adaptively-secure OT in the programmable random oracle (PRO) model, relying upon the framework of Peikert et al. (Crypto 2008). When instantiated with Decisional Diffie Hellman assumption, it incurs a minimal communication overhead of one k bit string and computational overhead of 5 random oracle queries over its static counterpart, where k is the security parameter. Additionally, we obtain a construction of adaptively secure 1-out-of-N OT by extending the result of Naor et al. (Journal of Cryptology 2005) that transforms logN copies of 1-out-of-2 OTs to one 1-out-of-N OT in the PRO model. We complete the picture of efficient OT constructions by presenting the first adaptively secure OT Extension, extending the protocol of Asharov et al. (Eurocrypt 2015) for the adaptive setting using PRO. Our OT extension enables us to obtain adaptive OTs at an amortized cost of 3 symmetric key operations and communication of 3k bit strings. We present an adaptively secure commitment scheme solely relying on observable random oracle (ORO). Our commitment scheme has a one-time offline setup phase, where a common reference string (crs) is generated between the parties using an ORO. In the online phase, the parties use the crs and ORO to generate commitments in a non-interactive fashion. Our construction incurs communication of 4k bit strings and computation of 8 exponentiations and 4 random oracle queries for committing to an arbitrary length message. It finds applications in secure two-party computation (2PC) protocols that adopt offline-online paradigm, where the crs can be generated in the offline phase and the scheme can be used in the online phase.

Video Archive Go Top

 

PAST SEMINARS

Series: Department Seminar
Title: Fractional L-intersecting families of sets

  • Speaker: Dr. Rogers Mathew
                   Assistant Professor
                   Dept. of Computer Science & Engineering
                   IIT Kharagpur
  • Date and Time: Wednesday, October 17, 2018, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Let $L = {frac{a_1}{b_1}, ldots , frac{a_s}{b_s}}$, where for every $i in [s]$, $frac{a_i}{b_i} in [0,1)$ is an irreducible fraction. Let $mathcal{F} = {A_1, ldots , A_m}$ be a family of subsets of $[n]$. We say $mathcal{F}$ is a "fractional $L$-intersecting family" if for every distinct $i,j in [m]$, there exists an $frac{a}{b} in L$ such that $|A_i cap A_j| in { frac{a}{b}|A_i|, frac{a}{b} |A_j|}$. In this talk, we introduce and study the notion of fractional $L$-intersecting families, a fractional variant of the classical L-intersecting families which have been studied extensively. The talk is based on our recent work which is available at https://arxiv.org/pdf/1803.03954.pdf

Host Faculty: Prof. Sunil L Chandran

Video Archive Go Top

 

Series: CSA Faculty Colloquium
Title: Cryptography and Machine Learning: Past, Present and Future

  • Speaker: Dr. Arpita Patra
                   Assistant Professor
                   Dept.of CSA
  • Date and Time: Friday, October 12, 2018, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The interplay of cryptography and machine learning (ML) has reached a new height with the unprecedented possibility of using modern machine learning algorithms in diverse domains such as medical diagnosis, facial recognition, finance and many more. This talk will throw light on what future they hold together, what is the state-of-the-art and how they contributed each other in the past. Along the way, I will discuss where my cryptographic research fits in and can contribute to securing ML.

Speaker Bio:
Arpita Patra is an Assistant Professor at Indian Institute of Science. Her area of interest is Cryptography, focusing on theoretical and practical aspects of secure multiparty computation protocols. She received her PhD from Indian Institute of Technology (IIT), Madras and held post-doctoral positions at University of Bristol, UK, ETH Zurich, Switzerland and Aarhus University, Denmark.

Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar

Video Archive Go Top

 

Series: Department Seminar
Title: New Paradigms in Cache Architectures.

  • Speaker: 1. Mr. Jayesh Gaur
                    Senior Research Scientist and Manager
                    Micro-Architecture Research Lab (MRL)
                    Intel India
                   
                   2. Mr. Anant Nori
                    Senior Research Scientist and Manager
                    Micro-Architecture Research Lab (MRL)
                    Intel India
  • Date and Time: Friday, October 05, 2018, 2:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The memory wall continues to be a major performance bottleneck. Caching has been well recognized as a powerful solution to filter requests going to the main memory and boost performance. Unsurprisingly the general industry trend has therefore been to increase the amount of cache that is put on die. In fact, recent advances in technologies like embedded DRAM (eDRAM) and high bandwidth memory (HBM), have even allowed building very large multi-MB to GB caches. All these solutions are driven by the conventional wisdom that increasing the hit rate in the cache subsystem improves average latency and bandwidth and hence gains performance.

At the Micro-Architecture Research Labs, India we have been fundamentally re-looking at caching, and have shown that cache design and architecture is more than just increasing overall cache hit rates. In this talk we will discuss two of our recent works in this direction.

The first talk will focus on how efficiently large HBM or eDRAM caches can be managed. We show that blindly increasing hit rates for such large caches can in fact be detrimental to performance ! Instead we develop a dynamic access partitioning scheme that sacrifices some amount of hit rates in order to tap the main memory bandwidth and overall increase performance. This work was adjudged as the best paper at HPCA 2017.

In the second work, we do a fundamental re-analysis of the popular three level cache hierarchy and show that it is not the most efficient way of designing on-die caches. Instead we show that a much lower area, two level cache hierarchy, aided with a learning of the program behaviour, can outperform the more costly three level cache hierarchy, thereby presenting interesting area-performance-cost trade-offs for cache designers. This work was published at ISCA 2018.

Speaker Bio:
1. Jayesh Gaur is a senior research scientist and manager at the Micro-Architecture Research Lab (MRL), Intel India where his focus is on improving the performance of modern out of order processors. Prior to joining MRL, he worked on the architecture of the last level cache of the Skylake family of Intel processors. Jayesh has published widely in architecture conferences and has been granted/filed for nearly two dozen patents. Jayesh has an MSE in Computer Engineering from University of Michigan, Ann Arbor and a BTech. in Electrical Engineering from IIT Kanpur. 2. Anant Nori is a senior research scientist and manager at MRL, Intel India. His focus is on novel prefetching techniques for large window processors. Prior to MRL, Anant worked on the architecture of the main memory controller for the Skylake family of Intel processors. Anant holds/has filed for a dozen patents in main memory optimizations, prefetching, quality of service etc and has been active in architecture publications. He holds an MTech. in Electrical Engineering from IIT Bombay, and a BTech. in Electrical Engineering from NIT Rourkela.

Host Faculty: Dr. Arkaprava Basu

Video Archive Go Top

 

Series: M.Sc. (Engg) Thesis Defense
Title: Handling Overloads with Social Consistency.

  • Speaker: Ms. Priyanka Singla
                   M.Sc (Engg.) student
                   Dept. of CSA
  • Faculty Advisor: Prof. K Gopinath
  • Date and Time: Thursday, October 04, 2018, 3:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Cloud computing applications have dynamic workloads, and they often observe spikes in the incoming traffic which might result in system overloads. System overloads are generally handled by various load balancing techniques like replication and data partitioning. These techniques are effective when the incoming bursty traffic is dominated by reads and writes to partitionable data, but they become futile against bursts of writes to a single hot object. Further, the systems which use these load balancing techniques, to provide good performance, often adopt a variant of eventual consistency and do not provide strong guarantees to applications, and programmers. In this thesis, we provide a solution to this single object overload problem and propose a new client based consistency model -- social consistency -- that advocates providing a stronger set of guarantees within subsets of nodes (socially related), and providing eventual consistency across different subsets. We argue that by using this approach, we can in practice ensure reasonably good consistency among the clients and a concomitant increase in performance.

We further describe the design of a prototype system, BLAST, which implements this model. It dynamically adjusts resource utilization in response to changes in the workload thus ensuring nearly constant latency, and throughput, which scales with the offered load. In particular, the workload spikes for a single hot object are handled by cloning the object and partitioning the clients according to their social connectivity, binding the partitions to different clones, where each partition has a unique view of the object. The clones and the client partitions are recombined when the spike subsides. We compare the performance of BLAST to Cassandra database system, and our experiments show that BLAST handles 1.6X (by performing one split) and 2.4X (by performing three splits) more workload. We also evaluate BLAST against another load balancing system and show that BLAST provides 37% better QoE.

Video Archive Go Top

 

Series: M.Sc. (Engg) Thesis Defense
Title: Active Learning for Efficient Testing of Student Programs

  • Speaker: Mr. Ishan Rastogi
                   M.Sc (Engg.) student
                   Dept. of CSA
  • Faculty Advisor: Prof. Shirish K Shevade & Prof. Aditya S Kanade
  • Date and Time: Thursday, October 04, 2018, 10:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Automated evaluation of student programs is an important problem since it eases instructor's burden by reducing or altogether eliminating the time required for program evaluation. A solution to this problem would also make it possible to scale up courses having computer programming content to a larger audience, such as to a massive online open courses setting. The problem is, however, inherently difficult as students can make a variety of mistakes spanning the entire gamut -- from shallow syntactic errors to more involved semantic ones. Among these, identifying whether a program has a logical error is perhaps the most challenging, since the error may only surface in a subset of all valid test cases. Additionally, unlike syntax errors, logical errors are task specific and hence require an additional input from the instructor (for example, in the form of a set of quality test cases) for every new task introduced into the system.

In this talk, we will discuss our work, Automated Testing using Active learning and Symbolic-execution (ATAS), an algorithm designed to identify whether a student program is logically incorrect in an online setting. This algorithm builds upon the recent advances in both symbolic execution and active learning. Symbolic execution is a program analysis technique which can generate test cases through symbolic constraint solving. Our method makes use of a reference implementation of the task as its sole input. We compare our method with a symbolic execution-based baseline on six programming tasks retrieved from CodeForces comprising of about 23000 student submissions. We demonstrate an average improvement of over $2.5$x over the baseline in terms of runtime (thus making it more suitable for online evaluation), without significant degradation in evaluation accuracy.

Video Archive Go Top

 

Series: Department Seminar
Title: Sample complexity of partition identification using multi-armed bandits

  • Speaker: Prof. Sandeep Juneja
                   Professor and Dean
                   School of Technology and Computer Science
                   Tata Institute of Fundamental Research
                   Mumbai
  • Date and Time: Wednesday, September 26, 2018, 2:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Given a vector of probability distributions, or arms, each of which can be sampled independently, we consider the problem of identifying the partition to which this vector belongs from a finitely partitioned universe of such vector of distributions. We study this as a pure exploration problem in multi armed bandit settings and develop sample complexity bounds on the total mean number of samples required for identifying the correct partition with high probability. This framework subsumes well studied problems in the literature such as finding the best arm or the best few arms. We consider distributions belonging to the single parameter exponential family and primarily consider partitions where the vector of means of arms lie either in a given set or its complement. The sets considered correspond to distributions where there exists a mean above a specified threshold, where the set is a half space and where either the set or its complement is convex. The latter cases are considered in illustrative simple settings. In all these settings, we characterize the lower bounds on mean number of samples for each arm. Further, inspired by the lower bounds, and building upon Garivier and Kaufmann 2016, we propose algorithms that can match these bounds asymptotically with decreasing probability of error. Applications of this framework may be diverse. We briefly discuss a few associated with nested simulation and its applications to finance.

Speaker Bio:
Sandeep is a Professor and Dean at the School of Technology and Computer Science in Tata Institute of Fundamental Research in Mumbai. His research interests lie in applied probability including in mathematical finance, Monte Carlo methods, multi-armed bandit based sequential decision making, and game theoretic analysis of queues. He is currently on the editorial board of Stochastic Systems. Earlier he has been on editorial boards of Mathematics of Operations Research, Management Science and ACM TOMACS.

Host Faculty: Prof. Shalabh Bhatnagar

Video Archive Go Top

 

Series: Ph.D. Thesis Defense
Title: Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning

  • Speaker: Mr. Prasenjit Karmakar
                   Ph.D student
                   Dept. of CSA
                   IISc
  • Faculty Advisor: Prof. Shalabh Bhatnagar
  • Date and Time: Wednesday, September 26, 2018, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Stochastic approximation algorithms are sequential non-parametric methods for finding a zero or minimum of a function in the situation where only the noisy observations of the function values are available. Two time-scale stochastic approximation algorithms consist of two coupled recursions which are updated with different (one is considerably smaller than the other) step sizes which in turn facilitate convergence for such algorithms.

1) We present for the first time an asymptotic convergence analysis of two time- scale stochastic approximation driven by 'controlled' Markov noise. In particular, the faster and slower recursions have non-additive controlled Markov noise components in addition to martingale difference noise. We analyze the asymptotic behavior of our framework by relating it to limiting differential inclusions in both time scales that are defined in terms of the ergodic occupation measures associated with the controlled Markov processes.

2) Using a special case of our results, we present a solution to the off-policy convergence problem for temporal-difference learning with linear function approximation.

3) One of the important assumption in the earlier analysis is the point-wise boundedness (also called the 'stability') of the iterates. However, finding sufficient verifiable conditions for this is very hard when the noise is Markov as well as when there are multiple timescales . We compile several aspects of the dynamics of stochastic approximation algorithms with Markov iterate-dependent noise when the iterates are not known to be stable beforehand. We achieve the same by extending the lock-in probability (i.e. the probability of convergence to a specific attractor of the limiting o.d.e. given that the iterates are in its domain of attraction after a sufficiently large number of iterations (say) n_0) framework to such recursions. Specifically, with the more restrictive assumption of Markov iterate-dependent noise supported on a bounded subset of the Euclidean space we give a lower bound for the lock- in probability. We use these results to prove almost sure convergence of the iterates to the specified attractor when the iterates satisfy an 'asymptotic tightness' condition. This, in turn, is shown to be useful in analyzing the tracking ability of general 'adaptive' algorithms. Additionally, we show that our results can be used to derive a sample complexity estimate of such recursions, which then can be used for step-size selection.

4) Finally, we obtain the first informative error bounds on function approximation for the policy evaluation algorithm proposed by Basu et al. when the aim is to find the risk-sensitive cost represented using exponential utility. We also give examples where all our bounds achieve the “actual error” whereas the earlier bound given by Basu et al. is much weaker in comparison. We show that this happens due to the absence of difference term in the earlier bound which is always present in all our bounds when the state space is large. Additionally, we discuss how all our bounds compare with each other.

Video Archive Go Top

 

Series: Ph.D. Thesis Defense
Title: Integrating Read-Copy-Update Synchronization and Memory Allocation

  • Speaker: Mr. Aravinda Prasad
                   Ph.D (ERP) student
                   Dept. of CSA
                   IISc
  • Faculty Advisor: Prof. K Gopinath & Dr. Vinayaka D Pandit (Organizational guide) IBM, Bangalore, India
  • Date and Time: Wednesday, September 19, 2018, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The evolution of large multicore systems with thousands of cores has led to the exploration of non-traditional procrastination-based synchronization techniques such as Read-Copy-Update (RCU). Deferred destruction is the fundamental technique used in such techniques where writers in order to synchronize with the readers defer the freeing of the objects until the completion of all pre-existing readers. This writer-wait time period is referred to as a grace period (GP). The readers, as a consequence, need not explicitly synchronize with the writers resulting in low overhead, wait free read-side synchronization primitives.

We observe that the deferred destruction of objects leads to newer and complex forms of interactions between the synchronization technique and the memory allocator. We study and analyze the impact of such interactions in the operating system kernels for enterprise workloads, high-performance computing environments, idle systems and virtualized environments. We explore different solutions to efficiently handle deferred destructions where our general solution integrates synchronization technique with the memory allocator. Our general solution further exploits interaction between the synchronization technique and memory allocator to optimize both of them.

In the first part we analyze the implication of RCU in enterprise environments. We observe that RCU determines when the deferred object is safe to reclaim and when it is actually reclaimed. As a result, the memory reclamation of the deferred objects are completely oblivious of the memory allocator state leading to poor memory allocator performance. Furthermore, we observe that the deferred objects provide hints about the future that inform memory regions that are about to be freed. Although useful, hints are not exploited as the deferred objects are not "visible" to memory allocators. We design Prudence, a new dynamic memory allocator, that is tightly integrated with RCU to ensure visibility of deferred objects to the memory allocator. Prudence exploits optimizations based on the hints about the future during important state transitions. Our evaluation in the Linux kernel shows that Prudence performs 3.9x to 28x better in micro benchmarks compared to SLUB allocator. It also improves the overall performance perceptibly (4%-18%) for a mix of widely used synthetic and application benchmarks.

In the second part we analyze the implication of deferred destruction in idle and High-performance computing (HPC) environments where the amount of memory waiting for reclamation in a grace period is negligible due to limited OS kernel activity. The default grace period computation is not only futile but also detrimental as the CPU cycles consumed to compute a grace period leads to jitter in HPC and frequent CPU wake-ups in idle environments. We design a frugal approach to reduce RCU grace period overhead that reduces the number of grace periods by 68% to 99% and the CPU time consumed by grace periods by 39% to 99% for NAS parallel benchmarks and idle systems.

Finally, we analyze the implication of deferred destruction in a virtualized environment. Preemption of RCU-readers can cause multi-second latency spikes and can increase peak memory footprint inside VMs which in turn can negate the server-consolidation benefits of virtualization. Although preemption of lock holders in VMs has been well-studied, the corresponding solutions do not apply to RCU due to its exceedingly lightweight read-side primitives. We present the first evaluation of RCU-reader preemption in a virtualized environment. Our evaluation shows 50% increase in the peak memory footprint and 155% increase in fragmentation for a microbenchmark. We propose Conflux, a confluence of three mutually independent solutions that enhances the RCU synchronization technique, memory allocator and the hypervisor to efficiently handle the RCU-reader preemption problem.

Speaker Bio:
Aravinda Prasad is a PhD (ERP) student in the Department of Computer Science and Automation at Indian Institute of Science, Bangalore. He is advised by Prof. K Gopinath and Dr. Vinayaka D Pandit (IBM).

Video Archive Go Top

 

Series: Research Student Colloquium
Title: 1. Encoding secrets (in a Non-malleable way) 2. Two algorithms based on separator on a planar graph

  • Speaker: 1. Ms. Sai Lakshmi Bhavana Obbattu, Ph.D student
                   2. Mr. Abhiruk Lahiri, Ph.D student
  • Date and Time: Friday, September 14, 2018, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
1. Non-malleable codes generalize the classical notion of error correcting codes by providing a powerful guarantee even in scenarios where the error correcting codes cannot provide any: a decoded message is either the same or completely independent of the underlying message. Non-malleable codes have seen a lot of exciting research in recent times. In this talk, I will give an introduction to NMCs and then focus on the question of non-malleably encoding randomness. In particular, I will introduce our notion of Non-malleable Randomness Encoders and present a construction for the same. Non-malleable Randomness encoders have interesting applications to Privacy Amplification and Non-malleable codes. This is joint work with Bhavana Kanukurthi and Sruthi Sekar (Eurocrypt 2018).

2. The problem of finding the minimum cut of a graph is one of the well-studied problems. In this talk, we will consider the problem when the underlying graph is planar and directed. In a recent paper [SODA '18] an improved O(nloglogn) time algorithm is reported by Mozes et al. We will discuss their technique. In the second part of this talk, we will discuss local search based approximation algorithm. In particular, we will discuss the idea of the paper by Gibson and Pirwani [ESA '10].

Speaker Bio:
1. Sai Lakshmi Bhavana Obbattu is a doctoral student at Indian Institute of Science, Bangalore, advised by Dr. Bhavana Kanukurthi. Her publication venues include the Theory of Cryptography Conference (TCC) and Eurocrypt. Her TCC publication on Four-state Non-malleable Codes was invited to the Journal of Cryptology, which is a premier journal for research in Cryptography. She received her Integrated Dual Degree (B.Tech and M.Tech) from IIT (BHU), Varanasi. Her research interests include Non-malleable codes, Privacy Amplification, and Applied Multi-party computation. 2. Abhiruk Lahiri is a Ph.D. candidate under the guidance of Prof Sunil Chandran. His research interest is graph theory, algorithms.

Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar

Video Archive Go Top

 

Series: Department Seminar
Title: Submodular Maximization Under A Matroid Constraint: Asking more from an old friend "Greedy Algorithm"

  • Speaker: Prof. Rahul Vaze (TIFR)
  • Date and Time: Monday, September 10, 2018, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The classical problem of maximizing a submodular function under a matroid constraint is considered. Defining a new measure for the increments made by the greedy algorithm at each step, called the {bf discriminant}, improved approximation ratio guarantees are derived for the greedy algorithm. The new guarantee subsumes all the previous known results for the greedy algorithm, including the curvature based ones, and the derived guarantees are shown to be tight via constructing specific instances. A brief 'tutorial-style' overview of prior results in the area will also be provided.

Host Faculty: Dr. Siddharth Barman

Video Archive Go Top

 

Series: Ph.D. Thesis Defense
Title: Deep Learning with Minimal Supervision

  • Speaker: Mr. Gaurav Pandey
                   Ph.D Student
                   Dept. of CSA
  • Faculty Advisor: Prof. Ambedkar Dukkipati
  • Date and Time: Wednesday, August 29, 2018, 11:30 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
In recent years, deep neural networks have achieved extraordinary performance on supervised learning tasks. Convolutional neural networks (CNN) have vastly improved the state of the art for most computer vision tasks including object recognition and segmentation. However, their success relies on the presence of a large amount of labeled data. In contrast, relatively fewer work has been done in deep learning to handle scenarios when access to ground truth is limited, partial or completely absent. In this thesis, we propose models to handle challenging problems with limited labeled information.

Our first contribution is a neural architecture that allows for the extraction of infinitely many features from an object while allowing for tractable inference. This is achieved by using the `kernel trick', that is, we express the inner product in the infinite dimensional feature space as a kernel. The kernel can either be computed exactly for single layer feedforward networks, or approximated by an iterative algorithm for deep convolutional networks. The corresponding models are referred to as stretched deep networks (SDN). We show that when the amount of training data is limited, SDNs with random weights drastically outperform fully supervised CNNs with similar architectures.

While SDNs perform reasonably well for classification with limited labeled data, they can not utilize unlabeled data which is often much easier to obtain. A common approach to utilize unlabeled data is to couple the classifier with an autoencoder (or its variants) thereby minimizing reconstruction error in addition to the classification error. We discuss the limitations of decoder-based architectures and propose a model that allows for the utilization of unlabeled data without the need of a decoder. This is achieved by jointly modeling the distribution of data and latent features in a manner that explicitly assigns zero probability to unobserved data. The joint probability of the data and the latent features is maximized using a two step EM-like procedure. Depending on the task, we allow the latent features to be one-hot or real-valued vectors and define a suitable prior on the features. For instance, one-hot features correspond to class labels and are directly used for the unsupervised and semi-supervised classification tasks. For real-valued features, we use hierarchical Bayesian models as priors over the latent features. Hence, the proposed model, which we refer to as discriminative encoder (or DisCoder), is flexible in the type of latent features that it can capture. The proposed model achieves state-of-the-art performance on several challenging datasets.

Having addressed the problem of utilizing unlabeled data for classification, we move to a domain where obtaining labels is a lot more expensive, that is, semantic image segmentation. Explicitly labeling each pixel of an image with the object that the pixel belongs to, is an expensive operation, in terms of time as well as effort. Currently, only a few classes of images have been densely (pixel-level) labeled. Even among these classes, only a few images per class have pixel-level supervision. Models that rely on densely-labeled images, can not utilize a much larger set of weakly annotated images available on the web. Moreover, these models can not learn the segmentation masks for new classes, where there is no densely labeled data.

Hence, we propose a model for utilizing weakly-labeled data for semantic segmentation of images. This is achieved by generating fake labels for each image, while simultaneously forcing the output of the CNN to satisfy the mean-field constraints imposed by a conditional random field. We show that one can enforce the CRF constraints by forcing the distribution at each pixel to be close to the distribution of its neighbors. The proposed model is very fast to train and achieves state-of-the-art performance on the popular VOC-2012 dataset for the task of weakly supervised semantic image segmentation.

Video Archive Go Top

 

Series: M.Tech (Research) Colloquium
Title: Data-Races and Static Analysis for Interrupt-Driven Kernels

  • Speaker: Nikita Chopra
  • Faculty Advisor: Deepak D'Souza
  • Date and Time: Thursday, August 23, 2018, 11:30 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Static analysis of concurrent programs is challenging due to the exponential number of program points one needs to consider in a naive analysis. Data-race free (DRF) programs are an important class of concurrent programs. Programmers normally write DRF programs, as they generally tend to obtain locks before accessing shared objects. There are many techniques in the literature which exploit the property of data-race freedom in programs to do an efficient static analysis on them. One class of these techniques use an efficient control-flow structure called a "Sync-CFG" [De et al, 2011].

In this thesis we consider a class of interrupt-driven programs that model the kernel API libraries of some popular real-time embedded operating systems and the synchronization mechanisms they use. Though these programs are similar to classical concurrent programs, they make use of non-standard synchronization mechanisms like disabling interrupts, suspending the scheduler, and flag-based synchronization. Our aim is to carry out efficient Sync-CFG style static analysis for the class of race-free interrupt-driven programs.

Since the definition of races as well as the construction of the Sync-CFG depend on the notion of "synchronization edges", we need a suitable way of defining these edges for interrupt-driven programs. We give a principled way of defining them using a key notion called "disjoint blocks". This notion also suggests an efficient and effective lockset based analysis for race detection in such programs.

We use our theory to carry out static analysis on the kernel library of FreeRTOS, a popular real-time operating system, to detect races and to infer simple relational invariants on key kernel variables and data-structures. We have implemented the lockset algorithm for race detection using CIL as the front-end. We were able to detect 14 races in the FreeRTOS kernel library. All of these races were found to be real races on inspection. We also carried out a region-based relational analysis using an implementation based on CIL/Apron, to prove several relational invariants on the kernel variables and abstracted data-structures.

Speaker Bio:
Nikita Chopra is an MSc(Engg) student in the CSA department.

Host Faculty: Deepak D'Souza

Video Archive Go Top

 

Series: Department Seminar
Title: Approximate Kernel PCA Using Random Features: Computational vs. Statistical Trade-off

  • Speaker: Prof. Bharath Sriperumbudur
                   Department of Statistics
                   The Pennsylvania State University
  • Date and Time: Tuesday, August 21, 2018, 2:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Kernel principal component analysis (KPCA) is a popular non-linear dimensionality reduction technique, which generalizes classical linear PCA by finding functions in a reproducing kernel Hilbert space (RKHS) such that the function evaluation at a random variable X has maximum variance. Despite its popularity, kernel PCA suffers from poor scalability in big data scenarios as it involves solving an x n eigensystem leading to a computational complexity of O(n^3) with n being the number of samples. To address this issue, in this work, we consider a random feature approximation to kernel PCA which requires solving an m x m eigenvalue problem and therefore has a computational complexity of O(m^3), implying that the approximate method is computationally efficient if m<n with m being the number of random features. The goal of this work is to investigate the trade-off between computational and statistical behaviors of approximate KPCA, i.e., whether the computational gain is achieved at the cost of statistical efficiency. We show that the approximate KPCA is both computationally and statistically efficient compared to KPCA in terms of the error associated with reconstructing a kernel function based on its projection onto the corresponding eigenspaces. Depending on the eigenvalue decay behavior of the covariance operator, we show that only n^{2/3} features (polynomial decay) or sqrt{n} features (exponential decay) are needed to match the statistical performance of KPCA, which means without losing statistically, approximate KPCA has a computational complexity of O(n^2) or O(n^{3/2}) depending on the eigenvalue decay behavior. We also investigate the statistical behavior of approximate KPCA in terms of the convergence of eigenspaces wherein we show that only sqrt{n} features are required to match the performance of KPCA and if fewer than sqrt{n} features are used, then approximate KPCA has a worse statistical behavior than that of KPCA.

Speaker Bio:
Bharath Sriperumbudur is an Assistant Professor in the Department of Satistics at Pennsylvania State University. He received his PhD in Electrical Engineering from UC San Diego and had stints as a research fellow at University College London and University of Cambridge. His research interests include nonparametric statistics, empirical process theory, regularization and inverse problems, reproducing kernel spaces in probability and statistics and statistical learning theory.

Host Faculty: Prof. Ambedkar Dukkipati

Video Archive Go Top

 

Series: Department Seminar
Title: Inferring Insertion Times in Bloom Filters

  • Speaker: Prof. C V Ravishankar, UC Riverside
  • Date and Time: Tuesday, August 21, 2018, 11:30 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Bloom filters are extremely useful in dealing with streaming data, but are easy to misuse. We first illustrate pitfalls in using Bloom Filters, and show how to generalize our techniques to infer insertion times. We introduce inferential filters, which integrate priors and information latent in filters to make optimal query-specific decisions.

We illustrate our approach on Time-Decaying Bloom Filters, which are probabilistic structures to test membership on recently inserted items. As new items are inserted, memory of older items decays. Incorrect query responses, however, will penalize the application using the filter. Current filters may only be tuned to static penalties, and ignore much information latent in the filter. While our methods are general, we focus here on inferential time-decaying filters, and show how to support novel query types and sliding window queries with varying error penalties.

We have developed inferential versions of the existing Timing Bloom Filter and Generalized Bloom Filter. Our experiments on real and synthetic datasets show that when penalties are dynamic and prior probabilities are known, these filters reduce penalties for incorrect responses to sliding-window queries by up to 70%.

Speaker Bio:
Chinya V Ravishankar is Professor of Computer Science at the Marlan and Rosemary Bourns College of Engineering at UC Riverside. Ravishankar’s current research and teaching focus is in the fields of Data Management as well as Computer Security. In the past, he has worked and taught in a wide range of areas, including Distributed Systems, Networking, and Programming Languages. Prof. Ravishankar has served as Associate Dean for at the Marlan and Rosemary Bourns College of Engineering for the past 14 years. His current portfolio covers Research and Graduate Education. His earlier previous portfolio covered Undergraduate Education. Before moving to UCR in 1999, Prof. Ravishankar was on the faculty of the EECS Department at the University of Michigan, Ann Arbor, between 1986—1999. He holds a PhD in Computer Sciences from the University of Wisconsin—Madison, and a bachelor’s degree in Chemical Engineering from the Indian Institute of Technology (IIT) Bombay.

Host Faculty: Prof. Jayant Haritsa

Video Archive Go Top

 

Series: Ph.D. Thesis Defense
Title: Typestates and Beyond: Verifying Rich Behavioral Properties Over Complex Programs

  • Speaker: Ashish Mishra
                   Ph.D Student, CSA Department
  • Faculty Advisor: Y.N. Srikant
  • Date and Time: Friday, August 17, 2018, 10:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Statically verifying behavioral/dynamic properties of programs is an important and challenging research problem. Typestates are the most prevalently used, static, light‐weight verification systems for verifying program properties. In our work we present both theoretical and practical contributions towards static analysis and verification of Typestate defined properties. We dicuss two major challenges in statically verifying typestate properties over programs.

The first challenge may be attributed to the ``complexity of programs'' being analyzed. The state‐of‐the‐art static typestate analysis works cannot handle formidably rich programming features like asynchrony, library calls and callbacks, concurrency, etc. The second challenge may be attributed to ``complexity of the property'' being verified. Classical typestates can only verify a property defined through a finite state machine, and are inadequate to verify richer non‐regular program properties. Currently, these rich behavioral properties are mostly verified/enforced at runtime via explicit checks either by the programmer or the compiler. Unfortunately, these runtime checks are costly, error‐prone, and lay an extra burden on the programmer.

In this thesis we take small steps towards tackling both these challenges. Addressing complex program features, we present an asynchrony‐aware static analysis framework, taking Android applications as our use case. We use this framework to develop a static typestate analysis to capture Android resource API usage protocol violations. We present a set of benchmark applications for different resource types, and empirically compare our typestate analysis with the state‐of‐the‐art synchronous static analyses for Android applications.

Addressing the challenges associated with increasing complexity of properties, we present an expressive notion of typestates called, Presburger definable typestates or p‐typestates. p‐typestates associate an extra Pressburger definable property along with the states of regular typestates. This allows p‐typestates to express many useful non‐regular properties. We present a dependent type system for p‐typestates and present a simple typestate‐oriented language incorporating p‐typestates called Decidable Rich Interface Programming (DRIP) language. Further, typechecking such rich p‐typestate properties requires a programmer to provide invariants for loops and recursive structures. Unfortunately, providing these invariants is a non‐trivial task even for expert programmers. To solve this problem, we present a simple and novel loop invariant calculation approach for Pressburger definable systems. We encode a number of real world programs in our dependently‐typed language to verify several rich and non‐regular properties.

Finally we discuss several possible extensions of our thesis along both these directions.

Speaker Bio:
Mr.Ashish Mishra is a Ph.D student in the CSA department. After submitting his thesis, he has been working as a post-doctoral research at North Eastern University, USA. His areas of interest are programming language theory, program analysis and verification, and semantics of programming languages.

Host Faculty: Y N Srikant

Video Archive Go Top

 

Series: Department Seminar
Title: On Complexity of Closest Pair Problem

  • Speaker: Mr. Karthik C.S.
                   Ph.D Student
                   Weizmann Institute of Science
                   Israel
  • Date and Time: Monday, August 13, 2018, 10:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Closest Pair is a fundamental problem in Computational Geometry, where we are given a set of n points in R^d and we would like to find the closest pair of points in the set. In this talk we will see that assuming the Strong Exponential Time Hypothesis for SAT, Closest Pair cannot be solved in subquadratic (in n) time when d=omega(log n) for all L_p metrics.

Based on two joint works - first one with Roee David and Bundit Laekhanukit and second one with Pasin Manurangsi.

Host Faculty: Dr. Arnab Bhattacharyya

Video Archive Go Top

 

Series: CSA Faculty Colloquium
Title: How to securely snapshot memory

  • Speaker: Prof. Vinod Ganapathy
                   Associate Professor
                   Dept. of CSA
                   IISc
  • Date and Time: Friday, August 10, 2018, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Computer systems security has historically been a game of cat and mouse between attackers and defenders. Attackers develop novel techniques to bypass proposed defenses, while defenders must think ahead and foresee novel attacks. In this setting, how can the defender get the upper hand? This talk will make the case for security from the hardware up. We will consider the problem of securely obtaining snapshots of a computer system's memory. Snapshots play a key role in computer forensics, and it is therefore key to ensure that a machine can be snapshot free from an adversary's tampering. We will describe how adversaries have subverted these techniques in the past, and how state-of-the-art approaches to obtaining snapshots fail. We will then propose a hardware-based mechanism to obtain snapshots and show that it offers attractive benefits.

Speaker Bio:
Vinod Ganapathy is an associate professor in the CSA department working on computer systems security.

Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar

Video Archive Go Top

 

Series: Department Seminar
Title: Interactive Visual Analysis of Large Urban Data using Urbane

  • Speaker: Dr. Harish Doraiswamy
                   Research Scientist
                   New York University
  • Date and Time: Thursday, August 02, 2018, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The recent explosion in the number and size of spatio-temporal data sets from urban environments and social sensors creates new opportunities for data-driven approaches to understand and improve cities. Visualization and visual analytics systems have been successfully used at enabling users to obtain insight: well-designed visualizations substitute perception for cognition, freeing up limited cognitive/memory resources for higher-level problems. Supporting the interactive response times these systems require is challenging as they often rely on computationally expensive spatial and spatio-temporal queries involving polygonal constraints of arbitrary shapes and sizes. This problem is further compounded as data set sizes increase.

In this talk I will first give an overview of Urbane, a multi-resolution visual analytics framework that enables a data-driven analysis of cities. I will then present techniques that use GPUs to obtain real time performance for spatial aggregation queries and are at least two orders of magnitude faster than existing database systems.

Speaker Bio:
Harish Doraiswamy is a Research Scientist at the NYU Center for Data Science and a Research Assistant Professor of Computer Science and Engineering at New York University. He received his Ph.D. in Computer Science and Engineering from the Department of Computer Science and Automation at Indian Institute of Science, Bangalore. His research lies in the intersection of computational topology, big data visualization, and databases. His recent research focuses on the visual analyses of large spatio-temporal datasets from urban environments.

Host Faculty: Prof. Vijay Natarajan

Video Archive Go Top

 

 

 

 

 

 

 

 

 

 

Copyright: CSA, IISc 2018      Phone: +91-80-22932368          Fax: +91-80-23602911 Travel Blog    Feedback    Credits