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 bag-of-visual-words (BoW) generation is a widely used unsupervised feature extraction method for the variety of computer vision applications. However, space and computational complexity of bag-of-visual-words generation increase with an increase in the size of the dataset because of computational complexities involved in underlying algorithms. In this paper, we present Fast-BoW, a scalable method for BoW generation for both hard and soft vector-quantization with time complexities O(|h|log2 k) and O(|h|k), respectively1. We replace the process of finding the closest cluster center with a softmax classifier which improves the cluster boundaries over k-means and also can be used for both hard and soft BoW encoding. To make the model compact and faster, we quantize the real weights into integer weights which can be represented using few bits (2−8) only. Also, on the quantized weights, we apply the hashing to reduce the number of multiplications which makes the process further faster. We evaluated the proposed approach on several public benchmark datasets. The experimental results outperform the existing hierarchical clustering tree-based approach by 12 times. © 2018. The copyright of this document resides with its authors. It may be distributed unchanged freely in print or electronic forms.

World University root node

British Machine Vision Conference 2018, BMVC 2018

Fast-bow: Scaling bag-of-visual-words generation

Adversarial examples are fabricated examples, indistinguishable from the original image that mislead neural networks and drastically lower their performance. Recently proposed AdvGAN, a GAN based approach, takes input image as a prior for generating adversaries to target a model. In this work, we show how latent features can serve as better priors than input images for adversary generation by proposing AdvGAN++, a version of AdvGAN that achieves higher attack rates than AdvGAN and at the same time generates perceptually realistic images on MNIST and CIFAR-10 datasets. © 2019 IEEE.

Proceedings - 2019 International Conference on Computer Vision Workshop, ICCVW 2019

AdvGAN++: Harnessing latent layers for adversary generation

We provide a randomized linear time approximation scheme for a generic problem about clustering of binary vectors subject to additional constraints. The new constrained clustering problem generalizes a number of problems and by solving it, we obtain the first linear time-approximation schemes for a number of well-studied fundamental problems concerning clustering of binary vectors and low-rank approximation of binary matrices. Among the problems solvable by our approach are Low GF(2)-Rank Approximation, Low Boolean-Rank Approximation, and various versions of Binary Clustering. For example, for Low GF(2)- Rank Approximation problem, where for anm × n binary matrix A and integer r > 0, we seek for a binary matrix B of GF(2) rank at most r such that the ∂0-norm of matrix A - B is minimum, our algorithm, for any ∈ > 0 in time f (r , ∈ ) nm, where f is some computable function, outputs a (1 + ∈ )-approximate solution with probability at least (1 - 1 e ). This is the first linear time approximation scheme for these problems. We also give (deterministic) PTASes for these problems running in time nf (r ) 1 ∈2 log 1 ∈ , where f is some function depending on the problem. Our algorithm for the constrained clustering problem is based on a novel sampling lemma, which is interesting on its own. © 2019 Association for Computing Machinery. All rights reserved.

ACM Transactions on Algorithms

Approximation schemes for low-rank binary matrix approximation problems

In this work, we discuss a numerical model checking algorithm for analyzing incompletely specified models of stochastic systems, specifically, Discrete Time Markov Chains (DTMC). Models of a system could be incompletely specified for several reasons. For example, they could still be under development or, there could be some doubt about the correctness of some components. We restrict ourselves to cases where incompleteness can be captured by expanding the logic of atomic propositions to a three valued logic that includes an unknown truth value. We seek to answer meaningful model checking queries even in such circumstances. The approach we adopt in this paper is to develop the model checking algorithm from first principles. We develop a tool based on the algorithm and compare the performance of this approach with the indirect approach of invoking a binary model checker. © Springer Nature Switzerland AG 2019.

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

Model Checking Branching Time Properties for Incomplete Markov Chains

Neural networks are vulnerable to adversarial attacks - small visually imperceptible crafted noise which when added to the input drastically changes the output. The most effective method of defending against adversarial attacks is to use the methodology of adversarial training. We analyze the adversarially trained robust models to study their vulnerability against adversarial attacks at the level of the latent layers. Our analysis reveals that contrary to the input layer which is robust to adversarial attack, the latent layer of these robust models are highly susceptible to adversarial perturbations of small magnitude. Leveraging this information, we introduce a new technique Latent Adversarial Training (LAT) which comprises of fine-tuning the adversarially trained models to ensure the robustness at the feature layers. We also propose Latent Attack (LA), a novel algorithm for constructing adversarial examples. LAT results in a minor improvement in test accuracy and leads to a state-of-the-art adversarial accuracy against the universal first-order adversarial PGD attack which is shown for the MNIST, CIFAR-10, CIFAR-100, SVHN and Restricted ImageNet datasets. © 2019 International Joint Conferences on Artificial Intelligence. All rights reserved.

IJCAI International Joint Conference on Artificial Intelligence

Harnessing the vulnerability of latent layers in adversarially trained models

