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

We show that the intersection dimension of graphs with respect to several hereditary properties can be bounded as a function of the maximum degree. As an interesting special case, we show that the circular dimension of a graph with maximum degree Δis at most O(ΔlogΔ/log logΔ) . It is also shown that permutation dimension of any graph is at most Δ(log Δ)1+o(1). We also obtain bounds on intersection dimension in terms of treewidth. © 2021 N.R. Aravind et al., published by Sciendo.

World University root node

Fulltext

Discussiones Mathematicae - Graph Theory

Intersection Dimension and Graph Invariants

In an undirected graph G, a conflict-free coloring with respect to open neighborhoods (denoted by CFON coloring) is an assignment of colors to the vertices such that every vertex has a uniquely colored vertex in its open neighborhood. The minimum number of colors required for a CFON coloring of G is the CFON chromatic number of G, denoted by χON(G). The decision problem that asks whether χON(G) ≤ k is NP-complete. Structural as well as algorithmic aspects of this problem have been well studied. We obtain the following results for χON(G):Bodlaender, Kolay and Pieterse [WADS 2019] showed the upper bound χON(G) ≤ fvs(G) + 3, where fvs(G) denotes the size of a minimum feedback vertex set of G. We show the improved bound of χON(G) ≤ fvs(G) + 2, which is tight, thereby answering an open question in the above paper.We study the relation between χON(G) and the pathwidth of the graph G, denoted pw(G). The above paper from WADS 2019 showed the upper bound χON(G) ≤ 2 tw(G) + 1 where tw(G) stands for the treewidth of G. This implies an upper bound of χON(G) ≤ 2 pw(G) + 1. We show an improved bound of.We prove new bounds for χON(G) with respect to the structural parameters neighborhood diversity and distance to cluster, improving the existing results of Gargano and Rescigno [Theor. Comput. Sci. 2015] and Reddy [Theor. Comput. Sci. 2018], respectively. Furthermore, our techniques also yield improved bounds for the closed neighborhood variant of the problem.We also study the partial coloring variant of the CFON coloring problem, which allows vertices to be left uncolored. Let χON∗(G) denote the minimum number of colors required to color G as per this variant. Abel et al. [SIDMA 2018] showed that χON∗(G)≤8 when G is planar. They asked if fewer colors would suffice for planar graphs. We answer this question by showing that χON∗(G)≤5 for all planar G. This approach also yields the bound χON∗(G)≤4 for all outerplanar G. All our bounds are a result of constructive algorithmic procedures. © 2020, Springer Nature Switzerland AG.

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

Combinatorial Bounds for Conflict-Free Coloring on Open Neighborhoods

Many kinds of disease-related data are now available and researchers are constantly attempting to mine useful information out of these. Medical data are not always homogeneous and in structured form, and mostly they are time-stamped data. Thus, special care is required to prevent any kind of information loss during mining such data. Mining medical data is challenging as predicting the non-accurate result is often not acceptable in this domain. In this paper, we have analyzed a partially annotated coronary artery disease (CAD) dataset which was originally in a semi-structured form. We have created a set of some well-defined features from the dataset, and then build predictive models for CAD risk identification using different supervised learning algorithms. We then further enhanced the performances of the models using a feature selection technique. Experiments show that results are quite interesting, and are expected to help medical practitioners for investigating CAD risk in patients. © 2020, International Association of Scientists in the Interdisciplinary Areas.

Interdisciplinary Sciences – Computational Life Sciences

Towards Predicting Risk of Coronary Artery Disease from Semi-Structured Dataset

Let B denote a set of bicolorings of [n], where each bicoloring is a mapping of the points in [n] to {−1,+1}. For each B∈B, let YB=(B(1),…,B(n)). For each A⊆[n], let XA∈{0,1}n denote the incidence vector of A. A non-empty set A is said to be an ‘unbiased representative’ for a bicoloring B∈B if XA,YB=0. Given a set B of bicolorings, we study the minimum cardinality of a family A consisting of subsets of [n] such that every bicoloring in B has an unbiased representative in A. © 2019 Elsevier B.V.

Discrete Applied Mathematics

System of unbiased representatives for a collection of bicolorings

A good seeding or initialization of cluster centers for the k-means method is important from both theoretical and practical standpoints. The k-means objective is inherently non-robust and sensitive to outliers. A popular seeding such as the k-means++ [3] that is more likely to pick outliers in the worst case may compound this drawback, thereby affecting the quality of clustering on noisy data. For any 0 &lt; δ ≤ 1, we show that using a mixture of D2 [3] and uniform sampling, we can pick O(k/δ) candidate centers with the following guarantee: they contain some k centers that give O(1)-approximation to the optimal robust k-means solution while discarding at most δn more points than the outliers discarded by the optimal solution. That is, if the optimal solution discards its farthest βn points as outliers, our solution discards its (β + δ)n points as outliers. The constant factor in our O(1)approximation does not depend on δ. This is an improvement over previous results for k-means with outliers based on LP relaxation and rounding [7] and local search [17]. The O(k/δ) sized subset can be found in time O(ndk). Our robust k-means++ is also easily amenable to scalable, faster, parallel implementations of k-means++ [5]. Our empirical results show a comparison of the above robust variant of k-means++ with the usual k-means++, uniform random seeding, threshold k-means++ [6] and local search on real world and synthetic data. © Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence, UAI 2020. All rights reserved.

Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence, UAI 2020

