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: CSA Faculty Colloquium
Title: Distributed algorithms for prototype selection and multi-label classification

  • Speaker: Dr. V. Susheela Devi
                   Principal Research Scientist
                   Dept. of CSA
  • Date and Time: Friday, September 06, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The Modified Condensed Nearest Neighbour (MCNN) algorithm is an algorithm for prototype selection which gives good performance but the time requirement is much higher than algorithms like Condensed Nearest Neighbour (CNN) algorithm. A distributed approach called Parallel MCNN (pMCNN) is proposed which cuts down the time required drastically. pMCNN has been used for prototype selection on large and streaming data and results are presented which shows good performance with saving in time.

The second part of the talk describes an algorithm for multilabel classification for discrete data. Two improvements are carried out to reduce the complexity. The first is feature selection which reduces both space and time complexity. The second is to use a distributed approach to this problem. Results show good performance as compared to standard techniques like ML-KNN (Multi label kNN). The use of feature selection and the distributed approach give saving in the time required which is helpful when the data sizes are large.

Speaker Bio:
V. Susheela Devi works in the Intelligent Systems group in the department. Her areas of interest include pattern recognition, machine learning and soft computing. She is the co-ordinator of the Pattern Analysis and Machine Intelligence lab. She has handled courses such as Pattern Recognition, Data Mining, Data Structures and Algorithms, Computational Methods of Optimization, Artificial Intelligence and Soft Computing.

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

Video Archive Go Top

 

Series: Theory Seminar Series
Title: Guarding Polygons via CSP

  • Speaker: Dr. Akanksha Agrawal
                   Postdoctoral Researcher
                   Department of Computer Science
                   Ben-Gurion University of the Negev
                   Israel
  • Date and Time: Friday, August 30, 2019, 1:00 PM
  • Venue: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract
