BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Manoj Gupta

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

ResearcherUnclaimed source record
Data Structures and Algorithmsphysics.app-phphysics.optics

Catalog footprint

What is connected

10works
3topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

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

10 published item(s)

preprint2022arXiv

Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path problem

In a graph $G$ with a source $s$, we design a distance oracle that can answer the following query: Query$(s,t,e)$ -- find the length of shortest path from a fixed source $s$ to any destination vertex $t$ while avoiding any edge $e$. We design a deterministic algorithm that builds such an oracle in $\tilde{O}(m\sqrt n)$ time. Our oracle uses $\tilde{O}(n\sqrt n)$ space and can answer queries in $\tilde{O}(1)$ time. Our oracle is an improvement of the work of Bilò et al. (ESA 2021) in the preprocessing time, which constructs the first deterministic oracle for this problem in $\tilde{O}(m\sqrt n+n^2)$ time. Using our distance oracle, we also solve the {\em single source replacement path problem} (SSR problem). Chechik and Cohen (SODA 2019) designed a randomized combinatorial algorithm to solve the SSR problem. The running time of their algorithm is $\tilde{O}(m\sqrt n + n^2)$. In this paper, we show that the SSR problem can be solved in $\tilde{O}(m\sqrt n + |\mathcal{R}|)$ time, where $\mathcal{R}$ is the output set of the SSR problem in $G$. Our SSR algorithm is optimal (upto polylogarithmic factor) as there is a conditional lower bound of $Ω(m\sqrt n)$ for any combinatorial algorithm that solves this problem.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Multiple Source Replacement Path Problem

One of the classical line of work in graph algorithms has been the Replacement Path Problem: given a graph $G$, $s$ and $t$, find shortest paths from $s$ to $t$ avoiding each edge $e$ on the shortest path from $s$ to $t$. These paths are called replacement paths in literature. For an undirected and unweighted graph, (Malik, Mittal, and Gupta, Operation Research Letters, 1989) and (Hershberger and Suri, FOCS 2001) designed an algorithm that solves the replacement path problem in $\tilde O(m+n)$ time. It is natural to ask whether we can generalize the replacement path problem: {\em can we find all replacement paths from a source $s$ to all vertices in $G$?} This problem is called the Single Source Replacement Path Problem. Recently (Chechik and Cohen, SODA 2019) designed a randomized combinatorial algorithm that solves the Single Source Replacement Path Problem in $\tilde O(m\sqrt n\ + n^2)$ time. One of the questions left unanswered by their work is the case when there are many sources, not one. When there are $n$ sources, the combinatorial algorithm of (Bernstein and Karger, STOC 2009) can be used to find all pair replacement path in $\tilde O(mn + n^3)$ time. However, there is no result known for any general $σ$. Thus, the problem we study is defined as follows: given a set of $σ$ sources, we want to find the replacement path from these sources to all vertices in $G$. We give a randomized combinatorial algorithm for this problem that takes $\tilde O(m\sqrt{n σ} +\ σn^2)$ time. This result generalizes both results known for this problem. Our algorithm is much different and arguably simpler than (Chechik and Cohen, SODA 2019). Like them, we show a matching conditional lower bound using the Boolean Matrix Multiplication conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Terahertz sensing of 7nm dielectric film with bound states in the continuum metasurfaces

Fingerprint spectral response of several materials with terahertz electromagnetic radiation indicates that terahertz technology is an effective tool for sensing applications. However, sensing few nanometer thin-film of dielectrics with much longer terahertz waves (1 THz = 0.3 mm) is challenging. Here, we demonstrate a quasi-bound state in the continuum (BIC) resonance for sensing of nanometer scale thin analyte deposited on a flexible metasurface. The large sensitivity originates from strong local field confinement of the quasi-BIC Fano resonance state and extremely low absorption loss of a low-index cyclic olefin copolymer substrate. A minimum thickness of 7 nm thin-film of germanium is sensed on the metasurface, which corresponds to a deep subwavelength length scale of λ/43000, where λ is the resonance wavelength. The low-loss, flexible and large mechanical strength of the quasi-BIC micro structured metamaterial sensor could be an ideal platform for developing ultrasensitive wearable terahertz sensors.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Better Analysis of GREEDY Binary Search Tree on Decomposable Sequences

