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: Theory Seminar Series
Title: Beyond trace reconstruction: Population recovery from the deletion channel

  • Speaker: Sandip Sinha
                   Ph.D Student
                   CS Theory Group
                   Columbia University
  • Date and Time: Monday, January 06, 2020, 1:00 PM
  • Venue: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract
Population recovery is the problem of learning an unknown distribution over an unknown set of n-bit strings, given access to independent draws from the distribution that have been independently corrupted according to some noise channel. Recent work has intensively studied such problems both for the bit-flip and erasure noise channels. We initiate the study of population recovery under the deletion channel, in which each bit is independently deleted with some fixed probability and the surviving bits are concatenated and transmitted, in both worst-case and average-case settings of the strings in the support. This is a generalization of trace reconstruction, a challenging problem that has received much recent attention.

For the worst case, we show that for any s = o(log n / log log n), a population of s strings from {0,1}^n can be learned under deletion channel noise using exp(n^{1/2+o(1)}) samples. On the lower bound side, we show that n^{Omega(s)} samples are required to perform population recovery under the deletion channel, for all s <= n^0.49.

For the average case, we give an efficient algorithm for population recovery. The algorithm runs in time poly(n,s,1/eps) and its sample complexity is poly(s, 1/eps, exp(log^{1/3} n)), where eps is the TV distance between the original and output distributions.

This is based on the following joint work with Frank Ban, Xi Chen, Adam Freilich and Rocco Servedio: https://arxiv.org/abs/1904.05532 https://arxiv.org/abs/1907.05964

Speaker Bio:
Bio: Sandip Sinha is a Ph.D student in the CS theory group at Columbia University. He is advised by Profs. Rocco Servedio, Alex Andoni, and Cliff Stein. His primary interest is in computational learning theory, as well as data structures for various problems on strings. He is also interested in sublinear algorithms. Before joining Columbia, he graduated from the Indian Institute of Science (IISc) with a B.S. degree in Mathematics in 2016.

Host Faculty: Dr. Arindam Khan

Video Archive Go Top

 

Series: Department Seminar
Title: Discover[i]: Component-based Parameterized Reasoning for Distributed Applications

  • Speaker: Roopsha Samanta
  • Date and Time: Thursday, December 19, 2019, 11:30 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
This talk begins with an overview of recent and ongoing work in Purdue’s Formal Methods (PurForM) research group. Next, the talk presents our Discover[i] project which seeks to automate reasoning about new classes of distributed applications built on top of verified components. The current focus of this project is on parameterized verification and synthesis of systems that use consensus protocols, such as Paxos, as a building block to provide higher-level functionality. The talk explains the key ingredients of our framework: (1) an abstraction of consensus with a simple atomic primitive, (2) a decidability result and algorithm for parameterized verification of safety properties of systems with such consensus primitives, and (3) an algorithm for parameterized synthesis of coordination for such systems.

Discover[i] is joint work with Nouraldin Jaber, Christopher Wagner, Swen Schewe and Milind Kulkarni.

Speaker Bio:
Roopsha Samanta is an Assistant Professor in the Department of Computer Science at Purdue University. Her research mission is to make it easier for people to build provably reliable programs. To this end, her research focuses on developing algorithms and tools for automated program verification, repair and synthesis, and targets diverse application domains such as concurrent and distributed systems, personalized education, machine learning and cryptography. Roopsha completed her Ph.D. at The University of Texas at Austin in 2013 and was a postdoctoral researcher at the Institute of Science and Technology Austria (IST Austria) from 2014-2016. She is a recipient of an NSF CAREER award.

Host Faculty: Deepak D'Souza

Video Archive Go Top

 

Series: Department Seminar
Title: Lessons Developing Conversational AI Interfaces

  • Speaker: Dr. Mitul Tiwari
                   CTO and Co-Founder, Passage AI
  • Date and Time: Monday, December 16, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
This talk will cover building conversational AI using deep learning technologies and lessons learnt in developing conversational interfaces. The first part of the talk will describe recent advances in deep learning that has led to tremendous progress in natural language processing and is making conversational AI a reality. Conversational AI includes intent classification, sequence labeling, understanding dialogs and context, and coming up with responses to users messages. The second part of the talk will address lessons learned developing conversational interfaces. A conversational interface needs to be personable in addressing, adaptive in understanding, and available with many different supported tasks. Overall, key take aways from the talk will be better understanding of (1) deep learning techniques for natural language processing and (2) interaction patterns for building a good conversational interface.

Speaker Bio:
Mitul Tiwari is the CTO and Co-founder of Passage.AI. His expertise lies in building data-driven products using AI, Machine Learning and big data technologies. Previously he was head of People You May Know and Growth Relevance at LinkedIn, where he led technical innovations in large-scale social recommender systems. Prior to that, he worked at Kosmix (now Walmart Labs) on web-scale document and query categorization, and its applications. He earned his PhD in Computer Science from the University of Texas at Austin and his undergraduate degree from the Indian Institute of Technology, Bombay. He has also co-authored more than twenty publications in top conferences such as KDD, WWW, RecSys, VLDB, SIGIR, CIKM, and SPAA.

Host Faculty: Prof. Vinod Ganapathy

Video Archive Go Top

 

