Publication

Exceptional graphs for the random walk

Publications associées (24)

Intrinsic area near the origin for self-similar growth-fragmentations and related random surfaces

We study the behaviour of a natural measure defined on the leaves of the genealogical tree of some branching processes, namely self-similar growth-fragmentation processes. Each particle, or cell, is attributed a positive mass that evolves in continuous tim ...

2022

On the robustness of the metric dimension of grid graphs to adding a single edge

Patrick Thiran, Gergely Odor, Satvik Mehul Mashkaria

The metric dimension (MD) of a graph is a combinatorial notion capturing the minimum number of landmark nodes needed to distinguish every pair of nodes in the graph based on graph distance. We study how much the MD can increase if we add a single edge to t ...

2022

Representing graphs through data with learning and optimal transport

Hermina Petric Maretic

Graphs offer a simple yet meaningful representation of relationships between data. This representation is often used in machine learning algorithms in order to incorporate structural or geometric information about data. However, it can also be used in an i ...

EPFL2021

Partition and Code: learning how to compress graphs

Andreas Loukas, Georgios Bouritsas, Nikolaos Karalias, Michael Bronstein

Can we use machine learning to compress graph data? The absence of ordering in graphs poses a significant challenge to conventional compression algorithms, limiting their attainable gains as well as their ability to discover relevant patterns. On the other ...

2021

Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization

Ali H. Sayed, Kun Yuan

This paper introduces a new algorithm for consensus optimization in a multi-agent network, where all agents collaboratively find a minimizer for the sum of their private functions. All decentralized algorithms rely on communications between adjacent nodes. ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Normal approximation of the solution to the stochastic heat equation with Levy noise

Carsten Hao Ye Chong

Given a sequence L & x2d9;epsilon of Levy noises, we derive necessary and sufficient conditions in terms of their variances sigma 2(epsilon) such that the solution to the stochastic heat equation with noise sigma(epsilon)-1L & x2d9;epsilon converges in law ...

SPRINGER2020

Non-Exponential Variations for Classical Results in First Passage Percolation

Jacques Saliba

We study in this thesis the asymptotic behavior of optimal paths on a random graph model, the configuration model, for which we assign continuous random positive weights on its edges. We start by describing the asymptotic behavior of the diameter and the f ...

EPFL2020

The n-term Approximation of Periodic Generalized Levy Processes

Michaël Unser, John Paul Ward, Julien René Pierre Fageot

In this paper, we study the compressibility of random processes and fields, called generalized Levy processes, that are solutions of stochastic differential equations driven by d-dimensional periodic Levy white noises. Our results are based on the estimati ...

2020

Scaling Limits of Solutions of Linear Stochastic Differential Equations Driven by Levy White Noises

Michaël Unser, Julien René Pierre Fageot

Consider a random process s that is a solution of the stochastic differential equation Ls = w with L a homogeneous operator and w a multidimensional Levy white noise. In this paper, we study the asymptotic effect of zooming in or zooming out of the process ...

2019

Approximating the rectilinear crossing number

János Pach

A straight-line drawing of a graph G is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. The rectilinear crossing number of a graph G, (cr) over bar (G), is the mi ...

2019

Gaussian versus Sparse Stochastic Processes : Construction, Regularity, Compressibility

Julien René Pierre Fageot

Although our work lies in the field of random processes, this thesis was originally motivated by signal processing applications, mainly the stochastic modeling of sparse signals. We develop a mathematical study of the innovation model, under which a signal ...

EPFL2017

Exponential extinction time of the contact process on finite graphs

Thomas Mountford, Daniel Rodrigues Valesin, Jean-Christophe Mourrat

We study the extinction time tau of the contact process started with full occupancy on finite trees of bounded degree. We show that, if the infection rate is larger than the critical rate for the contact process on Z, then, uniformly over all trees of degr ...

Elsevier Science Bv2016

On random subgraphs of Kneser and Schrijver graphs

Andrei Kupavskii

A Kneser graph KG(n,k) is a graph whose vertices are in oneto-one correspondence with k -element subsets of [n], with two vertices connected if and only if the corresponding sets do not intersect. A famous result due to Lowisz states that the chromatic num ...

Academic Press Inc Elsevier Science2016

A Precise Threshold For Quasi-Ramsey Numbers

János Pach

We consider the variation of Ramsey numbers introduced by Erdos and Pach [J. Graph Theory, 7 (1983), pp. 137-147], where instead of seeking complete or independent sets we only seek a t-homogeneous set, a vertex subset that induces a subgraph of minimum de ...

SIAM Publications2015

Downsampling of Signals on Graphs Via Maximum Spanning Trees

Minh Do, Quy Ha Nguyen

Downsampling of signals living on a general weighted graph is not as trivial as of regular signals where we can simply keep every other samples. In this paper we propose a simple, yet effective downsampling scheme in which the underlying graph is approxima ...

Ieee-Inst Electrical Electronics Engineers Inc2015

Random walks generated by equilibrium contact processes

Thomas Mountford

We consider dynamic random walks where the nearest neighbour jump rates are determined by an underlying supercritical contact process in equilibrium. This has previously been studied by den Hollander and dos Santos (arXiv: 1209.1511). We show the CLT for s ...

Univ Washington, Dept Mathematics2015

Lyapunov exponents of random walks in small random potential: the upper bound

Thomas Mountford, Jean-Christophe Mourrat

We consider the simple random walk on Z(d) evolving in a random i.i.d. potential taking values in [0, +infinity). The potential is not assumed integrable, and can be rescaled by a multiplicative factor lambda > 0. Completing the work started in a companion ...

Univ Washington, Dept Mathematics2015

Bootstrap Percolation in Power-Law Random Graphs

Léo Hamed Amini

A bootstrap percolation process on a graph is an "infection" process which evolves in rounds. Initially, there is a subset of infected nodes and in each subsequent round each uninfected node which has at least infected neighbours becomes infected and remai ...

Springer2014

The Range of a Random Walk on a Comb

János Pach, Gábor Tardos

The graph obtained from the integer grid Z x Z by the removal of all horizontal edges that do not belong to the x-axis is called a comb. In a random walk on a graph, whenever a walker is at a vertex v, in the next step it will visit one of the neighbors of ...

Electronic Journal Of Combinatorics2013

Lévy walk description of suprathermal ion transport

Paolo Ricci, Kyle Gustafson

Transport of suprathermal ions is examined from the Levy walk perspective in a simple magnetized toroidal plasma. Depending on their energy, these suprathermal ions exhibit superdiffusive, diffusive, or subdiffusive dispersion as a result of the complex in ...

American Institute of Physics2012