DIMACS
DIMACS REU 2019

General Information

me
Student: Mikhail Beliayeu
Office: CoRE 450
School: Faculty of Mathematics and Physics, Charles University
E-mail: mikhail.beliayeu [at] rutgers [dot] edu
Project: Random walks with 'geodesic bias'
Adviser: Bhargav Narayanan
Coworkers: Petr Chmel, Jan Petr

Project Description

When considering simple random walks on a graph, it is known that the expected hitting time has the upper bound of approximately O(n^3). However, the random walker may use some heuristics or biases to try to get to the target vertex quicker.

One of such biases is 'geodesic bias' - some vertices in the graph are 'excited' and from them, the random walker takes a step along a fixed shortest path. The question is, do the upper bounds differ?

Weekly Log

Week 1:
We met with Dr. Narayanan and discussed topics of our interest. Later he gave us material to read. To understand what happens when vertex gets excited we tried to come up with conterexamples. First presentation done.
Week 2:
Read few chapters from [1]. We observed that exciting vertex may increase the hitting time asymptotically. Tried to adjust [2] to derive any polynomial bound on our problem. Proved lemma mentioned in [2] whose proof is nowhere to be found.

In one respect every act of art, science and mathematics is one of exploration as opposite to creation. The birth of idea is spontaneous and unconscious and most of the time you are trying to discover and comprehend it.
Week 3:
The week started with disproving the conjecture. Now we are considering whether it works for graphs of bounded degree (it doesn't, see Week 4). We attended workshops on the strong perfect graph theory and Hadamard matrices given by Maria Chudnovsky and Danny Scheinerman respectively.

Non-stop air conditioning is killing me. My only salvation is periodic rain.
Week 4:
On Monday we went to Bell Labs where we visited anechoic chamber (it is awesome). We managed to prove that biased graphs have exponential lower bound while those of bounded degree do not have polynomial bound.

I thank my cat for showing me what incredible things one is able to achieve given a proper mindset.
Week 5:
This almost unfruitful week ended with a bit of hope (which is yet to be crashed few days later).

Week 6:
Brief meeting with Dr. Narayanan revealed to us everything. Although we quickly forgot why P = NP and how squirrels sleep, we made a considerable jump in our progress, and next week will show whether our calculations are correct.

Week 7:
It works. The entire week we were busy formalising our results and doing presentation.

Week 8:
Conferences, workshops, talks, lectures, parties, trips and back home.

Presentations

References