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: Department Seminar
Title: Two unsolved problems:Birkhoff–von Neumann graphs and PM-compact graphs

  • Speaker: Dr. Nishad Kothari
                   Postdoctoral Researcher
                   Institute of Computing
                   University of Campinas (UNICAMP)
                   Brazil
  • Date and Time: Friday, February 08, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
A well-studied ob ject in combinatorial optimization is the perfect matching polytope of a graph G — the convex hull of the incidence vectors of all perfect matchings of G. In any such investigation, one may assume that G is matching covered — that is, G is a connected graph (on at least two vertices) and each edge of G lies in some perfect matching.

A graph G is Birkhoff–von Neumann if its perfect matching polytope is characterized solely by non-negativity and degree constraints. A result of Balas (1981) implies that G is Birkhoff–von Neumann if and only if G does not contain a pair of vertex-disjoint odd cycles ( C1 , C2) such that G − V( C1) − V( C2) has a perfect matching. It follows immediately that the corresponding decision problem is in co-NP. However, it is not known to be in NP. The problem is in P if the input graph is planar — due to a result of Carvalho, Lucchesi and Murty (2004). More recently, in a joint work with these three authors, we have shown that this problem is equivalent to the seemingly unrelated problem of deciding whether a given graph is ‘prism-free’.

The combinatorial diameter of a polytope is the diameter of its 1-skeleton graph. A graph G is PM-compact if the combinatorial diameter of its perfect matching polytope equals one. A result of Chv´atal (1975) implies that G is PM-compact if and only if G does not contain a pair of vertex-disjoint even cycles ( C1 , C2) such that G − V( C1) − V( C2) has a perfect matching. Once again the corresponding decision problem is in co-NP, but it is not known to be in NP. The problem is in P if the input graph is bipartite or is ‘near-bipartite’ — due to results of Wang, Lin, Carvalho, Lucchesi, Sanjith and Little (2013).

Recently, in a joint work with Marcelo H. de Carvalho, Xiumei Wang and Yixun Lin, we considered the “intersection” of the aforementioned problems. We give a complete characterization of matching covered graphs that are Birkhoff–von Neumann as well as PM-compact. Thus the corresponding decision problem is in P.

I will discuss the two problems, and our recent results mentioned above. The talk will be mostly self-contained. I will assume only basic knowledge of graph theory. I will perhaps not present any lengthy proofs. For more details, see: https://arxiv.org/abs/1807.07339 and https://epubs.siam.org/doi/abs/10.1137/17M1138704.

Speaker Bio:
Nishad Kothari is a postdoctoral researcher at the Institute of Computing, University of Campinas (UNICAMP), Brazil. His research is in structural graph theory and combinatorial optimization --- with a focus on Matching Theory and Pfaffian Orientations. Prior to this, he was a postdoctoral researcher at the Faculty of Mathematics, University of Vienna, Austria. He completed his PhD from the Department of Combinatorics and Optimization at the University of Waterloo (Canada) under the supervision of Joseph Cheriyan and U. S. R. Murty, and before that he completed his Masters degree in Computer Science from Georgia Tech (USA).

Host Faculty: Dr. Anand Louis

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defense
Title: Guarding Terrain using k watchtowers

  • Speaker: Mr. Nitesh Tripathi
                   M.Tech. (Research) Student
                   Dept. of CSA
                   IISc
  • Faculty Advisor: Prof. Sunil L Chandran
  • Date and Time: Tuesday, January 29, 2019, 11:15 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The discrete k-watchtower problem for a polyhedral terrain T in 3D with n vertices is to find k vertical segments, called watchtowers, of smallest height, whose bottom end-points (bases) lie on some vertices of T , and every point of T is visible from the top end-point (tip) of at least one of those watchtowers. In other words, we have to find k watchtowers whose bottom end-points (bases) lie on some vertices of T , such that every point of T is visible from the tip of at least one watchtower and the maximum height among these k watchtowers is minimized. In 1997, Zhu gave an algorithm for this problem when k = 1 with running time O(n log n). In 2010, Agrawal et al. proposed a polynomial time algorithm using parametric search technique for this problem with k = 2. Surprisingly, no result is known for the problem when k > 2. In this thesis, we briefly describe above mentioned algorithmic approaches of Zhu and Agarwal et al. Further, we propose an easy to implement algorithm to solve k-watchtower problem in 3D for a fixed constant k. Our algorithm does not use parametric search and it’s running time is polynomial in n.

Video Archive Go Top

 

Series: Ph.D. Thesis Defense
Title: Problems on bend-number, circular separation dimension and maximum edge 2-colouring

  • Speaker: Mr. Abhiruk Lahiri
                   Ph.D student
                   Dept. of CSA
                   IISc
  • Faculty Advisor: Prof. Sunil L Chandran
  • Date and Time: Tuesday, January 29, 2019, 10:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Representation of graphs as the intersection graphs of geometric objects has a long history. The objective is to a find a collection of “simple” sets S such that a given graph G is its intersection graph. We are interested in two types of intersection representations motivated by VLSI circuit layout problem. In these models, vertices are represented by polygonal paths with alternating horizontal and vertical segments. The measure of the complexity of a path is defined by the number of bends it has. The objective is to minimise the maximum number of bends used by any path in a representation. This minimum number (over all possible representations) is called the bend number of the graph.

