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 design exact algorithms for the following two problems in survivable network design: (i) designing a minimum cost network with a desired value of edge connectivity, which is called Minimum Weight λ-connected Spanning Subgraph and (ii) augmenting a given network to a desired value of edge connectivity at a minimum cost which is called Minimum Weight λ-connectivity Augmentation. Many well known problems such as Minimum Spanning Tree, Hamiltonian Cycle, Minimum 2-Edge Connected Spanning Subgraph and Minimum Equivalent Digraph reduce to these problems in polynomial time. It is easy to see that a minimum solution to these problems contains at most 2λ(n−1) edges. Using this fact one can design a brute-force algorithm which runs in time 2O(λn(log n+log λ)However no better algorithms were known. In this paper, we give the first single exponential time algorithm for these problems, i.e. running in time 2O(λn)for both undirected and directed networks. Our results are obtained via well known characterizations of λ-connected graphs, their connections to linear matroids and the recently developed technique of dynamic programming with representative sets. © Springer International Publishing AG 2017.

World University root node

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

Fast exact algorithms for survivable network design with uniform requirements

As microblogging services like Twitter are becoming more and more influential in today's globalized world, its facets like sentiment analysis are being extensively studied. We are no longer constrained by our own opinion. Others' opinions and sentiments play a huge role in shaping our perspective. In this paper, we build on previous works on Twitter sentiment analysis using Distant Supervision. The existing approach requires huge computation resource for analyzing large number of tweets. In this paper, we propose techniques to speed up the computation process for sentiment analysis. We use tweet subjectivity to select the right training samples. We also introduce the concept of EFWS (Effective Word Score) of a tweet that is derived from polarity scores of frequently used words, which is an additional heuristic that can be used to speed up the sentiment classification with standard machine learning algorithms. We performed our experiments using 1.6 million tweets. Experimental evaluations show that our proposed technique is more efficient and has higher accuracy compared to previously proposed methods. We achieve overall accuracies of around 80% (EFWS heuristic gives an accuracy around 85%) on a training dataset of 100K tweets, which is half the size of the dataset used for the baseline model. The accuracy of our proposed model is 2-3% higher than the baseline model, and the model effectively trains at twice the speed of the baseline model. © 2017 IEEE.

2017 9th International Conference on Communication Systems and Networks, COMSNETS 2017

Efficient Twitter sentiment classification using subjective distant supervision

Long-short term memory networks(LSTM) models have shown considerable performance on variety of problems dealing with sequential data. In this paper, we propose a variant of Long-Term Recurrent Convolutional Network(LRCN) to detect road intersection. We call this network as IntersectNet. We pose road intersection detection as binary classification task over sequence of frames. The model combines deep hierarchical visual feature extractor with recurrent sequence model. The model is end to end trainable with capability of capturing the temporal dynamics of the system. We exploit this capability to identify road intersection in a sequence of temporally consistent images. The model has been rigorously trained and tested on various different datasets. We think that our findings could be useful to model behavior of autonomous agent in the real-world. © 2017 IEEE.

IEEE International Conference on Intelligent Robots and Systems

Have i reached the intersection: A deep learning-based approach for intersection detection from monocular cameras

The input for the Geometric Coverage problem consists of a pair Σ = (P,R), where P is a set of points in ℝd and R is a set of subsets of P defined by the intersection of P with some geometric objects in ℝdThese coverage problems form special instances of the Set Cover problem which is notoriously hard in several paradigms including approximation and parameterized complexity. Motivated by what are called choice problems in geometry, we consider a variation of the Geometric Coverage problem where there are conflicts on the covering objects that precludes some objects from being part of the solution if some others are in the solution. As our first contribution, we propose two natural models in which the conflict relations are given: (a) by a graph on the covering objects, and (b) by a representable matroid on the covering objects. We consider the parameterized complexity of the problem based on the structure of the conflict relation. Our main result is that as long as the conflict graph has bounded arboricity (that includes all the families of intersection graphs of low density objects in low dimensional Euclidean space), there is a parameterized reduction to the problem without conflicts on the covering objects. This is achieved through a randomization-derandomization trick. As a consequence, we have the following results when the conflict graph has bounded arboricity. -If the Geometric Coverage problem is fixed parameter tractable (FPT), then so is the conflict free version. -If the Geometric Coverage problem admits a factor α-approximation, then the conflict free version admits a factor α-approximation algorithm running in FPT time. As a corollary to our main result we get a plethora of approximation algorithms running in FPT time. Our other results include an FPT algorithm and a W[1]-hardness proof for the conflict-free version of Covering Points by Intervals. The FPT algorithm is for the case when the conflicts are given by a representable matroid, and the W[1]-hardness resultis for all the families of conflict graphs for which the Independent Set problem is W[1]-hard. © Springer International Publishing AG 2017.

Parameterized complexity of geometric covering problems having conflicts

In this paper we propose a new framework for analyzing the performance of pre-processing algorithms. Our framework builds on the notion of kernelization from parameterized complexity. However, as opposed to the original notion of kernelization, our definitions combine well with approximation algorithms and heuristics. The key new definition is that of a polynomial size α-approximate kernel Loosely speaking, a polynomial size α-approximate kernel is a polynomial time pre-processing algorithm that takes as input an instance (I, k) to a parameterized problem, and outputs another instance (I′, k′) to the same problem, such that |I′| + k′ ≤ kO(1). Additionally, for every c ≥ 1, a c-approximate solutions' to the pre-processed instance (I′ k′) can be turned in polynomial time into a (c·α)-approximate solution s to the original instance (I, k). Amongst our main technical contributions are α-approximate kernels of polynomial size for three problems, namely CONNECTED VERTEX COVER, DISJOINT CYCLE PACKING and DISJOINT FACTORS. These problems are known not to admit any polynomial size kernels unless NP ⊆ coNP/Poly Our approximate kernels simultaneously beat boththe lower bounds on the (normal) kernel size, and thehardness of approximation lower bounds for all three problems. On the negative side we prove that LONGEST PATH parameterized by the length of the path and SET COVER parameterized by the universe size do not admit even an α-approximate kernel of polynomial size, for any α ≥ 1, unless NP ⊆ coNP/Poly. © 2017 ACM.

Proceedings of the Annual ACM Symposium on Theory of Computing

Lossy kernelization

Let F be a family of graphs. Given an n-vertex input graph G and a positive integer k, testing whether G has a vertex subset S of size at most k, such that G- S belongs to F, is a prototype vertex deletion problem. These type of problems have attracted a lot of attention in recent times in the domain of parameterized complexity. In this paper, we study two such problems; when F is either the family of forests of cacti or the family of forests of odd-cacti. A graph H is called a forest of cacti if every pair of cycles in H intersect on at most one vertex. Furthermore, a forest of cacti H is called a forest of odd cacti, if every cycle of H is of odd length. Let us denote by C and Codd, the families of forests of cacti and forests of odd cacti, respectively. The vertex deletion problems corresponding to C and Codd are called Diamond Hitting Set and Even Cycle Transversal, respectively. In this paper we design randomized algorithms with worst case run time 12 knO ( 1 ) for both these problems. Our algorithms considerably improve the running time for Diamond Hitting Set and Even Cycle Transversal, compared to what is known about them. © 2017, Springer Science+Business Media New York.

Fulltext

Algorithmica

Quick but Odd Growth of Cacti

For a graph H, the H-free Edge Deletion problem asks whether there exist at most k edges whose deletion from the input graph G results in a graph without any induced copy of H. H-free Edge Completion and H-free Edge Editing are defined similarly where only completion (addition) of edges are allowed in the former and both completion and deletion are allowed in the latter. We completely settle the classical complexities of these problems by proving that H-free Edge Deletion is NP-complete if and only if H is a graph with at least two edges, H-free Edge Completion is NP-complete if and only if H is a graph with at least two nonedges, and H-free Edge Editing is NP-complete if and only if H is a graph with at least three vertices. Our result on H-free Edge Editing resolves a conjecture by Alon and Stav [Theoret. Comput. Sci., 2009, pp. 4920-4927]. Additionally, we prove that these NP-complete problems cannot be solved in parameterized subexponential time, i.e., in time 2o(k)•|G|O(1), unless the exponential time hypothesis fails. Furthermore, we obtain implications on the incompressibility and the inapproximability of these problems. © 2017 Society for Industrial and Applied Mathematics.

SIAM Journal on Discrete Mathematics

Dichotomy results on the hardness of H-free edge modification problems

Social media has now become the de facto information source on real world events. The challenge, however, due to the high volume and velocity nature of social media streams, is in how to follow all posts pertaining to a given event over time – a task referred to as story detection. Moreover, there are often several different stories pertaining to a given event, which we refer to as sub-stories and the corresponding task of their automatic detection – as sub-story detection. This paper proposes hierarchical Dirichlet processes (HDP), a probabilistic topic model, as an effective method for automatic sub-story detection. HDP can learn sub-topics associated with sub-stories which enables it to handle subtle variations in sub-stories. It is compared with state-of-the-art story detection approaches based on locality sensitive hashing and spectral clustering. We demonstrate the superior performance of HDP for sub-story detection on real world Twitter data sets using various evaluation measures. The ability of HDP to learn sub-topics helps it to recall the sub-stories with high precision. This has resulted in an improvement of up to 60% in the F-score performance of HDP based sub-story detection approach compared to standard story detection approaches. A similar performance improvement is also seen using an information theoretic evaluation measure proposed for the sub-story detection task. Another contribution of this paper is in demonstrating that considering the conversational structures within the Twitter stream can bring up to 200% improvement in sub-story detection performance. © 2016 The Authors

Information Processing and Management

Sub-story detection in Twitter with hierarchical Dirichlet processes

Due to the increase in manufacturing/environmental uncertainties in the nanometer regime, testing digital chips under different operating conditions becomes mandatory. Traditionally, stuck-at tests were applied at slow speed to detect structural defects and transition fault tests were applied at-speed to detect delay defects. Recently, it was shown that certain cell-internal defects can only be detected using at-speed stuck-at testing. Stuck-at test patterns are power hungry, thereby causing excessive voltage droop on the power grid, delaying the test response, and finally leading to false delay failures on the tester. This motivates the need for peak power minimization during at-speed stuck-at testing. In this article, we use input toggle minimization as a means to minimize a circuit’s power dissipation during at-speed stuck-at testing under the Combinational State Preservation scan (CSP-scan) Design-For-Testability (DFT) scheme. For circuits whose test sets are dominated by don’t cares, this article maps the problem of optimal X-filling for peak input toggle minimization to a variant of the interval coloring problem and proposes a Dynamic Programming (DP) algorithm (DP-fill) for the same along with a theoretical proof for its optimality. For circuits whose test sets are not dominated by don’t cares, we propose a max scatter Hamiltonian path algorithm, which ensures that the ordering is done such that the don’t cares are evenly distributed in the final ordering of test cubes, thereby leading to better input toggle savings than DP-fill. The proposed algorithms, when experimented on ITC99 benchmarks, produced peak power savings of up to 48% over the best-known algorithms in literature. We have also pruned the solutions thus obtained using Greedy and Simulated Annealing strategies with iterative 1-bit neighborhood to validate our idea of optimal input toggle minimization as an effective technique for minimizing peak power dissipation during at-speed stuck-at testing. © 2017 ACM.

Department of Electrical Engineering

ACM Transactions on Design Automation of Electronic Systems

Optimal don’t care filling for minimizing peak toggles during at-speed stuck-at testing

Palmprint recognition is a variant of fingerprint matching as both the systems share almost similar matching criteria and the minutiae feature extraction methods. However, there is a performance degradation with palmprint biometrics because of the failure of extracting genuine minutia points from the region of highly distorted ridge information with huge data. In this paper, we propose an efficient palmprint matching algorithm using nearest neighbor minutiae quadruplets. The representation of minutia points in the form of quadruplets improves the matching accuracy at nearest neighbors by discarding scope of the global matching on false minutia points. The proposed algorithm is evaluated on publicly available high resolution palmprint standard databases, namely, palmprint benchmark data sets (FVC ongoing) and Tsinghua palmprint database (THUPALMLAB). The experimental results demonstrate that the proposed palmprint matching algorithm achieves the state-of-the-art performance. © Springer Science+Business Media Singapore 2017.