Schwellen in halbzufälligen Prozessen und Grapheinbettungen
Thresholds in semi-random processes and graph embeddings
Wissenschaftsdisziplinen
Mathematik (100%)
Keywords
- Threshold,
- Semi-Random Process,
- Strategy,
- Random Graphs,
- Embedding,
- Geometric Graph
Ein stochastischer Prozess besteht aus einer Abfolge von Schritten, bei denen bei jedem Schritt eine neue Zufallseingabe bereitgestellt wird. Stochastische Prozesse sind von zentraler Bedeutung für das Studium der Wahrscheinlichkeitstheorie und beschreiben viele Naturphänomene in der physikalischen Welt. Aufgrund der unbeaufsichtigten Natur der meisten stochastischen Prozesse stellt sich jedoch häufig heraus, dass die Einführung eines deterministischen Einflusses (z. B. durch einen externen Beobachter) bestimmte Eigenschaften des Ergebnisses drastisch verbessern und es für bestimmte praktische Zwecke geeigneter machen kann. Ziel des aktuellen Projekts ist die Untersuchung von Fällen stochastischer Prozesse, die von einem Beobachter gesteuert werden. Konkreter zielt das Projekt darauf ab, mehrere natürliche (kombinatorische und geometrische) Variationen des gut untersuchten Power-of-Two-Choice- Paradigmas zu entwickeln, das wie folgt beschrieben wird. Einem Beobachter werden n zunächst leere Behälter gegeben. Bei jedem Schritt werden ihnen zwei gleichmäßig zufällige Bins vorgeschlagen. Anschließend darf der Beobachter einen Ball in einen der beiden Behälter werfen. Wie sich herausstellt, gelingt es dem Beobachter, die maximale Belastung eines Behälters nach n Schritten im Vergleich zur rein zufälligen (unüberwachten) Einstellung deutlich zu reduzieren. Bei diesem Prozess handelt es sich um ein vereinfachtes stochastisches Modell im Bereich des Lastausgleichs, dessen praktische Anwendungen paralleles Rechnen und Aufgabenplanung umfassen.
- Technische Universität Wien - 100%
- Matthew Kwan, Institute of Science and Technology - Austria (ISTA) , Mentor:in
- Fabio Lucio Toninelli, Technische Universität Wien , Mentor:in
Research Output
- 13 Publikationen
- 12 Disseminationen
-
2025
Titel Hitting times and the power of choice for random geometric graphs Typ Conference Proceeding Abstract Autor Ignasiak D Konferenz 10th Cracow conference on graph theory Link Publikation -
0
Titel Label propagation on binomial random graphs Typ Other Autor M. Kiwi -
0
Titel Approximate Itai-Zehavi conjecture for random graphs Typ Other Autor Hollom L -
0
Titel Diameter and mixing time of the giant component in the percolated hypercube Typ Other Autor Anastos M -
0
Titel Sharp thresholds, hitting times and the power of choice for random geometric graphs Typ Other Autor Ignasiak D -
0
Titel On the depth of depth-weighted trees Typ Other Autor Lichev L -
0
Titel Cycle lengths in the percolated hypercube Typ Other Autor Anastos M -
0
Titel On the local resilience of random geometric graphs with respect to connectivity and long cycles Typ Other Autor A. Espuny Diaz -
0
Titel Vertex-separating path systems in random graphs Typ Other Autor L. Lichev -
0
Titel Colouring random Hasse diagrams and box-Delaunay graphs Typ Other Autor Z. Jin -
0
Titel Explosive appearance of cores and bootstrap percolation on lattices Typ Other Autor I. Hartarsky -
0
Titel Universality of the matching number in percolated regular graphs Typ Other Autor S. Diskin -
0
Titel Nearly spanning cycle in the percolated hypercube Typ Other Autor M. Anastos
-
2024
Link
Titel Workshop (Montserrat, near Barcelona) Typ Participation in an activity, workshop or similar Link Link -
2025
Titel Talk and research visit at the University of Passau Typ A talk or presentation -
2026
Titel Talk and research visit at the Tel Aviv University Typ A talk or presentation -
2026
Titel Research visit and seminar talk at the University of Sheffield Typ A talk or presentation -
2024
Link
Titel Probability meets combinatorics at ISTA Typ Participation in an activity, workshop or similar Link Link -
2026
Titel Workshop (Barbados) Typ Participation in an activity, workshop or similar -
2025
Titel Research visit and seminar talk of Sahar Diskin Typ Participation in an activity, workshop or similar -
2026
Titel Talk and research visit at the University of Oxford Typ A talk or presentation -
2024
Titel Research visit and seminar talk (Innsbruck) Typ A talk or presentation -
2025
Titel Talk and research visit at EPFL Typ A talk or presentation -
2024
Titel Research visit and seminar talk (Graz) Typ Participation in an activity, workshop or similar -
2024
Link
Titel Workshop (Edinburgh) Typ Participation in an activity, workshop or similar Link Link