Series: CSA Faculty Colloquium
Title: Cryptography...In Anticipation of Quantum Computer

  • Speaker: Prof. Sanjit Chatterjee
                   Associate Professor
                   Dept. of CSA
                   IISc
  • Date and Time: Friday, December 13, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Does the quantum supremacy has any impact on cryptographic security as practiced today? Will we be prepared enough in case quantum computer becomes a reality in a not-so-distant future?

Painting with a broad brush, the talk will attempt to draw the contours of cryptography in a post-quantum world. We will touch upon the challenges and difficulties of securing our various mundane activities that involve communication over a public channel and the kind of research that have been initiated as part of this broad agenda.

Speaker Bio:
The speaker is a faculty member in the Dept. of CSA, IISc. He pretends that he enjoys thinking about various facets of security including the futility of compulsive rumination on security...cryptographic or otherwise.

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

Video Archive Go Top

 

Series: CSA Distinguished Lecture
Title: Securing a World of Physically Capable Computers

  • Speaker: Bruce Schneier
  • Date and Time: Thursday, December 12, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Computer security is no longer about data; it's about life and property. This change makes an enormous difference, and will shake up our industry in many ways. First, data authentication and integrity will become more important than confidentiality. And second, our largely regulation-free Internet will become a thing of the past. Soon we will no longer have a choice between government regulation and no government regulation. Our choice is between smart government regulation and stupid government regulation. Given this future, it's vital that we look back at what we've learned from past attempts to secure these systems, and forward at what technologies, laws, regulations, economic incentives, and social norms we need to secure them in the future.

Speaker Bio:
Bruce Schneier is an internationally renowned security technologist, called a security guru by the Economist. He is the New York Times best-selling author of 14 books -- including Click Here to Kill Everybody -- as well as hundreds of articles, essays, and academic papers. His influential newsletter Crypto-Gram and blog Schneier on Security are read by over 250,000 people. Schneier is a fellow at the Berkman Klein Center for Internet and Society at Harvard University; a Lecturer in Public Policy at the Harvard Kennedy School; a board member of the Electronic Frontier Foundation, AccessNow, and the Tor Project; and an advisory board member of EPIC and VerifiedVoting.org.

Host Faculty: Prof. Vinod Ganapathy

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defense
Title: Achieving Fairness in the Stochastic Multi-armed Bandit Problem

  • Speaker: Ms. Vishakha Patil
                   M.Tech. (Research) Student
                   Dept. of CSA
                   IISc
  • Faculty Advisor: Prof. Y Narahari
  • Date and Time: Thursday, December 12, 2019, 3:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The classical Stochastic Multi-armed Bandit (MAB) problem provides an abstraction for many real-world decision making problems such as sponsored-search auctions, crowd-sourcing, wireless communication, etc. In this work, we study Fair-MAB, a variant of the MAB problem, where, in addition to the goal of maximizing the sum of expected rewards, the algorithm also has to ensure that each arm is pulled for at least a given fraction of the total number of rounds which imposes an additional fairness constraint on the algorithm. The non-trivial aspect of Fair-MAB arises when the time horizon T is unknown to the algorithm. The treatment of fairness in the MAB problem is either procedural or outcome-based. Procedural notions of fairness require that the decision-making process of the algorithm must satisfy some fairness guarantees. In contrast to this, we consider an outcome-based fairness notion which can be validated based on the outcome of the decisions of the algorithm.

Our primary contribution is characterizing a class of Fair-MAB algorithms by two parameters: the unfairness tolerance and the learning algorithm used as a black-box. We define an appropriate notion of fairness and show that our algorithms guarantee fairness independent of the choice of the learning algorithm. We define the notion of fairness-aware regret which naturally extends the conventional notion of regret, and show that the fairness-aware regret of our algorithm matches in order the regret of the black-box learning algorithm in the absence of fairness constraints. Finally, we show via detailed simulations that our algorithm outperforms the best known algorithm for the Fair-MAB problem, both in terms of the regret and in terms of the fairness guarantee that it provides. We also evaluate the cost of fairness in the MAB setting in terms of the conventional notion of regret.

Video Archive Go Top

 

Series: Department Seminar
Title: Optimistic Hybrid Analysis for System Security and Reliability

  • Speaker: Prof. Satish Narayanasamy
                   University of Michigan, Ann Arbor, USA
  • Date and Time: Wednesday, December 11, 2019, 10:30 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Dynamic analysis tools such as information-flow tracking (DIFT) and data-race detection are useful for enforcing security policies and improving software reliability. But these tools are rarely used in production systems, as it can slow down a program by an order of magnitude. Static whole program analyses can be used to prove safe execution states and elide unnecessary runtime checks, but in practice, they are mostly ineffective for large programs. The reason is that they are greatly hindered by the need to prove their soundness, as soundness requires analysis of all possible executions and sound over-approximations of a program. This talk presents Optimistic Hybrid Analysis (OHA). OHA improves the scalability and precision of whole program static analysis by one to two orders of magnitude by making optimistic assumptions about a program’s properties that are almost always true, but are hard to prove statically. By making these assumptions, we sacrifice soundness of static analysis, but yet, we preserve soundness of dynamic analysis by checking them at runtime and recovering when they fail. OHA has been used to obtain three promising results. It speeds up FastTrack, a well-known dynamic data-race detector by 3.5x; reduces the overhead of DIFT to less than 10%, a 4.4x improvement; enables the first known solution for a sound garbage collector for C/C++ using efficient pointer provenance.

