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

Retrieving relevant tweets corresponding to cultural events can be used in various applications like event reporting, event recommendation, etc. This type of retrieval is challenging due to short length of the tweet, noise, out of vocabulary words, abbreviations in the tweet. In this paper, we focus on the problem of retrieving relevant tweets related to given cultural event of a festival. We consider several factors like BM25, DFR, presence of artist name, relevant hashtag, festival name for finding the relevance of tweets to the event. We apply BM25 + DFR model to retrieve candidate set of tweets related to each event of a festival. We find the top hashtags for each event by exploring meta-attributes of an event. We re-rank the initial rank list from BM25 + DFR based on two strategies, namely, presence of the event meta-attributes (artist name, festival name, title, etc.) and the identified top hashtags in the tweet, and based on the timestamp of the event. We experimented on a subset of CLEF 2017 cultural microblog contextualization dataset. The experimental results show that the proposed method is able to put relevant tweets at the top of the retrieval list.

World University root node

CEUR Workshop Proceedings

IITH at CLEF 2017: Finding relevant tweets for cultural events

At present, news channels are using social media to disseminate news to a large audience. These news channels try to convey the news in such a way that attracts more user interaction in the form of views, likes, comments, and shares. In online news, one of the important factors in getting higher user interaction is to recommend the top news articles that would attract more number of users to give opinion, especially in the form of comments. When a news article starts getting many comments, it automatically attracts other readers to participate in the discussion. We say that a news article has “high-arousal” content if it can attract more number of comments from users. When a new news article is written it has no user interaction information, such as number of views, likes, shares or comments. In this paper, our aim is to predict news articles which have higher potential to generate high-arousal. In other words, they would attract a large number of users to give opinion in the form of comments. Unlike previous studies, we predict the arousal of news articles prior to their release, which brings the possibility of appropriate decision making to modify the article content or its ranking in audience newsfeed. We generate multiple features from the content of news articles and show that our best set of features can predict the arousal with an accuracy of 81%. We perform our experiments on social media page of CNN news channel, containing four years of data with 33,324 news articles and 226.83 million reactions. © 2017, Springer International Publishing AG.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Arousal prediction of news articles in social media

We investigate the value of parallel repetition of one-round games with any number of players k ≥ 2. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games. Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are connected in a certain sense. We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.

Leibniz International Proceedings in Informatics, LIPIcs

Multiplayer parallel repetition for expanding games

We consider the problem of embedding a finite set of points {x1, . . . , xn} 2 Rd that satisfy 22 triangle inequalities into 1, when the points are approximately low-dimensional. Goemans (unpublished, appears in [20]) showed that such points residing in exactly d dimensions can be embedded into 1 with distortion at most p d. We prove the following robust analogue of this statement: if there exists a r-dimensional subspacesuch that the projections onto this subspace satisfy P i,j2[n] kxi - xjk 22 (1) P i,j2[n] kxi - xjk 22 , then there is an embedding of the points into 1 with O(p r) average distortion. A consequence of this result is that the integrality gap of the well-known Goemans-Linial SDP relaxation for the Uniform Sparsest Cut problem is O(p r) on graphs G whose r-th smallest normalized eigenvalue of the Laplacian satisfies r(G)/n(1)SDP (G). Our result improves upon the previously known bound of O(r) on the average distortion, and the integrality gap of the Goemans-Linial SDP under the same preconditions, proven in [7, 6]. © Yuval Rabani and Rakesh Venkat.

Approximating sparsest cut in low rank graphs via embeddings from approximately low dimensional spaces

With ever increasing number of publication venues and research topics, it is becoming difficult for users to find out topics of interest for conferences or research areas. Although we have many popular topic modeling techniques, we still find that conferences are listing their topics of interest using a manual approach. Topics that are generated by existing topic modeling algorithms are good for text categorization, but they are not ideal for displaying to users because they generate topics that are not so readable and are often redundant. In this paper, we propose a novel technique to generate topics of interest using association mining and natural language processing. We show that the topics of interest that are generated by our technique is much more similar to manually written topics of interest compared to existing topic modeling algorithms. Our results show that the proposed method generates meaningful, interpretable topics, and leads to 13.9% higher precision than existing techniques. © Springer International Publishing AG 2017.

Generating topics of interests for research communities

