Department of Computer Science and Automation Department of Computer Science and Automation, IISc, Bangalore, India Indian Institute of Science
HOME | ABOUT US | PEOPLE | RESEARCH | ACADEMICS | FACILITIES | EVENTS / SEMINARS | NEWS | CONTACT US

UPCOMING SEMINARS

Series: Theory Seminar
Title: Monotone Arithmetic Lower Bounds Via Communication Complexity.

  • Speaker: Dr. Arkadev Chattopadhyay
                   Associate Professor
                   School of Technology and Computer Science
                   TIFR Mumbai
  • Date and Time: Friday, September 24, 2021, 4:00 PM
  • Venue: Microsoft Teams - ON-LINE

Abstract
How much power does negation or cancellation provide to computation?

This is a fundamental question in theoretical computer science that

appears in various parts: in Boolean circuits, Arithmetic circuits and

also in communication complexity. I will talk about some new connections

between the latter two fields and their applications to extend two

classical results from four decades ago: Valiant (1979) showed that

monotone arithmetic circuits are exponentially weaker than general

circuits for computing monotone polynomials. Our first result gives a

qualitatively more powerful separation by showing an exponential

separation between general monotone circuits and constant-depth

multi-linear formulas. Neither such a separation between general

formulas and monotone circuits, nor a separation between multi-linear

circuits and monotone circuits were known before. Our result uses the

recent counter-example to the Log-Approximate-Rank Conjecture in

communication complexity.



Jerrum and Snir (1982) also obtained a separation between the powers of

general circuits and monotone ones via a different polynomial, i.e. the

spanning tree polynomial (STP), a polynomial that is well known to be in

VP, using non-multi-linear cancellations of determinantal computation.

We provide the first extension of this result to show that the STP

remains `robustly hard` for monotone circuits in the sense of Hrubes

recent notion of epsilon-sensitivity. The latter result is proved via

formulating a discrepancy method for monotone arithmetic circuits that

seems independently interesting.

We will discuss several open problems arising from these results.

(These are based on joint works with Rajit Datta, Utsab Ghosal and

Partha Mukhopadhyay).

Microsoft Teams Link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d

For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/

Host Faculty: Dr. Anand Louis

Video Archive Go Top

 

Series: Department Seminar
Title: Vertex Coloring Problem with Some Domination Properties

  • Speaker: Dr. Sayani Das
                   Department of Mathematics
                   Indian Institute of Technology Madras
                   Chennai
  • Date and Time: Thursday, September 23, 2021, 4:00 PM
  • Venue: Microsoft Teams - ON-LINE

Abstract
Coloring and Dominating Set are two well known and well studied problems in Graph Theory. Here we consider a vertex coloring problem by imposing some domination property on it. Given a simple graph G = (V,E), in domination coloring, we need to find a vertex coloring of V such that each vertex v in V dominates some color class and each color class is dominated by some vertex v in V. The domination chromatic number of G, is the minimum number of colors used in a domination coloring of G. In minimum domination coloring we need to compute a domination coloring with minimum number of colors. We prove that, this problem is as hard as minimum vertex coloring problem. We also show that, it cannot be approximated within a factor of O(ln n), even when restricted to weakly chordal graphs. We also consider node deletion problems associated with domination coloring. Given a graph G and a positive integer q, in Minimum q-Domination Partization, it is required to find a vertex set S of minimum size such that the remaining graph is domination colorable with at most q colors. We only consider q-domination partization problem for q = 2 and q =3. We prove that Minimum 2-Domination Partization is APX-complete. It is approximable within a factor of 2 and this approximation factor is the best possible approximation factor. Then we have given the characterizations for 3-domination colorable graphs. Finally, we prove that Minimum 3-Domination Partization is APX-hard, it is equivalent to minimum odd cycle transversal and design approximation algorithm for it.

Speaker Bio:
Ph.D. Scholar, Department of Mathematics, IIT Madras. Microsoft teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_YzI4MTA2NGQtZDAwZS00MGU4LWI4MzktM2YyYzVjMjE0ZmYx%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%222671ab71-955e-4e4e-9268-ebb188b00539%22%7d

Host Faculty: Dr. Arindam Khan

Video Archive Go Top

 

Series: Department Seminar
Title: Designing Secure Cryptographic Systems: Journey from Theory to Practice

  • Speaker: Dr. Sikhar Patranabis, Visa Research
  • Date and Time: Wednesday, September 22, 2021, 8:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The study of cryptography is aimed at keeping information secure in an increasingly digitized world. Modern cryptography uses theoretical frameworks to prove the security of cryptographic primitives against precisely modeled attacks. However, translating cryptographic primitives from provably secure algorithms into secure deployable systems remains a massive challenge. In particular, existing theoretical models do not account for potential weaknesses inherent to practical cryptographic implementations. Hence, provable security guarantees often collapse in the face of attacks that exploit implementation-level weaknesses to devastating effect.

In this talk, I will give an overview of my journey so far in attempting to bridge the wonderfully multi-faceted aspects of cryptography, with the aim of designing, analyzing and securely implementing cryptographic solutions to real-world problems while relying on as minimal a set of assumptions as possible. In the process, I will summarize my past research works spanning theoretical cryptographic foundations, applied cryptography and secure cryptographic implementations.

I will begin with an overview of my foundational research into enabling a variety of functionally rich and provably secure cryptographic applications based on Minicrypt (the world of “symmetric-key” cryptoprimitives), and some additional algebraic structure. I will then discuss my research efforts towards enabling a specific cryptographic application - searchable symmetric encryption (SSE) - that supports a wide class of Boolean queries over encrypted relational databases at scale while relying on purely symmetric-key primitives. Finally, I will showcase that despite the theoretical security guarantees afforded by standardized symmetric-key cryptographic algorithms such as AES-128, practical implementations of SSE schemes remain vulnerable to “fault-injection attacks'' – a special class of implementation-level attacks powerful enough to reduce the keyspace for AES-128 from 2^{128} to a single key while relying on a single fault-injection. In particular, I will describe my recent work (appeared at Eurocrypt 2020) on a “fault propagation”-based key-recovery attack that completely breaks the security of an AES-128 implementation, even when equipped with dedicated protections against standard implementation-level attacks.