Speaker Bio:
Satish Narayanasamy is an Associate Professor at the University of Michigan. He is also the CEO of Sequal Inc., a precision health startup. His research interests are in parallel computer architecture and program analysis, and more recently, systems for health. His research led to the development of several tools, some of which are now used in practice such as PinPlay at Intel. His research has been recognized through several awards, including an NSF CAREER award, best paper awards at ASPLOS and ISPASS, and four IEEE Micro Top Picks awards. He was a Morris Wellman Faculty Development Professor.

Host Faculty: Arkaprava Basu

Video Archive Go Top

 

Series: Department Seminar
Title: CHET: An Optimizing Compiler for Fully-Homomorphic Neural-Network Inferencing

  • Speaker: Mr. Roshan Dathathri
                   Ph.D. Student
                   Intelligent Software Systems Lab
                   University of Texas
                   Austin
  • Date and Time: Tuesday, December 10, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Fully Homomorphic Encryption (FHE) refers to a set of encryption schemes that allow computations on encrypted data without requiring a secret key. Recent cryptographic advances have pushed FHE into the realm of practical applications. However, programming these applications remains a huge challenge, as it requires cryptographic domain expertise to ensure correctness, security, and performance.

CHET is a domain-specific optimizing compiler designed to make the task of programming FHE applications easier. Motivated by the need to perform neural network inference on encrypted medical and financial data, CHET supports a domain-specific language for specifying tensor circuits. It automates many of the laborious and error prone tasks of encoding such circuits homomorphically, including encryption parameter selection to guarantee security and accuracy of the computation, determining efficient tensor layouts, and performing scheme-specific optimizations.

Our evaluation on a collection of popular neural networks shows that CHET generates homomorphic circuits that outperform expert-tuned circuits and makes it easy to switch across different encryption schemes. We demonstrate its scalability by evaluating it on a version of SqueezeNet, which to the best of our knowledge, is the deepest neural network to be evaluated homomorphically.

Speaker Bio:
Roshan is a Ph.D. student advised by Prof. Keshav Pingali in the University of Texas at Austin. He works on domain-specific programming languages, compilers, and runtime systems that make it easy to develop efficient sparse computation and privacy-preserving computation on large-scale distributed clusters, while utilizing heterogeneous architectures. He has built programming systems for distributed and heterogeneous graph analytics and privacy-preserving neural network inferencing. He received his masters from Indian Institute of Science advised by Prof. Uday Kumar Reddy B, where he worked on automatic parallelization of affine loop nests for distributed and heterogeneous architectures.

Host Faculty: Prof. Uday Kumar Reddy .B

Video Archive Go Top

 

PAST SEMINARS

Series: CSA Golden Jubilee Frontier Lecture Series
Title: A Graph-Theorist's Perspective on the Quest for Dichotomy

  • Speaker: Professor Pavol Hell
                   Professor of Computing Science
                   Simon Fraser University
  • Date and Time: Friday, December 06, 2019, 4:00 PM
  • Venue: Faculty Hall, Indian Institute of Science

Abstract
The celebrated Feder-Vardi Dichotomy Conjecture for Constraint Satisfaction has recently been established by Bulatov and by Zhuk. Because of the profound impact the conjecture had on theoretical computer science, Feder and Vardi were jointly awarded the Alonzo Church Award for 2019. The solution involved a beautiful blend of graph theory, logic, and universal algebra, developed over a period of 25 years; these developments, in turn, impacted all these fields. I will present a personal account of how a graph-theorist perceived the events and developments leading up to the formulation, and the solution, of the conjecture. I will focus on the impact on graph theory, but briefly mention the other fields as well.

Speaker Bio:
Pavol Hell is a Canadian computer scientist, born in Czechoslovakia. He is a professor of computing science at Simon Fraser University. His interests are in algorithmic graph theory and complexity of graph problems. He has over 200 journal and conference publications, and has supervised almost 20 PhD students, and many MSc students, over his career. He is a Fellow of the Society of Industrial and Applied Mathematics, and a Managing Editor of the Journal of Graph Theory.

Host Faculty: Prof. Shalabh Bhatnagar

Video Archive Go Top

 

Series: Ph.D. Thesis Defense
Title: Geometric Search Techniques for Provably Robust Query Processing

  • Speaker: Mr. Srinivas Karthik V
                   Ph.D student
                   Dept. of CSA
  • Faculty Advisor: Prof. Jayant R. Haritsa
  • Date and Time: Friday, December 06, 2019, 3:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Relational Database Management Systems (RDBMS) constitute the backbone of today's information-rich society, providing a congenial environment for handling enterprise data during its entire life cycle of generation, storage, maintenance and processing. The Structured Query Language (SQL) is the de facto standard interface to query the information present in RDBMS based repositories. An extremely attractive feature of SQL is that it is declarative in nature, meaning that the user species only the end objectives, leaving to the system the task of identifying the optimal execution strategy to achieve these objectives.

A crucial input to generating efficient query execution strategies, called "plans", are the statistical estimates of the output data volumes for the algebraic predicates present in the query. However, in practice, these estimates, called "selectivities", are often significantly in error with respect to the actual values subsequently encountered during query execution. These inaccuracies arise due to a variety of reasons including intrinsic database complexities such as data skew and correlations. The unfortunate outcome is a poor choice of execution plan, leading to highly inflated query response times. Therefore, achieving robustness in query execution performance has been a long-standing open problem in the database research community.

