DIMACS REU 2019

General Information

The Czech group

Project Description

When considering simple random walks on a graph, it is known that the expected hitting time has the upper bound of approximately \$\mathcal{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:

On Wednesday, we talked with Dr Narayanan about the proposed problems.
Then, for the rest of the week, we spent most of the time reading about the machinery behind the problems and choosing our main problem.
On Friday evening, we had another meeting with Dr Narayanan, where we were given more material to prepare.

Week 2:

On Monday, we gave our initial presentation about the biased random walks problem and I continued reading the given literature.
Through the rest of the week, I kept reading [1] and read [2], which we then discussed as a group. In addition to that, we have also proved a lemma, which was referenced in [2], but no proof was provided.
Other than that, we have shown that excitation of a single vertex may asymptotically change the expected hitting time for the worse. There are some other possibilites we want to explore, which could prove a polynomial bound, but not a cubic one. We would also like to modify [2] to work for the excited vertices, but currently, that seems out of reach.

Week 3:

We have continued with our problem of biased random walks and we think we found a solution for the general case with a complete proof. However, we think that the bound may differ for graphs with a bounded degree, as there is a difference in the unexcited case, so we're trying to find a way to modify [2] or our result in the bounded case.
Other than that, we attended a talk by Maria Chudnovsky about her work on perfect graphs and \$\chi\$-boundedness and a Bridge Workshop with Danny Scheinerman on specific linear algebra problems.

Week 4:

On Monday, we visited the Nokia Bell Labs and attended some talks there. I especially liked the talk about reducing the amount of measurements for MRI.
On Tuesday, we took part in a Bridge Workshop with Cole Franks on discrepancies of set systems. In the afternoon, we met with Dr. Narayanan to check our current results and to talk about the direction of our research.
For the rest of the week, we tried to continue with the bounded degree case, which seems more complicated than the unbounded case.
On Friday, we also attended a talk by Sid Dalal on deep analytics.

Week 5:

On Monday, we had another meeting with Dr. Narayanan, in which we discussed possible approaches regarding the bounded degree case.
For the rest of the week, we were trying to analyze the behaviour on a specific graph, however we were unable to obtain any meaningful results, as the computations are quite difficult. Even the best bound we have obtained was rather trivial.

Week 6:

On Monday, another meeting with Dr. Narayanan took place. We discussed our past efforts and possible improvements on the methods we used.
For the rest of our week, we tried to improve methods and possibly succeded. After another meeting with Dr. Narayanan on Thursday, it seems like we have found a solution for the bounded case, and we spent the whole Friday trying to formalize the result (and probably succeeding).

Week 7:

We spent the first three days of the week preparing the presentation and writing the basis of our paper.
Thursday and Friday were mostly delegated to seeing other presentations and bureaucracy regarding the nearing end of our stay here.

Week 8

I planned to spend most of my time on the conferences and the rest of my time (which was sadly not much) was spent on the preparation of our paper.
On Monday and Tuesday, I took part in the CoSP Workshop and School on Algorithms and Complexity.
On Wednesday, I participated in the DIMACS Day of Complexity Tutorials.
From Thursday to Saturday, I spent most of my time at the Computational Complexity Conference.

Weeks 9-10

The Prague part of the REU starts.

---

Presentations

• First Presentation
• Final Presentation

References

• [1] LEVIN, David A., PERES, Yuval and WILMER, Elizabeth L. Markov chains and mixing times [online]. American Mathematical Society, 2006. Available online
• [2] LAWLER, Gregory F. Expected hitting times for a random walk on a connected graph. Discrete Mathematics [online]. Vol. 61, no. 1, p. 85–92. Available online