In their seminal paper [Sleator and Tarjan, J.ACM, 1985], the authors conjectured that the splay tree is dynamically optimal binary search tree (BST). In spite of decades of intensive research, the problem remains open. Perhaps a more basic question, which has also attracted much attention, is if there exists any dynamically optimal BST algorithm. One such candidate is GREEDY which is a simple and intuitive BST algorithm [Lucas, Rutgers Tech. Report, 1988; Munro, ESA, 2000; Demaine, Harmon, Iacono, Kane and Patrascu, SODA, 2009]. [Demaine et al., SODA, 2009] showed a novel connection between a geometric problem. Since dynamic optimality conjecture in its most general form remains elusive despite much effort, researchers have studied this problem on special sequences. Recently, [Chalermsook, Goswami, Kozma, Mehlhorn and Saranurak, FOCS, 2015] studied a type of sequences known as $k$-{\em decomposable sequences} in this context, where $k$ parametrizes easiness of the sequence. Using tools from forbidden submatrix theory, they showed that GREEDY takes $n2^{O(k^2)}$ time on this sequence and explicitly raised the question of improving this bound. In this paper, we show that GREEDY takes $O(n \log{k})$ time on $k$-decomposable sequences. In contrast to the previous approach, ours is based on first principles. One of the main ingredients of our result is a new construction of a lower bound certificate on the performance of any algorithm. This certificate is constructed using the execution of GREEDY, and is more nuanced and possibly more flexible than the previous independent set certificate of Demaine et al. This result, which is applicable to all sequences, may be of independent interest and may lead to further progress in analyzing GREEDY on $k$-decomposable as well as general sequences.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Fully dynamic maximal matching in O(log n) update time

We present an algorithm for maintaining maximal matching in a graph under addition and deletion of edges. Our data structure is randomized that takes O(log n) expected amortized time for each edge update where n is the number of vertices in the graph. While there is a trivial O(n) algorithm for edge update, the previous best known result for this problem for a graph with n vertices and m edges is O({(n+ m)}^{0.7072})which is sub-linear only for a sparse graph. For the related problem of maximum matching, Onak and Rubinfield designed a randomized data structure that achieves O(log^2 n) amortized time for each update for maintaining a c-approximate maximum matching for some large constant c. In contrast, we can maintain a factor two approximate maximum matching in O(log n) expected time per update as a direct corollary of the maximal matching scheme. This in turn also implies a two approximate vertex cover maintenance scheme that takes O(log n) expected time per update.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Simple and Faster algorithm for Reachability in a Decremental Directed Graph

Consider the problem of maintaining source sink reachability($st$-Reachability), single source reachability(SSR) and strongly connected component(SCC) in an edge decremental directed graph. In particular, we design a randomized algorithm that maintains with high probability: 1) $st$-Reachability in $\tilde{O}(mn^{4/5})$ total update time. 2) $st$-Reachability in a total update time of $\tilde{O}(n^{8/3})$ in a dense graph. 3) SSR in a total update time of $\tilde{O}(m n^{9/10})$. 4) SCC in a total update time of $\tilde{O}(m n^{9/10})$. For all the above problems, we improve upon the previous best algorithm (by Henzinger et. al. (STOC 2014)). Our main focus is maintaining $st$-Reachability in an edge decremental directed graph (other problems can be reduced to $st$-Reachability). The classical algorithm of Even and Shiloach (JACM 81) solved this problem in $O(1)$ query time and $O(mn)$ total update time. Recently, Henzinger, Krinninger and Nanongkai (STOC 2014) designed a randomized algorithm which achieves an update time of $\tilde{O}(m n^{0.98})$ and broke the long-standing $O(mn)$ bound of Even and Shiloach. However, they designed four algorithms $A_i (1\le i \le 4)$ such that for graphs having total number of edges between $m_i$ and $m_{i+1}$ ($m_{i+1} > m_i$), $A_i$ outperforms other three algorithms. That is, one of the four algorithms may be faster for a particular density range of edges, but it may be too slow asymptotically for the other ranges. Our main contribution is that we design a {\it single} algorithm which works for all types of graphs. Not only is our algorithm faster, it is much simpler than the algorithm designed by Henzinger et.al. (STOC 2014).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Fully Dynamic $(1+ε)$-Approximate Matchings