The first success in the above quest was achieved five years ago by the PlanBouquet algorithm. The algorithm provide guarantees on Maximum Sub-optimality (MSO), a metric capturing the worst-case execution performance relative to an oracular system that magically knows the correct selectivities. The guarantees are achieved by constructing a carefully calibrated "trial-and-error" sequence of time-budgeted plan executions that lead to run-time selectivity discovery in a space constructed from the error-prone predicates. However, in spite of this breakthrough, PlanBouquet suffers from critical limitations, including: (i) huge compile-time efforts to be amenable for run-time MSO guarantees, (ii) inability to handle queries with a large number of predicates prone to estimation errors, and (iii) performance variability across database platforms.

In this thesis, we address all the above-mentioned issues and take a substantive step forward in delivering practical robust query processing. Specifically, we design a new suite of robust query processing algorithms based on potent geometrical search techniques. We begin with "SpillBound", which provides an MSO guarantee of D^2+3D, where D is the number of predicates prone to estimation errors. This is achieved by incorporating focused allocation of execution time budgets through "spilling", whereby operator pipelines are prematurely terminated at chosen locations in the plan tree. The spilling feature extends PlanBouquet's hypograph pruning of the selectivity space to a much stronger half-space pruning. A collateral benefit is that the guarantee is platform-independent and can be issued simply by query inspection. Further, we also prove a lower bound of D on the guarantee, which shows that SpillBound is within a factor of O(D) of the best deterministic algorithm in its class. Through an optimized variant of SpillBound, called AlignedBound, we achieve the linear lower bound for a restricted set of environments. Finally, when empirically evaluated on contemporary database engines over both synthetic and real-world benchmarks, SpillBound and AlignedBound provide markedly superior robustness as compared to PlanBouquet, with the latter typically achieving single-digit MSO guarantees.

Although providing strong and portable performance guarantees, SpillBound falls prey to the "curse of dimensionality" since the query compilation overheads are exponential in D, and contemporary decision-support queries often possess a high ab initio value for this parameter. We tackle this issue in the second segment of the thesis by proposing a principled and efficient three-stage pipeline, called Dimensionality Reduction, that reduces the effective D to "anorexic" (small absolute number) levels even for highly complex queries. This drastic reduction results in SpillBound becoming practical for canned queries that are repeatedly invoked by the parent application. However, for ad-hoc queries which are issued on the fly, the overheads prove to be still too high. Therefore, in the third segment of the thesis, we investigate the trade-off between compilation overheads and the MSO guarantees. This leads us to a modified version of SpillBound, called FrugalSpillBound, that explicitly leverages the concave-down trajectory typically exhibited by plan cost functions over the selectivity space. From a theoretical perspective, FrugalSpillBound exponentially reduces the compilation overheads for a linear increase in the MSO guarantee. Empirically, we obtain more than three orders of magnitude reduction in exchange for a doubling in MSO.

The above robustness guarantees are welcome for the many real-world query workloads that exhibit error-prone selectivity estimation. However, it is possible that even these workloads may include specific database queries for which the native query optimizer itself is capable of accurate selectivity estimations, and hence efficient plan choices with an MSO close to 1. For such queries, our query processing algorithms would be an overkill, incurring unnecessary performance penalties. Therefore, in the last segment of the thesis, we construct a software "OptAssist" that aids the user, based on a geometric characterization of MSO behavior for the query, in making the choice of whether to use the native optimizer or our robust alternatives.

Overall, in this thesis, we achieve practical performance guarantees for SQL query processing by leveraging a potent set of geometrical search techniques, thereby taking a major step towards making robust query processing a contemporary reality.

Publications based on the thesis:

1) Platform-independent Robust Query Processing, Proc. of 32nd IEEE Intl. Conf. on Data Engineering (ICDE), Helsinki, Finland, May 2016, pgs. 325-336.

2) Robust Query Processing, PhD Workshop, 32nd IEEE Intl. Conf. on Data Engineering (ICDE), Helsinki, Finland, May 2016, pgs. 226-230.

3) A Concave Path to Low-overhead Robust Query Processing, PVLDB Journal, 11(13), September 2018, pgs. 2183-2195.

4) Platform-independent Robust Query Processing, IEEE Trans. on Knowledge and Data Engineering (TKDE), 31(1), January 2019, pgs. 17-31.

Video Archive Go Top

 

Series: Department Seminar
Title: Cyber(-Physical) Systems and Machine Learning: Research Challenges

  • Speaker: Dr. Tilak Agerwala
                   IBM Emeritus and IBM Vice-President, Data Centric Systems (Retired)
                   Dr. S.Radhakrishnan Chair Visiting Professor, NIAS
  • Date and Time: Friday, December 06, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The rapid digital transformation of our world, the exponential improvements in computing, communication, and storage, and the evolution of machine learning are transforming the very nature of scientific discovery and engineering research and making advances in many areas including personalized health care, emergency response, traffic flow management, and electric power generation. These developments have resulted in new complex applications and workflows that require sophisticated cyber and cyber-physical systems that deeply integrate computation, communication, and control into physical systems. After a brief overview of machine learning, I will describe the characteristics of the new applications and the architectures of the required cyber(-physical) systems. The focus will be on the current research challenges in programming, debugging, and managing these systems safely and securely, utilizing machine learning technologies.

