Department of Computer Science and Engineering

Indian Institute of Technology Hyderabad (IITH) is a premier institute of science and technology established in 2008. IITH has been consistently ranked in the&nbsp;<a href="https://iith.ac.in/reports/" rel="noopener noreferrer">top 10 institutes</a>&nbsp;in India for Engineering&nbsp;<a href="https://www.nirfindia.org/2021/EngineeringRanking.html" rel="noopener noreferrer" target="_blank">according to NIRF</a>&nbsp;making it one of the most coveted schools for science and technology in the country.

IITH offers&nbsp;<a href="https://iith.ac.in/academics/under-graduate/">undergraduate programs</a>&nbsp;in all the classical engineering disciplines, applied sciences, design, as well as several modern interdisciplinary areas. Students are given a flexibility to explore a broad set of areas, and potentially pursue a minor or double major in a discipline that is not their own. Students who wish to seek a deeper understanding of their own discipline are strongly encouraged to get involved in cutting-edge research with the help of a faculty to mentor them, and earn an Honors in their own field.

The very foundation of IIT Hyderabad is based on&nbsp;<a href="https://iith.ac.in/research/">research and innovation</a>. The vibrant research culture is evident from the number of patents and publications that IITH produces consistently every year. IITH offers&nbsp;<a href="https://iith.ac.in/academics/programmes-offered/">graduate programs</a>&nbsp;at both a masters, and a doctoral level, in several diverse areas. There are separate programs for technology, design, science, and liberal arts. The&nbsp;<a href="https://iith.ac.in/academics/post-graduate/">MTech program</a>&nbsp;is offered in various modes and durations to cater to the ever-growing need of postgraduate level professionals in the country.

IITH encourages and supports&nbsp;<a href="https://iic-iith.netlify.app/index.html" rel="noopener noreferrer" target="_blank">innovation and entrepreneurship</a>&nbsp;at every stage. The minor program in entrepreneurship is open to all students of IITH, and many of the courses are offered by industrialists who are entrepreneurs themselves. There are various&nbsp;<a href="https://iith.ac.in/research/centres-incubators/">innovation centers and incubators</a>&nbsp;that promote entrepreneurship and help mentor young innovators. IITH has been very successful in building tie-ups with leading academic institutions around the globe.

IITH enjoys a very special relationship with Japanese universities and industries that goes beyond academic and research collaborations. In fact, some of the iconic buildings in IITH campus will carry the signature of Japanese architecture.

IITH creates a unique holistic ecosystem for education that offers interactive learning, a very flexible academic structure, cutting-edge research, strong industry collaboration, and entrepreneurship. This is an environment which enables students and faculty to translate their dreams into realities.

IIT Hyderabad

Let L = {a1/b1,..., as/bs }, where for every i ε [s], ai/bi ε [0, 1) is an irreducible fraction. Let F = {A1,..., Am} be a family of subsets of [n]. We say F is a fractional Lintersecting family if for every distinct i, j ε [m], there exists an a b ε L such that |Ai ∩ Aj| ε {a/b |Ai|, a/b |Aj|}. In this paper, we introduce and study the notion of fractional L-intersecting families. © The authors.

World University root node

Fulltext

Electronic Journal of Combinatorics

Fractional L-intersecting families

In this paper, we propose an efficient concurrent wait-free algorithm to construct an unbounded directed graph for shared memory architecture. To the best of our knowledge that this is the first wait-free algorithm for an unbounded directed graph where insertion and deletion of vertices and/or edges can happen concurrently. To achieve wait-freedom in a dynamic setting, threads help each other to perform the desired tasks using operator descriptors by other threads. We also prove that all graph operations are wait-free and linearizable. We implemented our algorithms in C++ and tested its performance through several micro-benchmarks. Our experimental results show an average of 9x improvement over the global lock-based implementation. © 2019 IEEE.

Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019

An efficient practical concurrent wait-free unbounded graph

In this paper, we propose an enhanced Automatic Checkpointing and Partial Rollback (CaPR++) algorithm to realize Software Transactional Memory (STM), that employs partial rollback mechanism for conflict resolution. We have comparatively evaluated the “Abort” and “Partial Rollback” mechanisms for STMs. For purposes of comparison, we have used the state-of-the-art RSTM system and for the “Partial Rollback”, and we have used our earlier CaPR+ algorithm that has been enhanced for our requirements. Note that we have enriched the STAMP benchmarks with varied delayed transaction times. The results obtained demonstrate the effectiveness of the Partial Rollback mechanism over pure abort mechanisms for applications consisting of large transaction delays, with up to 1.6x performance gain for applications with large transactional delays. Our study makes the case for a hybrid system of pure aborts and partial rollbacks, which can extract the benefits of both mechanisms. Keeping in line with our study, we have proposed a hybrid implementation where some of the transactions of an application subscribe to abort mechanisms and the rest to partial rollback. Our initial implementation demonstrates various scenarios where the hybrid approach outperforms the pure abort and partial rollback approaches. © 2018 John Wiley & Sons, Ltd.

