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

The problem of computing the vertex expansion of a graph is an NP-hard problem. The current best worst-case approximation guarantees for computing the vertex expansion of a graph are a O log n-approximation algorithm due to Feige et al. [16], and O OPT log d bound in graphs having vertex degrees at most d due to Louis et al. [29]. We study a natural semi-random model of graphs with sparse vertex cuts. For certain ranges of parameters, we give an algorithm to recover the planted sparse vertex cut exactly. For a larger range of parameters, we give a constant factor bi-criteria approximation algorithm to compute the graph's balanced vertex expansion. Our algorithms are based on studying a semidefinite programming relaxation for the balanced vertex expansion of the graph. In addition to being a family of instances that will help us to better understand the complexity of the computation of vertex expansion, our model can also be used in the study of community detection where only a few nodes from each community interact with nodes from other communities. There has been a lot of work on studying random and semi-random graphs with planted sparse edge cuts. To the best of our knowledge, our model of semi-random graphs with planted sparse vertex cuts has not been studied before. © 2018 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

World University root node

Leibniz International Proceedings in Informatics, LIPIcs

Semi-random graphs with planted sparse vertex cuts: Algorithms for exact and approximate recovery

User feedback in the form of customer reviews, blogs, and forum posts is an essential feature of e-commerce. Users often read online product reviews to get an insight into the quality of various aspects of a product. Besides, users have different aspect preferences, and they look for reviews that contain relevant information regarding their preferred aspect(s). However, as reviews are unstructured and voluminous, it becomes exhaustive and laborious for users to find relevant reviews. Lack of domain knowledge about various aspects and sub-aspects of a product, and how they are related to each other, also add to the problem. Although this information could be there in product reviews, it is not easy for users to spot it instantly from the reviews. This paper seeks to address the above problems and presents two novel algorithms that summarize product reviews, and provides an interactive search interface, similar to popular faceted navigation. We solve the problem by creating an aspect ontology tree with high aspect extraction precision. © 2018 Elsevier B.V.

Electronic Commerce Research and Applications

Aspect ontology based review exploration

In the UNDIRECTED EULERIAN EDGE DELETION problem, we are given an undirected graph and an integer k, and the objective is to delete k edges such that the resultant graph is a connected graph in which all the vertices have even degrees. The corresponding problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same in-degree as its out-degree is called DIRECTED EULERIAN EDGE DELETION. In this paper, using the technique of computing representative families of co-graphic matroids we design algorithms which solve these problems in time 2O(k)nO(1), improving the algorithms by Cygan et al. [Algorithmica, 2014] and affirmatively answer the open problem posed by them. The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid. © 2018 Elsevier Inc.

Fulltext

Journal of Computer and System Sciences

Finding even subgraphs even faster

For a graph G, a set D ⊆ V (G) is called a [1, j]-dominating set if every vertex in V (G) \ D has at least one and at most j neighbors in D. A set D ⊆ V (G) is called a [1, j]-total dominating set if every vertex in V (G) has at least one and at most j neighbors in D. In the [1, j]-(Total) Dominating Set problem we are given a graph G and a positive integer k. The objective is to test whether there exists a [1, j]-(total) dominating set of size at most k. The [1, j]-Dominating Set problem is known to be NP-complete, even for restricted classes of graphs such as chordal and planar graphs, but polynomial-time solvable on split graphs. The [1, 2]-Total Dominating Set problem is known to be NP-complete, even for bipartite graphs. As both problems generalize the Dominating Set problem, both are W[1]-hard when parameterized by solution size. In this work, we study [1, j]-Dominating Set on sparse graph classes from the perspective of parameterized complexity and prove the following results when the problem is parameterized by solution size: [1, j]-Dominating Set is W[1]-hard on d-degenerate graphs for d = j + 1; [1, j]-Dominating Set is FPT on nowhere dense graphs. We also prove that the known algorithm for [1, j]-Dominating Set on split graphs is optimal under the Strong Exponential Time Hypothesis (SETH). Finally, assuming SETH, we provide a lower bound for the running time of any algorithm solving the [1, 2]-Total Dominating Set problem parameterized by pathwidth. © M. Alambardar Meybodi, F. Fomin, A. E. Mouawad, and F. Panolan.

