Research
Research
Research
Research
18+ open-access research outputs.
The online bisection problem requires maintaining a dynamic partition of $n$ nodes into two equal-sized clusters. Requests arrive sequentially as node pairs. If the nodes lie in different clusters, th…
Perfect $L_p$ sampling in a stream was introduced by Jayaram and Woodruff (FOCS 2018) as a streaming primitive which, given turnstile updates to a vector $x \in \{-\text{poly}(n), \ldots, \text{poly}(…
We establish the first update-time separation between dynamic algorithms against oblivious adversaries and those against adaptive adversaries in natural dynamic graph problems, based on popular fine-g…
Software architecture research relies on key architectural artifacts -- Software Architectures, Reference Architectures, and Architectural Frameworks -- that underpin the design and analysis of comple…
Modern software systems are guided by hierarchical architectural concepts -- software architectures, reference architectures, and architectural frameworks -- each operating at a distinct level of abst…
We consider the problem of maintaining a proper $(\Delta + 1)$-vertex coloring in a graph on $n$-vertices and maximum degree $\Delta$ undergoing edge insertions and deletions. We give a randomized alg…
This paper presents a novel AI-powered framework designed to streamline database management and query optimization for PostgreSQL systems. Structured in three phases: Natural Language to SQL Translati…
Given a vector $x \in \mathbb{R}^n$ induced by a turnstile stream $S$, a non-negative function $G: \mathbb{R} \to \mathbb{R}$, a perfect $G$-sampler outputs an index $i$ with probability $\frac{G(x_i)…
Given points from an arbitrary metric space and a sequence of point updates sent by an adversary, what is the minimum recourse per update (i.e., the minimum number of changes needed to the set of cent…
We study the classic Euclidean Minimum Spanning Tree (MST) problem in the Massively Parallel Computation (MPC) model. Given a set $X \subset \mathbb{R}^d$ of $n$ points, the goal is to produce a spann…
We study streaming algorithms for the fundamental geometric problem of computing the cost of the Euclidean Minimum Spanning Tree (MST) on an $n$-point set $X \subset \mathbb{R}^d$. In the streaming mo…
We study the problem of approximating the eigenspectrum of a symmetric matrix $\mathbf A \in \mathbb{R}^{n \times n}$ with bounded entries (i.e., $\|\mathbf A\|_{\infty} \leq 1$). We present a simple …
In the $G$-sampling problem, the goal is to output an index $i$ of a vector $f \in\mathbb{R}^n$, such that for all coordinates $j \in [n]$, \[\textbf{Pr}[i=j] = (1 \pm \epsilon) \frac{G(f_j)}{\sum_{k\…
A large fraction of textual data available today contains various types of 'noise', such as OCR noise in digitized documents, noise due to informal writing style of users on microblogging sites, and s…
Rapid household food insecurity (HFI) tracking has been identified as a priority in the context of the COVID-19 pandemic and its aftermath. We report the validation of the Latin American and Caribbean…
Weighted automata are nondeterministic automata with numerical weights on transitions. They can define quantitative languages~$L$ that assign to each word~$w$ a real number~$L(w)$. In the case of infi…
This paper presents improved approximation algorithms for the problem of multiprocessor scheduling under uncertainty, or SUU, in which the execution of each job may fail probabilistically. This proble…
Several important decision problems on conjunctive queries (CQs) are NP-complete in general but become tractable, and actually highly parallelizable, if restricted to acyclic or nearly acyclic queries…
Free open-access publishing with Google Scholar indexing.
Submission Guide →