No prior background on cryptography will be needed.

Speaker Bio:
Sikhar Patranabis is a staff research scientist at Visa Research USA. His research focuses on cryptographic foundations, post-quantum cryptography, database encryption, and cryptographic hardware security. Prior to joining Visa Research, he was a postdoctoral researcher at ETH Zurich, Switzerland. He received his PhD and B.Tech in Computer Science and Engineering from IIT Kharagpur. His research has appeared in reputed international conferences and journals, including IACR Crypto, IACR Eurocrypt, IACR Asiacrypt, ACM CCS, NDSS, IEEE TC and IEEE TIFS. He has delivered invited talks at many prestigious international forums, including an invited tutorial at IACR CHES 2015. He is the recipient of an IBM PhD fellowship, a Qualcomm Innovation Fellowship and the President of India gold medal from IIT Kharagpur. This seminar will be given via Teams Meeting: https://teams.microsoft.com/l/meetup-join/19%3ameeting_MzlkOTZhMmMtYmJjOC00MTJiLTg4OGYtZjg4ZjNkZTVmNTVj%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%224bcd3d56-e405-4b06-99fb-27742262f261%22%7d

Host Faculty: R. Govindarajan

Video Archive Go Top

 

PAST SEMINARS

Series: Theory Seminar
Title: Efficient Intervention Design for Learning Causal DAGs

  • Speaker: Dr. Karthikeyan Shanmugam
                   Research Staff Member
                   IBM Research AI group
                   New York
  • Date and Time: Friday, September 17, 2021, 4:00 PM
  • Venue: Microsoft Teams - ON-LINE

Abstract
Network of cause effect relationships between measured variables is modeled as a causal DAG (Directed Acyclic Graph). In this talk, we focus on efficient adaptive intervention design for learning a causal DAG, with no latent confounders, given the observational equivalence class it belongs to as an input. We first consider equivalence class inputs whose skeleton is a tree. We consider a Bayesian framework where a prior over all directed trees is updated based on the outcome of every single node intervention each of which is adaptively designed based on current posterior. We provide an efficient algorithm that requires interventions that is within a factor of 2 from the best adaptive algorithm. We also show that information greedy approaches are exponentially sub-optimal in terms of the optimal number of interventions required. The main technical tool is a simple greedy algorithm that myopically optimizes a centrality measure on the skeleton of the true causal tree.

We generalize and extend the above approach for adaptive interventional design to learn an arbitrary causal DAGs given its equivalence class. We show that the half the maximum clique size is an instance specific fundamental lower bound for any algorithm to even verify the DAG structure through interventions given the equivalence class. Under mild assumptions on the equivalence class, we provide an adaptive algorithm inspired by the algorithm on causal trees that requires interventions that matches the optimal number of interventions up to a multiplicative logarithmic factor in the number of maximal cliques.

Microsoft Teams Link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d

For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/

Host Faculty: Dr. Rahul Saladi

Video Archive Go Top

 

Series: M.Tech (Research) Colloquium- ON-LINE
Title: Security of Post-Quantum Multivariate Blind Signature Scheme: Revisited and Improved

  • Speaker: Ms. Aalo Majumdar
                   M.Tech (Research) student
                   Dept. of CSA
  • Faculty Advisor: Prof. Sanjit Chatterjee
  • Date and Time: Thursday, September 16, 2021, 4:00 PM
  • Venue: Microsoft teams - ONLINE

Abstract
Current ubiquitous cryptosystems face an imminent threat from quantum algorithms like Shors and Grovers, leading us to a future of post-quantum cryptography. Multivariate signatures are prominent in post-quantum cryptography due to their fast, low-cost implementations and shorter signatures. Blind signatures are a special category of digital signatures with two security notions: blindness and one-more unforgeability (OMF). Our work primarily focuses on the multivariate blind signature scheme (MBSS) proposed by Petzoldt et al. We construct a formal proof along the lines of the heuristic sketch given by the authors of MBSS based on the proposed universal one-more unforgeability (UOMF) model, a weaker variant of OMF. The construction of this proof led us to identify the various issues in the security argument - mainly the difficulty in simulating the response to the blind signature queries without knowing the secret key of the underlying Rainbow scheme used. Since our investigation revealed the difficulty in reducing the UOMF security to the hardness assumption used by the authors, therefore we design a new class of hardness assumptions: (1) Single Target Inversion Problem, PR-STI (2) Modified version of Single Target Inversion Problem, PR-mSTI (3) Chosen Target Inversion Problem, PR-CTI. Armed with the new class of computational problems, we reduce the UOMF and OMF security of MBSS to these problems. We begin by giving an improved security argument of MBSS in the UOMF security model using the PR-mSTI assumption. We employ the general forking algorithm in this security reduction. However, we cannot apply the forking algorithm directly owing to the wrapper algorithm being split and the presence of the blind signature oracle. We thus suitably modify the algorithm and then derive the corresponding forking probability. To argue the security of MBSS in the standard security model, i.e., in the OMF model, we try using the PR-CTI assumption. The PR-CTI problem demands computing the solution for more than one target. With the high cost of forking, a significant degradation factor appears in the success probability. So, instead, we reduce the OMF security of MBSS to the PR-mSTI assumption (in a restricted setting) and give a comparative analysis between the security argument in the UOMF and OMF models.