Transactional memory promises to make concurrent programming tractable and efficient by allowing the user to assemble sequences of actions in atomic transactions with all-or-nothing semantics. It is believed that, by its very virtue, transactional memory must ensure that all committed transactions constitute a serial execution respecting the real-time order. In contrast, aborted or incomplete transactions should not “take effect.” But what does “not taking effect” mean exactly? It seems natural to expect that aborted or incomplete transactions do not appear in the global serial execution, and, thus, no committed transaction can be affected by them. We investigate another, less obvious, feature of “not taking effect” called non-interference: aborted or incomplete transactions should not force any other transaction to abort. In the strongest form of non-interference that we explore in this paper, by removing a subset of aborted or incomplete transactions from the history, we should not be able to turn an aborted transaction into a committed one without violating the correctness criterion. We show that non-interference is, in a strict sense, not implementable with respect to the popular criterion of opacity that requires all transactions (be they committed, aborted or incomplete) to witness the same global serial execution. In contrast, when we only require local correctness, non-interference is implementable. Informally, a correctness criterion is local if it only requires that every transaction can be serialized along with (a subset of) the transactions committed before its last event (aborted or incomplete transactions ignored). We give a few examples of local correctness properties, including the recently proposed criterion of virtual world consistency, and present a simple though efficient implementation that satisfies non-interference and local opacity. © 2016 Elsevier B.V.

Theoretical Computer Science

Non-interference and local correctness in transactional memory

We give algorithms with running time 2O(√κ log κ)· nO(1) for the following problems. Given an n-vertex unit disk graph G and an integer k, decide whether G contains a path on exactly/at least k vertices, a cycle on exactly κ vertices, a cycle on at least k vertices, a feedback vertex set of size at most k, and a set of κ pairwise vertex-disjoint cycles. For the first three problems, no subexponential time parameterized algorithms were previously known. For the remaining two problems, our algorithms significantly outperform the previously best known parameterized algorithms that run in time 2O(κ0.75 log κ)· nO(1). Our algorithms are based on a new kind of tree decompositions of unit disk graphs where the separators can have size up to kO(1) and there exists a solution that crosses every separator at most O(√κ) times. The running times of our algorithms are optimal up to the log k factor in the exponent, assuming the Exponential Time Hypothesis. © Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi.

Finding, hitting and packing cycles in subexponential time on unit disk graphs

The b-chromatic number of a graph G, χb(G), is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other color classes. In the b-CHROMATIC NUMBER problem, the objective is to decide whether χb(G)≥k. Testing whether χb(G)=Δ(G)+1, where Δ(G) is the maximum degree of a graph, itself is NP-complete even for connected bipartite graphs (Kratochvíl, Tuza and Voigt, WG 2002). We show that b-CHROMATIC NUMBER is W[1]-hard when parameterized by k, resolving the open question posed by Havet and Sampaio (Algorithmica 2013). When k=Δ(G)+1, we design an algorithm for b-CHROMATIC NUMBER running in time 2°(k2log⁡k)n°(1). Finally, we show that b-CHROMATIC NUMBER for an n-vertex graph can be solved in time O(3nn4log⁡n). © 2016 Elsevier Inc.

Journal of Computer and System Sciences

On the parameterized complexity of b-CHROMATIC NUMBER

In the mixed dominating set (mds) problem, we are given an n-vertex graph G and a positive integer k, and the objective is to decide whether there exists a set S⊆ V(G) ∪ E(G) of cardinality at most k such that every element x∈ (V(G) ∪ E(G)) \ S is either adjacent to or incident with an element of S. We show that mds can be solved in time 7. 465 knO ( 1 ) on general graphs, and in time 2O(k)nO(1) on planar graphs. We complement this result by showing that mds does not admit an algorithm with running time 2 o ( k )nO ( 1 ) unless the Exponential Time Hypothesis (ETH) fails, and that it does not admit a polynomial kernel unless coNP ⊆ NP/ poly. In addition, we provide an algorithm which, given a graph G together with a tree decomposition of width tw, solves mds in time 6 twnO ( 1 ). We finally show that unless the Set Cover Conjecture (SeCoCo) fails, mds does not admit an algorithm with running time O((2 - ϵ) tw ( G )nO ( 1 )) for any ϵ&gt; 0, where tw(G) is the tree-width of G. © 2017, Springer International Publishing AG.

Mixed dominating set: A parameterized perspective

Performance of chip multiprocessors (CMPs) heavily depends on the efficiency of the caches. There is still a large gap between implemented replacement policies and the theoretical optimal policy. Among other factors, replacement policies play a major role in deciding the memory access time as they directly affect the miss-rate. In a CMP environment, the cost incurred by a miss in the higher level cache needs to take into account the communication latency over the on-chip network as well as power consumption.There are existing replacement policies which use this misscost rather than miss-count as an optimisation factor. These existing policies targeting the optimisation of miss-cost are mainly designed for the Last-Level Caches (LLC). Due to their significant hardware overheads, these policies are not directly applicable for the L1 caches. In this paper, we propose a new replacement policy, LA-LRU, for L1 caches which uses communication latency as a factor in deciding the victim. Experimental evaluation on full system simulation shows 7.4% improvement in Average Memory Access Time (AMAT) which leads to 7% improvement in Cycles Per Instruction (CPI). Reduction in on-chip communication also helps in improving the on-chip network power consumption by 14.8%. © 2017 IEEE.