Thresholds in semi-random processes and graph embeddings
Disciplines
Mathematics (100%)
Keywords
- Threshold,
- Semi-Random Process,
- Strategy,
- Random Graphs,
- Embedding,
- Geometric Graph
A stochastic process consists of a sequence of steps where a new random input is provided at every step. Stochastic processes are central in the study of probability theory and describe many natural phenomena in the physical world. However, due to the unsupervised nature of most stochastic processes, it often turns out that introducing a deterministic influence (for example, introducing an observer) could drastically improve the properties of the outcome and make it more suitable for given practical purposes. The aim of the current project is to study instances of stochastic processes controlled by an observer. More concretely, the project aims to develop several natural (combinatorial and geometric) variations of the well-studied power of two choices paradigm described as follows. An observer is given initially empty bins. At every step, two uniformly random bins are proposed to them. The observer is then allowed to throw a ball in one of the two bins. As it turns out, the observer manages to reduce significantly the maximum load of a bin after steps compared to the purely random (unsupervised) setting. This process is a simplified stochastic model in the field of load balancing whose practical applications include parallel computing and task scheduling.
- Technische Universität Wien - 100%
- Matthew Kwan, Institute of Science and Technology - Austria (ISTA) , mentor
- Fabio Lucio Toninelli, Technische Universität Wien , mentor
Research Output
- 13 Publications
- 12 Disseminations
-
2025
Title Hitting times and the power of choice for random geometric graphs Type Conference Proceeding Abstract Author Ignasiak D Conference 10th Cracow conference on graph theory Link Publication -
0
Title Label propagation on binomial random graphs Type Other Author M. Kiwi -
0
Title Approximate Itai-Zehavi conjecture for random graphs Type Other Author Hollom L -
0
Title Diameter and mixing time of the giant component in the percolated hypercube Type Other Author Anastos M -
0
Title Sharp thresholds, hitting times and the power of choice for random geometric graphs Type Other Author Ignasiak D -
0
Title On the depth of depth-weighted trees Type Other Author Lichev L -
0
Title Cycle lengths in the percolated hypercube Type Other Author Anastos M -
0
Title On the local resilience of random geometric graphs with respect to connectivity and long cycles Type Other Author A. Espuny Diaz -
0
Title Vertex-separating path systems in random graphs Type Other Author L. Lichev -
0
Title Colouring random Hasse diagrams and box-Delaunay graphs Type Other Author Z. Jin -
0
Title Explosive appearance of cores and bootstrap percolation on lattices Type Other Author I. Hartarsky -
0
Title Universality of the matching number in percolated regular graphs Type Other Author S. Diskin -
0
Title Nearly spanning cycle in the percolated hypercube Type Other Author M. Anastos
-
2024
Link
Title Workshop (Montserrat, near Barcelona) Type Participation in an activity, workshop or similar Link Link -
2025
Title Talk and research visit at the University of Passau Type A talk or presentation -
2026
Title Talk and research visit at the Tel Aviv University Type A talk or presentation -
2026
Title Research visit and seminar talk at the University of Sheffield Type A talk or presentation -
2024
Link
Title Probability meets combinatorics at ISTA Type Participation in an activity, workshop or similar Link Link -
2026
Title Workshop (Barbados) Type Participation in an activity, workshop or similar -
2025
Title Research visit and seminar talk of Sahar Diskin Type Participation in an activity, workshop or similar -
2026
Title Talk and research visit at the University of Oxford Type A talk or presentation -
2024
Title Research visit and seminar talk (Innsbruck) Type A talk or presentation -
2025
Title Talk and research visit at EPFL Type A talk or presentation -
2024
Title Research visit and seminar talk (Graz) Type Participation in an activity, workshop or similar -
2024
Link
Title Workshop (Edinburgh) Type Participation in an activity, workshop or similar Link Link