BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Manoj Gupta

Manoj Gupta contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and Algorithmsphysics.app-phphysics.optics

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

4 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
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