Chennai Mathematical Institute

research

∙ 06/20/2020

How do SGD hyperparameters in natural training affect adversarial robustness?

Learning rate, batch size and momentum are three important hyperparamete...

Sandesh Kamath, et al. ∙

research

∙ 02/26/2020

Invariance vs. Robustness of Neural Networks

We study the performance of neural network models on random geometric tr...

Sandesh Kamath, et al. ∙

research

∙ 05/18/2020

Universalization of any adversarial attack using very few test examples

Deep learning models are known to be vulnerable not only to input-depend...

Sandesh Kamath, et al. ∙

research

∙ 11/21/2017

Groupwise Maximin Fair Allocation of Indivisible Goods

We study the problem of allocating indivisible goods among n agents in a...

Siddharth Barman, et al. ∙

research

∙ 10/26/2017

Big Data Classification Using Augmented Decision Trees

We present an algorithm for classification tasks on big data. Experiment...

Rajiv Sambasivan, et al. ∙

research

∙ 07/24/2017

Big Data Regression Using Tree Based Segmentation

Scaling regression to large datasets is a common problem in many applica...

Rajiv Sambasivan, et al. ∙

research

∙ 09/17/2011

A KdV-like advection-dispersion equation with some remarkable properties

We discuss a new non-linear PDE, u_t + (2 u_xx/u) u_x = epsilon u_xxx, i...

Abhijit Sen, et al. ∙

research

∙ 08/17/2016

Clustering Mixed Datasets Using Homogeneity Analysis with Applications to Big Data

Datasets with a mixture of numerical and categorical attributes are rout...

Rajiv Sambasivan, et al. ∙

research

∙ 09/17/2015

Fast Gaussian Process Regression for Big Data

Gaussian Processes are widely used for regression tasks. A known limitat...

Sourish Das, et al. ∙

research

∙ 11/27/2017

Frameworks for Designing In-place Graph Algorithms

Read-only memory model is a classical model of computation to study time...

Sankardeep Chakraborty, et al. ∙

research

∙ 10/09/2017

Discovering the roots: Uniform closure results for algebraic classes under factoring

Newton iteration (NI) is an almost 350 years old recursive formula that ...

Pranjal Dutta, et al. ∙

research

∙ 01/27/2018

Greedy Algorithms for Maximizing Nash Social Welfare

We study the problem of fairly allocating a set of indivisible goods amo...

Siddharth Barman, et al. ∙

research

∙ 02/05/2018

Shortest k-Disjoint Paths via Determinants

The well-known k-disjoint path problem (k-DPP) asks for pairwise vertex-...

Samir Datta, et al. ∙

research

∙ 04/23/2018

Reachability and Distances under Multiple Changes

Recently it was shown that the transitive closure of a directed graph ca...

Samir Datta, et al. ∙

research

∙ 04/24/2018

Covering and separation for logical fragments with modular predicates

For every class C of word languages, one may associate a decision proble...

Thomas Place, et al. ∙

research

∙ 05/17/2018

A Note on Polynomial Identity Testing for Depth-3 Circuits

Let C be a depth-3 arithmetic circuit of size at most s, computing a pol...

V. Arvind, et al. ∙

research

∙ 05/23/2018

Maximal and maximum transitive relation contained in a given binary relation

We study the problem of finding a maximal transitive relation contained ...

Sourav Chakraborty, et al. ∙

research

∙ 07/12/2018

Fast Exact Algorithms Using Hadamard Product of Polynomials

In this paper we develop an efficient procedure for computing a (scaled)...

V. Arvind, et al. ∙

research

∙ 08/31/2018

Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators

Let F[X] be the polynomial ring over the variables X={x_1,x_2, ..., x_n}...

V. Arvind, et al. ∙

research

∙ 09/22/2018

A 2-Approximation Algorithm for Feedback Vertex Set in Tournaments

A tournament is a directed graph T such that every pair of vertices is ...

Daniel Lokshtanov, et al. ∙

research

∙ 11/09/2018

A Bayesian Perspective of Statistical Machine Learning for Big Data

Statistical Machine Learning (SML) refers to a body of algorithms and me...

Rajiv Sambasivan, et al. ∙