On the parameterized complexity of [1, J]-domination problems

In this paper, we present TRAFAN, a system to analyze traffic activities of various cities in India. Traffic information is publicly available on various social networking sites. We aim to analyze the transportation data moving through the most popular social networking site Facebook. We take the data from various Facebook traffic pages as input to our system. Our system performs three important functions: fast browsing through keyword search result, compare Facebook pages and get statistical summaries about the Facebook pages. Our system can assist the government organizations to know the most chaotic traffic issue in a city. Organizations can retrieve all the problems in a city related to a traffic issue. The system also allows to compare the severity of an issue across the cities. We perform our experiment on Facebook pages containing 21,000 posts and 0.5 million reactions. We show through experimental results that our system effectively analyzes the traffic activities of cities. We present the results using information visualization techniques to improve the usability of our proposed TRAFAN interface. © 2018 IEEE.

2018 10th International Conference on Communication Systems and Networks, COMSNETS 2018

TRAFAN: Road traffic analysis using social media web pages

Tax evasion is committed in a number of ways, in which, some are easily identifiable while few others are very difficult to detect. This article deals with a sophisticated technique used by tax-evaders known as circular trading. Dealers who commit this fraud often collude together and make bogus companies using fraudulent identities with the motivation to show heavy sales transaction among them. This huge quantity of data from transactions helps the dealers to hide their actual tax manipulation. Here, we devise clustering techniques that detects and groups together the dealers who are highly susceptible in performing circular trading. We represented the entire sales database for these dealers using weighted directed graphs. The clustering algorithm is run on the commercial tax dataset provided by the state government of Telangana, India, which helped in identifying potential circular trading activities. © Springer Nature Switzerland AG 2019.

Advances in Intelligent Systems and Computing

Clustering collusive dealers in commercial taxation system

Radio level integration (RLI) architectures such as LTE Wi-Fi aggregation (LWA) and LTE Wi-Fi integration with IPSec tunnel (LWIP) are gaining momentum in the context of Multiple Radio Access Technology (Multi-RAT) connectivity in 5G. It is unclear whether a transport layer solution like Multipath TCP (MPTCP) could serve better in aggregating multiple RATs than radio level aggregation, Or are these two different solutions complementing each other? In this paper, we address these questions by experimenting on a testbed. LWA testbed has been set up using OpenAirInterface (OAI) LTE base station and off-the-shelf Wi-Fi Access Point (AP). We present interesting outcomes of various experiments which can be adopted as design principles for developing 5G Multi-RAT architectures. Our findings include, (i) LWA fails to aggregate link capacities when there is congestion in the network, and (ii) Co-operative MPTCP and LWA solution is robust and achieves significant performance improvement compared to individual LWA and MPTCP, even when the network is congested and Wi-Fi channel contention is high. © 2018 Association for Computing Machinery.

Proceedings of the Annual International Conference on Mobile Computing and Networking, MOBICOM

A framework for integrating MPTCp over LWA - A testbed evaluation

