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

UPCOMING SEMINARS

Series: Ph.D. Colloquium
Title: Neural Graph Embedding methods for Natural Language Processing

  • Speaker: Mr. Shikhar Vashishth
                   PhD Student
                   Dept. of CSA
  • Faculty Advisor: Dr. Partha Pratim Talukdar & Prof. Chiranjib Bhattacharyya
  • Date and Time: Thursday, October 31, 2019, 3:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Graphs are all around us, ranging from citation and social networks to Knowledge Graphs (KGs). They are one of the most expressive data structures which have been used to model a variety of problems. Knowledge graphs are structured representations of facts in a graph, where nodes represent entities and edges represent relationships between them. Recent research has resulted in the development of several large KGs; examples include DBpedia, YAGO, NELL, and Freebase. However, all of them tend to be sparse with very few facts per entity. For instance, NELL KG consists of only 1.34 facts per entity. In the first part of the thesis, we propose three solutions to alleviate this problem: (1) KG Canonicalization, i.e., identifying and merging duplicate entities in a KG, (2) Relation Extraction which involves automating the process of extracting semantic relationships between entities from unstructured text, and (3) Link prediction which includes inferring missing facts based on the known facts in a KG. For KG Canonicalization, we propose CESI (Canonicalization using Embeddings and Side Information), a novel approach that performs canonicalization over learned embeddings of Open KGs. The method extends recent advances in KG embedding by incorporating relevant NP and relation phrase side information in a principled manner. For relation extraction, we propose RESIDE, a distantly-supervised neural relation extraction method which utilizes additional side information from KGs for improved relation extraction. Finally, for link prediction, we propose InteractE which extends ConvE, a convolutional neural network-based link prediction method, by increasing the number of feature interaction through three key ideas – feature permutation, a novel feature reshaping, and circular convolution. Through extensive experiments on multiple datasets, we demonstrate the effectiveness of our proposed methods.

Traditional Neural Networks like Convolutional Networks and Recurrent Neural Networks are constrained to handle Euclidean data. However, graphs in Natural Language Processing (NLP) are prominent. Recently, Graph Convolutional Networks (GCNs) have been proposed to address this shortcoming and have been successfully applied for several problems. In the second part of the thesis, we utilize GCNs for Document Timestamping problem, which forms an essential component of tasks like document retrieval, and summarization.

For this, we propose NeuralDater which leverages GCNs for jointly exploiting syntactic and temporal graph structures of document for obtaining state-of-the-art performance on the problem. We also propose SynGCN, a flexible Graph Convolution based method for learning word embeddings which utilize dependency context of a word instead of linear context for learning more meaningful word embeddings. In this third part of the thesis, we address two limitations of existing GCN models, i.e., (1) The standard neighborhood aggregation scheme puts no constraints on the number of nodes that can influence the representation of a target node. This leads to a noisy representation of hub-nodes which coves almost the entire graph in a few hops. To address this shortcoming, we propose ConfGCN (Confidence-based GCN) which estimates confidences to determine the importance of a node on another during aggregation, thus restricting its influence neighborhood. (2) Most of the existing GCN models are limited to handle undirected graphs. However, a more general and pervasive class of graphs are relational graphs where each edge has a label and direction associated with it. Existing approaches to handle such graphs suffer from over-parameterization and are restricted to learning representation of nodes only. We propose CompGCN, a novel Graph Convolutional framework which jointly embeds entity and relations in a relational graph. CompGCN is parameter efficient and scales with the number of relations. It leverages a variety of entity-relation composition operations from KG Embedding techniques and achieves demonstrably superior results on node classification, link prediction, and graph classification tasks.

Video Archive Go Top

 

Series: Department Seminar
Title: Recent Progress in Code Obfuscation

  • Speaker: Dr Venkata Koppula,
                   Postdoctoral Research Fellow, Weizmann Institute
  • Date and Time: Friday, October 25, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Code obfuscation has been one of the main focal points of cryptographic research over the last few years. A code obfuscator is a compiler that hides the implementation of programs while preserving functionality. Barak et al showed that the most desirable definition of code obfuscation - virtual black box (VBB) obfuscation - is impossible for general functions. Therefore, we must either restrict our attention to weaker notions of obfuscation, or study obfuscation for restricted classes of functions. In this talk, I will first discuss one such weaker notion of obfuscation (called indistinguishability obfuscation) and its tremendous impact on cryptography.