Speaker Bio:
Dr. Agerwala’s career has focused on developing advanced research programs and game-changing strategic initiatives and on bringing innovative computing technologies to market. He is an IBM Emeritus, Dr. S. Radhakrishnan Chair Visiting Professor, NIAS, Adjunct Associate Professor, Pace University, New York, and Executive-in-Residence, Grove School of Engineering, New York. In his IBM career, spanning 35 years, Dr. Agerwala held executive positions in research, strategy, advanced development, marketing, and business development. He was part of and led teams that developed and delivered leadership cyberinfrastructure technologies and supercomputers to industry, academia, and the national labs. As vice president, Systems, (2002 to 2013), he was responsible for IBM’s research and advanced technology activities worldwide in future systems hardware and software technologies, including the BlueGene supercomputer. As vice president of Data Centric Systems (2013-2014), his team established a new paradigm for scalable systems leading to the delivery of” Summit,” currently the world's most powerful supercomputer, to Oakridge National Lab.

Host Faculty: Prof. R.C. Hansdah

Video Archive Go Top

 

Series: Theory Seminar Series
Title: Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders

  • Speaker: Dr. Sahil Singla
                   Research Instructor (postdoc)
                   Princeton University
                   USA
  • Date and Time: Wednesday, December 04, 2019, 12:30 PM
  • Venue: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract
A longstanding open problem in Algorithmic Mechanism Design is to design computationally efficient truthful mechanisms for (approximately) maximizing welfare in combinatorial auctions with submodular bidders. The first such mechanism was obtained by Dobzinski, Nisan, and Schapira [STOC’06] who gave an O(log^2 m)-approximation where m is number of items. This problem has been studied extensively since, culminating in an O(sqrt{log m})-approximation mechanism by Dobzinski [STOC’16]. We present a computationally-efficient truthful mechanism with approximation ratio that improves upon the state-of-the-art by an exponential factor. In particular, our mechanism achieves an O((loglog m)^3)-approximation in expectation, uses only O(n) demand queries, and has universal truthfulness guarantee. This settles an open question of Dobzinski on whether Θ(sqrt{log m}) is the best approximation ratio in this setting in negative. This is based on a joint work with Sepehr Assadi and appeared in FOCS 2019.