Stochastic geometry has been used in the literature to develop amenable models to delineate and apprehend the performance of wireless networks. In this paper, we develop a tractable and flexible model for heterogeneous wireless networks consisting of tightly coupled long-term evolution (LTE) Small cell eNodeBs (SeNBs) and wireless fidelity (Wi-Fi) access points (APs). We leverage stochastic geometry to characterize the key performance metrics of LTE-Wi-Fi Aggregation (LWA) system. The positions for SeNBs and APs are modeled as two independent homogeneous Poisson Point Processes (PPPs) in a non co-located LWA scenario. Enabling LWA operation with arbitrary number of Wi-Fi APs in a given region may not ensure maximum rate and coverage. Hence we propose a scheme, InterfereNCe Aware matéRN hArd-core poinT procEss (INCARNATE) to increase the performance of LWA system by allowing LWA operation with a chosen set of Wi-Fi APs. We derive Signal-to-Interference-plus-Noise Ratio (SINR) distribution of UE which is associated to SeNB, AP or LWA. INCARNATE is modelled as a modified Matérn Hard-Core Point Process (MHCPP). This further helps to find joint coverage probability and average data rate over the network. We then verify the accuracy of the analytical results with empirical outcomes. INCARNATE scheme outperforms the traditional MHCPP scheme by 73% and 17% in terms of data rate and coverage probability, respectively. Similarly, LWA with INCARNATE scheme excels by 51% and 6.23% as compared to regular LWA in terms of data rate and coverage probability, respectively. © 2018 IEEE.

INCARNATE: An interference aware spatial scheme for tightly coupled LTE-Wi-Fi networks

Recently, the use of LTE in the unlicensed spectrum has gained a lot of attention to address bandwidth crunch. Due to restriction on the transmission power in the unlicensed spectrum, LTE-U/LAA cells will get deployed mostly inside residential and office buildings to provide high data rates for indoor User Equipments (UEs). The UEs with high Signal-To-Interference plus Noise Ratio (SINR) experience good throughput, but the SINR decreases significantly due to walls and other obstacles that are present in the communication path. The coverage difference of licensed and unlicensed spectrum leads to different SINRs so, efficient placement of LAA Base Stations (BSS) inside the buildings is very crucial for attaining desirable SINR for the indoor UEs. Our primary objective is to find the optimal number of LAA/LTE-U BSS with minimum SINR requirements in the unlicensed band, and the secondary objective is to maximize the minimum SINR inside the building in the licensed band with power control. To do this, we formulate an optimization model (MinLF) to find the minimum number of LAA/LTE-U BSS along with their positions in indoor scenarios which resulted in Mixed Integer Linear Programming (MILP) problem. Further, to maximize the minimum SINR in the licensed spectrum, we formulate MinLPower model to find the optimal transmission power of each LTE-U/LAA cell inside the building which resulted in Mixed Integer Non-Linear Programming (MINLP) problem. Our proposed models achieve optimal placement with a maximum energy saving of 88% compared to the maximum power scheme. © 2018 ACM. 978-1-4503-6372-3/18/01. . . $15.00.

ACM International Conference Proceeding Series

On placement of LAA/LTE-u base stations in heterogeneous wireless networks

The ambitious goals of Fifth Generation (5G) mobile networks for higher system capacity, massive number of devices and flexibility in operations demand the network architecture to be much more flexible, efficient and autonomous. The design of Radio Access Network (RAN) is undergoing architectural transformations to increase the flexibility of deployment and programmability by leveraging Network Functions Virtualization (NFV), Software Defined Networking (SDN), and Cloud Computing. Hence, efficient resource management strategies with enhanced service quality play a vital role in realizing true benefits of 5G RAN. In this work, we propose a novel and dynamic resource management framework called «KORA» for 5G Cloud Radio Access network (C-RAN) considering spatio-temporal traffic heterogeneity exhibited at Remote Radio Units (RRUs). To minimize net energy consumption in the cloud data center and to maximize the service quality to end users, we formulate an Integer Linear Programming model (ILP) for KORA that performs efficient consolidation and relocation of Control Units (CUs) in 5G C-RAN. To alleviate the computational heaviness of the ILP optimization model, we propose a light-weight heuristic algorithm that is scalable and applicable to real-world dense deployments spanning a large set of CUs. By simulations, we compare and contrast between various distinctive features of 5G C-RAN architecture under study as well as evaluate the efficacy of our proposed KORA framework. The heuristic algorithm can save 27% of relocations and 33% of GBR flows from disruption, at increased energy consumption of 6.6% in data center as compared to KORA. © 2018 IEEE.