We present the first data structures that maintain near optimal maximum cardinality and maximum weighted matchings on sparse graphs in sublinear time per update. Our main result is a data structure that maintains a $(1+ε)$ approximation of maximum matching under edge insertions/deletions in worst case $O(\sqrt{m}ε^{-2})$ time per update. This improves the 3/2 approximation given in [Neiman,Solomon,STOC 2013] which runs in similar time. The result is based on two ideas. The first is to re-run a static algorithm after a chosen number of updates to ensure approximation guarantees. The second is to judiciously trim the graph to a smaller equivalent one whenever possible. We also study extensions of our approach to the weighted setting, and combine it with known frameworks to obtain arbitrary approximation ratios. For a constant $ε$ and for graphs with edge weights between 1 and N, we design an algorithm that maintains an $(1+ε)$-approximate maximum weighted matching in $O(\sqrt{m} \log N)$ time per update. The only previous result for maintaining weighted matchings on dynamic graphs has an approximation ratio of 4.9108, and was shown in [Anand,Baswana,Gupta,Sen, FSTTCS 2012, arXiv 2012].

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs

We present a fully dynamic algorithm for maintaining approximate maximum weight matching in general weighted graphs. The algorithm maintains a matching ${\cal M}$ whose weight is at least $1/8 M^{*}$ where $M^{*}$ is the weight of the maximum weight matching. The algorithm achieves an expected amortized $O(\log n \log \mathcal C)$ time per edge insertion or deletion, where $\mathcal C$ is the ratio of the weights of the highest weight edge to the smallest weight edge in the given graph. Using a simple randomized scaling technique, we are able to obtain a matching whith expected approximation ratio 4.9108.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On Dynamic Optimality for Binary Search Trees

Does there exist O(1)-competitive (self-adjusting) binary search tree (BST) algorithms? This is a well-studied problem. A simple offline BST algorithm GreedyFuture was proposed independently by Lucas and Munro, and they conjectured it to be O(1)-competitive. Recently, Demaine et al. gave a geometric view of the BST problem. This view allowed them to give an online algorithm GreedyArb with the same cost as GreedyFuture. However, no o(n)-competitive ratio was known for GreedyArb. In this paper we make progress towards proving O(1)-competitive ratio for GreedyArb by showing that it is O(\log n)-competitive.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The update complexity of selection and related problems

We present a framework for computing with input data specified by intervals, representing uncertainty in the values of the input parameters. To compute a solution, the algorithm can query the input parameters that yield more refined estimates in form of sub-intervals and the objective is to minimize the number of queries. The previous approaches address the scenario where every query returns an exact value. Our framework is more general as it can deal with a wider variety of inputs and query responses and we establish interesting relationships between them that have not been investigated previously. Although some of the approaches of the previous restricted models can be adapted to the more general model, we require more sophisticated techniques for the analysis and we also obtain improved algorithms for the previous model. We address selection problems in the generalized model and show that there exist 2-update competitive algorithms that do not depend on the lengths or distribution of the sub-intervals and hold against the worst case adversary. We also obtain similar bounds on the competitive ratio for the MST problem in graphs.

0 citations0 reviewsNo code linkedOpen access