Robust k-means++

Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most k is Zariski-closed, an important property in geometric complexity theory. It follows that approximations cannot help to reduce the required ABP width. It was mentioned by Forbes that this result would probably break when going from single-(source,sink) ABPs to trace ABPs. We prove that this is correct. Moreover, we study the commutative monotone setting and prove a result similar to Nisan, but concerning the analytic closure. We observe the same behavior here: The set of polynomials with ABP width complexity at most k is closed for single-(source,sink) ABPs and not closed for trace ABPs. The proofs reveal an intriguing connection between tangent spaces and the vector space of flows on the ABP. We close with additional observations on VQP and the closure of VNP which allows us to establish a separation between the two classes. © Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, and Nitin Saurabh; licensed under Creative Commons License CC-BY 35th Computational Complexity Conference (CCC 2020).

Leibniz International Proceedings in Informatics, LIPIcs

Algebraic branching programs, border complexity, and tangent spaces

Deep Learning Processor Unit (DPU) from XILINX is among the numerous accelerators that have been proposed to speed up the execution of Convolutional Neural Networks (CNNs) on embedded platforms. DPUs are available in different configurable sizes and can execute any given CNN. Neural network researchers are also rapidly bringing out newer CNN algorithms with improved performance (typically higher prediction accuracy) with a trade-off in size or energy consumption for embedded applications. To enable quick evaluation of choices among evolving CNN algorithms and accelerator configurations, we propose INFER (INterFerence-Aware Estimation of Runtime). INFER is a framework to estimate the execution time of any CNN on a given size of DPU without actual implementation. Further, current FPGA platforms are capable of implementing multiple DPUs whereas many applications consist of multiple sub-Tasks with each requiring separate and/or different CNNs. In such scenarios of concurrent use of multiple DPUs on an FPGA, INFER is also capable of estimating the additional time taken for execution due to the sharing of memory bandwidth. Our evaluation on various mixes of 16 standard CNNs and eight configurations of DPU shows that INFER has an average prediction error of 6.6%, which can be useful for design space exploration as well as scheduling in multi-DPU platforms. © 2020 IEEE.

Proceedings - 2020 International Conference on Field-Programmable Technology, ICFPT 2020

INFER: INterFerence-Aware Estimation of Runtime for Concurrent CNN Execution on DPUs

Deep learning models such as convolutional neural networks have brought advances in computer vision and were found to surpass human accuracy in computer vision problems. This has resulted in their use in many safety critical applications such as autonomous driving and healthcare, where decision making under uncertainty is crucial. However, deep learning models are vulnerable to out of sample and adversarial examples and they can be very risky to use in safety critical applications. Deep Gaussian process provide a Bayesian non-parametric approach to deep learning and are capable of modelling the uncertainty in data and model. In this paper, we show the uncertainty quantification capabilities of Convolutional deep Gaussian processes for computer vision problems. We show that convolutional deep Gaussian processes provide better uncertainty estimates for various settings such as out-of-distribution samples, adversarial attacks and uncertainty calibration experiments. They are found to be more robust than convolutional neural networks, Bayesian convolutional neural networks and deep Gaussian processes for image classification. © 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM.

ACM International Conference Proceeding Series

Decision making under uncertainty with convolutional deep Gaussian processes

The problem of verifying the 'Unbounded Until' fragment in temporal logic formulas has been studied extensively in the past, especially in the context of statistical model checking. Statistical model checking, a computationally inexpensive sampling based alternative to the more expensive numerical model checking technique, presents the following decision dilemma-what length of the sample is enough in general? In this paper, we discuss an algorithm for this problem that combines ideas from graph theory, statistical model checking and numerical model checking. We analyze the algorithm, and show through experiments that this approach outperforms the standard statistical model checking algorithm for verifying unbounded until for low density Discrete Time Markov Chains. © 2020 IEEE.

Proceedings - 2020 International Symposium on Theoretical Aspects of Software Engineering, TASE 2020

The Bouquet Algorithm for Model Checking Unbounded until Properties

Recommendation of publication venues is very much the need of the hour. There is a sea of options for research conferences and journals. As a result, it is often found that researchers are not even aware of many publication venues in their research area. Existing work uses information, such as all the references in a given paper, past publication venues of the author(s), co-Author relationships, and the paper content to do venue recommendation. However, in this paper, we propose a system that uses very limited context, namely the paper title, abstract, and a venue network, which is constructed using only a small subset of authors' publication history, to do venue recommendation. Our venue recommendation system, FLY, gives 30% higher accuracy compared to the current state-of-The-Art limited context venue recommendation system. © 2020 IEEE.