|
|
Posters
25 November, 12:20-13:00
|
Ayan Bhattacharya (ISI, Kolkata)
|
Regularly varying branching random walk: branching process in Markovian environment
|
|
We obtain the point process convergence for the branching random walk with regularly varying step size. In this poster we consider the case where the underlying genealogical tree comes from branching process in Markovian environment. This is a joint work with Zbigniew Palmowski.
|
|
Arko Chatterjee
(IIT, Bombay)
|
How to Defend: Network Coordination and Stability
|
|
In networks, the question of paramount importance is how does a network change from one equilibrium to another equilibrium. A closely related question is to see whether a particular equilibrium is stable or not when new nodes (invaders) join the network. In this paper, we address this question. In particular, we address the behaviour of a network when the network is subjected to invasions. Under what conditions is a node in the network “initially” going to change its existing strategy, especially when it is an equilibrium strategy? Fundamentally, we are not asking for the set of nodes which when triggered would create the maximum possible cascading effect. Instead, we are asking when and how would a node in the network get triggered at all?
|
|
Sarat Babu Moka (TIFR, Bombay)
|
Perfect Sampling and Estimation for Gibbs Point Processes
|
|
Monte Carlo algorithms are ubiquitous in many applied domains. A fundamental and essential ingredient of Monte Carlo simulation is to generate random samples from some underlying probability distributions and estimate the associated parameters. We consider and analyze a simple acceptance-rejection (AR) based sampling algorithm for generating perfect (or, unbiased) samples from Gibbs point processes, the family of spatial point processes that are absolutely continuous with respect to some Poisson point process; examples include Area-interaction processes, Strauss processes, Ising models, Loss systems. Our primary focus is on the {\it hard-sphere} model, which is a set of randomly generated spheres on a space such that the centers of the spheres constitute a Poisson point process conditioned that no sphere overlaps with any other sphere. We propose a modified AR method, based upon {\it importance sampling} techniques, that is shown to be improving the running time complexity significantly compare with the naive AR method. We show that the proposed method performs better than an existing {\it dominated coupling from the past} based method in many asymptotic regimes. We further develop and analyze importance sampling and infinite series based representations that are seen to provide unbiased estimators for functions of these point processes. The proofs of the effectiveness of both perfect sampling and estimation algorithm for a hard-sphere model depends on our large deviations analysis of no overlap probability of spheres when their centers are distributed as a homogeneous Poisson point process; this analysis may also be of independent interest.
|
25 November, 17:30-18:30
|
Tulasi Ram Reddy (NYU, Abu Dhabi)
|
Recurrent Rotor-Router configurations
|
|
Rotor-Router walks are deterministic analogues of random walks
determined completely by the initial rotor-router configurations. I will
discuss some known results about these models and end with an open
question.
|
|
Krishanu Maulik (ISI, Kolkata)
|
Generalization of Perron Frobenius theorem
|
|
Perron Frobenius theorem for positive regular or irreducible matrices are well known and provide for a unique real positive eigenvalue which exceeds the real part of any other eigenvalue. Furthermore, it is known that the said eigenvalue is the only one whose eigenvector can have all coordinates positive. The theorem has useful application in Markov chain theory, for example. A theorem due to Krein and Rutman generalizes the result to higher dimension, but has some limitation. We shall discuss these issues.
|
|
Yogeshwaran D (ISI, Bangalore)
|
Spectral gap of Laplacian of random geometric graphs
|
|
We consider the random geometric graph formed by 'n' points in a unit Euclidean ball with edges placed between points within a unit distance. We are interested in the asymptotic
spectral gap of the normalised Laplacian of this graph. I shall mention known results, some motivation arising from random topology and possible extensions.
|
26 November, 12:20-13:00
|
Wolfgang Loehr (Universitat Duisberg-Essen)
|
Scaling limits for tree-valued stochastic processes
|
|
Many models of random graph-theoretic trees are known to have the Brownian continuum random tree (CRT) as scaling limit. For (finite) tree-valued Markov chains, it is often only conjectured that they converge to a continuum tree-valued processes with the CRT as stationary distribution. Examples are the subtree-prune-and-regraft and the Aldous move on cladograms.
|
|
Rajat Subhra Hazra (ISI, Kolkata)
|
Level set percolation for Gaussian free field
|
|
In this talk I will present some recent results and conjectures on level set percolation on Gaussian free field.
|
26 November, 17:30-18:30
|
Atul Sekhar (ISI, Bangalore)
|
Entropy Influence Conjecture
|
|
Entropy-Influence conjecture was posed by Ehud Friedgut and Gil Kalai. It is a speculative statement about binary functions and gives a quantitative relation between total influence and entropy of binary functions. The conjecture has variety of applications in graph theory, coding theory and in metric spaces. The famous KKL theorem follows from the conjecture as its corollary. In this talk, we will explain the statement of the conjecture, see some of its application and take a look at some works in this direction.
|
|
Srikanth Iyer (IISc, Bangalore)
|
Connecting the random connection model
|
|
A random geometric graph (RGG) has as its vertex set, points distributed in the d-dimensional Euclidean space with edges
between any pair of vertices that are at some distance r apart. It is known that this graph gets connected with high probability at
the same critical radius at which isolated nodes vanish. This question has been answered for a soft-random geometric graph, a graph
in which the edges in a RGG is retained with probability p, independently of everything else. We present some result for a more
general random connection model and present a sufficient condition for the graph to be connected. It remains open whether vanishing
of isolated nodes is sufficient to ensure connectivity.
|
|
Parimal Parag (IISc, Bangalore)
|
Job completion time for jobs served by a pool of servers
|
|
In distributed systems, an important parameter is completion time for a
single job that can be served by a set of servers. Two such examples are download time of a content stored on a distributed storage system and computation time of an application run on a compute
cluster. In a coded distributed system, each job can be served by an equal sized
subset of all servers. However, a server can only serve one job at a time, and the service time
of each job is an iid random variable. We are interested in characterizing the job completion time for a finite
number of such jobs.
|
28 November, 12:20-13:00
|
Veeraruna Kavitha (IIT, Bombay)
|
Random Fixed Points, Their Limits and applications to Finance
|
|
We consider a sequence of random fixed points, with corresponding domains increasing to R^infinity. We would like to study the limit (if it exists) of such random fixed points. This kind of a sequence of random fixed points can, for example, arise in large financial networks.
Consider a large finance network, whose liability structure is given by Erdos-Renyi graphs. When there is an (directed) edge between two nodes, it implies that the start node is liable to the end node. The banks anticipate some returns from their previous financial investments, however receive a lower amount due to economic shocks. This can lead to some of the banks defaulting, i.e., not repaying the entire money that they are liable for. This can further result in some more banks defaulting, and this can go on. Clearing vector, the vector of actual returns paid by each bank to its obligators, would often be given by certain fixed point equations.
We begin with a very simple case study, that of symmetric scenario, complete graph, IID binary shocks, and characterize the fixed point of the limit system. These limits can be used to study the large deviation results related to the fraction of defaulters. We then pose the problem with heterogenous network, Erdos-Reny graph and conjecture the result. One also needs to show that the fixed points with finite population increases to the fixed point of this limit system.
|
|
Manjunath Krishnapur (IISc, Bangalore)
|
Positivity of the inverse of a matrix
|
|
If (X_n)_n is a discrete-time, centered, stationary Gaussian process with a spectral measure that is not singular, then the persistence probability P(X_1
>0,...,X_n>0) cannot decay faster than \exp(-cn^2) [M.K. and Krishna Maddaly]. We suspect that it does decay that fast when the spectral density vanishes in a neighbourhood of the origin. This leads to a question about a certain matrix, whose inverse appears to have all positive entries by numerical experiments. We are unable to show that.
|
28 November, 17:30-18:30
|
Neeraja Sahasrabudhe (IIT, Bombay)
|
Ranking with Adversaries
|
|
The problem of obtaining a global rank over a set of objects has been of interest for a very long time to address questions like ranking of players, aggregating social opinions, deciding business strategies etc. We consider this problem over a set of $n$ comparable objects given the pair-wise comparisons with adversarial manipulations. Given the adversarial action, we obtain a lower bound for the number of comparisons needed to get the correct rank with high probability. Looking at this problem from an adversarial point of view, we compare different adversarial strategies given a fixed adversarial power.
|
|
Antar Bandyopadhyay (ISI, Delhi and Kolkata)
|
Interacting Urns on Lattices
|
|
Suppose $G := \left(V, E\right)$ be a graph on a countable set of vertices $V$, which is locally finite. We consider urns been placed on each of the vertices with some initial configurations. Let $R$ be a stochastic matrix indexed by the color set $S$ with only non-negative entries. At time point $n$ we denote the configuration of the urn at vertex $v$ by $U_{v,n}$. The discrete time interacting urn process runs according to the following dynamics:
\[
U_{v,n+1} = U_{v,n} + \sum_{u \sim v} \chi_{u,n+1} R, \,\,\, v \in V
\]
where $P\left(\chi_{u,n+1}(j) = 1 \,\Big\vert\, {\mathcal F}_n\right) = \frac{U_{u,n}(j)}{n+1}$ and $\left({\mathcal F}_{n \geq 0}\right)$ is the natural filtration. In other words, at each time $n+1$, a ball is selected unifomly at random from the urn at "location" $v \in V$ and it replaces balls of different colors in all of its "neighboring" vertices. The question is what is the asymptotic distribution of the process. Say for example, if $G$ is the one dimensional integer lattice and $R$ is the identity matrix on only two colors (classically resulting to the famous Pólya Urn Scheme), then what is the joint distribution of the scaled limit of the configurations? A guess is, it is a location invariant (stationary) distribution on ${\mathbb Z}$ with each marginal Beta.
|
|
Bapi Chatterjee (IBM IRL, New Delhi)
|
Concurrent Random Binary Search Tree
|
|
Binary Search Tree (BST) is a fundamental ordered data structure that enables fast preorder queries. Given the wide availability of multi-core and many-core compute machines, concurrent design of a BST is a significant problem. Recently, a number of designs of concurrent BSTs have been presented in literature. In general, the designers support their claim of better efficiency by way of empirical observations using micro benchmarks.
The literature of sequential random BST - one based on uniform random permutation - is large that includes several papers, theses and monographs. Scheduling of multiple threads in a multi-core machine, which depends on various system parameters like cache misses, time sharing, etc., is modelled as a stochastic system. However, analysis of a concurrent BST considering the natural randomization provided by such a scheduler has attracted very limited attention: to be precise, a single paper published just a month ago.
We consider a stochastic scheduler that is modelled as an adversary: it schedules every (non-faulty) thread with probability at least $\theta>0$ at each step. Given this scheduler, we find the expectation and variance of the depth of a concurrent BST.
|
|