Concurrency and Computation: Practice and Experience

STMs in practice: Partial rollback vs pure abort mechanisms

ACM International Conference Proceeding Series

Welcome message from ICDCN 2019 workshop program co-chairs

The notion of stability is the foundation of several classic problems in economics and computer science that arise in a wide-variety of real-world situations, including Stable Marriage, Stable Roommate, Hospital Resident and Group Activity Selection. We study this notion in the context of barter exchange markets. The input of our problem of interest consists of a set of people offering goods/services, with each person subjectively assigning values to a subset of goods/services offered by other people. The goal is to find a stable transaction, a set of cycles that is stable in the following sense: there does not exist a cycle such that every person participating in that cycle prefers to his current “status”. For example, consider a market where families are seeking vacation rentals and offering their own homes for the same. Each family wishes to acquire a vacation home in exchange of its own home without any monetary exchange. We study such a market by analyzing a stable transaction of houses involving cycles of fixed length. The underlying rationale is that an entire trade/exchange fails if any of the participating agents cancels the agreement; as a result, shorter (trading) cycles are desirable. We show that given a transaction, it can be verified whether or not it is stable in polynomial time, and that the problem of finding a stable transaction is NP-hard even if each person desires only a small number of other goods/services. Having established these results, we study the problem of finding a stable transaction in the framework of parameterized algorithms. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.

Autonomous Agents and Multi-Agent Systems

Stability in barter exchange markets

Bidimensionality is the most common technique to design subexponential-time parameterized algorithms on special classes of graphs, particularly planar graphs. The core engine behind it is a combinatorial lemma of Robertson, Seymour and Thomas that states that every planar graph either has a k × k-grid as a minor, or its treewidth is O(k). However, bidimensionality theory cannot be extended directly to several well-known classes of geometric graphs like unit disk or map graphs. This is mainly due to the presence of large cliques in these classes of graphs. Nevertheless, a relaxation of this lemma has been proven useful for unit disk graphs. Inspired by this, we prove a new decomposition lemma for map graphs, the intersection graphs of finitely many simply-connected and interior-disjoint regions of the Euclidean plane. Informally, our lemma states the following. For any map graph G, there exists a collection (U1,..., Ut) of cliques of G with the following property: G either contains a k × k-grid as a minor, or it admits a tree decomposition where every bag is the union of O(k) cliques in the above collection. The new lemma appears to be a handy tool in the design of subexponential parameterized algorithms on map_ graphs. We demonstrate its usability by designing algorithms on map graphs with running time 2O(k log k) · nO(1) for Connected Planar F-Deletion (that encompasses problems such as Feedback Vertex Set and Vertex Cover). Obtaining subexponential algorithms for Longest Cycle/Path and Cycle Packing is more challenging. We have to construct tree decompositions with more powerful properties and to prove sublinear bounds on the number of ways an optimum solution could “cross” bags in these decompositions. For Longest Cycle/Path, these are the first subexponential-time parameterized algorithm on map graphs. For Feedback Vertex Set and Cycle Packing, we improve upon known 2O(k0.75 log k) · nO(1)-time algorithms on map graphs. © Graham Cormode, Jacques Dark, and Christian Konrad; licensed under Creative Commons License CC-BY

Leibniz International Proceedings in Informatics, LIPIcs

Decomposition of map graphs with applications

Given a graph G and a pair (F1, F2) of graph families, the function GDISJG, F1, F2 takes as input, two induced subgraphsG1 andG2 ofG, such thatG1 ∈ F1 andG2 ∈ F2 and returns 1 ifV(G1) ∩ V(G2) = ∅ and 0 otherwise. We study the communication complexity of this problem in the two-party model. In particular, we look at pairs of hereditary graph families. We show that the communication complexity of this function, when the two graph families are hereditary, is sublinear if and only if there are finitely many graphs in the intersection of these two families. Then, using concepts from parameterized complexity, we obtain nuanced upper bounds on the communication complexity of GDISJG, F1, F2. A concept related to communication protocols is that of a (F1, F2)-separating family of a graph G. A collection F of subsets of V(G) is called a (F1, F2)-separating family for G, if for any two vertex disjoint induced subgraphs G1 ∈ F1,G2 ∈ F2, there is a set F ∈ F with V(G1) ⊆ F andV(G2) ∩ F = ∅. Given a graphG onn vertices, for any pair (F1, F2) of hereditary graph families with sublinear communication complexity for GDISJG, F1, F2, we give an enumeration algorithm that finds a subexponential sized (F1, F2)-separating family. In fact, we give an enumeration algorithm that finds a 2o(k)nO(1) sized (F1, F2)-separating family, where k denotes the size of a minimum sized set S of vertices such that V(G) \ S has a bipartition (V1,V2) with G[V1] ∈ F1 and G[V2] ∈ F2. We exhibit a wide range of applications for these separating families, to obtain combinatorial bounds, enumeration algorithms, as well as exact and FPT algorithms for several problems. © 2019 Association for Computing Machinery.