In the first model, two vertices share an edge if and only if corresponding paths intersect. A graph that can be represented in such a way is called a VPG graph. We study a subclass of the planar graphs on this model. In the second model, two vertices of the graph share an edge if and only if corresponding paths overlap on a non-zero length segment. A graph that can be represented in such a way is called an EPG graph. We studied Halin graphs which are a subclass of the planar graphs, fully subdivided graphs and minimally 2-connected graphs for this model. Using one of these results, we showed optimization problems such as maximum independent set, minimum dominating set are APX-hard on 1-bend EPG graphs and its subclass which is called L-EPG graphs.

In the second part, we studied the notion of circular separation dimension which was introduced recently by Douglas West. Formally, a pair of non-adjacent edges is said to be separated in a permutation of vertices if the endpoints of the two edges do not alternate in the ordering. The circular separation dimension (CSD) of a graph G is the minimum number of circular orderings of the vertices of G such that every pair of non-adjacent edges is separated in at least one of the orderings. We established a new upper bound for CSD in terms of the chromatic number of the graph. We further studied this question for special graph classes such as series-parallel graph and two-outerplanar graph.

In the final part, we studied maximum edge 2-colouring problem. For a graph G, the maximum edge 2-colouring problem seeks the maximum possible colours that can be used to colour the edges of the graph such that edges incident on a vertex span at most two distinct colours. The problem is well studied in combinatorics, in the context of the anti-Ramsey number. Algorithmically, the problem is known to be NP-hard. It is also known that no polynomial time algorithm can approximate to a factor less than 3/2 assuming the unique games conjecture. The obvious but the only known algorithm issues different colours to the edges of a maximum matching and different colours to remaining connected components. We established an improved approximation bound of 8/5 for the algorithm, for triangle-free graphs with perfect matching.

Video Archive Go Top

 

Series: Department Seminar
Title: Error Correcting Codes for Machine Learning - Low rank approximation and Multilabel classification

  • Speaker: Dr. Shashanka Ubaru
                   Goldstine Postdoctoral Fellow
                   IBM T.J. Watson Research Center
  • Date and Time: Monday, January 28, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
In this talk, we discuss two machine learning applications of error correcting codes. Low rank approximation is an important tool used in many applications of machine learning and signal processing. Recently, randomized sketching algorithms were proposed to effectively construct low rank approximation and obtain approximate singular value decomposition of large matrices. In the first part of the talk, we discuss how matrices formed using error correcting codes can be used to find such low rank approximations and matrix decompositions, and extend the framework to linear least squares regression problems. The theoretical results which establish the desired approximation guarantees will be discussed, along with the numerous benefits of code matrices over other sketching matrices in different computational environments.

In recent years, the multiclass and mutlilabel classification problems we encounter in applications have very large (10^3-10^6) number of classes. However, each instance belongs to only one or few classes, i.e., the label vectors are sparse. In the second part of this talk, we present a novel multilabel classification method based on group testing and codes. The proposed approach has several advantages over existing popular methods, including the error correction capabilities of codes being leveraged for the first time in the learning problem to correct prediction errors.

Speaker Bio:
Shashanka is a Goldstine Postdoctoral Fellow at IBM T.J. Watson Research Center. He completed his Ph.D. in Computer Science at University of Minnesota, USA in summer, 2018. His research interests are in Machine Learning, Numerical Linear Algebra, and Coding Theory Applications. Shashanka is a recipient of the IBM Herman Goldstine Fellowship 2018 and the IEEE ICMLA 2017 Best Paper award.

Host Faculty: Prof. Chiranjib Bhattacharyya

Video Archive Go Top

 

Series: Ph.D. Thesis Defense
Title: Structured Regularization Through Convex Relaxations of Discrete Penalties.

  • Speaker: Raman sankaran
  • Faculty Advisor: Prof. Chiranjib Bhattacharyya
  • Date and Time: Monday, January 21, 2019, 3:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Motivation.



Empirical risk minimization(ERM) is a popular framework for learning predictive models from data, which has been used in various domains such as computer vision, text processing, bioinformatics, neuro-biology, temporal point processes, to name a few. We consider the cases where one has apriori information regarding the model structure, the simplest one being the sparsity of the model. The desired sparsity structure can be imputed into ERM problems using a regularizer, which is typically a norm on the model vector. Popular choices of the regularizers include the $ell_1$ norm (LASSO) which encourages sparse solutions, block-$ell_1$ which encourages block level sparsity, among many others which induce more complicated structures. To impute the structural prior, recently, many studies have considered combinatorial functions on the model's support to be the regularizer. But this leads to an NP-hard problem, which thus motivates us to consider convex relaxations of the corresponding combinatorial functions, which are tractable.



Existing work and research gaps.



The convex relaxations of combinatorial functions have been studied recently in the context of structured sparsity, but they still lead to inefficient computational procedures in general cases: e.g., even when the combinatorial function is submodular, whose convex relaxations are well studied and easier to work with than the general ones, the resulting problem is computationally expensive (the proximal operator takes $O(d^6)$ time for $d$ variables). Hence, the associated high expenses have limited the research interest towards these these regularizers, despite the submodular functions which generate them are expressive enough to encourage many of the structures such as those mentioned before.

Hence it remains open to design efficient optimization procedures to work with the submodular penalties, and with combinatorial penalties in general. It is also desirable that the optimization algorithms designed to be applicable across the possible choices of the loss functions arising from various applications. We identify four such problems from these existing research gaps, and address them through the contributions which are listed below. We provide the list of publications related to this thesis following this abstract.



