CSE Seminar

2021 talks

  • 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 © 2021 Department of Computer Science and Engineering. All Rights Reserved.