Ashish Saxena

Ashish Saxena, Anisur Rahaman Molla, Kaushik Mondal et al.

We study the fundamental problem of graph exploration in dynamic graphs using mobile agents. We consider $1$-interval connected dynamic graphs, where the topology may change arbitrarily from round to round as long as the graph remains connected, and edges are assigned with the dynamic port labeling at each round. The execution follows a semi-synchronous scheduler, under which an adversary may deactivate an arbitrary subset of agents in each round. For a graph with $n$ nodes and $k$ agents, we show that exploration is impossible if the adversary can deactivate at least $ \left\lceil \frac{k}{n-2} \right\rceil - 1$ agents per round, even when agents are equipped with unbounded memory, have global communication and full visibility. This yields an upper bound, implying that exploration is solvable only when the adversary deactivates at most $\left\lceil \frac{k}{n-2} \right\rceil - 2$ agents per round. We further establish that achieving exploration at this threshold requires agents to have both $1$-hop visibility and $1$-hop communication. Finally, we present the exploration algorithm using $k$ agents when the adversary deactivates at most $ \left\lceil \frac{k}{n-2} \right\rceil - 2$ agents, assuming agents are equipped with $1$-hop visibility and global communication, and matches the adversarial deactivation bound implied by the impossibility results.

Tanvir Kaur, Ashish Saxena

A black hole is a harmful node in a graph that destroys any agent entering it, making its identification a critical task. In the \emph{Black Hole Search with Verification (BHSV)} problem, a team of agents operates on a graph $G$ with the objective that at least one agent survives and correctly identifies an edge incident to the black hole; if no black hole exists, then all agents must terminate. Prior work has studied BHS in arbitrary dynamic graphs under the restrictive \emph{face-to-face} communication model, where agents can exchange information only when co-located. This constraint significantly increases the number of agents required to solve the problem. In this work, we strengthen the capabilities of agents by equipping them with (i) \emph{1-hop visibility}, (ii) \emph{global communication}, and (iii) both \emph{1-hop visibility} and \emph{global communication}. We show that these enhancements lead to more efficient solutions for the BHSV problem in dynamic graphs.

Junpeng Lao, Christopher Suter, Ian Langmore et al.

Markov chain Monte Carlo (MCMC) is widely regarded as one of the most important algorithms of the 20th century. Its guarantees of asymptotic convergence, stability, and estimator-variance bounds using only unnormalized probability functions make it indispensable to probabilistic programming. In this paper, we introduce the TensorFlow Probability MCMC toolkit, and discuss some of the considerations that motivated its design.