The Art Gallery problem is a fundamental visibility problem in Computational Geometry, introduced by Klee in 1973. The input consists of a simple polygon P, (possibly infinite) sets X and Y of points within P, and an integer k, and the objective is to decide whether at most k guards can be placed on points in X so that every point in Y is visible to at least one guard. In the classic formulation of Art Gallery, X and Y consist of all the points within P. Other well-known variants restrict X and Y to consist either of all the points on the boundary of P or of all the vertices of P. The above mentioned variants of Art Gallery are all W[1]-hard with respect to k [Bonnet and Miltzow, ESA'16]. Given the above result, the following question was posed by Giannopoulos [Lorentz Center Workshop, 2016].

``Is Art Gallery FPT with respect to the number of reflex vertices?''

In this talk, we will obtain a positive answer to the above question, for some variants of the Art Gallery problem. By utilising the structural properties of ``almost convex polygons'', we design a two-stage reduction from (Vertex,Vertex)-Art Gallery to a new CSP problem where constraints have arity two and involve monotone functions. For the above special version of CSP, we obtain a polynomial time algorithm. Sieving these results, we obtain an FPT algorithm for (Vertex,Vertex)-Art Gallery, when parameterized by the number of reflex vertices. We note that our approach also extends to (Vertex,Boundary)-Art Gallery and (Boundary,Vertex)-Art Gallery.

Speaker Bio:
I am a postdoctoral researcher at the Department of Computer Science, Ben-Gurion University of the Negev, Israel, where I work in the group of Prof. Meirav Zehavi. Before moving to Israel, I was a postdoctoral researcher at the Institute for Computer Science and Control, Hungarian Academy of Sciences, Hungary. I did my Ph.D at the Department of Informatics, University of Bergen, Norway, under the guidance of Prof. Saket Saurabh and Prof. Daniel Lokshtanov. My research interests include Parameterized Complexity, Computational Geometry, Exact Algorithms, and Fine Grained Complexity.

Host Faculty: Dr. Anand Louis

Video Archive Go Top

 

PAST SEMINARS

Series: Ph.D. Colloquium
Title: On Certain Learning and Lower Bound Problems Related to Iterated Matrix Multiplication Polynomial

  • Speaker: Mr. Vineet Nair
  • Faculty Advisor: Prof. Chandan Saha
  • Date and Time: Friday, August 23, 2019, 3:00 PM
  • Venue: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract
The iterated matrix multiplication polynomial (IMM) of width w and length d is the 1x1 entry in the product of d square matrices of size w. The w2d entries in the d matrices are distinct variables. In this thesis, we study certain learning and lower bound problems related to IMM.

Our first work gives a polynomial time randomized algorithm for equivalence testing of IMM. At its core, the equivalence testing algorithm exploits a connection between the irreducible invariant subspaces of the Lie algebra of the group of symmetries of a polynomial f that is equivalent to IMM and the layer spaces of a full-rank algebraic branching program computing f. This connection also helps determine the group of symmetries of IMM and show that IMM is characterized by its group of symmetries.

Our second work is related to learning affine projections of IMM, which is believed to be a very hard problem as it is equivalent to reconstructing a powerful model to compute polynomials called algebraic branching programs (ABP). Equivalence test for IMM can be viewed as reconstructing ABPs in the average-case, when the width of the ABP is at most (n/d)0.5, where n and d are the number of variables and the degree of the polynomial computed by the ABP respectively. Our second work improves this by first considering a related problem called `linear matrix factorization’ (LMF) which is a natural generalization of the polynomial factorization problem. We give a polynomial time randomized algorithm for average-case LMF for matrix products of width at most 0.5n0.5. In fact, we give a polynomial time randomized algorithm that solves (worst-case) LMF problem when the input matrix product is non-degenerate or pure product-- a notion we define in this work. Using our algorithm for LMF, we give a non-trivial average-case reconstruction algorithm for ABPs of width at most 0.5n0.5, which is interesting in the context of the Ω(n0.5) width lower bound known for homogeneous ABPs.

Our last work gives lower bounds on interesting restrictions of arithmetic formulas computing IMM. We prove a wΩ(d) lower bound on the size of multilinear depth three formulas computing IMM of width w and length d. The lower bound is proved by introducing a novel variant of the partial derivatives measure called skewed partial derivatives, which found applications in other subsequent works. Improving this result to wΩ(log d) size lower bound on multilinear formulas computing IMM would imply a super-polynomial separation between ABPs and arithmetic formulas. We also show an exponential separation between multilinear depth three and multilinear depth four formulas which was an improvement over the quasi-polynomial separation already known. We also consider a restriction of multilinear formulas, called interval set-multilinear formulas computing IMM. Proving a super-polynomial size lower bound on interval set-multilinear formulas computing IMM would imply a super-polynomial separation between algebraic branching programs and homogeneous formulas in the non-commutative world. We make progress in this direction by giving a super-polynomial size lower bound on an interesting restriction of the interval set-multilinear formula computing IMM.

Video Archive Go Top

 

Series: Ph.D. Colloquium
Title: Constant-rate Non-malleable Codes and their Applications

  • Speaker: MS.Sai Lakshmi Bhavana Obbattu
                   CSA Department
  • Faculty Advisor: Dr. Bhavana Kanukurthi
  • Date and Time: Friday, August 23, 2019, 10:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Non-malleable codes (NMCs) introduced by Dziembowski, Pietrzak and Wichs in ITCS 2010, provide powerful security guarantees where standard error-correcting codes can not provide any guarantee: a decoded message is either the same or completely independent of the underlying message. NMCs have found applications to various aspects of cryptography such as CCA secure encryption, tamper and leakage resilient cryptography, non-malleable commitments, non-malleable secret sharing schemes and so on. In this talk, we present the first explicit construction of a constant rate, constant state non-malleable code. Next, we will present an application of NMCs to the fascinating problem of "Privacy Amplification". In the problem of privacy amplification, two parties, Alice and Bob, who a-priori share a weak secret, to agree on a uniform secret key, in the presence of a computationally unbounded adversary Eve. Building privacy amplification protocols with constant "entropy loss" and constant "round complexity" was open since 1988 (and recently closed in an independent work of Li [CCC '19]). In this talk, we will show how to construct such a privacy amplification protocol under the existence of non-malleable code with certain strong security guarantees.

This talk is based on joint works with Eshan Chattopadhyay, Bhavana Kanukurthi and Sruthi Sekar.

References: [1] Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, and Sruthi Sekar. Four-state non-malleable codes with explicit constant rate. In Theory of Cryptography Conference, TCC 2017. Invited to Journal of Cryptology.

[2] Eshan Chattopadhyay, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, and Sruthi Sekar. Privacy amplification from non-malleable codes. In submission.

Video Archive Go Top

 

Series: CSA Golden Jubilee Frontier Lecture Series
Title: Shuffling Chromosomes, Chasing Kangaroos and Other Mathematical Curiosities

  • Speaker: Prof. Prasad Tetali
                   Regents’ Professor,
                   School of Mathematics and School of Computer Science,
                   Georgia Institute of Technology, Atlanta, USA
  • Date and Time: Thursday, August 22, 2019, 4:00 PM
  • Venue: Faculty Hall, Indian Institute of Science

Abstract
This popular-level lecture will focus on some modern applications of the classical topic of Markov chains. The mixing time of a Markov chain measures the time to get close to the equilibrium distribution of the chain. After introducing the topic briefly, the speaker will address a few surprising applications of Markov chain mixing times. These range from cracking ciphers and modelling chromosomal mutations to solving the discrete logarithm problem (using Pollard’s kangaroos), of particular relevance to digital security. The lecture is expected to be self-contained.

Speaker Bio:
Prof. Prasad Tetali is a Regents’ Professor in the School of Mathematics and the School of Computer Science at Georgia Institute of Technology. Dr. Tetali obtained his Ph.D. (1991) from the Courant Institute of Mathematical Sciences (NYU) after earning an M.S. (1987) from the School of Automation at IISc. His research interests lie in probability, discrete mathematics, algorithms and optimization and he has published more than 110 research articles. He is recognized as a SIAM Fellow (2009) and an AMS Fellow (2012). Dr. Tetali is a former director and a current member of the steering committee of Georgia Tech’s Algorithms and Randomness Center Think Tank (ARC) and has been on the coordinating committee of Georgia Tech’s renowned interdisciplinary Ph.D. program in Algorithms, Combinatorics and Optimization (ACO) for the past two decades. He served as the interim Chair of the School of Mathematics at Georgia Tech during CY 2015-2016. He is currently on the leadership team of the NSF-funded Transdisciplinary Research Institute for Advancing Data Science (TRIAD) at Georgia Tech.

Host Faculty: Prof. Shalabh Bhatnagar

Video Archive Go Top

 

Series: Department Seminar
Title: Data Viz in a Box

  • Speaker: Christopher Arnold
                   Wells Fargo
  • Date and Time: Wednesday, August 21, 2019, 3:30 PM
  • Venue: CSA Lecture Hall (Room No. 112, Ground Floor)

Abstract
Data Viz in a box is an hour-long, interactive, and entertaining exploration of some of the key principles in data graphic design. This particular lecture focuses on the concept of Data/Ink ratio and how to eliminate unnecessary and “spend” helpful ink so that the reader can better interpret the data graphic. The session is highly interactive and infused with humour to engage and encourage students to put themselves in the place of the person trying to interpret their work. The course objective is to fundamentally change the students’ concept of data graphics. The instructor will bring a single page of paper for each student. The only materials required for the instructor are a whiteboard and three (working) dark-coloured markers. For large classes, a head microphone is preferred, but hand-held can also work. This class can also be taught remotely through a sharing session on Skype or Zoom.

Speaker Bio:
Chris Arnold (popularly known as the Data Whisperer) has been making data talk since the age of mainframes. Spanning quantitative and qualitative analysis, he has built high functioning quant teams and data mart solutions across pharmaceutical, automotive, and financial services industries; within risk, operations, and marketing domains. He has also conducted ethnographic research in the Amazon basin. He currently leads Wells Fargo’s offshore analytics practice, with teams in India and the Philippines. He guest lectures at universities and has been a Lecturer of Data Visualization at UC Berkeley’s Master’s in Data Science program. Chris has an interdisciplinary master’s degree from UC Santa Barbara, where he additionally completed the National Center for Geographic Information & Analysis program. Chris speaks passionately about data visualization, intuitive use of complex analytics, and the alleged intelligence of so-called business intelligence tools. Warning: if you don't have an hour to waste, don't ask him about pie charts. Chris is a surfer, fly fisherman, and photographer, although not particularly proficient in any one. He is based in Namma Bengaluru.

Host Faculty: Prof. Vijay Natarajan

Video Archive Go Top

 

Series: Theory Seminar Series
Title: Inapproximability of Clustering in L_p metrics

  • Speaker: Mr. Karthik C.S
                   Postdoctoral fellow
                   Weizmann Institute of Science
  • Date and Time: Friday, August 16, 2019, 1:00 PM
  • Venue: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract
The two most popular objectives optimized in clustering algorithms are k-means and k-median. The k-means (resp. k-median) problem in the L_p-metric is specified by n points as input and the goal is to classify the input point-set into k clusters such that the k-means (resp. k-median) objective is minimized. The best-known inapproximability factor in literature for these NP-hard problems in L_p-metrics were well-below 1.01. In this talk, we take a significant step to improve the hardness of approximating these problems in various L_p-metrics. Our techniques are inspired by the tools and perspectives developed in fine-grained complexity in the last couple of years. The talk is based on a joint work with Vincent Cohen-Addad.

Speaker Bio:
Karthik C.S. is a postdoctoral fellow in Weizmann Institute of Science. He is interested in Hardness of Approximation in Fine-Grained and Fixed-Parameter Complexity, Probabilistically Checkable Proofs, and Communication Complexity. He received his PhD from Weizmann Institute of Science and Master's from École Normale Supérieure de Lyon.

Host Faculty: Dr. Arindam Khan

Video Archive Go Top

 

Series: Ph.D. Thesis Defense
Title: On Representations and Spectral Inequalities for Non-Uniform Hypergraphs

  • Speaker: Mr. Ashwin Guha
  • Faculty Advisor: Prof. Ambedkar Dukkipati
  • Date and Time: Tuesday, August 13, 2019, 11:30 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Spectral graph theory involves the study of the eigenvalues and eigenvectors of graph connectivity matrices such as the adjacency matrix, Laplacian or the sign-less Laplacian. Spectral methods have often proved to be efficient and are widely used in solving problems where the underlying objects can be represented by graphs. While graph theory has a variety of applications, it has often been observed in many real-world instances that the pair-wise relationships captured in graphs do not describe the data in its entirety. To overcome this limitation, the notion of hypergraphs was introduced. Hypergraphs are a general version of a graph, where an edge may span more than two nodes. They have been studied extensively from a combinatorial perspective. Recently there has been renewed interest in applying spectral methods to problems in hypergraphs, especially hypergraph partitioning and community detection, which have applications in machine learning. In order to employ spectral techniques, a crucial issue that needs to be addressed is the appropriate representation of the hypergraphs. In this work, we consider various representations of hypergraphs to study their spectral properties. These representations include some matrix-based representations such as clique expansion, star expansion and simplicial complexes as well as tensor representations. We present a comparative study of the representations and study how one can extend existing results for 2-graphs to hypergraphs, in particular, to non-uniform hypergraphs. We define a Laplacian in each of the representation and study its spectrum. We also provide bounds for the largest and the second smallest eigenvalue of the Laplacians in terms of each of the representations. One of the most important results in spectral graph theory is the Cheeger inequality, which relates the isoperimetric number of a graph and the second smallest eigenvalue of the graph Laplacian. We provide a generalized version of Cheeger inequality for non-uniform hypergraphs using the weighted clique approach as well as using a tensor approach. This is the main contribution of this work. We then compare these results with the existing Cheeger inequality for simplicial complexes. In addition, we also provide a conjecture on a generalized Mixing Lemma for simplicial complexes.

Video Archive Go Top

 

Series: CSA Golden Jubilee Frontier Lecture Series
Title: The Multi-armed Bandit Problem Revisited

  • Speaker: Prof. P.R.Kumar
                   Professor and College of Engineering Chair in Computer Engineering
                   Texas A&M University, USA
  • Date and Time: Thursday, August 08, 2019, 4:00 PM
  • Venue: Faculty Hall, Indian Institute of Science

Abstract
We address the classical multi-armed bandit problem, and. exhibit a family of scheduling policies that appear to have the best empirical performance compared to those known in the literature, as well as low complexity. We also establish regret bounds, both in expectation and on sample paths.

[Joint work with Xi Liu, Ping-Chun Hsieh and Anirban Bhattacharya].

Speaker Bio:
P. R. Kumar obtained his B.Tech. degree in Electrical Engineering (Electronics) from I.I.T. Madras in 1973, and the M.S. and D.Sc. degrees in Systems Science and Mathematics from Washington University, St. Louis in 1975 and 1977, respectively. From 1977-84, he was a faculty member in the Department of Mathematics at the University of Maryland Baltimore County. From 1985-2011, he was a faculty member in the Department of Electrical and Computer Engineering and the Coordinated Science Laboratory at the University of Illinois. Currently he is at Texas A&M University where he is a University Distinguished Professor, Regents Professor, and holds the College of Engineering Chair in Computer Engineering. Kumar has worked on problems in game theory, adaptive control, stochastic systems, simulated annealing, neural networks, machine learning, queueing networks, manufacturing systems, scheduling, wafer fabrication plants and information theory. His current research focus includes renewable energy, smart grid, security, privacy, automated transportation, unmanned aerial vehicle traffic management, wireless networks, 5G, cyber-physical systems, control theory, information theory, stochastic systems, and operations research. Kumar is a member of the National Academy of Engineering of the USA, the World Academy of Sciences, and the Indian National Academy of Engineering. He was awarded an honorary doctorate by the Swiss Federal Institute of Technology (Eidgenossische Technische Hochschule) in Zurich. He received the IEEE Field Award for Control Systems, the Donald Eckman Award of American Automatic Control Council, the Fred Ellersick Prize of IEEE Communications Society, the Outstanding Contribution Award of ACM SIGMOBILE, the Infocom Achievement Award, and a SIGMOBILE Test-of-Time Paper Award. He is an ACM Fellow and a Fellow of IEEE. He was a Guest Chair Professor and Leader of the Guest Chair Professor Group on Wireless Communication and Networking at Tsinghua University, Beijing, China. He is an Honorary Professor at IIT Hyderabad. He is a D. J. Gandhi Distinguished Visiting Professor at IIT Bombay. He was awarded the Distinguished Alumnus Award from IIT Madras, the Alumni Achievement Award from Washington University in St. Louis, and the Daniel C. Drucker Eminent Faculty Award from the College of Engineering at the University of Illinois.

Host Faculty: Dr. Shalabh Bhatnagar

Video Archive Go Top

 

Series: Department Seminar
Title: AI: towards Ambient Intelligence

  • Speaker: 1. Professor Yossi Matias
                   Tel Aviv University and Google Israel Research and Engineering,
                   
                   2. Anand Rangarajan
                   Google Research, Bangalore
  • Date and Time: Tuesday, August 06, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Speaker Bio:
1. Yossi is Vice President, Engineering, at Google. He is leading efforts in Search (Google Autocomplete, Search Live Results, Google Trends, Search Console), Conversational AI (Google Duplex, Call Screen, Listening to the web), and other Research initiatives (from foundations to applications in Health). He is the global lead of Crisis Response (SOS Alerts, Public Alerts, Flood Forecasting), and is on the steering committee for the AI for Social Good initiative. Yossi is the founding Head of Google's R&D Center in Israel (which he grew to over 1000 on staff). He is also the founding executive lead of Google for Startup Campus Tel Aviv, and of Launchpad and other global entrepreneurship programs. In addition to his experience as an executive and entrepreneur, Yossi has a rich record of scientific research as a Computer Science professor at Tel Aviv University, and previously a Research Scientist at Bell Labs and visiting professor at Stanford. He published extensively, has dozens of patents on his name, and pioneered some of the early technologies for the effective analysis of big data, internet privacy, and contextual search. Yossi is a recipient of the Godel Prize and is an ACM Fellow. 2. Anand is the Site Lead for Google Bangalore, and an Engineering Director in Search. He joined Google in California in 2008 and worked in Enterprise, Gmail Ads and YouTube in Mountain View before moving to Bangalore in Aug 2013. In prior life, he has invested ~10 years in designing, coding, and managing teams working in various aspects of Computer Networking. He fondly remembers the day when his startup Sahasra Networks was acquired by Cypress Semiconductor. He treasures the company of his B.Tech classmates from IIT Madras and Masters friends from Stanford University. He enjoys playing chess, running, word puzzles, sanskrit and listening to indian classical music. His cofounder and he enjoy nurturing their 2 startups aged 11 and 8.

Host Faculty: Prof. Shalabh Bhatnagar

Video Archive Go Top

 

Series: Department Seminar
Title: Formal Methods in Network Games

  • Speaker: Dr Shibashis Guha
                   Universite Libre de Bruxelles
                   Belgium
  • Date and Time: Tuesday, August 06, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Network games (NGs) are played on directed graphs and are extensively used in network design and analysis. In the classical model, each player selects a path connecting her source and target vertices. The cost of traversing an edge depends on the load; namely, number of players that traverse it. NGs abstract the fact that different users may use a resource at different times and for different durations; time plays an important role in determining the costs of the users in reality. For example, when transmitting packets in a communication network, routing traffic in a road network, or processing a task in a production system, actual sharing and congestion of resources crucially depends on time. In the first part of the talk, we will discuss timed network games (TNGs), which add a time component to network games. The time in our model is continuous and cannot be discretized. In particular, players have uncountably many strategies, and a game may have uncountably many pure Nash equilibria. We will also mention how different reductions to a formal model called timed automata help in reasoning about TNGs.

In the second part of the talk, we consider search problems for NGs that include finding special strategy profiles such as a Nash equilibrium and a globally optimal solution. The networks modeled by NGs may be huge. In formal verification, abstraction has proven to be an extremely effective technique for reasoning about systems with big and even infinite state space. We describe an abstraction-refinement methodology for reasoning about NGs.

Based on joint works with Guy Avni and Orna Kupferman.

Host Faculty: Prof. Matthew Jacob Thazhuthaveetil

Video Archive Go Top

 

Series: Department Seminar
Title: Asymptotically Optimal Threshold Policies for Appointment Scheduling and Stochastic Knapsacks.

  • Speaker: Dr. Harsha Honnappa
                   School of Industrial Engineering
                   Purdue University
  • Date and Time: Monday, July 29, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
We revisit a classic appointment scheduling (AS) problem wherein a finite pool of jobs must be scheduled at a single server queue over a finite fixed time horizon. Jobs once scheduled may not show up (or ‘no show’) with fixed probability, and will take a random amount of time in the server. The AS problem seeks an arrangement of the jobs over the finite horizon such that the cumulative wait times of jobs that turn up are balanced against overage costs. In general, the AS integer program is quite hard to solve, and we seek non-adaptive optimal threshold policies that can be easily implemented. In this work, we prove by construction the existence of an asymptotically optimal sequence of heuristic policies as the number of jobs/items increases to infinity, both in a fluid and diffusion scale. In fact, our policy shows that asymptotically it is optimal to keep the system critically loaded. We also quantify the ’stochasticity gap’ of using the heuristic policies against the best offline/oracle policy where all the stochasticity is unveiled ahead of time. Our results also point to an equivalence between an online version of the AS problem and dynamic and stochastic knapsack problems (DSKPs). In the latter, items of random sizes are presented (one after another) over a finite time horizon to a decision-maker who seeks to pack a fixed capacity ‘knapsack’ with a minimal number of items while maximizing a cumulative reward. This is joint work with Mor Armony (NYU) and Rami Atar (Technion).

Speaker Bio:
Harsha Honnappa is an Assistant Professor in the School of Industrial Engineering at Purdue University. His research group at the Stochastic Systems Lab works on the theory of stochastic models and stochastic optimization, with a particular interest in system design. His works is supported by the National Science Foundation and the Purdue Research Foundation.

Host Faculty: Dr. Siddharth Barman

Video Archive Go Top

 

Series: CSA Faculty Colloquium
Title: Connections between Computational Geometry and Combinatorial Geometry

  • Speaker: Prof. Sathish Govindarajan
                   Associate Professor
                   Dept. of CSA
  • Date and Time: Friday, July 26, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Given a collection of geometric objects, the area of Computational Geometry looks at algorithmic questions on them and the area of Combinatorial Geometry looks at structural/combinatorial questions on them. In this talk, we will explore connections between these two areas.

Specifically, we will look at geometric optimization problems like independent set, hitting set and set cover on geometric objects. The talk will survey and describe various methods of designing approximation algorithms for these problems using techniques and results in Combinatorial Geometry.

Speaker Bio:
Sathish Govindarajan is an Associate Professor in the Department of Computer Science and Automation at IISc. He received his B.E degree from BITS, Pilani and Ph.D degree from Duke University. His research interests are broadly in the areas of Combinatorial Geometry and Computational Geometry. In current work, he is interested in solving geometric optimization problems using techniques and results from Combinatorial Geometry.

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

Video Archive Go Top

 

Series: Department Seminar
Title: Resource Management for Efficient, Scalable and Resilient Network Function Chains

  • Speaker: Dr Sameer G Kulkarni
                   University of California, Riverside
  • Date and Time: Thursday, July 25, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Networks, the basis of the modern connected world, have evolved beyond the connectivity services. Network Functions (NFs) or traditionally the middleboxes are the basis of realizing different types of in-network services such as security, optimization functions, and value-added services. Typically, multiple NFs are chained together (also known as Service Function Chaining) to realize distinct network services, which are pivotal in providing policy enforcement and performance in networks. Network Function Virtualization (NFV) is becoming more prevalent and enabling the softwarized NFs to fast replace the traditional dedicated hardware-based middleboxes in Communication Service Provider (CSP) networks. However, Virtualized Network Function (VNF) chains posit several systems and network level resource management and failure resiliency challenges: to ensure optimal resource utilization and performance at the system level; and at the network-level to address optimal NF placement and routing for service chains, traffic engineering, and load balancing the traffic across Virtualized Network Function Instances (VNFIs); and to provide High Availability (HA), Fault Tolerance (FT) and Disaster Recovery (DR) guarantees.

This talk presents an NFV resource management framework to realize efficient, scalable and resilient network service chaining. The presented solutions enable to improve scalability, performance, resource-utilization efficiency, and resiliency of deploying the NF chains in SDN/NFV ecosystem and are based on the standardized ETSI MANO NFV reference architecture. We address system-level NF resource utilization, performance, and scale challenges by designing a userspace NF scheduling framework for service function chains. We present a novel rate-cost proportional scheduler and chain-aware backpressure mechanisms to optimize the resource utilization through judicious Central Processing Unit (CPU) allocation to the NFs and improve on the chain-wide performance. We address network-level challenges i.e. orchestration and management of NF chains through a semi-distributed resource management framework that can efficiently instantiate, place and relocate the network functions and to distribute traffic across the active NF instances to optimize both the utilization of network links and NFs. We address HA and FT for NF chains through a novel NF state replication strategy and distinct mechanisms to provide timely detection of NFs, hardware node (Virtualized Network Function Manager), and network link failures. We exploit the concept of external synchrony and rollback recovery to address non- determinism and significantly reduce the amount of state transfer required to maintain consistent chain-wide state updates. We provide distinct failover mechanisms for individual NF failures and global service chain-wide failures with strict correctness guarantees.

Host Faculty: Matthew Jacob

Video Archive Go Top

 

Series: CSA Distinguished Lecture
Title: From Causal Inference to Autoencoders, Memorization and Gene Regulation

  • Speaker: Professor Caroline Uhler
                   Massachusetts Institute of Technology
                   USA
  • Date and Time: Tuesday, July 23, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Recent progress in genomics makes it possible to perform perturbation experiments at a very large scale. This motivates the development of a causal inference framework that is based on observational and interventional data. We characterize the causal relationships that are identifiable and present the first provably consistent algorithm for learning a causal network from such data. I will then couple gene expression with the 3D genome organization. In particular, we will discuss approaches for integrating different data modalities such as sequencing or imaging via autoencoders. We end by a theoretical analysis of autoencoders linking overparameterization to memorization. In particular, we will show that overparameterized single-layer fully connected autoencoders as well as deep convolutional autoencoders memorize images, i.e., they produce outputs in the span of the training images. Collectively, this talk will highlight the symbiosis between biology and machine learning, showing how biology can lead to new theorems, which in turn can guide biological experiments.

Speaker Bio:
Caroline Uhler is the Henry L. & Grace Doherty Associate Professor in the Electrical Engineering and Computer Science Department at MIT. She joined the MIT faculty in 2015 as an assistant professor in EECS and IDSS. She holds an MSc in Mathematics, a BSc in Biology, and an MEd in High School Mathematics Education from the University of Zurich. She obtained her PhD in Statistics from UC Berkeley in 2011. Before joining MIT, she spent short postdoctoral positions at the Institute for Mathematics and its Applications at the University of Minnesota and at ETH Zurich, and 3 years as an assistant professor at IST Austria. Her research focuses on mathematical statistics and computational biology, in particular on graphical models, causal inference and algebraic statistics, and on applications to learning gene regulatory networks and the development of geometric models for the organization of chromosomes. She is an elected member of the International Statistical Institute and she is the recipient of a Sloan Research Fellowship, an NSF Career Award, a Sofja Kovalevskaja Award from the Humboldt Foundation, and a START Award from the Austrian Science Fund.

Host Faculty: Prof. Arnab Bhattacharyya

Video Archive Go Top

 

Series: Department Seminar
Title: A Tale of Two Hardware Prefetchers: Prefetchers for Performance and Security

  • Speaker: Prof. Biswabandan Panda, Faculty, CSE, IIT Kanpur
  • Date and Time: Tuesday, July 23, 2019, 11:30 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
This talk will be about two recent works on hardware prefetching:

(i) Bouquet of instruction pointers, an L1 data prefetching technique that outperforms the state-of-the-art data prefetchers. We propose an instruction pointer classifier based hardware prefetching technique for the DPC-3. We use multiple instruction pointer based prefetchers that suit different access patterns and overall cover a wide spectrum of access patterns. Our classifier classifies instruction pointers at the L1 cache level and communicates the same to the L2 prefetcher. Our prefetching framework named Instruction Pointer Classifier based Prefetching (IPCP) provides 43.75% improvement for single-core and 22% for 25 selectively chosen multi-core mixes, respectively. IPCP demands a hardware overhead of 16.7KB per core. The bouquet approach won the data prefetching championship@ISCA '19.

(ii) A hardware prefetcher that can fool a cross-core side-channel attacker at the shared last-level cache. The fundamental principle behind all the cross-core eviction attack strategies is that the attacker can observe LLC access time differences (in terms of latency differences between events such as hits/misses) to infer about the data used by the victim. We fool the attacker (by providing LLC hits to the addresses of interest) through a back-invalidation-hits triggered hardware prefetching technique (BITP). BITP is an L2 cache level hardware prefetcher that prefetches the back-invalidated block addresses and refills the LLC (along with the L2) before the attacker’s observation/access, efficiently nullifying inferences due to differences in LLC access latencies. BITP will appear in the upcoming PACT '19.

Speaker Bio:
Biswabandan Panda is an Assistant Professor at the CSE dept. of IIT Kanpur. Prior to that, he was at the PACAP team of INRIA, Rennes, working with André Seznec. He received his Ph.D. and Masters from Indian Institute of Technology Madras. His area of research includes performance and security issues related to memory systems.

Host Faculty: Arkaprava Basu

Video Archive Go Top

 

Series: CSA Distinguished Lecture
Title: Explainable Artificial Intelligence

  • Speaker: Prof. Sargur N. Srihari
                   SUNY Distinguished Professor
                   Department of Computer Science and Engineering
                   University at Buffalo
                   The State University of New York
                   USA
  • Date and Time: Thursday, July 18, 2019, 4:00 PM
  • Venue: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract
Today’s AI approaches based on deep learning perform perceptual and other tasks exceedingly well. However the methods optimize the solution to each task, without considering the interpretability of the solution by humans. In tasks where human judgment is a necessary component, as in critical applications such as medicine, defense and forensics, it is necessary for the decision by the AI system to be accompanied by an explanation. We will describe different types of explainability in AI, emphasizing probabilistic approaches. We will take the example of forensic comparison and show how a high performance deep learning system and an explainable system can coexist.

Speaker Bio:
Srihari is a SUNY Distinguished Professor in the Department of Computer Science and Engineering at the University at Buffalo, The State University of New York. Srihari's research and teaching is in artificial intelligence and machine learning. His work led to the world’s first automated system for reading handwritten postal addresses. It was deployed on a large-scale by the United States Postal Service and then expanded to the UK and Australia. A side-effect was that it led to the task of recognizing handwritten digits to be considered the fruit-fly of AI. Srihari also spent a decade extending the methods to forensic pattern evidence-- latent prints, handwriting and footwear impressions-- which provided a scientific basis for presenting such testimony in US federal courts. Srihari's honors include: Fellow of the IEEE, Fellow of the International Association for Pattern Recognition and distinguished alumnus of the Ohio State University College of Engineering. Srihari received a B.Sc. from the Bangalore University, a B.E. from the Indian Institute of Science and a Ph.D. in Computer and Information Science from the Ohio State University.

Host Faculty: Prof. M. Narasimha Murty

Video Archive Go Top

 

Series: Department Seminar
Title: Ph.D. Studies at EPFL

  • Speaker: Prof. Babak Falsafi
  • Date and Time: Thursday, July 18, 2019, 11:30 AM
  • Venue: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract
The Ph.D. program in Computer & Communication Sciences at EPFL is a US-style research program with the duration of 4-6 years with full funding. The program admits both MS students and 4-year BS students directly. Our award-winning student's intern among a global group of industrial affiliates, participate in industrial fellowships, benefit from a resourceful environment that gives them access to cutting edge technologies and enables them to attend conferences around the world, and compete for global employment in industry and academia among the top echelon of peers. In this talk, I will go over what life and the program is like at EPFL.

Speaker Bio:
Babak Falsafi is Professor in the School of Computer and Communication Sciences and the founding director of the EcoCloud research center at EPFL. He has worked on server architecture for quite some time and has had contributions to a few industrial platforms including the WildFire/WildCat family of multiprocessors by Sun Microsystems (now Oracle), memory system technologies for IBM BlueGene/P and Q and ARM cores, and server evaluation methodologies in use by AMD, HP and Google (PerfKit). His recent work on scale-out server processor design lays the foundation for Cavium ThunderX. He is a fellow of ACM and IEEE.

Video Archive Go Top

 

Series: CSA Distinguished Lecture
Title: Part 3/3: Server architectures: Network-centric server architecture

  • Speaker: Prof. Babak Falsafi
  • Date and Time: Wednesday, July 17, 2019, 11:00 AM
  • Venue: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract
Information technology has undergone a major paradigm shift with sensors, embedded and mobile devices generating massive amounts of data to be augmented with backend cloud services for an enhanced experience. Data has emerged as a currency for modern society. Datacenters are now the backbone of IT offering large-scale cloud services at low costs benefiting from and exploiting the economies of scale. With silicon efficiency scaling having dwindled since 2004 and silicon density scaling slowing down, future digital platforms will rely on heterogeneous logic and memory to allow for IT scalability. Meanwhile, the demand for large-scale cloud services has grown dramatically faster than conventional silicon scaling making IT platform scalability a grand challenge. Future platforms will need hand-in-hand collaboration of application domain experts and platform designers to improve scalability. With many online services being in-memory and the minimum communication latency between the farthest nodes in a 20MW datacenter being microseconds, future server platforms will go through revolutionary changes in architecture to enable seamless aggregation of logic and memory resources across nodes, breaking the conventional system abstraction layers.

In a set of three lectures, I will go over research projects in PARSA @ EPFL that have focused on the impact of the slowdown in silicon scaling on data-centric technologies in servers. These lectures will be divided into three parts: - Logic heterogeneity in servers: This lecture covers proposals for accelerators data management and neural networks. - Memory heterogeneity in servers: This lecture covers proposals for incorporation emerging memory technologies into conventional hierarchies including designs for near-memory accelerators, high-bandwidth DRAM caches, and storage-class memory. - Network-centric server architecture: This lecture covers proposals for hardware/software co-design for memory pooling and micro-scale services.

Speaker Bio:
Babak Falsafi is Professor in the School of Computer and Communication Sciences and the founding director of the EcoCloud research center at EPFL. He has worked on server architecture for quite some time and has had contributions to a few industrial platforms including the WildFire/WildCat family of multiprocessors by Sun Microsystems (now Oracle), memory system technologies for IBM BlueGene/P and Q and ARM cores, and server evaluation methodologies in use by AMD, HP and Google (PerfKit). His recent work on scale-out server processor design lays the foundation for Cavium ThunderX. He is a fellow of ACM and IEEE.

Host Faculty: Arkaprava Basu

Video Archive Go Top

 

Series: CSA Distinguished Lecture
Title: Part 2/3: Server architectures: Memory heterogeneity in servers

  • Speaker: Prof. Babak Falsafi
  • Date and Time: Tuesday, July 16, 2019, 3:00 PM
  • Venue: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract
Information technology has undergone a major paradigm shift with sensors, embedded and mobile devices generating massive amounts of data to be augmented with backend cloud services for an enhanced experience. Data has emerged as a currency for modern society. Datacenters are now the backbone of IT offering large-scale cloud services at low costs benefiting from and exploiting the economies of scale. With silicon efficiency scaling having dwindled since 2004 and silicon density scaling slowing down, future digital platforms will rely on heterogeneous logic and memory to allow for IT scalability. Meanwhile, the demand for large-scale cloud services has grown dramatically faster than conventional silicon scaling making IT platform scalability a grand challenge. Future platforms will need hand-in-hand collaboration of application domain experts and platform designers to improve scalability. With many online services being in-memory and the minimum communication latency between the farthest nodes in a 20MW datacenter being microseconds, future server platforms will go through revolutionary changes in architecture to enable seamless aggregation of logic and memory resources across nodes, breaking the conventional system abstraction layers.

In a set of three lectures, I will go over research projects in PARSA @ EPFL that have focused on the impact of the slowdown in silicon scaling on data-centric technologies in servers. These lectures will be divided into three parts: - Logic heterogeneity in servers: This lecture covers proposals for accelerators data management and neural networks. - Memory heterogeneity in servers: This lecture covers proposals for incorporation emerging memory technologies into conventional hierarchies including designs for near-memory accelerators, high-bandwidth DRAM caches, and storage-class memory. - Network-centric server architecture: This lecture covers proposals for hardware/software co-design for memory pooling and micro-scale services.

Speaker Bio:
Babak Falsafi is Professor in the School of Computer and Communication Sciences and the founding director of the EcoCloud research center at EPFL. He has worked on server architecture for quite some time and has had contributions to a few industrial platforms including the WildFire/WildCat family of multiprocessors by Sun Microsystems (now Oracle), memory system technologies for IBM BlueGene/P and Q and ARM cores, and server evaluation methodologies in use by AMD, HP and Google (PerfKit). His recent work on scale-out server processor design lays the foundation for Cavium ThunderX. He is a fellow of ACM and IEEE.

Host Faculty: Arkaprava Basu

Video Archive Go Top

 

 

 

 

 

 

 

 

 

 

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