Amit Kumar

Indian Institute of Technology Delhi

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

Anupam Gupta

Carnegie Mellon University

Naveen Garg

Indian Institute of Technology Delhi

Ragesh Jaiswal

Indian Institute of Technology Delhi

Ravishankar Krishnaswamy

Microsoft Research (India)

Debmalya Panigrahi

Duke University

Sandeep Sen

St. Mary's Health Center

Anup Bhattacharya

Indian Institute of Technology Kharagpur

Yogish Sabharwal

IBM Research - India

Viswanath Nagarajan

University of Michigan–Ann Arbor

Sahil Singla

Google (United States)

Cooperative Institutions

Indian Institute of Technology Delhi

Carnegie Mellon University

Microsoft (United States)

Cornell University

Stanford University

Max Planck Institute for Informatics

Google (United States)

University of Maryland, College Park

ETH Zurich

Microsoft Research (United Kingdom)

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

Multifactor Authentication System

Amit Kumar Dharmendra Kumar Jhariya

Authentication plays a crucial role in our day-to-day life. Whether it is in your office, college, university, hospitals, banks, social media account, and whatnot. In the present day, most authentication systems are using a single metric to determine authenticity (i.e., password). Although there are some systems that use Multi-Factor Authentication which includes OTPs, unique codes such as Time-based codes, etc., they require an additional device to carry. In our project, we want to develop a Multi-modal Authentication system where we use the unique metrics of a person to identify him such as the face, and fingerprint. In order to develop such a system, we made use of Raspberry Pi, OpenCV, and AWS services.

Email authentication

Raspberry Pi

10.1109/pcems58491.2023.10136041

Cite

Citations (0)

Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-polynomial time

arXiv (Cornell University) (2018)

Jatin Batra Naveen Garg Amit Kumar

In the weighted flow-time problem on a single machine, we are given a set of n jobs, where each job has a processing requirement p_j, release date r_j and weight w_j. The goal is to find a preemptive schedule which minimizes the sum of weighted flow-time of jobs, where the flow-time of a job is the difference between its completion time and its released date. We give the first pseudo-polynomial time constant approximation algorithm for this problem. The running time of our algorithm is polynomial in n, the number of jobs, and P, which is the ratio of the largest to the smallest processing requirement of a job. Our algorithm relies on a novel reduction of this problem to a generalization of the multi-cut problem on trees, which we call the Demand Multi-Cut problem. Even though we do not give a constant factor approximation algorithm for the Demand Multi-Cut problem on trees, we show that the specific instances of Demand Multi-Cut obtained by reduction from weighted flow-time problem instances have more structure in them, and we are able to employ techniques based on dynamic programming. Our dynamic programming algorithm relies on showing that there are near optimal solutions which have nice smoothness properties, and we exploit these properties to reduce the size of DP table.

Constant (computer programming)

Smoothness

Maximum flow problem

10.48550/arxiv.1802.07439

Cite

Citations (1)

Stochastic Load Balancing on Unrelated Machines

Mathematics of Operations Research (2020)

Anupam Gupta Amit Kumar Viswanath Nagarajan Xiangkun Shen

We consider the problem of makespan minimization on unrelated machines when job sizes are stochastic. The goal is to find a fixed assignment of jobs to machines, to minimize the expected value of the maximum load over all the machines. For the identical-machines special case when the size of a job is the same across all machines, a constant-factor approximation algorithm has long been known. Our main result is the first constant-factor approximation algorithm for the general case of unrelated machines. This is achieved by (i) formulating a lower bound using an exponential-size linear program that is efficiently computable and (ii) rounding this linear program while satisfying only a specific subset of the constraints that still suffice to bound the expected makespan. We also consider two generalizations. The first is the budgeted makespan minimization problem, where the goal is to minimize the expected makespan subject to scheduling a target number (or reward) of jobs. We extend our main result to obtain a constant-factor approximation algorithm for this problem. The second problem involves q-norm objectives, where we want to minimize the expected q-norm of the machine loads. Here we give an [Formula: see text]-approximation algorithm, which is a constant-factor approximation for any fixed q.

Rounding

Constant (computer programming)

Minification

10.1287/moor.2019.1049

Cite

Citations (8)

Online Carpooling Using Expander Decompositions

Foundations of Software Technology and Theoretical Computer Science (2020)

Anupam Gupta Ravishankar Krishnaswamy Amit Kumar Sahil Singla

We consider the online carpooling problem: given n vertices, a sequence of edges arrive over time. When an edge e_t = (u_t, v_t) arrives at time step t, the algorithm must orient the edge either as v_t → u_t or u_t → v_t, with the objective of minimizing the maximum discrepancy of any vertex, i.e., the absolute difference between its in-degree and out-degree. Edges correspond to pairs of persons wanting to ride together, and orienting denotes designating the driver. The discrepancy objective then corresponds to every person driving close to their fair share of rides they participate in. In this paper, we design efficient algorithms which can maintain polylog(n,T) maximum discrepancy (w.h.p) over any sequence of T arrivals, when the arriving edges are sampled independently and uniformly from any given graph G. This provides the first polylogarithmic bounds for the online (stochastic) carpooling problem. Prior to this work, the best known bounds were O(√{n log n})-discrepancy for any adversarial sequence of arrivals, or O(log log n)-discrepancy bounds for the stochastic arrivals when G is the complete graph. The technical crux of our paper is in showing that the simple greedy algorithm, which has provably good discrepancy bounds when the arriving edges are drawn uniformly at random from the complete graph, also has polylog discrepancy when G is an expander graph. We then combine this with known expander-decomposition results to design our overall algorithm.