Microsoft Teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_NzFiMjNmODEtN2ZkZi00OGU4LWEzOGEtZTdjMjM5OWI0ZWZl%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22f24581ee-9350-45bb-b76b-26beecd9d45f%22%7d

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defense
Title: GPM: Exploring GPUs with Persistent Memory

  • Speaker: Shweta Pandey
  • Faculty Advisor: Arkaprava Basu
  • Date and Time: Monday, September 13, 2021, 11:00 AM
  • Venue: https://teams.microsoft.com/l/meetup-join/19%3a13ca80f16f7948a2a87ac38e29410e0a%40thread.tacv2/1630390106337?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%2282f39501-c5b2-4bfb-87c3-f17ca74c00b6%22%7d

Abstract
GPUs are a key computing platform for many application domains. While the emergence of non-volatile memory has brought the promise of fi ne-grain byte-addressable persistence (a.k.a., persistent memory, or PM) to CPU applications, the same unfortunately is beyond the reach of GPU programs.

This work takes three steps toward enabling GPU programs to directly access PM. First, we show how various existing software and hardware technologies can be put together to enable direct access to PM from within a GPU kernel. Next, we created a workload suite of 10 GPU-accelerated applications to demonstrate how GPUs can benefit from PM. We then created a GPU library to support logging, checkpointing, and primitives for native persistence to enable GPU programmers to easily leverage PM.

Speaker Bio:
Shweta Pandey is an MTech (Research) student in the Department of Computer Science and Automation. She is advised by Prof. Arkaprava Basu. She is interested in building systems that use heterogeneous computing and are heterogeneous memory aware.

Host Faculty: Arkaprava Basu

Video Archive Go Top

 

Series: Theory Seminar
Title: Better-Than-2 Approximations for Weighted Tree Augmentation

  • Speaker: Dr. Vera Traub
                   Postdoctoral Researcher
                   ETH Zurich (Switzerland)
  • Date and Time: Friday, September 10, 2021, 4:00 PM
  • Venue: Microsoft Teams - ON-LINE

Abstract
The Weighted Tree Augmentation Problem (WTAP) is one of the most basic connectivity augmentation problems. It asks how to increase the edge-connectivity of a given graph from 1 to 2 in the cheapest possible way by adding some additional edges from a given set. There are many standard techniques that lead to a 2-approximation for WTAP, but despite much progress on special cases, the factor 2 remained unbeaten for several decades. In this talk we present two algorithms for WTAP that improve on this longstanding approximation ratio of 2. The first algorithm is a relative greedy algorithm, which starts with a simple, though weak, solution and iteratively replaces parts of this starting solution by stronger components.

This algorithm achieves an approximation ratio of (1+ln(2)+ϵ)<1.7. Second, we present a local search algorithm that achieves an approximation ratio of 1.5+ϵ (for any constant ϵ>0).

This is joint work with Rico Zenklusen.

Microsoft Teams Link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d

For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/

Host Faculty: Dr. Arindam Khan

Video Archive Go Top

 

Series: Theory Seminar
Title: A (2 + ϵ)-approximation algorithm for preemptive weighted flow time on a single machine

  • Speaker: Dr. Lars Rohwedder
                   Postdoctoral Researcher
                   Theoretical Computer Science
                   EPFL, Lausanne (Switzerland)
  • Date and Time: Friday, September 03, 2021, 4:00 PM
  • Venue: Microsoft Teams - ON-LINE

Abstract
In a recent breakthrough in scheduling, Batra, Garg, and Kumar gave the first constant approximation algorithm for minimizing the sum of weighted flow times. Wiese and I (STOC 21) managed to improve this large unspecified constant to 2+ϵ. I will give a very graphic presentation of the algorithmic techniques behind this.

Microsoft Teams Link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d



For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/

Host Faculty: Dr. Arindam Khan

Video Archive Go Top

 

Series: M.Tech (Research) Colloquium- ON-LINE
Title: A Syntactic Neural Model for Question Decomposition

  • Speaker: Ms. Suman Gupta
                   M.Tech (Research) student
                   Dept. of CSA
  • Faculty Advisor: Prof. Shirish K Shevade
  • Date and Time: Friday, September 03, 2021, 2:00 PM
  • Venue: Microsoft Teams - ON-LINE

Abstract
Question decomposition along with single-hop Question Answering (QA) system serve as useful modules in developing multi-hop Question Answering systems, mainly because the resulting QA system is interpretable and has been demonstrated to exhibit better performance. The problem of Question Decomposition can be posed as a machine translation problem and it can be solved using any sequence-to-sequence neural architecture. Using this approach, it is difficult to capture the innate hierarchical structure of the decomposition. Inspired by database query languages a pseudo-formalism for capturing the meaning of questions, called Question Decomposition Meaning Representation (QDMR) was recently introduced. In this approach, a complex question is decomposed into simple queries which are mapped into a small set of formal operations. This method does not utilize the underlying syntax information of QDMR to generate the decomposition.

In the area of programming language code generation, methods that use syntax information as a prior knowledge have been demonstrated to perform better. Moreover, the syntax-aware models are usually interpretable. Motivated by the success of syntax-aware models, we propose a new syntactic neural model for question decomposition in this thesis. In particular, we encode the underlying syntax of the QDMR structures into a grammar model as a sequence of actions.

This is done using a deterministic framework which uses Abstract Syntax Trees (AST) and Parse Trees. The proposed approach can be thought of as an encoder-decoder method for QDMR structures where a sequence of possible actions is a latent representation of the QDMR structure. The advantage of using this latent representation is that it is interpretable. Experimental results on a real-world dataset demonstrate that the proposed approach outperforms the state-of-the-art approach especially in scenarios where training data is limited. Some heuristics to further improve the performance of the proposed approach are also suggested in this work.