Contributions.



First, we propose a novel kernel learning technique termed as textbf{Variable sparsity kernel learning} (VSKL) for support vector machines (SVM), which are applicable when there is an apriori information regarding the grouping among the kernels. In such cases, we propose a novel mixed-norm regularizer, which encourages sparse selection of the kernels within a group while selecting all groups. This regularizer can also be viewed as the convex relaxation of a specific discrete penalty on the model's support. The resulting non-smooth optimization problem is difficult, where off-the-shelf techniques are not applicable. We propose a mirror descent based optimization algorithm to solve this problem, which has a guaranteed convergence rate of $O(1/sqrt{T})$ over $T$ iterations. We demonstrate the efficiency of the proposed algorithm in various scaling experiments, and applicability of the regularizer in an object recognition task.



Second, we introduce a family of regularizers termed as textbf{Smoothed Ordered Weighted L1 (SOWL) norms}, which are derived as the convex relaxation of non-decreasing cardinality-based submodular penalties, which form an important special class of the general discrete penalties. Considering linear regression, where the presence of correlated predictors cause the traditional regularizers such as Lasso to fail recovering the true support, SOWL has the property of selecting the correlated predictors as groups. While Ordered Weighted $ell_1$ (OWL) norms address similar use cases, they are biased to promote undesirable piece-wise constant solutions, which SOWL does not have. SOWL is also shown equivalent to group-lasso, but without specifying the groups explicitly. We develop efficient proximal operators for SOWL, and illustrate its computational and theoretical benefits through various simulations.



Third, we discuss textbf{Hawkes-OWL}, an application of OWL regularizers for the setting of multidimensional Hawkes processes. Hawkes process is a multi-dimensional point process (collection of multiple event streams) with self and mutual influences between the event streams. While the popular $ell_1$ regularizer fails to recover the true models in the presence of strongly correlated event streams, OWL regularization address this issue and groups the correlated predictors. This is the first instance in the literature, where OWL norms, which predominantly have been studied with respect to simple loss functions such as the squared loss, are extended to the Hawkes process with similar theoretical and computational guarantees.



In the fourth part, we discuss generic first-order algorithms for learning with textbf{Subquadraic norms}, a special sub-family of convex relaxations of submodular penalties. We consider subquadratic norms regularization in a very general setting, covering all loss functions, and propose different reformulations of the original problem. The reformulations enable us to propose two different primal-dual algorithms, CP-$eta$ and ADMM-$eta$, both of which having a guaranteed convergence rate of $O(1/T)$. This study thus provides the first ever algorithms with efficient convergence rates for learning with subquadratic norms.

Video Archive Go Top

 

PAST SEMINARS

Series: Department Seminar
Title: Computing, Freedom and Privacy

  • Speaker: Richard M Stallman
                   Free Software Foundation
  • Date and Time: Saturday, January 19, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Digital technology is developing in a way that increasingly controls and snoops on people. It denies freedom, within our computers and in the internet. What are the threats? What must we demand, for the sake of freedom and privacy. What must we change?

Host Faculty: Prof. K Gopinath

Video Archive Go Top

 

Series: Department Seminar
Title: μSuite & μTune: Auto-Tuned Threading for OLDI Microservices

  • Speaker: Akshitha Sriraman
                   Ph.D. Candidate
                   University of Michigan, Ann Arbor
  • Date and Time: Friday, January 18, 2019, 2:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Modern On-Line Data Intensive (OLDI) applications have evolved from monolithic systems to instead comprise numerous, distributed microservices interacting via Remote Procedure Calls (RPCs). Microservices face sub-ms RPC latency goals, much tighter than their monolithic ancestors that must meet >= lOOms latency targets. Sub- ms-scale threading and concurrency design effects as well as 05 and network overheads that were once insignificant for such monoliths, can now come to dominate in the sub- ms-scale microservice regime. It is therefore vital to characterize the influence of threading design, 05, and network effects on microservices. Unfortunately, widely used academic data center benchmark suites are unsuitable to aid this characterization as they use monolithic rather than microservice architectures.

We first investigate how OS/network overheads impact microservice tai| latency by developing a complete suite of microservices called, uSuite that we use to facilitate our study. Our characterization reveals that the relationship between optimal OS/network parameters and service load are complex. Our primary finding is that non- optimal OS scheduler decisions can degrade microservice tai| latency by up to ~ 87%.

Secondly, we investigate how threading design critically impacts microservice tai| latency by developing a taxonomy of threading models -- a structured understanding of the implications of how microservices manage concurrency and interact with RPC interfaces under wide-ranging loads. We develop, uTune, a system that has two features: (1) a novel framework that abstracts threading model implementation from the application code, and (2) a novel automatic load adaptation system that curtails microservice tai| latency by exploiting inherent latency trade-offs revealed in our taxonomy to transition among threading models. We study, uTune in the context of, uSuite to demonstrate up to 1.9x tai| latency improvements over static threading choices and state-of-the-art adaptation techniques.

Speaker Bio:
Akshitha is a fourth-year Ph.D. student at the University of Michigan, where she is advised by Dr. Thomas F. Wenisch. Her primary research interests are in software systems and computer architecture. Her research focuses on developing software and hardware optimizations to improve the performance of large-scale distributed data center systems."

Host Faculty: Arkaprava Basu

Video Archive Go Top

 

