CSE Seminar

2022 talks

  • The Compiler as a Database of Code Transformations


    Speaker:

    Sorav Bansal

    Date:2022-01-12
    Time:12:00:00 (IST)
    Venue:Microsoft teams
    Abstract:
    A modern compiler is perhaps the most complex machine developed by humankind. Yet it remains fragile and inadequate for meeting the demands of modern optimization tasks necessitated by Moore’s law saturation. In our research, we explore a different approach to building compiler optimizers that is both completely automatic and more systematic. The basic idea is to use superoptimization techniques to automatically discover replacement rules that resemble peephole optimizations. A key component of this compiler architecture is an equivalence checker that validates the optimization rules automatically. I will describe the overall scheme, and delve into some interesting details of automatic equivalence checking. I will also share our recent work on automatic generation of debugging headers. This talk is based on work published at ASPLOS06, OSDI08, SOSP13, APLAS17, HVC17, SAT18, PLDI20, OOPSLA20, and CGO22.

    Teams link:
    https://teams.microsoft.com/l/meetup-join/19%3ac00a05b5843f4486843ed7ca9c863eeb%40thread.tacv2/1641802730821?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%220ca83376-feac-4ea2-88fe-f0688c4de543%22%7d


2021 talks

  • Leveraging AI for Smart Transportation


    Speaker:

    Prof. Sanjay Ranka, Distinguished Professor in the Department of Computer Information Science and Engineering at University of Florida

    Date:2021-10-27
    Time:14:00:00 (IST)
    Venue:Bharti-501
    Abstract:

    Mitigating traffic congestion and improving safety are the cornerstones of transportation within smart cities. Current practices collect and analyze data from sensors and video processing and then process it offline. Hence, they are limited in proactively reducing traffic fatalities and preventable delays at intersections. We are developing real-time artificial intelligence algorithms and software to analyze video feeds from cameras and fuse them with ground sensor data to develop deep learning based digital twins that mimic traffic behavior both at an intersection and at the city level. We are also using the resultant output to develop technologies that will quantitatively measure and rank intersections by safety, to transmit information about unsafe behavior to connected vehicles and pedestrians in real-time to prevent accidents, and to optimize signal timing to reduce congestion.


    Bio:

    Sanjay Ranka is a Distinguished Professor in the Department of Computer Information Science and Engineering at University of Florida. From 1999-2002, as the Chief Technology Officer at Paramark (Sunnyvale, CA), he developed a real-time optimization service called PILOT for marketing campaigns. PILOT served more than 10 million optimized decisions a day in 2002 with a 99.99% uptime. Paramark was recognized by VentureWire/Technologic Partners as a Top 100 Internet technology company in 2001 and 2002 and was acquired in 2002. Sanjay has also held positions as a tenured faculty member at Syracuse University, academic visitor at IBM and summer researcher at Hitachi America Limited.

    Research in high performance computing and bigdata science is an important avenue for novel discoveries in large-scale applications. The focus of his current research is the development of efficient computational methods and data analysis techniques to model scientific phenomenon, and practical applications of focus are improvements to the quality of healthcare and the reduction of traffic accidents.  A core aspiration of his research is to develop novel algorithms and software that make an impact on the application domain, exploiting the interdependence between theory and practice of computer science

    He has coauthored one book, four monographs, 300+ journal and refereed conference articles. His recent coauthored work has received a best student paper runner-up award at IGARSS 2015, best paper award at BICOB 2014, best student paper award at ACM-BCB 2010, best paper runner-up award at KDD-2009, a nomination for the Robbins Prize for the best paper in the Journal of Physics in Medicine and Biology in 2008, and a best paper award at ICN 2007.

    He is a fellow of the IEEE, AAAS and AAIA (Asia-Pacific Artificial Intelligence Association) and a past member of IFIP Committee on System Modeling and Optimization. He won the 2020 Research Impact Award from IEEE Technical Committee on Cloud Computing. He is an associate editor-in-chief of the Journal of Parallel and Distributed Computing and an associate editor for ACM Computing Surveys, IEEE/ACM Transactions on Computational Biology and Bioinformatics, Sustainable Computing: Systems and Informatics, Knowledge and Information Systems, and International Journal of Computing. Additionally, he is a book series editor for CRC Press for Bigdata. In the past, he has been an associate editor for IEEE Transactions on Parallel and Distributed Systems and IEEE Transactions on Computers.

    He was a general co-chair for ICDM in 2009, International Green Computing Conference in 2010 and International Green Computing Conference in 2011, a general chair for ACM Conference on Bioinformatics and Computational Biology in 2012, and a program chair for 2013 International Parallel and Distributed Processing Symposium and 2015 High Performance Computing Conference. He was a co-general chair for DataCom 2017 and co-program chair for ICMLDS 2017 and 2018.

    His work has received 14,000+ citations with an h-index of 58 (based on Google Scholar). He has consulted for several startups and Fortune 500 companies.



  • Automating Property Directed Self Composition for Hypersafety Verification


    Speaker:

    Kumar Madhukar

    Date:2021-10-27
    Time:12:00:00 (IST)
    Venue:Microsoft teams
    Abstract:

    In this talk, I will present a hypersafety verification technique called Property Directed Self Composition (PDSC), and discuss our ideas to improve the technique further. Hypersafety (or, k-safety) verification deals with verifying properties that talk about multiple (k) interacting executions of a program. For example, verifying that a program is deterministic is 2-safety verification, because it talks about two executions of the program (that start from the same initial state, but diverge). Self-composition is a common way of doing hypersafety verification, because it reduces the k-safety property into the standard (1-)safety property. However, there are many ways to self-compose -- that are semantically the same, but some may be easier to prove safe than others. We will look at the work of Ron et al. from CAV 2019 where they presented the PDSC technique, discuss some of its limitations and how they may be addressed.

     

    Teams link:
    https://teams.microsoft.com/l/meetup-join/19%3ac00a05b5843f4486843ed7ca9c863eeb%40thread.tacv2/1634558485857?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%220ca83376-feac-4ea2-88fe-f0688c4de543%22%7d


  • Efficient Analysis of Release-Acquire Concurrency using Partial Orders


    Speaker:

    Subodh Sharma

    Date:2021-10-13
    Time:12:00:00 (IST)
    Venue:Microsoft teams
    Abstract:

    Mechanised analysing of concurrent programs is known to be a notoriously hard problem. This talk will discuss a specific problem of verifying concurrent programs under a well-behaved and relatively cleaner subset of the C11 concurrency standard, namely, the release-acquire (RA) memory model. I will argue that localised thread-modular reasoning is the natural way to analyse RA concurrency. Furthermore, I will show that one can succinctly capture ordering dependencies among RA program events using an appropriate partial order relation and abstraction. Finally, to perform efficient verification and refutation of RA programs, I will present our solution as a combination of thread-modular reasoning with a novel abstract domain that efficiently captures ordering dependencies.

    Teams Link:

    https://teams.microsoft.com/l/meetup-join/19%3ac00a05b5843f4486843ed7ca9c863eeb%40thread.tacv2/1633704647985?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%220ca83376-feac-4ea2-88fe-f0688c4de543%22%7d


  • Learning Subgraph Similarity via Graph Neural Networks


    Speaker:

    Sayan Ranu

    Date:2021-09-29
    Time:12:00:00 (IST)
    Venue:Microsoft teams
    Abstract:

    Subgraph similarity search is one of the fundamental operators in graph analysis. In this framework, given a query graph and a database of graphs, the goal is to identify all subgraphs of the database graphs that are structurally similar to the query. Subgraph edit distance (SED) is one of the most expressive mechanisms to quantify subgraph similarity. In this work, we study the problem of learning SED from a train set of graph pairs and their corresponding SED values. Towards that end, we design a novel siamese graph neural network called NEUROSED, which embeds graphs in an embedding space with a rich structure reminiscent of SED. Furthermore, with the help of a specially crafted inductive bias, NEUROSED not only enables high accuracy but also transfers triangle inequality from the original space to the embedding space. The architecture of NEUROSED is generic enough to model graph edit distance (GED) while ensuring that the predicted GED space remains metric. Extensive experiments on real graph datasets establish that the RMSE obtained by NEUROSED is, on average, 2 times lower than the state of the art. In addition, NEUROSED is up to 34 times faster than the fastest baseline for computing SED.

    Teams link:
    https://teams.microsoft.com/l/meetup-join/19%3ac00a05b5843f4486843ed7ca9c863eeb%40thread.tacv2/1632654643342?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%220ca83376-feac-4ea2-88fe-f0688c4de543%22%7d
     

  • Local-Global Algorithms for Large-Scale Geometry Optimization


    Speaker:

    Rahul Narain

    Date:2021-09-01
    Time:12:00:00 (IST)
    Venue:Microsoft teams
    Abstract:

    In computer graphics, shapes are typically represented as meshes, consisting of a set of vertices connected by triangular or tetrahedral elements. Many problems involving shape deformation, from the simulation of elastic bodies to the parameterization of surfaces, can then be formulated as the minimization of an energy function that measures the distortion of these elements. The resulting optimization problems are highly nonlinear, ill-conditioned, and large-scale -- often involving many thousands or millions of unknowns -- but are also highly structured, with each objective term depending only on a small subset of unknowns and being subject to geometrical invariants. In this talk, I will describe a family of algorithms that exploit this problem structure using a local-global approach. Such algorithms provide fast and robust computation for real-time applications, and can scale favourably to high-resolution meshes. I will also discuss our ongoing research and directions for future work in this area.

    Teams link: 
    https://teams.microsoft.com/l/meetup-join/19%3ac00a05b5843f4486843ed7ca9c863eeb%40thread.tacv2/1630088256401?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%220ca83376-feac-4ea2-88fe-f0688c4de543%22%7d


  • Bridging the Semantic Gap between Robots and Humans


    Speaker:

    Rohan Paul

    Date:2021-04-07
    Time:12:00:00 (IST)
    Venue:Microsoft teams
    Abstract:

    In recent years, intelligent robotic systems are entering human-centric environments like factories, homes and workplaces. To be effective as a teammate, we expect robots to accomplish more than performing simplistic repetitive tasks; they must perceive, reason, perform semantic tasks in a human-like way. However, there exists a "semantic" gap between the human's higher order understanding of the world and the low-level representation of the robot. In this talk, I will discuss AI-based models that allow a robot to the problem of understanding, reasoning and synthesizing plans as instructed by a human partner. I will discuss recent research progress and overview ongoing efforts; aimed towards intelligent robots of the future that will assist people in everyday domains.

    Teams link:
    https://teams.microsoft.com/l/meetup-join/19%3ac00a05b5843f4486843ed7ca9c863eeb%40thread.tacv2/1617301398863?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%220ca83376-feac-4ea2-88fe-f0688c4de543%22%7d


  • The IITD Optical Stack: Devices, Circuits, and Systems


    Speaker:
    Smruti R. Sarangi
    Date:2021-03-24
    Time:12:00:00 (IST)
    Venue:Microsoft teams
    Abstract:
    On-chip optical communication is an extremely promising technology that has the potential to deliver significant performance gains in the next 5-10 years. It has several advantages that include communication at the speed of light and high bandwidth. However, the reason that such technologies have not been adopted by the industry is because of high static power consumption. Such networks need to be powered by either on-chip or off-chip lasers that need to be powered on all the time. This restriction arises from the fundamental nature of light. The laser power consumption can be as high as 2 times the overall power consumption of the rest of the chip.

    We have published a series of papers that show that it is possible to indeed reduce the power consumption by 8-10X and bring it within limits. Our contributions at the device level include the design of a novel tunable power splitter that can split optical power between two waveguides (optical channels) programmatically. This device is used to implement a dynamic programming-based algorithm in hardware that computes the split ratios of all the tunable splitters at runtime. This core technology is then used to design extremely power-efficient buses for CPUs, GPUs, custom SoCs, 1000-core chips, and board-level systems.

    In all these systems, a key requirement is to predict the network traffic in the future and modulate the laser power including the split ratios of splitters accordingly. We propose a wide range of methods for accurately predicting network traffic in the future that includes utilizing new sources of information, creating neural network-based predictors, and running distributed algorithms to share prediction results between predictors. We were able to demonstrate that the power consumption in our networks is within 2X of the ideal value and is well below the industry-accepted 30% ceiling for network-on-chip power consumption.

    Finally, we look at the issue of security in such networks. We show that we can design a simple protocol using stream ciphers and replicated state machines. This is paradigmatically different from the way we approach security problems in chip-level and board-level networks.

    Teams link: 
    https://teams.microsoft.com/l/meetup-join/19%3ac00a05b5843f4486843ed7ca9c863eeb%40thread.tacv2/1615488258072?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%220ca83376-feac-4ea2-88fe-f0688c4de543%22%7d

  • Coping with irrational identity issues using random ideals


    Speaker:

    Nikhil Balaji

    Date:2021-03-10
    Time:12:00:00 (IST)
    Venue:Microsoft teams
    Abstract:

    Identity testing is a fundamental problem in algorithmic algebra. In particular, identity testing in number fields has been much studied in relation to solving systems of polynomial equations, polynomial identity testing, and decision problems on matrix groups and semi groups, among many other problems. Among number fields, cyclotomic fields, i.e., those generated by roots of unity, play a particularly important role. I'll introduce the problem of identity testing integers in cyclotomic fields and present efficient algorithms for some special cases. As an application, we will see how cyclotomic identity testing can yield a simple parallel algorithm for testing equality of compressed strings. No background in number theory or computational complexity will be assumed for this talk. Based on joint work with Sylvain Perifel, Mahsa Shirmohammadi and James Worrell.

    Teams link: https://teams.microsoft.com/l/meetup-join/19%3ac00a05b5843f4486843ed7ca9c863eeb%40thread.tacv2/1614787005953?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%220ca83376-feac-4ea2-88fe-f0688c4de543%22%7d


  • A strongly software independent verifiable voting protocol


    Speaker:
    Subhashis Banerjee
    Date:2021-02-24
    Time:12:00:00 (IST)
    Venue:Microsoft teams
    Abstract:
    In this talk we will first examine the nuances of electronic voting, and the extent to which they are consonant with democracy principles. In the second part of the talk we will present a direct-recording electronic (DRE) polling booth protocol that can be proved to be end-to-end verifiable and can provide sound cast-as-intended, recorded-as-cast and counted-as-recorded verifiability to every individual voter. The protocol can support voter-verifiable paper records (VVPR) - which are required by law in most jurisdictions - in a tightly coupled manner. Moreover, in case an election does not verify, the protocol enables localization of the problem and possible recovery from errors.
     
    Teams link:
    https://teams.microsoft.com/l/meetup-join/19%3ac00a05b5843f4486843ed7ca9c863eeb%40thread.tacv2/1613844565377?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%220ca83376-feac-4ea2-88fe-f0688c4de543%22%7d

  • When the Umpire is also a Player: Bias in Private Label Product Recommendations on E-commerce Marketplaces


    Speaker:

    Abhijnan Chakraborty

    Date:2021-02-10
    Time:12:00:00 (IST)
    Venue:Microsoft teams
    Abstract:

    Algorithmic recommendations mediate interactions between millions of customers and products (in turn, their producers and sellers) on large e-commerce marketplaces like Amazon. In recent years, the producers and sellers have raised concerns about the fairness of black-box recommendation algorithms deployed on these marketplaces. Many complaints are centered around marketplaces biasing the algorithms to preferentially favor their own 'private label' products over competitors. These concerns are exacerbated as marketplaces increasingly de-emphasize or replace 'organic' recommendations with ad-driven 'sponsored' recommendations, which include their own private labels. While these concerns have been covered in popular press and have spawned regulatory investigations, there has not been any public audit of these marketplace algorithms. In this talk, I'll talk about our recent work to bridge this gap by performing an end-to-end systematic audit of related item recommendations on Amazon. We proposed a network-centric framework to quantify and compare the biases across organic and sponsored related item recommendations. Along a number of our proposed bias measures, we found that the sponsored recommendations are significantly more biased toward Amazon private label products compared to organic recommendations. While our findings are primarily interesting to producers and sellers on Amazon, our proposed bias measures are generally useful for measuring link formation bias in any social or content networks.

    Teams link:
    https://teams.microsoft.com/l/meetup-join/19%3ac00a05b5843f4486843ed7ca9c863eeb%40thread.tacv2/1611597271860?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%220ca83376-feac-4ea2-88fe-f0688c4de543%22%7d


  • Upgrading Security of Encryption Schemes


    Speaker:

    Venkata Koppula

    Date:2021-01-15
    Time:12:00:00 (IST)
    Venue:Microsoft teams
    Abstract:

    What does it mean for an encryption scheme to be secure? Perhaps the most basic definition, given in the seminal work of Goldwasser-Micali, states that an encryption scheme is secure if no adversary, given a ciphertext, can learn anything about the underlying message. But this only offers security against "passive attacks". For example, suppose Alice sends an encryption of message 'm' to Bob. An active adversary can intercept this ciphertext, and tamper the ciphertext in such a way that it is now an encryption of a different message 'm'. The adversary still doesn't learn anything about the underlying message, but this is a valid attack (and such attacks have been shown in the real-world). Therefore, security against active adversaries should be the "gold standard" definition of secure encryption.

    It is generally easier to construct encryption schemes that are secure against passive attacks. Can we upgrade any passively secure scheme to one that is actively secure? This question is still open. In this talk, I will present two approaches[1,2] towards achieving adaptive security, and on the way, discuss how they relate to the aforementioned open question.

    [1] Chosen Ciphertext Security from Injective Trapdoor Functions. [Hohenberger, K, Waters]
    [2] Realizing Chosen Ciphertext Security Generically in Attribute-Based Encryption and Predicate Encryption.  [K, Waters]

    No crypto background will be required for this talk.

    Teams link:
    https://teams.microsoft.com/l/meetup-join/19%3ac00a05b5843f4486843ed7ca9c863eeb%40thread.tacv2/1610201184560?context=%7b%22Tid%22%3a%22624d5c4b-45c5-4122-8cd0-44f0f84e945d%22%2c%22Oid%22%3a%220ca83376-feac-4ea2-88fe-f0688c4de543%22%7d