Graph algorithms applied in many applications, including social networks, communication networks, VLSI design, graphics, and several others, require dynamic modifications - addition and removal of vertices and/or edges - in the graph. This paper presents a novel concurrent non-blocking algorithm to implement a dynamic unbounded directed graph in a shared-memory machine. The addition and removal operations of vertices and edges are lock-free. For a finite sized graph, the lookup operations are wait-free. Most significant component of the presented algorithm is the reachability query in a concurrent graph. The reachability queries in our algorithm are obstruction-free and thus impose minimal additional synchronization cost over other operations. We prove that each of the data structure operations are linearizable. We extensively evaluate a sample C/C++ implementation of the algorithm through a number of micro-benchmarks. The experimental results show that the proposed algorithm scales well with the number of threads and on an average provides 5 to 7x performance improvement over a concurrent graph implementation using coarse-grained locking. © 2019 Association for Computing Machinery.

ACM International Conference Proceeding Series

A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries

To utilize the multi-core processors properly concurrent programming is needed. The main challenge is to design a correct and efficient concurrent program. Software Transactional Memory Systems (STMs) provide ease of multithreading to the programmer without worrying about concurrency issues as deadlock, livelock, priority inversion, etc. Most of the STMs work on read-write operations known as RWSTMs. Some STMs work at higher-level operations and ensure greater concurrency than RWSTMs. Such STMs are known as Single-Version Object-based STMs (SVOSTMs). The transactions of SVOSTMs can return commit or abort. Aborted SVOSTMs transactions retry. But in the current setting of SVOSTMs, transactions may starve. So, we propose a Starvation-Freedom in SVOSTM as SF-SVOSTM that satisfies the correctness criteria conflict-opacity. Databases and STMs say that maintaining multiple versions corresponding to each shared data-item (or key) reduces the number of aborts and improves the throughput. So, to achieve greater concurrency further, we propose Starvation-Freedom in Multi-Version OSTM as SF-MVOSTM algorithm. The number of versions maintains by SF-MVOSTM either be unbounded with garbage collection as SF-MVOSTM-GC or bounded with latest K-versions as SF-KOSTM. SF-MVOSTM satisfies the correctness criteria as local opacity and shows the performance benefits as compared with state-of-the-art STMs. © Springer Nature Switzerland AG 2019.

Achieving Starvation-Freedom with Greater Concurrency in Multi-Version Object-based Transactional Memory Systems

For \alpha &gt; 1, an \alpha -approximate (bi)kernel is a polynomial-time algorithm that takes as input an instance (I, k) of a problem \scrQ and outputs an instance (I\prime , k\prime ) (of a problem \scrQ \prime ) of size bounded by a function of k such that, for every c \geq 1, a c-approximate solution for the new instance can be turned into a (c \cdot \alpha )-approximate solution of the original instance in polynomial time. This framework of lossy kernelization was recently introduced by Lokshtanov and co-authors. We study Connected Dominating Set (and its distance-r variant) parameterized by solution size on sparse graph classes like biclique-free graphs, classes of bounded expansion, and nowhere dense classes. We prove that for every \alpha &gt; 1, Connected Dominating Set admits a polynomial-size \alpha -approximate (bi)kernel on all the aforementioned classes. Our results are in sharp contrast to the kernelization complexity of Connected Dominating Set, which is known to not admit a polynomial kernel even on 2-degenerate graphs and graphs of bounded expansion, unless NP \subseteq coNP/poly. We complement our results by the following conditional lower bound. We show that if a class \scrC is somewhere dense and closed under taking subgraphs, then for some value of r \in \BbbN there cannot exist an \alpha -approximate bi-kernel for the (Connected) Distance-r Dominating Set problem on \scrC for any \alpha &gt; 1 (assuming FPT \not = W[1]). ©2019 Society for Industrial and Applied Mathematics

Fulltext

SIAM Journal on Discrete Mathematics

Lossy kernels for connected dominating set on sparse graphs

In the EDGE EDITING TO CONNECTED f-DEGREE GRAPH problem we are given a graph G, an integer k, and a function f assigning integers to vertices of G. The task is to decide whether there is a connected graph F on the same vertex set as G, such that for every vertex v, its degree in F is f(v), and the number of edges in E(G)\bigtriangleup E(F), the symmetric difference of E(G) and E(F), is at most k. We show that EDGE EDITING TO CONNECTED f-DEGREE GRAPH is fixed-parameter tractable (FPT) by providing an algorithm solving the problem on an n-vertex graph in time 2\scrO (k)n\scrO (1). We complement this result by showing that the weighted version of the problem with costs 1 and 0 is W[1]-hard when parameterized by k and the maximum value of f even when the input graph is a tree. Our FPT algorithm is based on a nontrivial combination of color-coding and fast computations of representative families over the direct sum matroid of \ell -elongation of the co-graphic matroid associated with G and a uniform matroid over the set of nonedges of G. We believe that this combination could be useful in designing parameterized algorithms for other edge editing and connectivity problems. © 2019 Society for Industrial and Applied Mathematics

Editing to connected F-degree graph

The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem was a long-standing, notorious open problem in parameterized complexity. Some years ago, the breakthrough work by Kratsch and Wahlström on representative sets finally answered this question in the affirmative [FOCS 2012]. In this paper, we present an alternative, algebraic compression of the Vertex Cover Above LP problem into the Rank Vertex Cover problem. Here, the input consists of a graph G, a parameter k, and a bijection between V(G) and the set of columns of a representation of a matroid M, and the objective is to find a vertex cover whose rank is upper bounded by k. © 2019 Society for Industrial and Applied Mathematics