Source author record

Rahul Mehta

Rahul Mehta appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

4works
4topics
1close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

4 published item(s)

preprint2020arXiv

Correlated Mixed Membership Modeling of Somatic Mutations

Recent studies of cancer somatic mutation profiles seek to identify mutations for targeted therapy in personalized medicine. Analysis of profiles, however, is not trivial, as each profile is heterogeneous and there are multiple confounding factors that influence the cause-and-effect relationships between cancer genes such as cancer (sub)type, biological processes, total number of mutations, and non-linear mutation interactions. Moreover, cancer is biologically redundant, i.e., distinct mutations can result in the alteration of similar biological processes, so it is important to identify all possible combinatorial sets of mutations for effective patient treatment. To model this phenomena, we propose the correlated zero-inflated negative binomial process to infer the inherent structure of somatic mutation profiles through latent representations. This stochastic process takes into account different, yet correlated, co-occurring mutations using profile-specific negative binomial dispersion parameters that are mixed with a correlated beta-Bernoulli process and a probability parameter to model profile heterogeneity. These model parameters are inferred by iterative optimization via amortized and stochastic variational inference using the Pan Cancer dataset from The Cancer Genomic Archive (TCGA). By examining the the latent space, we identify biologically relevant correlations between somatic mutations.

preprint2014arXiv

2048 is (PSPACE) Hard, but Sometimes Easy

We prove that a variant of 2048, a popular online puzzle game, is PSPACE-Complete. Our hardness result holds for a version of the problem where the player has oracle access to the computer player's moves. Specifically, we show that for an $n \times n$ game board $\mathcal{G}$, computing a sequence of moves to reach a particular configuration $\mathbb{C}$ from an initial configuration $\mathbb{C}_0$ is PSPACE-Complete. Our reduction is from Nondeterministic Constraint Logic (NCL). We also show that determining whether or not there exists a fixed sequence of moves $\mathcal{S} \in \{\Uparrow, \Downarrow, \Leftarrow, \Rightarrow\}^k$ of length $k$ that results in a winning configuration for an $n \times n$ game board is fixed-parameter tractable (FPT). We describe an algorithm to solve this problem in $O(4^k n^2)$ time.

preprint2014arXiv

A New Push-Relabel Algorithm for Sparse Networks

In this paper, we present a new push-relabel algorithm for the maximum flow problem on flow networks with $n$ vertices and $m$ arcs. Our algorithm computes a maximum flow in $O(mn)$ time on sparse networks where $m = O(n)$. To our knowledge, this is the first $O(mn)$ time push-relabel algorithm for the $m = O(n)$ edge case; previously, it was known that push-relabel implementations could find a max-flow in $O(mn)$ time when $m = Ω(n^{1+ε})$ (King, et. al., SODA `92). This also matches a recent flow decomposition-based algorithm due to Orlin (STOC `13), which finds a max-flow in $O(mn)$ time on sparse networks. Our main result is improving on the Excess-Scaling algorithm (Ahuja & Orlin, 1989) by reducing the number of nonsaturating pushes to $O(mn)$ across all scaling phases. This is reached by combining Ahuja and Orlin's algorithm with Orlin's compact flow networks. A contribution of this paper is demonstrating that the compact networks technique can be extended to the push-relabel family of algorithms. We also provide evidence that this approach could be a promising avenue towards an $O(mn)$-time algorithm for all edge densities.

preprint2013arXiv

Max-Flows on Sparse and Dense Networks

In this paper, we present an improved algorithm for the maximum flow problem on general networks with $n$ vertices and $m$ arcs. We show how to solve the problem in $O(mn)$ time, when $m = O(n^{2-ε})$, for some $0 <ε\leq 1$. This improves upon the results of both Orlin and King, et. al., who solved the problem in $O(mn + m^{31/16} \log^2 n)$ and $O(mn\log_{m/n\log n}n)$ time, respectively. Our main result is reducing the number of nonsaturating pushes to $O(mn)$ across all scaling phases. Our algorithm can be seen as complementary to King, et. al., in the sense that we solve the max-flow problem in $O(mn)$ time when $m = O(n^{2-ε})$ (all sparse and non-dense networks), whereas King, et. al. solve it in $O(mn)$ time when $m = Ω(n^{1+ε})$ (all dense and non-sparse networks). Our improvement is reached by a novel combination of Ahuja and Orlin's excess scaling method and Orlin's compact flow networks. To our knowledge, this is the first $O(mn)$ time max-flow algorithm that runs on this range of networks. Further, we extend the range of Orlin's $O(mn)$ time algorithm from $O(n^{16/15-ε})$ to $O(n^{2-ε})$, which is an improvement of approximately $O(n^{0.94})$. Our result also establishes that the problem can be solved for all $n$ and $m$ using exclusively the push-relabel method. We also give improved algorithms for parametric flows and efficiently constructing Gomory-Hu trees, and suggest a new approach to the minimum-cost flow problem.