Microsoft teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_YTQ3YzdhOWMtMDBiYy00ODQxLWJmMDItMzlmY2MwNjFjYjY5%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%229c3e2bfe-1b0f-4d7b-a589-832878069dc6%22%7d

Video Archive Go Top

 

Series: Ph.D. (Engg.) Colloquium- ONLINE
Title: Neural Models for Personalized Recommendation Systems with External Information

  • Speaker: Mr. Vijaikumar M
                   Ph.D student
                   Dept. of CSA
  • Faculty Advisor: Prof. Shirish K Shevade & Prof. M Narasimha Murty
  • Date and Time: Thursday, August 26, 2021, 2:00 PM
  • Venue: Microsoft Teams - ON-LINE

Abstract
Personalized recommendation systems use the data generated by user-item interactions (for example, in the form of ratings) to predict different users interests in available items and recommend a set of items or products to the users. The sparsity of data, cold start, and scalability are some of the important challenges faced by the developers of recommendation systems. These problems are alleviated by using external information, which can be in the form of a social network or a heterogeneous information network, or cross-domain knowledge. This thesis develops novel neural network models for designing personalized recommendation systems using the available external information.

The first part of the thesis studies the top-N item recommendation setting where the external information is available in the form of a social network or heterogeneous information network. Unlike a simple recommendation setting, capturing complex relationships amongst entities (users, items, and connected objects) becomes essential when a social and heterogeneous information network is available. In a social network, all socially connected users do not have equal influence on each other. Further, estimating the quantum of influence among entities in a user-item interaction network is important when only implicit ratings are available. We address these challenges by proposing a novel neural network model, SoRecGAT, which employs a multi-head and multi-layer graph attention mechanism. The attention mechanism helps the model learn the influence of entities on each other more accurately. Further, we exploit heterogeneous information networks (HIN) to gather multiple views for the items. A novel neural network model -- GAMMA (Graph and Multi-view Memory Attention mechanism) is proposed to extract relevant information from HINs. The proposed model is an end-to-end model which eliminates the need for learning a similarity matrix offline using some manually selected meta-paths before optimizing the desired objective function.

In the second part of the thesis, we focus on top-N bundle recommendation and list continuation setting. Bundle recommendation is the task of recommending a group of products instead of individual products to users. We study two interesting challenges -- (1) how to personalize and recommend existing bundles to users and (2) how to generate personalized novel bundles targeting specific users. We propose GRAM-SMOT -- a graph attention-based framework that considers higher-order relationships among the users, items, and bundles and the relative influence of items present in the bundles. For efficiently learning the embeddings of the entities, we define a loss function based on the metric-learning approach. A strategy that leverages submodular optimization ideas is used to generate novel bundles.

We also study the problem of top-N personalized list continuation where the task is to curate the next items to user-generated lists (ordered sequence of items) in a personalized way by using the sequential information of the items in the list. The main challenge in this task is understanding the ternary relationships among the users, items, and lists. We propose HyperTeNet -- a self-attention hypergraph and Transformer-based neural network architecture for the personalized list continuation task. Here, graph convolutions are used to learn the multi-hop relationship among entities of the same type. A self-attention-based hypergraph neural network is proposed to learn the ternary relationships among the interacting entities via hyperlink prediction in a 3-uniform hypergraph. Further, the entity embeddings are shared with a Transformer-based architecture and are learned through an alternating optimization procedure.

The final part of the thesis focuses on the personalized rating prediction setting where external information is available in the form of cross-domain knowledge. We propose an end-to-end neural network model, NeuCDCF, that provides a way to alleviate data sparsity problems by exploiting the information from related domains. NeuCDCF is based on a wide and deep framework and learns the representations jointly using matrix factorization and deep neural networks. We study the challenges involved in handling diversity between domains and learning complex non-linear relationships among entities within and across domains.

We conduct extensive experiments in each of these settings using several real-world datasets and demonstrate the efficacy of the proposed models.

Microsoft teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_MWVhYWRkODUtZGI4OC00ZDZmLTk2NGMtZmViNTNiZmFmM2E3%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%229c3e2bfe-1b0f-4d7b-a589-832878069dc6%22%7d

Video Archive Go Top

 

Series: Department Seminar
Title: The Story of Arjun Guha, or: the Arc of a Research Project

  • Speaker: Shriram Krishnamurthi
                   Vice President for Programming Languages
                   Brown University
                   Providence, RI, USA
  • Date and Time: Saturday, August 21, 2021, 5:30 PM
  • Venue: Online on Zoom: https://brown.zoom.us/j/94769764745 Meeting ID: 947 6976 4745 at 5:30pm IST

Abstract
There are many ways to do research successfully, so you should take all advice with a pinch of salt. That said, I will try to describe some of the attributes that have worked well for my students and me. To make it concrete, I will use my former student, Arjun Guha, as a case study. I will strip away most of the technical detail while trying to retain the essential ideas, so people from any area of computer science will be able to follow almost all of it. Questions are welcome at any time. The talk will be followed by plenty of time for Q&A.