Speaker Bio:
Sahil Singla is a Research Instructor (postdoc) at Princeton University and the Institute for Advanced Study. Prior to this, he was a graduate student at Carnegie Mellon University where he was advised by Prof Manuel Blum and Prof Anupam Gupta. Broadly, his research interests are in theoretical problems related to the theme `Optimization Under Uncertainty'. More particularly, he has been working on discrete optimization problems using uncertainty models from areas like Online & Approximation Algorithms, Machine Learning Theory, and Algorithmic Game Theory.

Host Faculty: Dr. Arindam Khan

Video Archive Go Top

 

Series: CSA Golden Jubilee Frontier Lecture Series
Title: An Algorithmic View of Smart Living: The Next Frontier

  • Speaker: Professor Sajal K. Das
                   Daniel St. Clair Endowed Chair
                   Department of Computer Science
                   Missouri University of Science and Technology, USA
  • Date and Time: Friday, November 29, 2019, 4:00 PM
  • Venue: Faculty Hall, Indian Institute of Science

Abstract
The advent of wireless sensor networks and Internet of Things (IoTs) are making our lives increasingly dependent on a wide variety of cyber-physical systems (CPS) and smart services (e.g., smart energy, transportation, healthcare, agriculture, etc.), while aiming to improve quality of life. The availability of rich mobile devices like smartphones are also empowering humans to act as sensors to collect fine-grained information via crowd sensing, resulting in actionable inferences and decisions. This talk will first provide a “smart living” vision and highlight the underlying research challenges. Next, it will formulate fundamental problems related to sensor data fusion, coverage and connectivity, mobile charging, security, network lifetime and resource trade-off. Novel solutions will be designed based on randomized and approximation algorithms on graphs, optimization techniques, geometric probability theory, uncertainty reasoning, trust model and game theory. Case studies and experimental results will be presented where possible. The talk will be concluded with emerging applications of sensors and IoTs, followed by directions of future research.

Speaker Bio:
Sajal K. Das, whose academic genealogy includes Thomas Alva Edison, is a Professor of Computer Science and Daniel St. Clair Endowed Chair at the Missouri University of Science and Technology, where he was the Chair of Computer Science Department during 2013-2017. Prior to that, he was a University Distinguished Scholar Professor of Computer Science and Engineering, and founding director of the Center for Research in Wireless Mobility and Networking (CReWMaN) at the University of Texas at Arlington. While serving the NSF as a Program Director during 2008-2011, Dr. Das spear headed a US-India collaboration program. His research interests include wireless sensor networks, mobile and pervasive computing, smart environments, CPS and IoTs, cyber security, distributed and cloud computing, social and biological networks, applied graph theory and game theory. He has contributed significantly to these areas, publishing over 300 journal articles, over 400 peer-reviewed conference papers, and 53 book chapters. A holder of 5 US patents, Dr. Das has directed numerous funded projects and coauthored 4 books: “Smart Environments: Technology, Protocols, and Applications” (John Wiley, 2005); “Handbook on Securing Cyber-Physical Critical Infrastructure: Foundations and Challenges” (Morgan Kaufman, 2012); “Mobile Agents in Distributed Computing and Networking” (Wiley, 2012); and “Principles of Cyber-Physical Systems: An Interdisciplinary Approach” (Cambridge University Press, 2019). His h-index is 83 with more than 29,500 citations according to Google Scholar. He is the founding Editor-in-Chief of Elsevier’s Pervasive and Mobile Computing journal, and an Associate Editor of the IEEE Transactions on Dependable and Secure Computing, IEEE Transactions on Mobile Computing, and ACM Transactions on Sensor Networks. A founder of IEEE PerCom, WoWMoM, SMARTCOMP and ACM ICDCN conferences, Dr. Das has served as General or Technical Program Chair of numerous conferences. He is a recipient of 10 Best Paper Awards in prestigious conferences like ACM MobiCom and IEEE PerCom, and received awards for teaching, mentoring and research including the IEEE Computer Society’s Technical Achievement Award for pioneering contributions to sensor networks, and University of Missouri System President’s Award for Sustained Career Excellence. Dr. Das has mentored 43 PhD dissertations, 32 MS theses, and 10 postdoctoral researchers. He is an IEEE Fellow and currently holding a Satish Dhawan Visiting Chair Professor position at IISc.

Host Faculty: Prof. Shalabh Bhatnagar

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defense
Title: Signcryption in a Quantum World

  • Speaker: Mr. Shravan Kumar Parshuram Puria
                   M.Tech. (Research) Student
                   Dept. of CSA
                   IISc
  • Faculty Advisor: Prof. Sanjit Chatterjee
  • Date and Time: Friday, November 29, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
With recent advancements and research on quantum computers, it is conjectured that in the foreseeable future, sufficiently large quantum computers will be built to break essentially all public key cryptosystems currently in use. As a response, quantum-safe cryptography has recently garnered significant attention. The aim of quantum-safe cryptography is to design cryptosystems that are secure against both classical and quantum computers. This involves identifying computational problems that are believed to be secure against quantum adversaries and building cryptosystems based on such problems. A related problem of interest is arguing security of quantum-safe cryptosystems within the paradigm of provable security. Quantum security models for basic primitives like encryption and signature are gradually evolving and the security of different cryptosystems are being investigated in these models.

Signcryption is a public key primitive that ensures both confidentiality and authenticity of data. Signcryption security can be modeled in different ways depending on whether the adversary can corrupt an insider, i.e., the sender or receiver, or not. The aim of this work is a comprehensive treatment of signcryption against quantum adversaries that are allowed to make oracle queries on quantum superposition of classical input values. We formulate suitable quantum security definitions for confidentiality and authenticity of signcryption both in insider and outsider models. We investigate the quantum security of generic constructions of signcryption schemes based on three paradigms, viz., encrypt-then-sign (EtS), sign-then-encrypt (StE) and commit-then-encrypt-and-sign (CtE&S). We show that the quantum analogues of the classical results hold in the insider model with an exception in the StE paradigm. However, in outsider model we need to consider an intermediate setting in which the adversary is given quantum access to unsigncryption oracle but classical access to signcryption oracle. In two-user outsider model, as in the classical setting, we show that post-quantum CPA security of the base encryption scheme is amplified in the EtS paradigm if the base signature scheme satisfies a stronger notion of security. We prove an analogous result in the StE paradigm. Interestingly, in the multi-user setting, our results strengthen the known classical results.

Our results for the EtS and StE paradigms in the two-user outsider model also extend to the setting of authenticated encryption. We briefly discuss the difficulties in analyzing the full quantum security of signcryption in outsider model. Finally, we briefly discuss about some existing quantum secure encryption and signature proposals which can be used to instantiate signcryption schemes based on the above paradigms.

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defense
Title: Honest Majority and Beyond: Efficient Secure Computation over Small Population

  • Speaker: Ms. Swati Singla
                   M.Tech (Research) Student
                   Dept. of CSA
  • Faculty Advisor: Dr. Arpita Patra
  • Date and Time: Thursday, November 21, 2019, 3:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Secure Multi-Party Computation for small population has witnessed notable practically-efficient works in the setting of both honest majority and dishonest majority. While honest majority provides the promise of stronger security goals of fairness (either all parties get the output or none of them do) and guaranteed output delivery (honest parties always get the output irrespective of adversary’s behaviour), the best that dishonest majority can offer is unanimous abort (either all honest parties get the output or none of them do). In this work, we consider the computation among 4 parties in two different threat models. To avoid clutter and enable ease of understanding, we segregate the work into two parts (one for each threat model). Part I considers the standard honest majority (i.e. 1 corruption) where we provide constant round (low-latency) protocols in a minimal model of pairwise private channels. Improving over the state-of-the-art work of Byali et al. (ACM CCS ’18), we present two instantiations that efficiently achieve: (a) fairness in 3 rounds using 2 garbled circuits (GC) (b) guaranteed output delivery (GOD) in 3 rounds using 4 GCs. Further, improving the efficiency of 2-round 4PC feasibility result of Ishai et al. (CRYPTO ’15) that achieves GOD at the expense of 12 GCs, we achieve GOD in 2 rounds with 8 GCs, thus saving 4 GCs over that of Ishai et al. Under a mild one-time setup, the GC count can further be reduced to 6 which is half of what the prior work attains.

This widely-followed demarcation of the world of MPC into the classes of honest and dishonest majority suffers from a worrisome shortcoming: one class of protocols does not seem to withstand the threat model of the other. Specifically, an honest-majority protocol promising fairness or GOD violates the primary notion of privacy as soon as half (or more) parties are corrupted, while a dishonest-majority protocol does not promise fairness or GOD even against a single corruption, let alone a minority. The promise of the unconventional yet much sought-after brand of MPC, termed as Best-of-Both-Worlds (BoBW), is to offer the best possible security in the same protocol depending on the actual corruption scenario. With this motivation in perspective, part II presents two practically-efficient 4PC protocols in the BoBW model, that achieve: (1) guaranteed output delivery against 1 corruption and unanimous abort against 2 corruptions. (2) fairness against 1 corruption and unanimous abort against arbitrary corruptions. The thresholds are optimal considering the feasibility given in the work of Ishai et al. (CRYPTO ’06) that marks the inauguration of the BoBW setting. We provide elaborate empirical results through implementation that support the theoretical claims made in all our protocols. We emphasize that this work is the first of its kind in providing practically-efficient constructions with implementation in the BoBW model. Also, the quality of constant-rounds makes all protocols in this work suitable for high-latency networks such as the Internet.

Video Archive Go Top

 

Series: CSA Golden Jubilee Frontier Lecture Series
Title: State of Permissionless and Permissioned Blockchains: Myths and Reality

  • Speaker: Dr. C. Mohan
                   IBM Fellow
                   IBM Almaden Research Center, USA
                   and
                   Distinguished Visiting Professor
                   Tsinghua University, China
  • Date and Time: Thursday, November 21, 2019, 2:30 PM
  • Venue: Faculty Hall, Indian Institute of Science

Abstract
It has been a decade since the concept of blockchain was invented as the underlying core data structure of the permissionless or public Bitcoin cryptocurrency network. Since then, several cryptocurrencies, and associated concepts like tokens and ICOs have emerged. After much speculation and hype, significant number of them have become problematic or worthless, even though some countries have embraced them! The permissionless blockchain system Ethereum emerged by generalizing the use of blockchains to manage any kind of asset, be it physical or purely digital, with the introduction of the concept of Smart Contracts. Over the years, numerous myths have developed with respect to the purported utility and the need for permissionless blockchains. The adoption and further adaptation of blockchains and smart contracts for use in the permissioned or private environments is what I consider to be useful and of practical consequence. Hence, the technical aspects of only private blockchain systems will be the focus of my talk. Along the way, I will bust many myths associated with permissionless blockchains. I will also compare traditional database technologies with blockchain systems’ features and identify desirable future research topics. Extensive blockchain related collateral can be found at http://bit.ly/CMbcDB.

Speaker Bio:
Dr. C. Mohan is currently an IBM Fellow at the IBM Almaden Research Center in Silicon Valley and a Distinguished Visiting Professor at Tsinghua University in China. He has been an IBM researcher for 38 years in the database and related areas, impacting numerous IBM and non-IBM products, the research and academic communities, and standards, especially with his invention of the well-known ARIES family of database locking and recovery algorithms, and the Presumed Abort distributed commit protocol. This IBM (1997), ACM (2002) and IEEE (2002) Fellow has also served as the IBM India Chief Scientist (2006-2009). In addition to receiving the ACM SIGMOD Edgar F. Codd Innovations Award (1996), the VLDB 10 Year Best Paper Award (1999) and numerous IBM awards, Mohan was elected to the US and Indian National Academies of Engineering (2009) and named an IBM Master Inventor (1997). This Distinguished Alumnus of IIT Madras (1977) received his PhD at the University of Texas at Austin (1981). He is an inventor of 50 patents. He is currently focused on Blockchain, Big Data and HTAP technologies (http://bit.ly/CMbcDB, http://bit.ly/CMgMDS). For over 2 years, he has been an evangelist for permissioned blockchains and the myth buster of permissionless blockchains. Since 2016, Mohan has been a Distinguished Visiting Professor of China’s prestigious Tsinghua University. He has served on the advisory board of IEEE Spectrum, and on numerous conference and journal boards. Mohan is a frequent speaker in North America, Europe and Asia, and has given talks in 40 countries. He is very active on social media and has a huge network of followers. More information can be found in the Wikipedia page at http://bit.ly/CMwIkP

Host Faculty: Prof. Shalabh Bhatnagar

Video Archive Go Top

 

Series: Department Seminar
Title: Statistical Analysis for Uncertainty Quantification and Visualization of Scientific Data

  • Speaker: Dr. Tushar Athawale
                   University of Utah
  • Date and Time: Monday, November 18, 2019, 2:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Data visualization has become indispensable for efficient interpretation of data generated across diverse scientific domains, such as biomedical imaging and meteorology. Many critical decisions directly rely on the quality of data visualizations. Inaccuracies in visualizations cannot be averted due to uncertainties inherent in underlying data and non-linear transformations of data caused by the stages of visualization pipeline. The uncertainty in the final visualizations can adversely impact the decision-making process. The accurate quantification of uncertainties in data visualizations has, therefore, been recognized as the top research challenge for minimizing risks associated with scientific decisions.

In this talk, I will present my contributions in the field of uncertainty visualization. My main topics of discussion are as follows: 1) Need for uncertainty visualizations, 2) abstract statistical methods for uncertainty quantification, 3) application of uncertainty visualization to level sets, specifically, the study of interaction of the marching cubes algorithm with uncertain data, 4) a few more applications of uncertainty visualization, 5) future work. Our uncertainty visualizations confirm the significance or need for incorporating statistical error analysis into computational models for visualization applications.

Speaker Bio:
Tushar Athawale was a postdoctoral fellow at the University of Utah's Scientific Computing & Imaging (SCI) Institute with Prof. Chris R. Johnson as his advisor since October, 2016. Soon he will join the Oak Ridge National Laboratory located in Tennessee as a Research Scientist. He received PhD in Computer Science from the University of Florida in May, 2015, and he worked with Prof. Alireza Entezari while pursuing his PhD. After his graduation, he worked as an application support engineer in MathWorks, the developer of the leading computing software MATLAB. His primary research interests are in uncertainty quantification and statistical analysis. (personal website: http://tusharathawale.info/home/)

Host Faculty: Prof. Vijay Natarajan

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defense
Title: Practically Efficient Secure Small Party Computation over the Internet

  • Speaker: Ms. Megha Byali
                   M.Tech (Research) Student
                   Dept. of CSA
  • Faculty Advisor: Dr. Arpita Patra
  • Date and Time: Monday, November 18, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Secure Multi-party Computation with small population has drawn focus specifically due to customization in techniques and resulting efficiency that the constructions can offer. Practically efficient constructions have been witnessed in the setting of both honest majority and dishonest majority. In this work, we investigate the efficiency of a wide range of security notions in the small party domain of 5 parties and 4 parties. Being constant-round, our protocols are best suited for real-time, high latency networks such as the Internet. All our constructions are backed with experimental results.

In the setting of five parties with honest majority, we present efficient instantiations with unanimous abort (where either all honest parties obtain the output or none of them do) and fairness (where the adversary obtains its output only if all honest parties also receive it) assuming a minimal setting of pairwise-private channels. With the presence of an additional broadcast channel (known to be necessary), we present a construction with the strongest security of guaranteed output delivery (where any adversarial behaviour cannot prevent the honest parties from receiving the output). The broadcast communication is minimal and independent of circuit size. In terms of performance (communication and run time), our protocols incur minimal overhead over the best known selective abort protocol of Chandran et al. (ACM CCS 2016) while retaining their round complexity. Further, our protocols for fairness and unanimous abort can be extended to n-parties with at most √n corruptions, similar to Chandran et al.

In the setting of four parties, surpassing the traditional model of honest majority, we aim to achieve stronger security goals in a mixed model where minority of the parties are actively corrupt and additionally some parties are passively corrupt, thus giving an overall dishonest majority. In this direction, we present the first efficient constructions that tolerate a mixed adversary corrupting 1 party actively and 1 party passively. Our constructions achieve the security goals of with guaranteed output delivery and fairness in a minimal setting of pairwise private channels and adhere to the feasibility result of Hirt et al. (CRYPTO’13).

Going beyond the most popular honest-majority setting of three parties with one corruption, our results demonstrate feasibility of attaining stronger security notions at an expense not too far from the least desired security of selective abort.

Video Archive Go Top

 

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: Minicrypt Primitives with Algebraic Structure

  • Speaker: Dr. Sikhar Patranabis
                   Research Associate
                   Dept. of CSA
                   IISc
  • Date and Time: Tuesday, October 29, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Algebraic structure lies at the heart of much of Cryptomania as we know it. An interesting question is the following: instead of building (Cryptomania) primitives from concrete assumptions, can we build them from simple Minicrypt primitives endowed with additional algebraic structure? In this work, we affirmatively answer this question by adding algebraic structure to the following Minicrypt primitives: one-way functions, weak unpredictable functions and weak pseudorandom functions. The algebraic structure that we consider is group homomorphism over the input/output spaces of these primitives. We show that these structured primitives can be used to construct several Cryptomania primitives in a generic manner. A few examples of such primitives include hash encryption, hinting PRGs, lossy trapdoor functions and maliciously secure OT/MPC in the plain/CRS model.

Our results make it substantially easier to show the feasibility of building many cryptosystems from novel assumptions in the future. In particular, we show how to realize any CDH/DDH-based protocol with certain properties in a generic manner from input-homomorphic weak unpredictable/pseudorandom functions, and hence, from any concrete assumption that implies the existence of these structured primitives. Our results also allow us to categorize many cryptographic protocols based on which structured Minicrypt primitive implies them. In particular, endowing Minicrypt primitives with increasingly richer algebraic structure allows us to gradually build a wider class of cryptoprimitives. This seemingly provides a hierarchical classification of many Cryptomania primitives based on the "amount" of structure inherently necessary for realizing them.

Speaker Bio:
Sikhar Patranabis received his PhD in Computer Science with a specialization in cryptography from IIT Kharagpur, India. His research interests span all aspects of cryptography, with special focus on cryptographic complexity, encrypted analytics, and the design and implementation of real world cryptographic protocols. Sikhar is currently visiting the CrIS Lab as a research associate, hosted by Dr. Arpita Patra. He will be joining as a postdoctoral researcher in the Applied Cryptography group at ETH Zürich, hosted by Dr. Kenny Paterson. Sikhar was an IBM PhD fellow for the academic sessions 2016-17 and 2017-18. Prior to joining the PhD program, he completed his B.Tech from IIT Kharagpur, where he was the recipient of the President of India gold medal.

Host Faculty: Dr. Arpita Patra

Video Archive Go Top

 

 

 

 

 

 

 

 

 

 

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