Series: CSA Distinguished Lecture
Title: Reading News with Maps by Exploiting Spatial Synonyms

  • Speaker: Prof. Hanan Samet
                   Distinguished University Professor
                   University of Maryland
                   College Park
                   USA
  • Date and Time: Thursday, January 17, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
NewsStand is an example application of a general framework to enable people to search for information using a map query interface, where the information results from monitoring the output of over 10,000 RSS news sources and is available for retrieval within minutes of publication. The advantage of doing so is that a map, coupled with an ability to vary the zoom level at which it is viewed, provides an inherent granularity to the search process that facilitates an approximate search. This distinguishes it from today's prevalent keyword-based conventional search methods that provide a very limited facility for approximate searches and which are realized primarily by permitting a match via the use of a subset of the keywords. However, it is often the case that users do not have a firm grasp of which keyword to use, and thus would welcome the search to also take synonyms into account. For queries to spatially-referenced data, the map query interface is a step in this direction as the act of pointing at a location (e.g., by the appropriate positioning of a pointing device) and making the interpretation of the precision of this positioning specification dependent on the zoom level is equivalent to permitting the use of spatial synonyms (i.e., letting spatial proximity play a role rather than only seeking an exact match of a query string). Of course, this is all predicated on the use of a textual specification of locations rather than a geometric one, which means that one must deal with the potential for ambiguity.

The issues that arise in the design of a system like NewsStand, including the identification of words that correspond to geographic locations, are discussed, and examples are provided of its utility. More details can be found in the video at http://vimeo.com/106352925 which accompanies the ``cover article'' of the October 2014 issue of the Communications of the ACM about NewsStand which can be found at http://tinyurl.com/newsstand-cacm or a cached version can be found at http://www.cs.umd.edu/~hjs/pubs/cacm-newsstand.pdf.