Speaker Bio:
Shriram is the Vice President for Programming Languages at Brown University in Providence, RI, USA. He is not, really, but thats what it says on his business card. At heart, he is a person of ill-repute: a Schemer, Racketeer, and Pyreteer. He believes tropical fruit are superior to all other kinds. He is terrified of success, because he may be forced to buy a suit. He is known to interrogate his audiences to ensure they are paying attention. So, be alert. You can read email later. On a more serious note: Shriram Krishnamurthi is a Professor in the Computer Science at Brown University. Shrirams research has cut across multiple disciplines ranging from Security, Networking, Formal Methods, and HCI, but always rooted firmly in programming language theory. Shriram has also made significant contributions to Computer Science education and outreach. Shriram is a recipient of SIGPLANs Robin Milner Young Researcher Award (2012), SIGSOFTs Influential Educator Award (2018), SIGPLANs Software Award (jointly in 2018), and Brown Universitys Wriston Fellowship. COMMUNICATIONS https://brown.zoom.us/j/94769764745 Meeting ID: 947 6976 4745 A few Zoom protocol recommendations: You are welcome to share video; the more people that do, the more it feels like we have a group of people rather than a sterile set of boxes. On the other hand, you are welcome to not share video for whatever reason (privacy, poor connection, etc.), which you dont have to explain or justify. Questions are WELCOME! However, I want to make sure everyone gets a fair chance to ask them. Therefore, to ask questions, please use the Raise Hand feature, and I will call on you. Please keep yourself muted, especially if you are in a noisy environment, unless you are asking a question. If you cant use audio, you are welcome to type questions. I will NOT be looking at the chat. Therefore, if you ask questions unbidden in chat, I wont see them. Please only type questions into chat once you ave been called on to ask (at which point I will look to see if there is one in chat). You can always type your questions offline and keep them handy to paste into chat.

Host Faculty: Prof. Deepak DSouza

Video Archive Go Top

 

Series: Theory Seminar
Title: A 3-Approximation Algorithm for Maximum Independent Set of Rectangles

  • Speaker: Dr. Arindam Khan
                   Assistant Professor
                   Department of Computer Science & Automation
                   Indian Institute of Science
                   Bengaluru, India.
  • Date and Time: Friday, August 20, 2021, 4:00 PM
  • Venue: Microsoft Teams - ON-LINE

Abstract
We study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overlapping rectangles of maximum cardinality. In a recent breakthrough, Mitchell [2021] obtained the first constant-factor approximation algorithm for MISR. His algorithm achieves an approximation ratio of 10 and it is based on a dynamic program that intuitively recursively partitions the input plane into special polygons called corner-clipped rectangles, without intersecting certain special horizontal line segments called fences.

In this work, we present a 3-approximation algorithm for MISR which is based on a similar recursive partitioning scheme. First, we use a partition into a more general class of axis-parallel polygons with constant complexity each, which allows us to provide an arguably simpler analysis and at the same time already improves the approximation ratio to 6. Then, using a more elaborate charging scheme and a recursive partitioning into general axis-parallel polygons with constant complexity, we improve our approximation ratio to 3. In particular, our partitioning uses more general fences that can be sequences of up to O(1) line segments each. This and our other new ideas may be useful for future work towards a PTAS for MISR.

For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/

Microsoft Teams Link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d

Host Faculty: Dr. Rahul Saladi

Video Archive Go Top

 

Series: M.Tech (Research) Thesis Defense
Title: nuKSM: NUMA-aware Memory De-duplication for Multi-socket Servers

  • Speaker: Akash Panda
  • Faculty Advisor: Arkaprava Basu
  • Date and Time: Tuesday, August 17, 2021, 2:30 PM
  • Venue: https://teams.microsoft.com/l/meetup-join/19%3ameeting_MzE5OGJmM2YtOWVhZC00YTM3LWJmMTEtZGZlZWM5YjFkZWE5%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%2282f39501-c5b2-4bfb-87c3-f17ca74c00b6%22%7d

Abstract
Teams meeting link: shorturl.at/jsAR9

Memory management is one of the most critical pieces in an operating system's design. It has several responsibilities ranging from ensuring quick access to data by applications to enabling memory consolidation. For example, judicious placement of pages in multi-socket NUMA (non-uniform memory access) servers could determine the access latencies experienced by an application. Similarly, memory de-duplication can play a pivotal role in memory consolidation and over-commitment.

Different responsibilities of memory management can conflict with each other. This often happens when different subsystems of an OS are responsible for different memory management goals, and each works in its silo. In this work, we report one such conflict that appears between memory de-duplication and NUMA management. Linux's memory de-duplication subsystem, namely KSM, is NUMA unaware. We demonstrate that memory de-duplication can have unintended consequences to NUMA overheads experienced by applications running on multi-socket servers. Linux's memory de-duplication subsystem, namely KSM, is NUMA unaware. Consequently, while de-duplicating pages across NUMA nodes, it can place de-duplicated pages in a manner that can lead to significant performance variations, unfairness, and subvert process priority.

We introduce NUMA-aware KSM, a.k.a., nuKSM, that makes judicious decisions about the placement of de-duplicated pages to reduce the impact of NUMA and unfairness in execution. nuKSM also enables users to avoid priority subversion. Finally, independent of the NUMA effect, we observed that KSM fails to scale well to large memory systems due to its centralized design. We thus extended nuKSM to adopt a decentralized design to scale to larger memory.

Speaker Bio:
Akash Panda is an M.Tech (Research) student who worked in the area of operating system's memory management for this thesis under the supervision of Arkaprava Basu.Currently, he is working in the Server Performance Group in AMD, Bangalore.

Host Faculty: Arkaprava Basu

Video Archive Go Top

 

Series: Theory Seminar
Title: Recent progress in online matching - Some open problems in online advertising

  • Speaker: Dr. Zhiyi Huang
                   Associate Professor
                   Department of Computer Science
                   University of Hong Kong
  • Date and Time: Friday, August 13, 2021, 11:00 AM
  • Venue: Microsoft Teams - ON-LINE

Abstract
Originated from the seminal work by Karp, Vazirani, and Vazirani (1990), online matching has been established as one of the most fundamental topics in the literature of online algorithms.

This is the second of two talks which presents the basics of online matching. The first talk focussed on General arrival models and todays talk will be looking at some Open problems in online advertising.