Next, I will present a VBB obfuscation scheme for a restricted but useful function class. We call this notion `lockable obfuscation'. Our obfuscation scheme's security is based on standard cryptographic assumptions. At the same time, it has a number of applications, for upgrading security of encryption schemes as well as showing separations between different security notions. I will present one such application, followed by a brief discussion of how research related to indistinguishability obfuscation led to this result.

Based on joint work with Rishab Goyal and Brent Waters, and no prior background on obfuscation/crypto will be needed.

Speaker Bio:
Venkata Koppula is a postdoctoral researcher at the Weizmann Institute of Science, hosted by Zvika Brakerski. Prior to this, he was a graduate student at the University of Texas at Austin, where his advisor was Brent Waters. He is interested in the theoretical aspects of cryptography.

Host Faculty: Prof. Matthew Jacob

Video Archive Go Top

 

Series: Department Seminar
Title: Does PD Control Always Work for Robotic Systems?

  • Speaker: Dr Shishir N Y Kolathaya,
                   INSPIRE Faculty Fellow, RBCCPS, IISc
  • Date and Time: Tuesday, October 22, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
In 2015, a committee created by the International Federation of Automatic Control (IFAC) surveyed its members to obtain their views on the impact of advanced control in industries. PID control was first with a 100% high-impact rating, and nonlinear control was tenth with a 22% rating. Clearly, despite great advances in the theory of nonlinear controls,PD and PID tracking control laws continue to be the most popular choice. This is true even for robotic systems. Therefore, the goal of the talk is to understand some of the stability guarantees provided by PD control laws in the context of robotic systems.

The talk is divided into two parts. First, we will discuss existing stability results for PD controlled robotic systems. Some of these results were established as early as the 1980's. Second, we will extend these stability properties to underactuated and hybrid robotic systems i.e., by introducing additional assumptions on the unactuated coordinates of the robot. We will demonstrate these results on bipedal walking robots, which are known to be textbook examples for hybrid robotic systems. Bipedal robots have the leg-swing as the continuous event, and the foot-strike as the discrete event, and these events alternate during walking. In addition, bipeds largely have underactuations due to the interactions between feet and ground. For each continuous event, we establish that the convergence rate of the tracking error can be regulated via appropriate tuning of the PD gains, and for each discrete event, we establish that this convergence rate sufficiently overcomes the nonlinear impacts by assumptions on the hybrid zero dynamics. Towards the end, we will validate these results on a 5-link bipedal walker in simulation.

Speaker Bio:
Shishir is an INSPIRE Faculty fellow in the Robert Bosch Center for Cyber Physical Systems (RBCCPS) in IISc Bangalore. He received his Ph.D. degree in Mechanical Engineering (2016) from the Georgia Institute of Technology, M.S. degree in Electrical Engineering (2012) from Texas A&M University, and B.Tech degree in Electrical & Electronics Engineering (2008) from National Institute of Technology Karnataka. His primary focus as a Ph.D. student was on stability and control of walking robots. Shishir is currently interested in safety-critical control, stability of hybrid systems, and deep reinforcement learning for all kinds of robotic platforms.

Host Faculty: Prof. Matthew Jacob

Video Archive Go Top

 

Series: Department Seminar
Title: Fault-Tolerant Reachability and Strong-connectivity Structures

  • Speaker: Dr Keerti Choudhary
  • Date and Time: Friday, October 18, 2019, 11:00 AM
  • Venue: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract
Reachability and strong-connectivity are some of the fundamental graph problems. In the static setting, both problems can be solved in O(m+n) time for any directed graph G with n vertices and m edges. However, most real-world networks are prone to failures. The failures are transient and occur for a small duration of time. Under such a setting, we would like to preprocess the graph to compute data-structures that can achieve robustness by being functional even after the occurrence of failures. In recent years, researchers have studied various questions pertaining to connectivity, distances, routing, min-cuts, etc. in the domain of fault tolerance networks.

In this talk, I will discuss the following questions: 1. Can we compute a reachability tree in just linear time, after the occurrence of a small number of failures? 2. How fast can we compute the strongly connected components, again on the occurrence of failures? 3. Does there exist a sparse certificate for these structures that remains valid even after a bounded number of failures?

The solutions to these problems employ extremely basic tools like max-flows, min-cuts, and heavy-path-decomposition.

Speaker Bio:
Keerti Choudhary is a postdoctoral fellow in the Computer Science department at Tel Aviv University, where she is hosted by Shiri Chechik. Prior to this, she was a postdoctoral fellow at the Weizmann Institute of Sciences (Oct 2017 - Sept 2019), where her host was David Peleg. Keerti completed her Ph.D. in Computer Science from IIT Kanpur in August 2017, where she was advised by Surender Baswana. She is also a 2013 graduate from the Mathematics department at IIT Kanpur. https://sites.google.com/view/keerti/

Host Faculty: Prof. Matthew Jacob

Video Archive Go Top

 

PAST SEMINARS

Series: CSA Faculty Colloquium
Title: Abstract 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: Static Analysis for Detecting High-Level Races in RTOS Kernels

  • Speaker: Rekha Pai
  • Date and Time: Monday, September 30, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
We propose a static analysis based approach for detecting high-level races in RTOS kernels popularly used in safety-critical embedded software. High-Level races are indicators of atomicity violations and can lead to erroneous software behaviour with serious consequences. Hitherto techniques for detecting high-level races have relied on model- checking approaches, which are inefficient and apriori unsound. In contrast we propose a technique based on static analysis that is both efficient and sound. The technique is based on the notion of disjoint blocks recently introduced in Chopra et al. We evaluate our technique on three popular RTOS kernels and show that it is effective in detecting races, many of them harmful, with a high rate of precision.

This is joint work with Abhishek Singh (IIIT Bangalore), Deepak D'Souza (IISc), and Meenakshi D'Souza (IIIT Bangalore). The work will be presented at the Formal Methods Symposium in Porto, Portugal, next month.

Speaker Bio:
Rekha Pai is a Kothari Post-Doctoral Fellow at the Computer Science and Automation department, IISc, Bangalore. Her interests are in Code Transformation and Static Race Detection.

Host Faculty: Deepak D'Souza

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

 

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

 

 

 

 

 

 

 

 

 

 

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