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

Given an undirected graph, a conflict-free coloring (CFON*) is an assignment of colors to a subset of the vertices of the graph such that for every vertex there exists a color that is assigned to exactly one vertex in its open neighborhood. The minimum number of colors required for such a coloring is called the conflict-free chromatic number. The decision version of the CFON* problem is NP-complete even on planar graphs. In this paper, we show the following results. The CFON* problem is fixed-parameter tractable with respect to the combined parameters clique width and the solution size.We study the problem on block graphs and cographs, which have bounded clique width. For both graph classes, we give tight bounds of three and two respectively for the CFON* chromatic number.We study the problem on the following intersection graphs: interval graphs, unit square graphs and unit disk graphs. We give tight bounds of two and three for the CFON* chromatic number for proper interval graphs and interval graphs. Moreover, we give upper bounds or the CFON* chromatic number on unit square and unit disk graphs.We also study the problem on split graphs and Kneser graphs. For split graphs, we show that the problem is NP-complete. For Kneser graphs K(n, k), when n≥ k(k+ 1 )2+ 1, we show that the CFON* chromatic number is k+ 1. We also study the closed neighborhood variant of the problem denoted by CFCN*, and obtain analogous results in some of the above cases. © 2021, Springer Nature Switzerland AG.

World University root node

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

Conflict-Free Coloring: Graphs of Bounded Clique Width and Intersection Graphs

