Events 

Seminars 

Prof. I. G. Sarma Memorial Lecture Series 

Prof. Priti Shankar Memorial Seminar Series 

Multimedia Archive 



UPCOMING SEMINARS 

Series: Department Seminar Title: Two unsolved problems:Birkhoff–von Neumann graphs and PMcompact 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 wellstudied 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 nonnegativity 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 vertexdisjoint 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 coNP. 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 ‘prismfree’.
The combinatorial diameter of a polytope is the diameter of its 1skeleton graph. A
graph G is PMcompact if the combinatorial diameter of its perfect matching polytope equals
one. A result of Chv´atal (1975) implies that G is PMcompact if and only if G does not
contain a pair of vertexdisjoint even cycles ( C1 , C2) such that G − V( C1) − V( C2) has a
perfect matching. Once again the corresponding decision problem is in coNP, but it is not
known to be in NP. The problem is in P if the input graph is bipartite or is ‘nearbipartite’
— 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 PMcompact.
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 selfcontained. 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
 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 kwatchtower problem for a polyhedral terrain T in 3D with n vertices is to
find k vertical segments, called watchtowers, of smallest height, whose bottom endpoints
(bases) lie on some vertices of T , and every point of T is visible from the top endpoint
(tip) of at least one of those watchtowers. In other words, we have to find k watchtowers
whose bottom endpoints (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 kwatchtower problem in
3D for a fixed constant k. Our algorithm does not use parametric search and it’s running
time is polynomial in n.
 Series: Ph.D. Thesis Defense Title: Problems on bendnumber, circular separation dimension and maximum edge 2colouring  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 nonzero 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 2connected graphs for this model. Using one of these results, we showed optimization problems such as maximum independent set, minimum dominating set are APXhard on 1bend EPG graphs and its subclass which is called LEPG graphs.
In the second part, we studied the notion of circular separation dimension which was introduced recently by Douglas West. Formally, a pair of nonadjacent 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 nonadjacent 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 seriesparallel graph and twoouterplanar graph.
In the final part, we studied maximum edge 2colouring problem. For a graph G, the maximum edge 2colouring 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 antiRamsey number. Algorithmically, the problem is known to be NPhard. 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 trianglefree graphs with perfect matching.
 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^310^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
 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, neurobiology, 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 NPhard 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 mixednorm 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 nonsmooth optimization problem is difficult, where offtheshelf 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 nondecreasing cardinalitybased 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 piecewise constant solutions, which SOWL does not have. SOWL is also shown equivalent to grouplasso, 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{HawkesOWL}, an application of OWL regularizers for the setting of multidimensional Hawkes processes. Hawkes process is a multidimensional 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 firstorder algorithms for learning with textbf{Subquadraic norms}, a special subfamily 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 primaldual 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.


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
 Series: Department Seminar Title: μSuite & μTune: AutoTuned 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 OnLine Data Intensive (OLDI) applications have evolved from monolithic
systems to instead comprise numerous, distributed microservices interacting via
Remote Procedure Calls (RPCs). Microservices face subms RPC latency goals, much
tighter than their monolithic ancestors that must meet >= lOOms latency targets. Sub
msscale 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
msscale 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 wideranging 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 tradeoffs 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 stateoftheart
adaptation techniques.
Speaker Bio: Akshitha is a fourthyear 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 largescale distributed data center systems."
Host Faculty: Arkaprava Basu
 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 keywordbased 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 spatiallyreferenced 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/newsstandcacm or a cached version can be found at http://www.cs.umd.edu/~hjs/pubs/cacmnewsstand.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
 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 learningbased verification and synthesis of complex systems.
Host Faculty: Deepak D'Souza
 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 nvariate 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
hardnessrandomness tradeoffs for constant depth arithmetic circuits.
Based on joint work with ChiNing 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 (AugDec 2018), and a postdoctoral fellow in the program on Combinatorics and Complexity at the Center for Mathematical Sciences & Applications at Harvard (June 2017June 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
 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 postdoctoral 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 "Nonmalleable Codes", published at the Theory of Cryptography Conference, was invited to the Journal of Cryptology.
Host Faculty: Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar
 Series: Department Seminar Title: ABR Streaming of CBR and VBRencoded 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 PIDbased control for ABR streaming and design a framework called PIA (PIDcontrol 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 qualitytobits 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 (Controltheoretic Adaption for VBRbased 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 optimizationbased 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 discreteoptimization algorithms for largescale systems and team decisionmaking. 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
 Series: Department Seminar Title: CityScale LowPower 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 cityscale lowpower wireless internetofthings. We build upon lowpower widearea networking (LPWAN), a technology that enables lowcost devices with a 10year 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 LPWAN 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 LPWANs at shorter ranges can eliminate the need for a battery altogether. Beyond communication, I also touch upon the opportunities of an omnipresent lowpower Internet. I present WiSh [MobiSys'18] that makes everyday surfaces around us shapeaware 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
 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, generalpurpose 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 everfaster 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 generalpurpose processor manufacturers (Intel, AMD and PowerPC) have turned to hyperthreading and multicore 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 multicore 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 multicore 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 highperformance concurrent program suitable for a multicore 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 codirector of the Advanced Networking and Dependable Systems Laboratory (ANDES) since 2002. His research interests include multicore computing, distributed computing, distributed algorithms for wireless networking and security.
Host Faculty: Deepak D'Souza
 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
 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 suboptimal 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 autotuning, (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 innerloop 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 stateoftheart 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.
 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
 Series: Department Seminar Title: Towards LowCost 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 offchip main memory is essential for protection from adversaries with physical access to systems. Current securememory designs, such as Intel SGX, incur significant slowdown, mainly due to the extra accesses required to obtain the securityrelated metadata  counters for encryption, MAC for integrity check, and Merkletree 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 colocating 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 MerkleTree by packing more counters per cache line. This solution, called Morphable Counter, can pack 2x more counters per line than stateoftheart by adapting the counter format to suit the application requirement. Finally, I will also briefly discuss our MICRO2018 work on protecting cache memories from evictionbased 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 (20072011) at IBM T.J. Watson Research Center, where he investigated the caching algorithms for Power7 processors and won the Outstanding Technical Achievement (OTA) award for studying nonvolatile memories for servers. He holds more than twodozen U.S. patents. His publications have received more than 7500 citations, including two leadauthor papers with more than 1000 citations each. He served as the Program Chair for MICRO 2015 and as the selection committee cochair for IEEE MICRO Top Picks 2017. He is a member of the HallofFame of ISCA, HallofFame of MICRO, and HallofFame of HPCA. He is a recipient of the Intel Faculty Award, NetApp Faculty Fellowship, MICRO2018 best paper award, two IEEE MICRO TopPick 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
 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 inmemory 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, energyefficient, reliable, and secure generalpurpose 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
 Series: Department Seminar Title: Improved Algorithms for MST and MetricTSP 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 MSTinterdiction 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 GR. Our main result is a 4approximation algorithm for this problem. This improves upon the previousbest 14approximation 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 overbudget 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, LPrelative 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 MSTinterdiction yields an 8approximation for metricTSP interdiction. We also show that the maximumspanningtree interdiction problem is at least as hard to approximate as the minimization version of densestksubgraph. This is joint work with Andre Linhares.
Host Faculty: Dr. Siddharth Barman