Degree (music)

Expander graph

Sequence (biology)

Online algorithm

10.4230/lipics.fsttcs.2020.23

Cite

Citations (4)

Machine Translation by Projecting Text into the Same Phonetic-Orthographic Space Using a Common Encoding

arXiv (Cornell University) (2023)

Amit Kumar Shantipriya Parida Ajay Pratap A. K. Singh

The use of subword embedding has proved to be a major innovation in Neural Machine Translation (NMT). It helps NMT to learn better context vectors for Low Resource Languages (LRLs) so as to predict the target words by better modelling the morphologies of the two languages and also the morphosyntax transfer. Even so, their performance for translation in Indian language to Indian language scenario is still not as good as for resource-rich languages. One reason for this is the relative morphological richness of Indian languages, while another is that most of them fall into the extremely low resource or zero-shot categories. Since most major Indian languages use Indic or Brahmi origin scripts, the text written in them is highly phonetic in nature and phonetically similar in terms of abstract letters and their arrangements. We use these characteristics of Indian languages and their scripts to propose an approach based on common multilingual Latin-based encodings (WX notation) that take advantage of language similarity while addressing the morphological complexity issue in NMT. These multilingual Latin-based encodings in NMT, together with Byte Pair Embedding (BPE) allow us to better exploit their phonetic and orthographic as well as lexical similarities to improve the translation quality by projecting different but similar languages on the same orthographic-phonetic character space. We verify the proposed approach by demonstrating experiments on similar language pairs (Gujarati-Hindi, Marathi-Hindi, Nepali-Hindi, Maithili-Hindi, Punjabi-Hindi, and Urdu-Hindi) under low resource conditions. The proposed approach shows an improvement in a majority of cases, in one case as much as ~10 BLEU points compared to baseline techniques for similar language pairs. We also get up to ~1 BLEU points improvement on distant and zero-shot language pairs.

Marathi

Transliteration

Bilingual dictionary

10.48550/arxiv.2305.12371

Cite

Citations (0)

Bag-Of-Tasks Scheduling on Related Machines

International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (2021)

Anupam Gupta Amit Kumar Sahil Singla

We consider online scheduling to minimize weighted completion time on related machines, where each job consists of several tasks that can be concurrently executed. A job gets completed when all its component tasks finish. We obtain an O(K³ log² K)-competitive algorithm in the non-clairvoyant setting, where K denotes the number of distinct machine speeds. The analysis is based on dual-fitting on a precedence-constrained LP relaxation that may be of independent interest.

Competitive Analysis

Processor scheduling

10.4230/lipics.approx/random.2021.3

Cite

Citations (0)

Uniform Number of a Graph

Iranian Journal of Mathematical Sciences and Informatics (2020)

Amit Kumar Elakkiya Mohankumar

Source

Cite

Citations (0)

In-Silico Consideration of Anti-Microbial Prospective of Plant Phenolic and Flavonoids

Middle East Research Journal of Pharmaceutical Sciences (2022)

Amit Kumar Jitender K Malik

Abstract: Background: Pathogenic microorganism infections pose a serious threat to human health. The need for innovative, safe, and efficient antimicrobial medicines has been driven by rising drug resistance cases, unfavorable antibiotic side effects, and the reemergence of previously identified illnesses. Virtual screening techniques used in drug development, such as drug-likeness and ADMET analysis, use computation to quickly and cheaply identify compounds that are likely to demonstrate physiological activity. Methods: In this regard, the enzyme aminoacyl-tRNA synthetase (AaRS) has been the focus of recent research in the discovery of antibacterial agents. Docking studies were performed Molecular docking of aminoacyl-tRNA synthetase (AaRS) with chlorogenic acid, rutin, quercetin and gallic acid was carried out by AutoDock. Results: The molecular docking result revealed that chlorogenic acid, gallic acid, quercetin and rutin showed encouraging docking score. Hence from above finding it can be predicted that phenolics and flavonoids found in the plants extract exhibited good inhibitor of IleRS enzyme.

Chlorogenic Acid

Docking (animal)

AutoDock

10.36348/merjps.2022.v02i01.001

Cite

Citations (0)

Linear-time approximation schemes for clustering problems in any dimensions

Journal of the ACM (2010)

Amit Kumar Yogish Sabharwal Sandeep Sen

We present a general approach for designing approximation algorithms for a fundamental class of geometric clustering problems in arbitrary dimensions. More specifically, our approach leads to simple randomized algorithms for the k -means, k -median and discrete k -means problems that yield (1+ε) approximations with probability ≥ 1/2 and running times of O (2 ( k /ε) O (1) dn ). These are the first algorithms for these problems whose running times are linear in the size of the input ( nd for n points in d dimensions) assuming k and ε are fixed. Our method is general enough to be applicable to clustering problems satisfying certain simple properties and is likely to have further applications.

Randomized Algorithm

10.1145/1667053.1667054

Cite

Citations (135)

Building Edge-Failure Resilient Networks

Lecture notes in computer science (2002)

Chandra Chekuri Anupam Gupta Amit Kumar Joseph Naor Danny Raz

Provisioning

traceroute

10.1007/3-540-47867-1_31

Cite

Citations (19)