Open problems in online advertising: AdWords and Display Ads are generalizations of the online bipartite matching problem by Karp et al. These problems capture online advertising which generates tens of billions of US dollars annually. This year, we introduce a new technique called online correlated selection, and design the first online algorithms for the general cases of AdWords and Display Ads outperforming greedy, which has remained the state of the art for more than 10 years, despite many attempts to find better alternatives.

For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/

Microsoft Teams Link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d

Host Faculty: Dr. Arindam Khan

Video Archive Go Top

 

Series: Department Seminar
Title: What makes a good applied Data scientist?

  • Speaker: Dr. Mayur Datar
                   Chief Data Scientist
                   Flipkart, Bengaluru
  • Date and Time: Wednesday, August 11, 2021, 5:00 PM
  • Venue: Microsoft Teams - ONLINE

Abstract
In this talk, I will briefly cover the rise of Data Science as an applied field. I will borrow examples from e-commerce to demonstrate how Data Science gets used in real life. I will discuss a few recent trends in data science and how development life cycles are changing. Finally, I will share a few tips on what makes a good applied data scientist. I will make a case for a well rounded computer science education (sound fundamentals of computer systems, algorithm analysis and design) along with some cross disciplinary exposure as essential to succeed in this rapidly evolving area. There will be plenty of room for questions and looking forward to an interactive discussion.

Speaker Bio:
Mayur Datar works as a Chief Data Scientist with Flipkart in Bengaluru. He leads a large team of data scientists and together they are working on building the most advanced e-commerce landscape in India. Prior to joining Flipkart, Mayur worked for Google as a Research Scientist for over 12 years. At Google, Mayur led various projects namely Keyword Suggestion Tool for advertisers, Google Adwords Broad Matching and others. He & his teams were credited with working on projects which had a big impact on Googles bottom-line. Mayur has a doctorate in computer science from Stanford university and obtained his Bachelor of Technology from I.I.T. Bombay. He was awarded the President of India, Gold Medal for the -most outstanding student- of his graduating batch at I.I.T. Bombay. He has several publications which have been presented in renowned conferences like SIGMOD, VLDB, KDD, FOCS, SODA, WWW. He serves on the review committees for most of these conferences. He is known in the industry for his technical leadership, pragmatic result oriented machine learning & systems design and experience in internet consumer related challenges. His research interests include data-mining, algorithms, databases and computer science theory. Microsoft teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_YWNhNmRmNWQtM2Y4Ni00OWZkLWFhMmMtZDg2OTgwMTA4NTBi%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22c747ccaa-ceaa-4197-b4cb-ce2f1d4694da%22%7d

Host Faculty: Prof. Chiranjib Bhattacharyya

Video Archive Go Top

 

Series: Ph.D. (Engg.) Colloquium- ONLINE
Title: Near-Optimal Non-malleable Codes and Leakage Resilient Secret Sharing Schemes

  • Speaker: Ms. Sruthi Sekar
                   IntPh.D student
                   Dept. of C.S.A/Maths
  • Faculty Advisor: Prof. Manjunath Krishnapur / Prof. Bhavana Kanukurthi
  • Date and Time: Monday, August 09, 2021, 2:00 PM
  • Venue: Microsoft Teams - ON-LINE

Abstract
Non-malleable codes (NMCs) are coding schemes that help in protecting crypto-systems under tampering attacks, where the adversary tampers the device storing the secret and observes additional input-output behavior on the crypto-system. NMCs give a guarantee that such adversarial tampering of the encoding of the secret will lead to a tampered secret, which is either same as the original or completely independent of it, thus giving no additional information to the adversary. Leakage resilient secret sharing schemes help a party, called a dealer, to share his secret message amongst n parties in such a way that any t of these parties can combine their shares to recover the secret, but the secret remains hidden from an adversary corrupting < t parties to get their complete shares and additionally getting some bounded bits of leakage from the shares of the remaining parties.

For both these primitives, whether you store the non-malleable encoding of a message on some tamper-prone system or the parties store shares of the secret on a leakage-prone system, it is important to build schemes that output codewords/shares that are of optimal length and do not introduce too much redundancy into the codewords/shares. This is, in particular, captured by the rate of the schemes, which is the ratio of the message length to the codeword length/largest share length. The research goal of the thesis is to improve the state of art on rates of these schemes and get near-optimal/optimal rates.

In this talk, I will specifically focus on leakage resilient secret sharing schemes, describe the leakage model, and take you through the state of the art on their rates. Finally, I will present a recent construction of an optimal (constant) rate, leakage resilient secret sharing scheme in the so-called "joint and adaptive leakage model" where leakage queries can be made adaptively and jointly on multiple shares.

Microsoft teams link:

https://teams.microsoft.com/dl/launcher/launcher.html?url=%2F_%23%2Fl%2Fmeetup-join%2F19%3Ameeting_ZjBiZDE0ZjgtYzM3Mi00YmQ4LTllZjMtZGI4YjBlNDdkMmI2%40thread.v2%2F0%3Fcontext%3D%257b%2522Tid%2522%253a%25226f15cd97-f6a7-41e3-b2c5-ad4193976476%2522%252c%2522Oid%2522%253a%25220144d79c-31b7-4e38-a5c7-4aacd1276766%2522%257d%26anon%3Dtrue&type=meetup-join&deeplinkId=0be388dc-57e8-4798-bb75-8e604af5b680&directDl=true&msLaunch=true&enableMobilePage=true&suppressPrompt=true

Video Archive Go Top

 

Series: Theory Seminar
Title: Recent progress in online matching - General arrival models

  • Speaker: Dr. Zhiyi Huang
                   Associate Professor
                   Department of Computer Science
                   University of Hong Kong
  • Date and Time: Friday, August 06, 2021, 11:00 AM
  • Venue: Microsoft Teams - ON-LINE