Speaker Bio:
Hanan Samet (http://www.cs.umd.edu/~hjs/) is a Distinguished University Professor of Computer Science at the University of Maryland, College Park and is a member of the Institute for Computer Studies. He is also a member of the Computer Vision Laboratory at the Center for Automation Research where he leads a number of research projects on the use of hierarchical data structures for database applications, geographic information systems (GIS), computer graphics, computer vision, image processing, games, robotics, search, and textual representations of location as in the NewsStand (http://newsstand.umiacs.umd.edu) and TwitterStand (http://twitterstand.umiacs.umd.edu) which enable accessing a database of news articles and tweets using a map query interface.

Host Faculty: Prof. Jayant R Haritsa

Video Archive Go Top

 

Series: Department Seminar
Title: Learning Linear Temporal Properties

  • Speaker: Daniel Neider
  • Date and Time: Thursday, January 17, 2019, 2:30 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Making sense of the observed behavior of complex systems is an important problem in practice. It arises, for instance, in debugging (especially in the context of distributed systems), reverse engineering (e.g., of malware and viruses), specification mining for formal verification, and the modernization of legacy systems to name but a few examples.

To help engineers understand the dynamic (i.e., temporal) behavior of complex systems, we develop algorithms to learn linear temporal properties from data. More precisely, the problem we address in this talk is the following: given two disjoint, finite sets of (potentially infinite) words, representing positive and negative examples, construct a (minimal) formula in Linear Temporal Logic such that all positive examples satisfy the formula, while all negative examples do not. In order to improve on the readability of the resulting formulas and to give a better "intuitive" explanation of the observed data, our learning algorithms are designed to learn minimal formulas, or at least formulas with a "simple" structure. We also discuss open problems in this area as well as interesting directions for future work.

Speaker Bio:
Daniel Neider is a research group leader at the Max Planck Institute for Software Systems in Kaiserslautern, Germany. His research interests are broadly in the intersection of machine learning and formal methods, with an emphasis on learning-based verification and synthesis of complex systems.

Host Faculty: Deepak D'Souza

Video Archive Go Top

 

Series: Department Seminar
Title: Some closure results for polynomial factorization and applications

  • Speaker: Dr Mrinal Kumar,
                   Postdoctoral Fellow, University of Toronto
  • Date and Time: Thursday, January 17, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
In a sequence of seminal results in the 80's, Kaltofen showed that if an n-variate polynomial of degree poly(n) can be computed by an arithmetic circuit of size poly(n), then each of its factors can also be computed an arithmetic circuit of size poly(n). In other words, the complexity class VP (the algebraic analog of P) of polynomials, is closed under taking factors.

A fundamental question in this line of research, which has largely remained open is to understand if other natural classes of multivariate polynomials, for instance, arithmetic formulas, algebraic branching programs, constant depth arithmetic circuits or the complexity class VNP (the algebraic analog of NP) of polynomials, are closed under taking factors. In addition to being

fundamental questions on their own, such 'closure results' for polynomial factorization play a

crucial role in the understanding of hardness randomness tradeoffs for algebraic computation.

I will talk about the following two results, whose study was motivated by these questions.

1. The class VNP is closed under taking factors. This proves a conjecture of B{"u}rgisser.

2. All factors of degree at most poly(log n) of polynomials with constant depth circuits of size poly(n) have constant (a slightly larger constant) depth arithmetic circuits of size poly(n). This partially answers a question of Shpilka and Yehudayoff and has applications to hardness-randomness tradeoffs for constant depth arithmetic circuits.

Based on joint work with Chi-Ning Chou and Noam Solomon.

Speaker Bio:
Mrinal Kumar is a postdoctoral fellow in the theory of computation group at the University of Toronto, Canada, where his host is Benjamin Rossman. Prior to this, he was a Research Fellow in the program on Lower Bounds in Computational Complexity at the Simons Institute in Berkeley (Aug-Dec 2018), and a postdoctoral fellow in the program on Combinatorics and Complexity at the Center for Mathematical Sciences & Applications at Harvard (June 2017-June 2018). Mrinal completed his PhD in Computer Science from Rutgers University in May 2017, where he was jointly advised by Swastik Kopparty and Shubhangi Saraf.

Host Faculty: Prof. Matthew Jacob

Video Archive Go Top

 

Series: CSA Faculty Colloquium
Title: Tour de Crypto

  • Speaker: Dr. Bhavana Kanukurthi
                   Assistant Professor
                   Dept. of CSA
  • Date and Time: Friday, January 11, 2019, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
In this talk, I'll walk the audience through the history of cryptography. In the process, I'll present a few simple ideas which I think best capture the essence of this fascinating field. I'll finally give a brief survey of the research themes that we are currently exploring in our research group. The talk will be suitable for a general CS audience. No prior knowledge of crypto (or, for that matter, any aspect of theoretical computer science) will be assumed.

Speaker Bio:
Bhavana Kanukurthi is an Assistant Professor at the Department of Computer Science and Automation, Indian Institute of Science. Prior to that, she was a post-doctoral researcher at University of California, Los Angeles. She conducted her doctoral research in Computer Science at Boston University during which period she received the Computer Science Department's "Research Excellence Award". Bhavana works in the area of Cryptography and has published at venues such as Journal of the ACM, IEEE Transactions of Information Theory, STOC, Crypto and Eurocrypt. Her recent paper on "Non-malleable Codes", published at the Theory of Cryptography Conference, was invited to the Journal of Cryptology.

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

Video Archive Go Top

 

Series: Department Seminar
Title: ABR Streaming of CBR and VBR-encoded Videos: Characterization, Challenges, and Solutions*

  • Speaker: Professor Krishna R. Pattipati
                   BoT Distinguished Professor and UTC Chair Professor of Systems Engineering
                   Department of Electrical and Computer Engineering
                   University of Connecticut (UCONN)
  • Date and Time: Wednesday, January 09, 2019, 12:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Adaptive bitrate (ABR) streaming has become the de facto technology for video streaming over the Internet. Despite a flurry of techniques, achieving high quality ABR streaming in dynamic network environments remains a significant technical challenge. ABR streaming can be naturally modeled as a feedback control problem. In the first part of the talk, we take a fresh look at PID-based control for ABR streaming and design a framework called PIA (PID-control based ABR streaming) that strategically leverages PID control concepts and incorporates several novel strategies to account for the various requirements of ABR streaming. PIA is designed and evaluated primarily in the context of Constant Bitrate (CBR) encodings, which encodes the entire video at a relatively fixed bitrate. Recently, commercial services have begun adopting Variable Bitrate (VBR) encodings, spurred by the promise of substantial improvements in the quality-to-bits ratio compared to CBR, and by the technological advancements in VBR encoding pipelines. However, VBR introduces new challenges for ABR streaming, whose nature and implications are little understood. In the second part of the talk, we explore these challenges across diverse video genres, encoding technologies, and platforms. We identify the distinguishing characteristics of VBR encodings that impact user QoE (Quality of Experience) and that should be factored in any ABR adaptation decisions. We develop novel best practice design principles to guide ABR rate adaptation for VBR encodings. As a proof of concept, we design a novel and practical control theoretic rate adaptation scheme, CAVA (Control-theoretic Adaption for VBR-based ABR streaming), incorporating these concepts.

Speaker Bio:
Krishna R. Pattipati is the Board of Trustees Distinguished Professor and the UTC Chair Professor of Systems Engineering in the department of Electrical and Computer Engineering at the University of Connecticut, Storrs, CT, USA. Prof. Pattipati’s research activities are in the areas of proactive decision support, autonomy, and optimization-based learning and inference. A common theme among these applications is that they are characterized by a great deal of uncertainty, complexity, and computational intractability. Prof. Pattipati received the Centennial Key to the Future award in 1984 from the IEEE Systems, Man and Cybernetics (SMC) Society, and was elected a Fellow of the IEEE in 1995 for his contributions to discrete-optimization algorithms for large-scale systems and team decision-making. He received the Andrew P. Sage award for the Best SMC Transactions Paper for 1999, Barry Carlton award for the Best Aerospace and Electronic Systems (AES) Transactions Paper for 2000, the 2002 and 2008 NASA Space Act Awards, the 2003 AAUP Research Excellence Award and the 2005 School of Engineering Teaching Excellence Award at the University of Connecticut. *Joint work with Prof. Bing Wang, Yanyuan Qin and Chaoqun Yue of CSE (UCONN), Drs. Shuai Hao and Subhabrata Sen of AT&T and Prof. Feng Qian of the University of Minnesota.

Host Faculty: Professor Y Narahari

Video Archive Go Top

 

Series: Department Seminar
Title: City-Scale Low-Power Wireless Internet

  • Speaker: Prof. Swarun Kumar
                   Assistant professor
                   Carnegie Mellon University (CMU), USA
  • Date and Time: Monday, January 07, 2019, 2:30 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
This talk presents the challenges and opportunities of building a city-scale low-power wireless internet-of-things. We build upon low-power wide-area networking (LP-WAN), a technology that enables low-cost devices with a 10-year battery to communicate at few kbps to a base station, kilometers away. Yet, deploying LPWANs in large urban environments is challenging, given the power limits of the clients and attenuation from buildings that limits signal range. I present Charm [IPSN'18 best paper] that shows how teams of LP-WAN base stations can collaborate to decode signals from extremely far away clients even if their signals are undetectable at any single base station. I also present PushID [NSDI'19] that shows how LP-WANs at shorter ranges can eliminate the need for a battery altogether. Beyond communication, I also touch upon the opportunities of an omnipresent low-power Internet. I present WiSh [MobiSys'18] that makes everyday surfaces around us shape-aware and connected to the Internet.

Speaker Bio:
Prof. Swarun Kumar is an assistant professor at CMU where heads the laboratory for emerging wireless technologies (WiTech lab). He designs and builds novel systems that leverage a deep understanding of the wireless physical layer to enable faster wireless networks and new services. Swarun is a recipient of the Google Faculty Research award, several best paper awards and the George Sprowls Award for best Ph.D. thesis in Computer Science at MIT.

Host Faculty: Arkaprava Basu

Video Archive Go Top

 

Series: Department Seminar
Title: Harnessing Concurrency in Multicore Systems

  • Speaker: Neeraj Mittal
  • Date and Time: Monday, January 07, 2019, 2:00 PM
  • Venue: CSA Faculty Room, (Room No. 101, Ground floor)

Abstract
Until fifteen years ago, general-purpose processor manufacturers were able to achieve regular improvements in CPU performance by using traditional approaches such as increasing the clock speed of the CPU, increasing the length of the instruction pipeline or increasing the size of the cache and/or the number of cache levels. These steady improvements in CPU performance, and to a lesser extent in memory and disk performances, enabled building of ever-faster mainstream computer systems. As a result, most classes of software applications enjoyed regular (and free) performance gains for several decades without even releasing new versions or doing anything special. Many of the traditional approaches for boosting CPU performance have now hit a Brick Wall, a term often used to describe the inherent physical limitations faced by hardware designers in boosting CPU performance further. The transistor count, which is the number of transistors in an integrated circuit chip, continues to increase as per the Moore's Law. To make use of these large number of additional transistors available on a chip and due to traditional approaches offering only limited gains, major general-purpose processor manufacturers (Intel, AMD and PowerPC) have turned to hyper-threading and multi-core architectures to improve hardware performance. A consequence of this trend is that the free ride that software programs have enjoyed for around four decades is finally over, and most current software applications will not benefit from this enormous parallel processing power offered by a modern computing device unless they are rewritten in a way that enables a program to distribute its tasks across several cores. Even a program written for a multi-core system may fail to scale well with the number of cores if poorly designed and coded.

Even though concurrency has been around for many decades, writing a concurrent program that runs correctly on a multi-core system is still known to be very hard, let alone writing a concurrent program that scales well with the number of cores. Not surprisingly, concurrent programming is largely the skill set of elite programmers often with doctoral degree in concurrent computing or related area. In this talk, I will present the current research on designing a high-performance concurrent program suitable for a multi-core system.

Speaker Bio:
Neeraj Mittal received his B.Tech. degree in Computer Science and Engineering from the Indian Institute of Technology, Delhi in 1995 and M.S. and Ph.D. degrees in Computer Science from the University of Texas at Austin in 1997 and 2002, respectively. He has been a faculty in the Department of Computer Science at the University of Texas at Dallas and a co-director of the Advanced Networking and Dependable Systems Laboratory (ANDES) since 2002. His research interests include multi-core computing, distributed computing, distributed algorithms for wireless networking and security.

Host Faculty: Deepak D'Souza

Video Archive Go Top

 

Series: Department Seminar
Title: Problem of Induction: East and West

  • Speaker: Prof. Kisor Kumar Chakrabarti
                   President
                   Institute for Cross Cultural Studies and Academic Exchange
                   NC, USA
  • Date and Time: Friday, January 04, 2019, 4:00 PM
  • Venue: CSA Faculty Room, (Room No. 101, Ground floor)

Abstract
Hume argued that any induction presupposes uniformity of nature that itself is an induction and hence induction is circular. More recently Goodman has argued that the same inductive evidence yields conflicting predictions. I shall try to show that various contemporary attempts to solve these problems are unsatisfactory. I shall also try to show that these problems were anticipated in Indian philosophies and that a Nyaya solution has more promise.

Speaker Bio:
Kisor Kumar Chakrabarti is a former Distinguished Professor of Philosophy and Religious Studies of the Davis and Elkins College (where he has served as the Vice President of Academic Affairs), the Bethany College, the Ferrum College, etc. He has also taught at the University of California at Berkeley, the University of Maine at Orono and the University of Calcutta. He has held Fellowships at the University of Oxford, Institute for Advanced Study, Princeton, the Indian Institute for Advanced Study, Shimla, the University of Pittsburgh and the Australian National University and received numerous honors and awards. He is fluent in Sanskrit, studied for decades original Sanskrit works of Indian Philosophical Schools under the guidance of eminent pundits and is a leading authority on Indian and comparative philosophy and religion. He is also devoted to the study of Greek philosophy from original Greek sources and has taught modern and contemporary philosophy in India and the USA for more than forty years and published substantially on all these areas. He has published eighty eight research papers and articles mainly dealing with topics of comparative logic, epistemology, metaphysics and ethics. He has also authored The Logic of Gotama (University of Hawaii Press, 1978), Definition and Induction (University of Hawaii Press, 1995), Classical Indian Philosophy of Mind (State University of New York Press, 1999) and Classical Indian Philosophy of Induction (Rowman and Littlefield, 2010).

Host Faculty: Prof. K Gopinath

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defense
Title: Optimizing Dense Matrix Computations with PolyMage

  • Speaker: Ms. Kumudha K N
  • Faculty Advisor: Prof. Uday Kumar Reddy and Prof. Deepak D'Souza
  • Date and Time: Thursday, January 03, 2019, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Linear algebra computations and other arbitrary affine accesses are ubiquitous in appli- cations from domains like scientific computing, digital signal processing (DSP), and deep neural networks. Libraries such as OpenBLAS, MKL, and FFTW provide efficient hand- optimized implementations for matrix and vector primitives used in these domains for various architectures. Applications are then built upon these standard library routines to obtain high performance. These libraries do not perform well for all matrix sizes and obtain sub-optimal performance for small matrices. The interface of these libraries can also be fairly complex requiring several input parameters. Thus, an even higher level of abstraction is often desired to improve productivity. Further, by using these libraries the opportunity to optimize across different library calls is lost and traditional programming to exploit this locality using library functions becomes complex. The work in this thesis proposes (i) a tile size selection model which works for any arbitrary affine access and eschews auto-tuning, (ii) a simple heuristic to determine prof- itability of library call mapping and falling back to generated code otherwise, (iii) an intra- tile optimization technique to expose inner-loop parallelism thus enabling general purpose compiler’s vectorizer to generate vector instructions, (iv) a DSL approach with high level primitives and functions to allow expressing computations efficiently. The optimizations proposed are implemented in the PolyMage DSL. PolyMage is a do- main specific language (DSL) originally designed for image processing pipelines. Its opti- mizer is able to perform optimizations like fusion, tiling, and loop optimizations for image processing pipelines. Firstly, PolyMage language specification is extended to support addi- tional functions and primitives for linear algebra and perform domain inference automat- ically. Second, PolyMage compilers fusion and tile size selection heuristics are extended to work with arbitrary affine accesses. It is thus able to optimize computations from addi- tional domains including dense linear algebra and certain DSP computations. The heuristic to map matrix operations to suitable optimized library implementations are incorporated with the help of an idiom recognition algorithm. The thesis finally experimentally evaluates these optimizations on modern multicore systems using representative benchmarks from PolyBench, digital signal processing and image processing. The results are compared to state-of-the-art optimization approaches and frameworks in each domain. Experiments on DSP benchmarks show that our optimiza- tions has a mean speed up of 7.7× over existing PolyMage optimizer, 5.1× over numpy and 1.9× over MATLAB toolboxes with parallel computing support. Linear algebra computa- tions from PolyBench benchmark suite obtains a speedup of 21.7× over existing PolyMage optimizer, 3.6× over Pluto and 4.1× over PPCG.

Video Archive Go Top

 

Series: CSA Distinguished Lecture
Title: Lectures on Brain and Computation

  • Speaker: Prof. Christos Papadimitriou
                   Donoval Family Professor of Computer Science
                   Columbia University
  • Date and Time: Wednesday, December 26, 2018, 3:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Despite a deluge of exciting results in experimental and theoretical neuroscience over the past decades, some of the top researchers in the area agree that progress has been slow on the field’s overarching question: How does the Brain (molecules, neurons, synapses) give rise to the Mind (cognition, behavior, learning, thought)? This is arguably one of the hardest and most fundamental challenges in science today. Many expect that computation will be an important workhorse, conceptual framework, and metaphor of this epic interdisciplinary scientific effort. On another front, advances in machine learning have often been inspired by the Brain, albeit in a pointedly tentative way.

The purpose of this series of three lectures is to give the participants some of the necessary background for appreciating this fascinating interface between computation and neuroscience, and for making progress in it.



Note: Three lectures will be held starting from 26/12/2018, 27/12/2018, and 28/12/2018

Speaker Bio:
Christos H. Papadimitriou is the Donoval Family Professor of Computer Science at Columbia University. Before joining Columbia this year, he taught at Harvard, MIT, NTU Athens, Stanford, UCSD, and at Berkeley since 1995. He has written many books and articles on the theory of algorithms and complexity, and its applications to optimization, databases, control, AI, robotics, economics and game theory, the Internet, evolution, and the brain. He holds a Phd from Princeton, and honorary doctorates from nine universities. He is a member of the National Academy of Sciences of the US, the American Academy of Arts and Sciences, and the National Academy of Engineering, and is a recipient of the Knuth prize, the Gödel prize, the Kalai prize for CS in Game Theory, the EATCS award, and the von Neumann medal. He has also written three novels: "Turing," " Logicomix," and his latest "Independence" (2017).

Host Faculty: Dr. Siddharth Barman

Video Archive Go Top

 

Series: Department Seminar
Title: Towards Low-Cost Memory Security

  • Speaker: Prof. Moinuddin Qureshi
                   Professor,
                   Electrical and Computer Engineering,
                   Georgia Institute of Technology, USA
  • Date and Time: Monday, December 17, 2018, 2:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Securing off-chip main memory is essential for protection from adversaries with physical access to systems. Current secure-memory designs, such as Intel SGX, incur significant slowdown, mainly due to the extra accesses required to obtain the security-related metadata -- counters for encryption, MAC for integrity check, and Merkle-tree counters for replay attack protection. To make secure memory solutions widespread, it is vital that the performance overhead of providing security is kept to a negligible amount, otherwise, such solutions will remain limited to only a narrow set of systems and applications.

In this talk, I will describe our recent works to reduce the overheads of secure memory. First, we avoid the bandwidth overhead of MAC accesses by co-locating the data and the MAC on an ECC DIMM. This solution, called SYNERGY, not only provides higher performance for secure memory but also provides stronger reliability than ECC alone. Second, we reduce the bandwidth overhead of obtaining counters for encryption and Merkle-Tree by packing more counters per cache line. This solution, called Morphable Counter, can pack 2x more counters per line than state-of-the-art by adapting the counter format to suit the application requirement. Finally, I will also briefly discuss our MICRO-2018 work on protecting cache memories from eviction-based attacks. This solution, called CEASER, can tolerate years of attack, has a slowdown of ~1%, and incurs a storage overhead of only 24 bytes.

Speaker Bio:
Moinuddin Qureshi is a Professor of Electrical and Computer Engineering at the Georgia Institute of Technology. His research interests include computer architecture, memory systems, hardware security, and quantum computing. He was a research staff member (2007-2011) at IBM T.J. Watson Research Center, where he investigated the caching algorithms for Power-7 processors and won the Outstanding Technical Achievement (OTA) award for studying non-volatile memories for servers. He holds more than two-dozen U.S. patents. His publications have received more than 7500 citations, including two lead-author papers with more than 1000 citations each. He served as the Program Chair for MICRO 2015 and as the selection committee co-chair for IEEE MICRO Top Picks 2017. He is a member of the Hall-of-Fame of ISCA, Hall-of-Fame of MICRO, and Hall-of-Fame of HPCA. He is a recipient of the Intel Faculty Award, NetApp Faculty Fellowship, MICRO-2018 best paper award, two IEEE MICRO Top-Pick awards, and two honorable mentions. He received his Ph.D. (2007) and M.S. (2003) from the University of Texas at Austin.

Host Faculty: Arkaprava Basu

Video Archive Go Top

 

Series: Department Seminar
Title: Breaking the Memory Wall in Current and Emerging Accelerators

  • Speaker: Prof. Adwait Jog
                   Assistant professor,
                   Computer Science at the College of William & Mary (W&M), Virginia, USA
  • Date and Time: Monday, December 17, 2018, 10:30 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The famous memory wall has been a problem in computer systems for decades. In this talk, I will revisit this problem in light of accelerators, which are becoming an inevitable part of almost all systems. First, I will discuss the limited memory capacity problem faced by accelerators, especially in emerging in-memory automata processors, and discuss one of the ways to address it to achieve higher throughput. Next, I will discuss the limited bandwidth problem in Graphics Processing Units (GPUs) and show that existing memory coalescing solution to address this bandwidth problem can actually expose a security vulnerability. Time permitting, I will briefly discuss our solution that partially addresses this issue. The bulk of my talk is inspired by my research group’s two recent conference papers (MICRO'18 and HPCA'18), which can be accessed here: http://adwaitjog.github.io/pubs.html

Speaker Bio:
Adwait Jog is an Assistant Professor of Computer Science at the College of William & Mary (W&M), Virginia, USA. He earned his Ph.D. from the Pennsylvania State University, University Park in 2015. His research interests lie in the broad area of computer architecture. Specifically, he is interested in designing capable, energy-efficient, reliable, and secure general-purpose Graphics Processing Units (GPUs) and other accelerators. He is the recipient of the NSF CAREER Award and Penn State Outstanding Graduate Research Assistant Award. More details can be found on Adwait's webpage: http://adwaitjog.github.io/

Host Faculty: Arkaprava Basu

Video Archive Go Top

 

Series: Department Seminar
Title: Improved Algorithms for MST and Metric-TSP Interdiction

  • Speaker: Prof. Chaitanya Swamy
  • Date and Time: Wednesday, December 12, 2018, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Interdiction problems investigate the sensitivity of an underlying optimization problem with respect to removal of a limited set of underlying elements in order to identify vulnerable spots for possible reinforcement or disruption. We consider the MST-interdiction problem: given a multigraph G with weights and interdiction costs on the edges, and an interdiction budget B, find a set R of edges of total interdiction cost at most B so as to maximize the weight of an MST of G-R. Our main result is a 4-approximation algorithm for this problem. This improves upon the previous-best 14-approximation due to Zenklusen, and notably, our analysis is also significantly simpler and cleaner. Whereas Zenklusen uses a greedy algorithm with an involved analysis to extract a good interdiction set from an over-budget set, we utilize a generalization of knapsack called the tree knapsack problem that nicely captures the key combinatorial aspects of this "extraction problem." We prove a simple, yet strong, LP-relative approximation bound for tree knapsack, which leads to our improved guarantees for MST interdiction. Our algorithm and analysis are nearly tight, as we show that one cannot achieve an approximation ratio better than 3 relative to the upper bound used in our (and the prior) analysis. Our guarantee for MST-interdiction yields an 8-approximation for metric-TSP interdiction. We also show that the maximum-spanning-tree interdiction problem is at least as hard to approximate as the minimization version of densest-k-subgraph. This is joint work with Andre Linhares.

Host Faculty: Dr. Siddharth Barman

Video Archive Go Top

 

 

 

 

 

 

 

 

 

 

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