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: Interpretation -- a framework for verifying correctness of programs

  • Speaker: Prof. K. V. Raghavan
                   Associate Professor
                   Dept. of CSA
                   IISc
  • Date and Time: Friday, October 04, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Abstract interpretation is a technique for static analysis of programs. The objective of any static analysis technique is to identify whether a property of interest holds across all executions of a program without running the program at all. Abstract interpretation has certain unique advantages: (1) It is a framework, in that it can be customized by a user to analyze any property of interest. (2) It is safe, in that it declares a property as holding only if it provably holds in all possible runs of the program. (3) Implementations of it are provided by many tools, for various prevalent programming languages. (4) It is efficient in practice, even on very large programs. In this talk we will explore abstract interpretation by going over some examples involving it, by taking a look at the mathematical theory underlying it, and by looking at its usage in practical settings.

Speaker Bio:
K. V. Raghavan is an Associate Professor at the Department of Computer Science and Automation, Indian Institute of Science, Bangalore. His areas of interest are program analysis and verification, programming tools, and formal methods in software engineering.

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

Video Archive Go Top

 

Series: Department Seminar
Title: Program Synthesis meets Machine Learning

  • Speaker: Sriram Rajamani
  • Date and Time: Friday, September 20, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
We give a tutorial overview of program synthesis, from its first formulation by Church in 1957, through its pragmatic evolution through sketching and programing-by-examples, and compare program synthesis with supervised machine learning. We then present our recent efforts (together with colleagues) in combining program synthesis and machine learning techniques to solve the problem of synthesizing extractors from heterogeneous data, as well as in solving NLP problems. Finally, we explore several opportunities at the intersection of program synthesis (and more broadly the PL community) and machine learning, such as pruning and ranking programs during synthesis, neural program synthesis and automatic differentiation. Towards the end, we will briefly outline plans for a course we are planning with Prof. Deepak D’Souza and Prof. Chiranjib Bhattacharyya in the Jan 2020 semester on this broad topic.

Speaker Bio:
Sriram Rajamani is Distinguished Scientist and Managing Director of Microsoft Research India. His research interests are in designing, building and analyzing computer systems in a principled manner. Over the years he has worked on various topics including Hardware and Software Verification, Type Systems, Language Design, Distributed Systems, Security and Privacy. His current research interest is in combining Program Synthesis and Machine Learning.

Host Faculty: Deepak D'Souza

Video Archive Go Top

 

PAST SEMINARS

Series: Department Seminar
Title: Term modal logic

  • Speaker: Anantha Padmanabha
  • Date and Time: Thursday, September 19, 2019, 12:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Modal logic has been ubiquitously used in many fields of computer science including verification, epistemic logic etc. Typically we have two modal operators "Box" and "Diamond" which in a broad sense refers to "necessity" and "possibility" respectively. For instance, (Box_i alpha) in an epistemic setting means that "Reasoner i knows that alpha". Similarly, (Diamond_i alpha) in the context of a system of processes is interpreted as "Process i can possibly change the system configuration to a state where alpha holds". These reasoners or process index are referred to as agents in general.

Classically, the number of agents is assumed to be fixed and finite. But in many settings like multi-process systems / client-server systems, we cannot fix the agent set beforehand. The active agents change not only from one model to the other but also from one state to the other in the same model. For instance, in multi-process systems, when the system configuration changes, some processes may be terminated and some new ones may be created.

Term modal logic introduced by Fitting et.al is suitable to study such settings, where we can state properties like "exists x Box_x alpha" which means "there exists some process x such that any state update by process x necessarily leads to a state where alpha holds".

In this talk we will look at term modal logic in some detail. This is a joint work with R. Ramanujam

Speaker Bio:
Anantha Padmanabha has recently submitted his PhD thesis in the Institute of Mathematical Sciences, Chennai.

Host Faculty: Deepak D'Souza

Video Archive Go Top

 

Series: Theory Seminar Series
Title: Breaking the $2^n$ Barrier in Secret Sharing

  • Speaker: Professor Vinod Vaikuntanathan
                   Associate Professor at MIT EECS
                   and Co-Founder of Duality Technologies
  • Date and Time: Friday, September 13, 2019, 1:00 PM
  • Venue: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract
Information-theoretic cryptography is full of open problems with a communication-complexity flavor. One such problem arises in the context of secret sharing for general access structures where there is a huge (exponential) gap between the best known upper and lower bounds. We will describe some recent progress on resolving some of these long-standing gaps in the context of secret sharing, CDS and PSM.

Based on work with Tianren Liu and Hoeteck Wee, at Crypto 2017, Eurocrypt 2017 and STOC 2018.

Speaker Bio:
Professor Vinod Vaikuntanathan is an associate professor of computer science at MIT and the chief cryptographer at Duality Technologies. Vinod is the co-inventor of most modern fully homomorphic encryption systems and many other lattice-based (post-quantum secure) cryptographic primitives. His work has been recognized with a George M. Sprowls PhD thesis award (2009), an IBM Josef Raviv Fellowship (2008), a Sloan Faculty Fellowship (2013), a Microsoft Faculty Fellowship (2014), an NSF CAREER Award (2014), a DARPA Young Faculty Award (2018), and a Harold E. Edgerton Faculty Award (2018). He holds SM and PhD degrees from MIT and a BTech degree from the Indian Institute of Technology Madras.