research

∙ 12/01/2018

Hierarchical Genetic Algorithms with evolving objective functions

We propose a framework of genetic algorithms which use multi-level hiera...

Harshavardhan Kamarthi, et al. ∙

research

∙ 01/08/2019

Subset Feedback Vertex Set in Chordal and Split Graphs

In the Subset Feedback Vertex Set (Subset-FVS) problem the input is a gr...

Geevarghese Philip, et al. ∙

research

∙ 03/27/2019

Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions

The Fourier-Entropy Influence (FEI) Conjecture states that for any Boole...

Sourav Chakraborty, et al. ∙

research

∙ 04/28/2019

Efficient Black-Box Identity Testing over Free Group Algebra

Hrubeš and Wigderson [HW14] initiated the study of noncommutative arithm...

V. Arvind, et al. ∙

research

∙ 06/19/2019

Space Efficient Algorithms for Breadth-Depth Search

Continuing the recent trend, in this article we design several space-eff...

Sankardeep Chakraborty, et al. ∙

research

∙ 07/02/2019

Logics for Reversible Regular Languages and Semigroups with Involution

We present MSO and FO logics with predicates `between' and `neighbour' t...

Paul Gastin, et al. ∙

research

∙ 08/22/2019

On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials

We study the arithmetic circuit complexity of some well-known family of ...

V. Arvind, et al. ∙

research

∙ 09/04/2019

Complexity of controlled bad sequences over finite powersets of N^k

We provide lower and upper bounds for the length of controlled bad seque...

A. R. Balasubramanian, et al. ∙

research

∙ 04/27/2020

Dynamic complexity of Reachability: How many changes can we handle?

In 2015, it was shown that reachability for arbitrary directed graphs ca...

Samir Datta, et al. ∙

research

∙ 05/01/2020

Uniform Welfare Guarantees Under Identical Subadditive Valuations

We study the problem of allocating indivisible goods among agents that h...

Siddharth Barman, et al. ∙

research

∙ 05/15/2020

Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations

We develop polynomial-time algorithms for the fair and efficient allocat...

Siddharth Barman, et al. ∙

research

∙ 06/08/2020

On Universalized Adversarial and Invariant Perturbations

Convolutional neural networks or standard CNNs (StdCNNs) are translation...

Sandesh Kamath, et al. ∙

research

∙ 08/13/2020

Dynamic Complexity of Expansion

Dynamic Complexity was introduced by Immerman and Patnaik <cit.> (see al...

Samir Datta, et al. ∙

research

∙ 01/12/2021

Diverse Collections in Matroids and Graphs

We investigate the parameterized complexity of finding diverse sets of s...

Fedor V. Fomin, et al. ∙

research

∙ 06/01/2021

Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles

We present a parallel algorithm for permanent mod 2^k of a matrix of uni...

Samir Datta, et al. ∙

research

∙ 09/08/2021

Convergence of Batch Asynchronous Stochastic Approximation With Applications to Reinforcement Learning

The stochastic approximation (SA) algorithm is a widely used probabilist...

Rajeeva L. Karandikar, et al. ∙

research

∙ 09/17/2021

Sublinear-Time Computation in the Presence of Online Erasures

We initiate the study of sublinear-time algorithms that access their inp...

Iden Kalemaj, et al. ∙

research

∙ 10/25/2021

Parameterized Convexity Testing

In this work, we develop new insights into the fundamental problem of co...

Abhiruk Lahiri, et al. ∙

research

∙ 12/21/2021

Efficient reductions and algorithms for variants of Subset Sum

Given (a_1, …, a_n, t) ∈ℤ_≥ 0^n + 1, the Subset Sum problem (𝖲𝖲𝖴𝖬) is to...

Pranjal Dutta, et al. ∙

research

∙ 02/11/2022

Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time

Hrubeš and Wigderson (2015) initiated the complexity-theoretic study of ...

V. Arvind, et al. ∙

research

∙ 04/20/2022

Evaluating Commit Message Generation: To BLEU Or Not To BLEU?

Commit messages play an important role in several software engineering t...

Samanta Dey, et al. ∙

Chennai Mathematical Institute

Featured Researchers