Abstract
Originated from the seminal work by Karp, Vazirani, and Vazirani (1990), online matching has been established as one of the most fundamental topics in the literature of online algorithms. This is the first of two talks that presents the basics of online matching, and surveys the recent progress in two directions. Todays talk will be focussing on General arrival models and for the next talk, we will look at some Open problems in online advertising.

General arrival models

Traditional online matching models consider bipartite graphs and assume knowing one side of the bipartite graph upfront. The matching problems in many modern scenarios, however, do not fit into the traditional models. In the problem of matching ride-sharing requests, for instance, the graph is not bipartite in general, and all vertices arrive online. There has been much progress in the past three years on online matching models beyond the traditional ones, including the fully online model, the general vertex arrival model, and the edge arrival model.

For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/

Microsoft Teams Link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d

Host Faculty: Dr. Arindam Khan

Video Archive Go Top

 

Series: Theory Seminar
Title: Superpolynomial lower bounds against low-depth algebraic circuits

  • Speaker: Dr. Nutan Limaye
                   Associate Professor
                   Department of Computer Science and Engineering
                   Indian Institute of Technology, Bombay
  • Date and Time: Friday, July 30, 2021, 4:00 PM
  • Venue: Microsoft Teams - ON-LINE

Abstract
An algebraic circuit computes a polynomial using addition and multiplication operators. Understanding the power of algebraic circuits has close connections to understanding general computation. It is known that proving lower bounds for algebraic circuits can serve as a stepping stone towards proving general Boolean circuit lower bounds.

Despite this, not many lower bounds are known for even simple Sigma Pi Sigma (product-depth 1) circuits. Before our work, the best known lower bound for product-depth 1 circuit was (slightly less than) cubic. No lower bounds were known for general product-depth 2 circuits.

In this work, we show the first superpolynomial lower bound for low-product-depth algebraic circuits.

In the talk, we discuss the main results and present the proof ideas used in the proof of the superpolynomial lower bound for product-depth 1 circuits.

This talk is based on joint work with Srikanth Srinivasan and Sébastien Tavenas.

Microsoft Teams Link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d

Host Faculty: Dr. Anand Louis

Video Archive Go Top

 

Series: Department Seminar
Title: Network Anonymity, Privacy, (Anti-) Censorship and the Whole Nine Yards.

  • Speaker: Dr. Sambuddho Chakravarty
                   Assistant Professor
                   Department of Computer Science and Engineering
                   Indraprastha Institute of Information Technology (IIIT Delhi)
  • Date and Time: Friday, July 30, 2021, 2:00 PM
  • Venue: Microsoft teams - ONLINE: https://teams.microsoft.com/l/meetup-join/19%3ameeting_NjA3ZmM1ZDYtZTdjYi00NTZjLTgzNDUtZjRhNjJmZmNiMDdl%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%220432f3a0-d225-405c-b0f4-ff1ffaf4f1fd%22%7d

Abstract
In the second decade of the century (circa the Arab Springs of 2011), the Internet is the new battlefield where wars between politicians, media, (h)activists, lawyers and the military, shape the destiny of millions of people. Historically incepted as the ARPANET, it was engineered to serve as means of communication, even in the face of calamities and wars. Political will often plays antithetical to this very attribute. For instance, countries like China, Iran and UAE use (homebrewed) firewalling infrastructure to censor web traffic -- sometimes with the pretext of preserving cultural and religious values, at other times to prevent political dissent. No wonder a large body of network censorship measurements focuses on these two countries. While such countries are inherently (constitutionally) undemocratic, free speech over the Internet is, in recent years, being regularly suppressed even in democracies like India. Such evolutions are positioned on concerns otherwise paramount to the preservation of human rights -- e.g., policing child pornography. But state control of communication channels has been abuse to silence dissent, even in India where the supreme court deems freedom of speech on the Internet a fundamental right.

In this context, it is natural to ask how free and open is the Internet and how robust it is to censorship by countries like India, that in the recent years has evolved a sophisticated censorship infrastructure.

In this talk I present an overview our work over the years that has focussed on evolution of Indians Internet censorship infrastructure, how it censors traffic (and now apps.), how various ISPs implement it. Further, I also present some research efforts to evade censorship (and also Internet shutdowns/blackouts).

To begin with we consider the question of whether India might potentially follow the Chinese model and institute a single, government-controlled filter. Our research shows that would not be difficult, as the Indian Internet is quite centralized already. A few key ASes (~ 1% of Indian ASes, i.e. less than 4) and routers (<5000) collectively intercept approximately 95% of paths to the censored sites and to all publicly-visible DNS resolvers. Thereafter we conducted an extensive study (first of its kind) involving nine major ISPs of the country in terms of what kind of censorship techniques they use, what triggers them, their consistency and coverage, and how to evade them. Our results indicate a clear disparity among the ISPs, on how widely they install censorship infrastructure. As of 2021, we have extensively explored the evolution of web censorship (HTTPS) along with exactly how Chinese apps are being filtered in the country.

While existing solutions to evade censorship include proxies, VPNs, Tor have been designed primarily for web, while other applications like VoIP (real-time voice) are mostly ignored. As a part of our research we have extensively explored the feasibility of transporting real-time voice (mostly UDP) over Tor (that primarily supports TCP). Prior research deemed Tor to be unsuitable for such purposes. In our research we tried to identify how the interplay of network attributes (delay, jitter, bandwidth etc.) impact performance of VoIP. To our surprise the belief established from prior research seems unfounded.

However, all such solutions that rely on proxies are prone to being filtered by the ISPs, as these end-points are easily discoverable. Futuristic solutions like Decoy Routing, that rely on routers that could double as “smart proxies”, are resilient to such filtering. They have hitherto relied mostly on commodity servers, and involve wide scale traffic observation, inadvertently posing a threat to the privacy of users who do not require such services. To that end, we devised a SDN based DR solution, SiegeBreaker, that not only performs at line rates (comparable to native TCP) but also does not require inspection of all network flows, thus preserving the privacy of oblivious users. However, the deployability of such solutions remains a challenge, as it requires support from major top-tier ISPs.