Host Faculty: Dr. Anand Louis

Video Archive Go Top

 

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: M.Tech (Research) Thesis Defense
Title: Optimum Policy Adaptation Learning for uSD cards

  • Speaker: Mr. Abhinav Anand
                   M.Tech (Research)Student
                   Dept. of CSA
  • Faculty Advisor: Prof. Chiranjib Bhattacharyya
  • Date and Time: Thursday, September 05, 2019, 10:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Machine Learning(ML) for Systems is a new and promising research area where performance of computer systems is optimized using machine learning methods. ML for Systems has outperformed traditional heuristics methods in various areas like learning memory access patterns in microarchitecture (Hashemi et. al), generating optimization heuristics using deep learning in compilers (Cummins et. al), avoiding unnecessary writes by efficient SSD caching using machine learning in storage systems (Wang et. al) etc. Systems for ML is another research area which is different from ML for Systems. In Systems for ML, focus is on designing specialized hardware for increasing computing capability for deep learning networks.

In this work, we apply machine learning to improve the performance and reliability of NAND flash based micro-SD(uSD) cards. In present scenario, NAND settings in uSD card are set heuristically to achieve desired performance. However manually tuning these configurations is very hard because of complex interactions between them and changing one can have a large and unexpected effect on another. This is where machine learning in storage systems is useful: manually it may not be possible to optimize thousands of NAND settings in uSD, but it's the type of exercise that machine learning systems excel at. However small storage devices like uSD cards are resource constrained. Therefore using ML algorithms on uSD card with low memory and computation power is in itself a challenge.

In comparison to SSDs, no workload characterization studies has been done for uSD cards. Thus we have no knowledge of existence of new patterns which in turn limits our understanding of policy space. Lot of research has been done to make SSDs firmware adaptive but current uSD firmware is non-adaptive in nature i.e it services all workloads using single policy. Another major issue is that uSD card is constrained on internal RAM and microprocessor, which restricts the use of computationally expensive ML algorithms.

To tackle these problem, we have proposed a machine learning based framework Optimum Policy Adaptation Learning(OPAL) to identify novel patterns and formulate targeted policies. The machine learning model in the controller of NAND flash will identify the incoming workload and map it to optimal policy thus making it adaptive for the incoming workloads. To the best our knowledge we are the first to collect workload data for uSD cards, categorize workloads into patterns, and design a computationally efficient adaptive firmware. Using OPAL we have achieved significant improvements in real world scenarios like 44 % reduction in file copy time and 54 % increase in the lifetime of card.

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defense
Title: Efficient and Secure Search over Encrypted Data

  • Speaker: Mr.Shah Akash Amritlal Rupa
                   M.Tech. (Research) Student
                   Dept. of CSA
                   IISc
  • Faculty Advisor: Prof. Sanjit Chatterjee
  • Date and Time: Friday, August 30, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Due to a variety of crucial benefits, enterprises outsource their data to cloud resident storage. The outsourced data needs to be stored in encrypted form on remote untrusted servers to preserve privacy. However, if the client has to retrieve the entire data and decrypt it in order to get results for a search query then that will defeat the purpose of outsourcing. A solution to this problem is Searchable Encryption that provides a reasonable trade-off between security and efficiency.

Our first contribution is in the context of Dynamic Searchable Symmetric Encryption (DSSE). DSSE schemes, apart from providing support for search operation, allows a client to perform update operations on outsourced database efficiently. Two security properties, viz., forward privacy and backward privacy are desirable from a DSSE scheme. The former captures that the newly updated entries cannot be related to previous search queries and the latter ensures that search queries should not leak matching entries after they have been deleted. These security properties are formalized in terms of the information leakage that can be incurred by the respective constructions. Existing backward private constructions either have a non-optimal communication overhead or they make use of heavy cryptographic primitives. This work makes two contributions: (i) propose alternative formulations of information leakage for backward privacy after revisiting the existing ones [Bost et al. CCS'17], (ii) construct three efficient backward private schemes that aim to achieve practical efficiency by using light weight symmetric cryptographic components only. Our first construction Π_BP-prime achieves a stronger notion of backward privacy whereas our next two constructions Π_BP and Π_WBP achieve optimal communication complexity at the cost of some additional leakage. The prototype implementations of our schemes depict the practicability of the proposed constructions and indicate that the cost of achieving backward privacy over forward privacy is substantially small.

Certain applications require some type of fuzzy searches like wildcard and edit-distance based search over encrypted data. In our second work, we investigate the problem of secure wildcard search over encrypted data in Outsourced Symmetric Private Information Retrieval (OSPIR) setting. The setting comprises of three entities, viz., the data owner, the server and the client. The data owner outsources the encrypted data to the server, who obliviously services the clients' queries. We propose two schemes, viz., Π_BS and Π_OTE to support secure wildcard search over encrypted data. Construction Π_BS reduces the problem of secure wildcard search to that of Boolean search. Π_BS is a sub-linear wildcard search protocol but it allows false positives. Our second construction Π_OTE utilizes Oblivious Transfer Extension protocols to obtain linear time wildcard search protocol with no false positives. Π_BS and Π_OTE can then be combined to obtain an efficient sub-linear solution with no false positives. We provide performance analysis based on our prototype implementation to depict the feasibility of our proposed constructions.

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

 

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

 

 

 

 

 

 

 

 

 

 

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