Due to the wide adoption of social media platforms like Facebook, Twitter, etc., there is an emerging need of detecting online posts that can go against the community acceptance standards. The hostility detection task has been well explored for resource-rich languages like English, but is unexplored for resource-constrained languages like Hindi due to the unavailability of large suitable data. We view this hostility detection as a multi-label multi-class classification problem. We propose an effective neural network-based technique for hostility detection in Hindi posts. We leverage pre-trained multilingual Bidirectional Encoder Representations of Transformer (mBERT) to obtain the contextual representations of Hindi posts. We have performed extensive experiments including different pre-processing techniques, pre-trained models, neural architectures, hybrid strategies, etc. Our best performing neural classifier model includes One-vs-the-Rest approach where we obtained 92.60%, 81.14%, 69.59%, 75.29% and 73.01% F1 scores for hostile, fake, hate, offensive, and defamation labels respectively. The proposed model (https://github.com/Arko98/Hostility-Detection-in-Hindi-Constraint-2021 ) outperformed the existing baseline models and emerged as the state-of-the-art model for detecting hostility in the Hindi posts. © 2021, Springer Nature Switzerland AG.

Communications in Computer and Information Science

Coarse and Fine-Grained Hostility Detection in Hindi Posts Using Fine Tuned Multilingual Embeddings

The subspace approximation problem with outliers, for given n points in d dimensions x1,x2,…,xn∈Rd, an integer 1≤k≤d, and an outlier parameter 0≤α≤1, is to find a k-dimensional linear subspace of Rd that minimizes the sum of squared distances to its nearest (1−α)n points. More generally, the ℓp subspace approximation problem with outliers minimizes the sum of p-th powers of distances instead of the sum of squared distances. Even the case of p=2 or robust PCA is non-trivial, and previous work requires additional assumptions on the input or generative models for it. Any multiplicative approximation algorithm for the subspace approximation problem with outliers must solve the robust subspace recovery problem, a special case in which the (1−α)n inliers in the optimal solution are promised to lie exactly on a k-dimensional linear subspace. However, robust subspace recovery is Small Set Expansion (SSE)-hard, and known algorithmic results for robust subspace recovery require strong assumptions on the input, e.g., any d outliers must be linearly independent. In this paper, we show how to extend dimension reduction techniques and bi-criteria approximations based on sampling and coresets to the problem of subspace approximation with outliers. To get around the SSE-hardness of robust subspace recovery, we assume that the squared distance error of the optimal k-dimensional subspace summed over the optimal (1−α)n inliers is at least δ times its squared-error summed over all n points, for some 0&lt;δ≤1−α. Under this assumption, we give an efficient algorithm to find a weak coreset or a subset of poly(k/ϵ)log⁡(1/δ)log⁡log⁡(1/δ) points whose span contains a k-dimensional subspace that gives a multiplicative (1+ϵ)-approximation to the optimal solution. Our technique is based on the squared-length sampling algorithm suggested for low-rank approximation problems in the seminal work of Frieze, Kannan, and Vempala [12]. The running time of our algorithm is linear in n and d. Interestingly, our results hold even when the fraction of outliers α is large, as long as the obvious condition 0&lt;δ≤1−α is satisfied. We show similar results for subspace approximation with ℓp error or more general M-estimator loss functions, and also give an additive approximation for the affine subspace approximation problem. © 2021 Elsevier B.V.

Theoretical Computer Science

Sampling-based dimension reduction for subspace approximation with outliers

Deep learning models such as Resnets have resulted in state-of-the-art accuracy in many computer vision problems. Neural ordinary differential equations (NODE) provides a continuous depth generalization of Resnets and overcome drawbacks of Resnet such as model selection and parameter complexity. Though NODE is more robust than Resnet, we find that NODE based architectures are still far away from providing robustness and uncertainty handling required for many computer vision problems. We propose novel NODE models which address these drawbacks. In particular, we propose Gaussian processes (GPs) to model the fully connected neural networks in NODE (NODE-GP) to improve robustness and uncertainty handling capabilities of NODE. The proposed model is flexible to accommodate different NODE architectures, and further improves the model selection capabilities in NODEs. We also find that numerical techniques play an important role in modelling NODE robustness, and propose to use different numerical techniques to improve NODE robustness. We demonstrate the superior robustness and uncertainty handling capabilities of proposed models on adversarial attacks and out-of-distribution experiments for the image classification tasks. © 2021 IEEE.

Proceedings - 2021 IEEE Winter Conference on Applications of Computer Vision, WACV 2021

Improving robustness and uncertainty modelling in neural ordinary differential equations

Given a Boolean function f:{ -1,1}n → {-1,1}, define the Fourier distribution to be the distribution on subsets of [n], where each S ⊆ [n] is sampled with probability f (S)2. The Fourier Entropy-influence (FEI) conjecture of Friedgut and Kalai [28] seeks to relate two fundamental measures associated with the Fourier distribution: does there exist a universal constant C > 0 such that H(f2) ≤ C · Inf (f), where H(f2) is the Shannon entropy of the Fourier distribution of f and Inf(f) is the total influence of f? In this article, we present three new contributions toward the FEI conjecture: (1) Our first contribution shows that H(f2) ≤ 2 · aUC⊕(f), where a UC⊕(f) is the average unambiguous parity-certificate complexity of f. This improves upon several bounds shown by Chakraborty et al. [20]. We further improve this bound for unambiguous DNFs. We also discuss how our work makes Mansour's conjecture for DNFs a natural next step toward resolution of the FEI conjecture. (2) We next consider the weaker Fourier Min-entropy-influence (FMEI) conjecture posed by O'Donnell and others [50, 53], which asks if H∞ (f2) ≤ C · Inf(f), where H ∞ (f2) is the min-entropy of the Fourier distribution. We show H∞(f2) ≤ 2·Cmin⊕(f), where Cmin⊕(f) is the minimum parity-certificate complexity of f. We also show that for all ϵ≥0, we have H∞(f2) ≤ 2 log (||f||1,ϵ/(1-ϵ)), where ||f||1,ϵ is the approximate spectral norm of f. As a corollary, we verify the FMEI conjecture for the class of read-k DNFs (for constant k). (3) Our third contribution is to better understand implications of the FEI conjecture for the structure of polynomials that 1/3-approximate a Boolean function on the Boolean cube. We pose a conjecture: no flat polynomial(whose non-zero Fourier coefficients have the same magnitude) of degree d and sparsity 2ω(d) can 1/3-approximate a Boolean function. This conjecture is known to be true assuming FEI, and we prove the conjecture unconditionally (i.e., without assuming the FEI conjecture) for a class of polynomials. We discuss an intriguing connection between our conjecture and the constant for the Bohnenblust-Hille inequality, which has been extensively studied in functional analysis. © 2021 Association for Computing Machinery.

Fulltext

ACM Transactions on Computation Theory

Improved Bounds on Fourier Entropy and Min-entropy

In recent years, DRAM-based main memories have become susceptible to the Row Hammer (RH) problem, which causes bits to flip in a row without accessing them directly. Frequent activation of a row, called an aggressor row, causes its adjacent rows' (victim) bits to flip. The state-of-The-Art solution is to refresh the victim rows explicitly to prevent bit flipping. There have been several proposals made to detect RH attacks. These include both probabilistic as well as deterministic counter-based methods. The technique of handling RH attacks, however, remains the same. In this work, we propose an efficient technique for handling the RH problem. We show that the mechanism is agnostic of the detection mechanism. Our RH handling technique omits the necessity of refreshing the victim rows. Instead, we use a small non-volatile Spin-Transfer Torque Magnetic Random Access Memory (STTRAM) that ensures no unnecessary refreshes of the victim rows on the DRAM device and thus allowing more time for normal applications in the same DRAM device. Our model relies on the migration of the aggressor rows. This accounts for removing blocking of the DRAM operations due to the refreshing of victim rows incurred in the previous solution. After extensive evaluation, we found that, compared to the conventional RH mitigation techniques, our model minimizes the blocking time of the memory that is imposed due to explicit refreshing by an average of 80.72% in the worst-case scenario and provides energy savings of about 15.82% on average, across different types of RH-based workloads. A lookup table is necessary to pinpoint the location of a particular row, which, when combined with the STTMRAM, limits the storage overhead to 0.39% of a 2 GB DRAM. Our proposed model prevents repeated refreshing of the same victim rows in different refreshing windows on the DRAM device and leads to an efficient RH handling technique. © 2021 ACM.

ACM Transactions on Architecture and Code Optimization

Towards Enhanced System Efficiency while Mitigating Row Hammer

Semantic characterization of the Point-of-Interest (POI) plays an important role for modeling location-based social networks and various related applications like POI recommendation, link prediction etc. However, semantic categories are not available for many POIs which makes this characterization difficult. Semantic annotation aims to predict such missing categories of POIs. Existing approaches learn a representation of POIs using graph neural networks to predict semantic categories. However, LBSNs involve complex and higher order mobility dynamics. These higher order relations can be captured effectively by employing hypergraphs. Moreover, visits to POIs can be attributed to various reasons like temporal characteristics, spatial context etc. Hence, we propose a Multi-view Hypergraph Convolution Network (Multi-HGCN) where we learn POI representations by considering multiple hypergraphs across multiple views of the data. We build a comprehensive model to learn the POI representation capturing temporal, spatial and trajectory-based patterns among POIs by employing hypergraphs. We use hypergraph convolution to learn better POI representation by using spectral properties of hypergraph. Experiments conducted on three real-world datasets show that the proposed approach outperforms the state-of-the-art approaches. © 2021 ACM.

Proceedings of the 2021 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2021

Multi-view hypergraph convolution network for semantic annotation in LBSNs

Multicore systems with shared Last Level Cache (LLC) possess a bigger challenge in allocating the LLC space among multiple applications running in the system. Since all applications use the shared LLC, interference caused by them may evict important blocks of other applications that result in premature eviction and may also lead to thrashing. Replacement policies applied locally to a set distributes the sets in a dynamic way among the applications. However, previous work on replacement techniques focused on the re-reference aspect of a block or application behavior to improve the overall system performance. The paper proposes a novel cache replacement technique Application Aware Re-reference Interval Prediction (AARIP) that considers application behavior, re-reference interval, and premature block eviction for replacing a cache block. Experimental evaluation on a four-core system shows that AARIP achieves an overall performance improvement of 7.28%, throughput by 4.9%, and improves overall system fairness by 7.85%, as compared to the traditional SRRIP replacement policy. © 2021 EDAA.

Proceedings -Design, Automation and Test in Europe, DATE

A Fairness Conscious Cache Replacement Policy for Last Level Cache

Owing to the diverse nature of traffic incidents, accepting and storing relevant data in the form of natural language is more convenient than in constrained value fields. Textual information in such cases can be rich enough for traffic incident analysis and modelling even in the absence of certain fixed set of parameters. However limited studies considered the complexity in processing such information to predict traffic incident duration. In this paper, we propose to represent the textual data from incident reports using BERT word embeddings. These text representations are then inputted into various regressors such as LSTM, XGBoost, RF and SVR to predict traffic incident duration. To demonstrate the significance of this approach, the method is compared with the state-of-the-art approach using LDA representation. Dataset used for the experiment is the Caltrans Performance Measurement System (PeMS). Result analysis indicates that the BERT- LSTM hybrid model is effective in capturing the contextual meaning of textual incident reports to predict the traffic incident duration and outperforms LDA topic modelling with MAE around 11.16 minutes. © 2021 IEEE.

Department of Civil Engineering

IEEE Vehicular Technology Conference

Traffic Incident Duration Prediction using BERT Representation of Text

Statistical Model Checking (SMC) is a popular technique in formal methods for analyzing large stochastic systems. As opposed to the expensive but exact model checking algorithms, this technique allows for a trade-off between accuracy and running time. SMC is based on Monte Carlo sampling of the runs of the stochastic system, and lends itself to stochastic discrete event simulators as well. In this paper, we use SMC to analyze traffic models like car-following and lane-changing models. We achieve this through an integration of the SMC tool MultiVeStA with the discrete event simulation software for urban mobility, SUMO. As illustration of the approach and the tool chain, we compare the car-following and lane-changing models against various performance parameters like throughput, emissions and waiting times. Importantly, the use of formal methods allows for formulating and evaluating complex queries that can be asked of the model. The results show the utility of such a tool chain in performing complex quantitative what-if analyses of various traffic models and policies. © 2021, Springer Nature Switzerland AG.