A third alternative, combining the best of both the above solutions, involves tunnelling Internet traffic over that of various (semi-)real time applications, e.g. Instant Messaging (IM). To that end, we designed and tested a scheme, Camoufler, that utilizes IM channels as-is for transporting traffic. The scheme provides unobservability and good QoS, due to its inherent properties, such as low-latency message transports. Moreover, unlike Decoy Routing, it does not pose new deployment challenges. Performance evaluation of Camoufler, implemented on five popular IM apps indicate that it provides sufficient QoS for web browsing. E.g., the median time to render the homepages of Alexa top-1k sites was recorded to be about 3.6s, when using Camoufler implemented over Signal.

Finally, I would like to conclude the talk with our new system Dolphin, that emulates old school dial-up modems, sans the ISP support, to relay Internet traffic especially in the face of Internet shutdowns. Dolphins protocol recovers from the losses and errors introduced by the cellular voice medium, while also assuring end-to-end confidentiality. At low data rates (<=64bps), the errors are under 5% and suitable for supporting delay-tolerant applications with acceptable latencies. E.g. a 280 character tweet can be posted in about a minute.

Speaker Bio:
Sambuddho Chakravarty works as an Asst Prof. at the Department of Computer Science and Engineering Department of Indraprastha Institute of Information Technology (IIIT Delhi) since June 2014. He completed his PhD in Computer Science from Columbia University, New York, where he worked at the Network Security Lab (NSL) and was advised by Prof. Angelos D. Keromytis. His research is broadly related to network security and more specifically related to network anti-censorship, counter-surveillance, network anonymity and privacy (and all problems revolving around such systems e.g. network measurements, infrastructure etc.). He heads a small research lab at IIIT Delhi that involves ten students (mostly PhDs and B.tech students) and collaborates actively with other networks and systems security researchers in India and abroad. Microsoft teams link https://teams.microsoft.com/l/meetup-join/19%3ameeting_NjA3ZmM1ZDYtZTdjYi00NTZjLTgzNDUtZjRhNjJmZmNiMDdl%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%220432f3a0-d225-405c-b0f4-ff1ffaf4f1fd%22%7d

Host Faculty: Prof. Vinod Ganapathy

Video Archive Go Top

 

Series: M.Tech (Research) Colloquium- ONLINE
Title: Hadwigers conjecture and total coloring

  • Speaker: Mr. Ankur Naskar
                   M.Tech (Research) student
                   Dept. of CSA
  • Faculty Advisor: Prof. Sunil L Chandran
  • Date and Time: Wednesday, July 28, 2021, 4:00 PM
  • Venue: Microsoft Teams - ONLINE

Abstract
Hadwigers conjecture is one of the most important and long-standing conjectures in graph theory. It was established that proving Hadwigers conjecture is equivalent to proving the conjecture for the special class of graphs that can be expressed as the square of some other graph. However, it is difficult to prove Hadwigers conjecture even for the squares of highly specialised graph classes. We decided to investigate the squares of subdivided graphs (a subdivided graph is a graph that can be obtained from another graph $H$ by replacing each edge $uv$ of $H$ by a path $uwv$, where $w$ is a new vertex).

It turns out that squares of subdivided graphs are exactly the class of total graphs, well-studied in the context of the total coloring conjecture, another well-known and long-standing conjecture in graph theory. The total graph of $G$, denoted by $T(G)$, is defined on the vertex set $V(G)sqcup E(G)$ with $c_{1},c_{2}in V(G)sqcup E(G)$ adjacent whenever $c_{1}$ and $c_{2}$ are adjacent to or incident on each other in $G$. The total-chromatic number $chi(G)$ of a graph $G$ is defined to be equal to the chromatic number of its total graph. That is, $chi(G)=chi(T(G))$.

The total coloring conjecture or textit{TCC} states that for every graph $G$, $chi(G)leqDelta(G)+2$. Though Hadwigers conjecture was proved for the closely related class of line graphs 20 years ago itself, Hadwigers conjecture is not yet studied in the context of total graphs. In this thesis, the following results are proved: (i) There exists a constant $C$ such that, if the connectivity of $Ggeq C$, then Hadwigers conjecture is true for $T(G)$.

(ii) Let $mathcal{F}$ be a class of graphs that is closed under the operation of taking subgraphs. If a weaker version of the total coloring conjecture (weak textit{TCC}) namely, $chi(G)leqDelta(G)+3$, is true for the class $mathcal{F}$, then Hadwigers conjecture is true for the class ${T(G): Gin mathcal{F} }$. The second statement motivates one to look for classes of graphs that satisfy weak textit{TCC}. It may be noted that a complete proof of textit{TCC} for even $4$-colorable graphs (in fact even for planar graphs) has remained elusive even after decades of effort; but weak textit{TCC} can be proved easily for $4$-colorable graphs.

It was noticed that in spite of interest in studying $chi(G)$ in terms of $chi(G)$ right from the initial days, weak textit{TCC} is not proven to be true for $k$-colorable graphs even for $k=5$. In the latter half of the thesis, an important contribution to the total coloring literature is made by proving that $chi(G)leq Delta(G)+3$, for every $5$-colorable graph $G$. Being close to some of the well studied topics in total coloring, it seems that this is a long-pending addition to the literature.

Microsoft teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGMzMDhiNTItM2IwNS00MDZhLWI4Y2ItMThhMjkwN2M4YjNi%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22ed2e5ccd-b870-455c-862e-26e9ab1908be%22%7d

Video Archive Go Top

 

 

 

 

 

 

 

 

 

 

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