3,305 research outputs found
Tideglusib: The Miracle Molecule for Tooth Repair
No full textGuest Comment by Sahil Gupta titled "Tideglusib: The Miracle Molecule for Tooth Repair
Possible worlds explorer: Combining declarative programming with user-friendly Jupyter Notebooks
No full text"Datalog and Answer Set Programming (ASP) are powerful languages for rule-based database querying and constraint solving, respectively. Similarly, Python is a popular and powerful procedural programming language with applications in many domains including data science. I have developed a problem solving framework called ""Possible Worlds Exploration"" which is based on combining the two programming paradigms to enable new exploration and problem solving capabilities for a wide audience of users. The primary component of this framework is the Possible Worlds Explorer (PWE), an open source Python-based toolkit that employs Jupyter Notebooks to make working with Datalog and ASP systems easier and more productive. PWE can parse output from different ASP reasoners (Clingo and DLV) and then run analytical queries over all answer sets or ""possible worlds"" (PWs), e.g., to calculate relative frequencies of atoms across PWs or to hierarchically cluster PWs based on user-defined complexity and similarity measures. PWE also has support for the three-valued well-founded semantics of Datalog programs (via DLV) and temporal models that use a special state argument. Using simple Python functions, generic as well as user-definable presentation and visualization formats can be easily created, e.g., to display all PWs (world views), the unique three-valued well founded model (partial views), and temporal models (timelines and time series). We have illustrated several examples, both theoretical and application-based, to showcase the abilities of PWE. We provide containerized versions of PWE that can be run in the cloud or locally. In this way the Possible Worlds Explorer makes Datalog and ASP more accessible for a wider audience."Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-08-25 without embargo termsThe student, Sahil Gupta, accepted the attached license on 2020-05-08 at 11:58.The student, Sahil Gupta, submitted this Thesis for approval on 2020-05-08 at 12:14.This Thesis was approved for publication on 2020-05-11 at 13:24.DSpace SAF Submission Ingestion Package generated from Vireo submission #15293 on 2020-08-25 at 17:13:29Made available in DSpace on 2020-08-26T21:57:58Z (GMT). No. of bitstreams: 2
GUPTA-THESIS-2020.pdf: 9645619 bytes, checksum: 7cddedaa0daff10449bbc775af5834d0 (MD5)
LICENSE.txt: 4208 bytes, checksum: 36c9b3f9593202cab0e1a98edf91e325 (MD5)
Previous issue date: 2020-05-1
Bag-Of-Tasks Scheduling on Related Machines
No full textWe 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
Tracking objects and distinguishing their states by watching egocentric videos
No full textSubmission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-11 without embargo termsThe student, Sahil Modi, accepted the attached license on 2022-04-20 at 10:51.The student, Sahil Modi, submitted this Thesis for approval on 2022-04-20 at 10:57.This Thesis was approved for publication on 2022-04-26 at 15:01.DSpace SAF Submission Ingestion Package generated from Vireo submission #17835 on 2022-11-11 at 13:42:25Interactive object understanding, or what we can do to objects and how, is a long-standing goal of computer vision. However, the inherent ambiguity of this task makes it difficult to annotate, and very few large-scale datasets exist. We realize that videos, especially egocentric ones, naturally contain this information through objects undergoing constant state changes, but learning from this data is nontrivial. Furthermore, objects are difficult to track in egocentric settings due to occlusion, drastic pose changes, and viewpoint changes. In this thesis, we propose solutions for these two challenges by (1) taking advantage of existing sparse annotations and self-supervision to achieve state-of-the-art tracking performance on TREK-150 and (2) observing human hands and their interactions with objects to learn object state-sensitive features in a self-supervised manner
Retracted: Robotic Process Automation use cases in academia and early implementation experiences
No full textAbstract Retraction: [Ankur Gupta, Purnendu Prabhat, Sahil Sawhney, Rajesh Gupta, Sudeep Tanwar, Neeraj Kumar, Mohammad Shabaz, Robotic Process Automation use cases in academia and early implementation experiences, IET Software 2022 (https://doi.org/10.1049/sfw2.12061)]. The above article from IET Software, published online on 19 May 2022 in Wiley Online Library (wileyonlinelibrary.com), has been retracted by agreement between the Editor‐in‐Chief, Hana Chockler, the Institution of Engineering and Technology (the IET) and John Wiley and Sons Ltd. This article was published as part of a Guest Edited special issue. Following an investigation, the IET and the journal have determined that the article was not reviewed in line with the journal’s peer review standards and there is evidence that the peer review process of the special issue underwent systematic manipulation. Accordingly, we cannot vouch for the integrity or reliability of the content. As such we have taken the decision to retract the article. The authors have been informed of the decision to retract
JHC-17-0093.R3_Production_Supplemental_Figures – Supplemental material for Increased Insulin-like Growth Factor Binding Protein-1 Phosphorylation in Decidualized Stromal Mesenchymal Cells in Human Intrauterine Growth Restriction Placentas
No full textSupplemental material, JHC-17-0093.R3_Production_Supplemental_Figures for Increased Insulin-like Growth Factor Binding Protein-1 Phosphorylation in Decidualized Stromal Mesenchymal Cells in Human Intrauterine Growth Restriction Placentas by Sahil S. Singal, Karen Nygard, Robert Gratton, Thomas Jansson and Madhulika B. Gupta in Journal of Histochemistry & Cytochemistry</p
Non-Clairvoyant Precedence Constrained Scheduling
No full textWe consider the online problem of scheduling jobs on identical machines, where jobs have precedence constraints. We are interested in the demanding setting where the jobs sizes are not known up-front, but are revealed only upon completion (the non-clairvoyant setting). Such precedence-constrained scheduling problems routinely arise in map-reduce and large-scale optimization. For minimizing the total weighted completion time, we give a constant-competitive algorithm. And for total weighted flow-time, we give an O(1/epsilon^2)-competitive algorithm under (1+epsilon)-speed augmentation and a natural "no-surprises" assumption on release dates of jobs (which we show is necessary in this context).
Our algorithm proceeds by assigning virtual rates to all waiting jobs, including the ones which are dependent on other uncompleted jobs. We then use these virtual rates to decide on the actual rates of minimal jobs (i.e., jobs which do not have dependencies and hence are eligible to run). Interestingly, the virtual rates are obtained by allocating time in a fair manner, using a Eisenberg-Gale-type convex program (which we can solve optimally using a primal-dual scheme). The optimality condition of this convex program allows us to show dual-fitting proofs more easily, without having to guess and hand-craft the duals. This idea of using fair virtual rates may have broader applicability in scheduling problems
Online Carpooling Using Expander Decompositions
No full textWe 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
Robust Algorithms for the Secretary Problem
No full textIn classical secretary problems, a sequence of n elements arrive in a uniformly random order, and we want to choose a single item, or a set of size K. The random order model allows us to escape from the strong lower bounds for the adversarial order setting, and excellent algorithms are known in this setting. However, one worrying aspect of these results is that the algorithms overfit to the model: they are not very robust. Indeed, if a few "outlier" arrivals are adversarially placed in the arrival sequence, the algorithms perform poorly. E.g., Dynkin’s popular 1/e-secretary algorithm is sensitive to even a single adversarial arrival: if the adversary gives one large bid at the beginning of the stream, the algorithm does not select any element at all.
We investigate a robust version of the secretary problem. In the Byzantine Secretary model, we have two kinds of elements: green (good) and red (rogue). The values of all elements are chosen by the adversary. The green elements arrive at times uniformly randomly drawn from [0,1]. The red elements, however, arrive at adversarially chosen times. Naturally, the algorithm does not see these colors: how well can it solve secretary problems?
We show that selecting the highest value red set, or the single largest green element is not possible with even a small fraction of red items. However, on the positive side, we show that these are the only bad cases, by giving algorithms which get value comparable to the value of the optimal green set minus the largest green item. (This benchmark reminds us of regret minimization and digital auctions, where we subtract an additive term depending on the "scale" of the problem.) Specifically, we give an algorithm to pick K elements, which gets within (1-ε) factor of the above benchmark, as long as K ≥ poly(ε^{-1} log n). We extend this to the knapsack secretary problem, for large knapsack size K.
For the single-item case, an analogous benchmark is the value of the second-largest green item. For value-maximization, we give a poly log^* n-competitive algorithm, using a multi-layered bucketing scheme that adaptively refines our estimates of second-max over time. For probability-maximization, we show the existence of a good randomized algorithm, using the minimax principle.
We hope that this work will spur further research on robust algorithms for the secretary problem, and for other problems in sequential decision-making, where the existing algorithms are not robust and often tend to overfit to the model
- …