2020 talks

  • Two easy-looking yet poorly understood problems


    Speaker:

    Ashish Chiplunkar

    Date:2020-12-31
    Time:12:00:00 (IST)
    Abstract:

    I will be talking about two easy-looking yet poorly understood problems, namely, the weighted k-server problem and the Bayesian online selection problem. Both problems are online in nature: an algorithm gets its input as a sequence of requests, and must respond to a request before it gets the next one. The challenge is to compete with the offline optimum, that is, the optimum solution considering the entire input, and the loss in optimality is captured by a quantity called competitive ratio.

    The weighted k-server problem is a generalization of the caching problem with the following modification: the cost of page replacement varies with the cache location where the page replacement takes place. While the optimal competitive ratio of caching has been already known for decades, the competitive ratio of weighted k-server isn't. In particular, after the seminal paper by Fiat and Ricklin in 1993, it was only in 2017 that the deterministic competitive ratio was established by Bansal et al., while finding the randomized competitive ratio is still an open problem.

    In the Bayesian online selection problem, an algorithm gets as input the realizations of some independent random variables and must pick one of them irrevocably, with the goal of maximizing the expectation of the value picked. When the arrival order of the values of the random variables is adversarial, it is known since 1977 that the optimal competitive ratio is 1/2. However, the natural cases of random arrival order and algorithmically chosen arrival order remain open.

    For each problem, I plan to discuss the literature, give an overview of techniques, point out open questions, and highlight the recent contributions of our students towards answering those questions. (This talk should be especially relevant to students who wish to work with me.)


  • Relaxed Memory Concurrency: Overview and Challenges


    Speaker:

    Soham Chakraborty

    Date:2020-12-16
    Time:12:00:00 (IST)
    Abstract:

    In most analysis/verification techniques, the behavior of concurrent programs is understood in terms of thread interleavings, a model formally known as sequential consistency (SC). For performance reasons, modern hardware implementations allow some executions which cannot be explained by thread interleavings. Similarly, standard compiler optimizations can affect the outcome of a concurrent program in ways that cannot be understood by SC. Therefore, to program concurrent systems correctly and effectively, it is important to come up with a programming language semantics that accounts for all the non-SC behaviors that hardware and compilers produce. Defining such a "relaxed" memory model is challenging due to conflicting requirements: the model should not only enable efficient compilation, but also provide programmability guarantees.


  • Discovering and Mitigating Security Vulnerabilities in Bluetooth Low Energy


    Speaker:

    Vireshwar Kumar

    Date:2020-12-02
    Time:12:00:00 (IST)
    Abstract:

    The Bluetooth Low Energy (BLE) protocol ubiquitously enables energy-efficient wireless communication among resource-constrained devices. To ease its adoption, the BLE requires limited or no user interaction to establish a connection between two devices. Unfortunately, this simplicity is the root cause of several security issues. In this talk, we analyze the security of the BLE focusing on the scenario in which two previously paired device reconnect. In the first half of the talk, we demonstrate the systematic approach that allows us to uncover critical security vulnerabilities in the BLE. We exploit these vulnerabilities to develop the BLE Spoofing Attack (BLESA) that enables an attacker to impersonate a BLE device and feed spoofed data to another previously paired device. BLESA can be easily carried out against the BLE stack implementations used by Linux, Android, and iOS. Defending the BLE against spoofing attacks, such as BLESA, is extremely difficult as security patches to mitigate them may not be adopted across vendors promptly; not to mention the millions of legacy BLE devices with limited I/O capabilities that do not support firmware updates. We address these challenges in the second half of the talk by presenting BlueShield, a legacy-friendly, non-intrusive monitoring system as the first line of defense against spoofing attacks. BlueShield is motivated by the observation that all spoofing attacks result in anomalies in certain cyber-physical features of the advertising packets containing the BLE device’s identity. BlueShield leverages a unique combination of these features to detect spoofed packets generated by an attacker. We conclude the talk with a discussion on the potential directions for discovering and mitigating security vulnerabilities in the BLE.


  • Can we preserve large distances?


    Speaker:

    Keerti Choudhary

    Date:2020-11-18
    Time:12:00:00 (IST)
    Abstract:

    In the area of graph sparsification, the distance spanners are sparse subgraphs preserving all-pairs distances up to a small stretch. These structures have been well studied for undirected graphs over the past three decades. However, for directed graphs, sparse (subquadratic-sized) distance approximating spanners are not possible in general. We thus focus on the notion of extremal distance spanners in directed graphs. For a directed graph G = (V, E), a subgraph H = (V, E') is said to be a "t"-diameter spanner if the diameter of H is at most "t" times the diameter of G. Similarly, a "t"-eccentricity spanner, is a subgraph that approximately preserves all vertex eccentricities of the original graph, up to a stretch factor t. In this talk, we will look at the existence of (and algorithms to compute) various t-diameter and t-eccentricity spanners with a sparse set of edges for stretch t at most 2.


Copyright © 2022 Department of Computer Science and Engineering. All Rights Reserved.