ACM Transactions on Computation Theory

Communication complexity and graph families

We give a new decomposition theorem in unit disk graphs (UDGs) and demonstrate its applicability in the fields of Structural Graph Theory and Parameterized Complexity. First, our new decomposition theorem shows that the class of UDGs admits a Contraction Decomposition Theorem. Prior studies on this topic exhibited that the classes of planar graphs [Klein, SICOMP, 2008], graphs of bounded genus [Demaine, Hajiaghayi and Mohar, Combinatorica 2010] and H-minor free graphs [Demaine, Hajiaghayi and Kawarabayashi, STOC 2011] admit a Contraction Decomposition Theorem. Even bounded-degree UDGs can contain arbitrarily large cliques as minors, therefore our result is a significant advance in the study of contraction decompositions. Additionally, this result answers an open question posed by Hajiaghayi (www.youtube.com/watch?v=2Bq2gy1N01w) regarding the existence of contraction decompositions for classes of graphs beyond H-minor free graphs. Second, we present a “parameteric version” of our new decomposition theorem. We prove that there is an algorithm that given a UDG G and a positive integer k, runs in polynomial time and outputs a collection of O(k) tree decompositions of G with the following properties. Each bag in any of these tree decompositions can be partitioned into O(k) connected pieces (we call this measure the chunkiness of the tree decomposition). Moreover, for any subset S of at most k edges in G, there is a tree decomposition in the collection such that S is well preserved in the decomposition in the following sense. For any bag in the tree decomposition and any edge in S with both endpoints in the bag, either its endpoints lie in different pieces or they lie in a piece which is a clique. Having this decomposition at hand, we show that the design of parameterized algorithms for some cut problems becomes elementary. In particular, our algorithmic applications include single-exponential (or slightly super-exponential) algorithms for well-studied problems such as Min Bisection, Steiner Cut, s-Way Cut, and Edge Multiway Cut-Uncut on UDGs; these algorithms are substantially faster than the best known algorithms for these problems on general graphs. Copyright © 2019 by SIAM

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity

Advancements in CMOS technology led to the increase in number of processing cores on a single chip. Communication between different cores in such multicore systems is facilitated by an underlying interconnect. Due to the limitations of traditional bus-based system Network on Chip (NoC) based interconnect is the most acceptable cost effective framework for inter-core communication. A packet in an NoC travels through a sequence of intermediate routers before arriving at its destination. As the size of NoC scales high, the average number of intermediate routers that a packet traverse also increases. This results in higher packet latency which degrades application performance. In this work, we introduce cost effective adaptive routing techniques that can forward long distance packets through specialized channels made of Transmission Line (TL). These extra TLs introduced in the chip reduce the diameter of the network thereby reducing average packet latency. We propose two novel router architectures; SBTR and e-SBTR that reduce packet latency by reducing the number of intermediate hops. We use PARSEC benchmark and SPEC CPU 2006 benchmark mixes to evaluate the performance of our proposed techniques. SBTR and e-SBTR reduce average packet latency by 7.9% and 25% respectively. Both the techniques also reduce average hop count by 8.13% and 27.6% respectively. We also observe that our proposed technique e-SBTR performs better than the state-of-the-art Express Virtual Channel technique in terms of packet latency and hop count respectively. © 2018 Elsevier Inc.

Journal of Parallel and Distributed Computing

Cost effective routing techniques in 2D mesh NoC using on-chip transmission lines

The spread of rumours on a social event affects the propagation of true information regarding the event. Separating a rumour from an informative post is of great importance nowadays because posts which contain rumours, try to provide an information which sounds similar to the actual happening. Rumour detection in social media can be treated as a text classification problem. However, the problem involves several challenges. Both rumours and non-rumours may contain a similar form of textual items like words, sentences etc. about an actual happening. The context and way of representing those textual items make a rumour different from a non-rumour post. In our work, we show that in many such cases, standard ways of feature construction does not always capture these patterns. Therefore, we propose a novel approach of feature construction by reweighting the TF-IDF score of some particular terms taking into account the label information of training data. This leads to a better construction of features than the standard TF-IDF representation leading to a more separable set of features. A classffier with TF-IDF boosted features performs better than the combination of standard TF-IDF and state-of-the-art machine learning algorithms using standard TF-IDF score like LightGBM, Gradient Boosting, SVM etc. This is experimentally validated on three different social events which created rumours. We also show that our model gives a comparable performance to a deep learning model like LSTM with Glove word embedding in a much lesser training time, making our model a convenient one for detecting rumours at an early stage. © 2019 IEEE.