Avi Silterra's Math ResearchSummer '02 - (Very) Rough Drafts of papers now available! Latest update 3-05-03 Summer '02 - I spent at SUNY Potsdam REU. This REU I worked with Mihai Tohaneahu, Margarethe Flanders, and advisor Kazem Mahdavi. It really is more interesting to obtain results than to obtain nothing. We defined a c-group to be a group which requires strictly more generators for it's center than for the group. We proved some existence and uniqueness results, and had a great time. Summer '01 - Two summers ago I engaged in math research with Ann Lewis over the summer at CMU as a part of SURF (Summer Undergraduate Research Fellowship). Research is a wonderfully fufilling experience, even if it is frustrating and straining. In my finer moments, I like to compare research to being an explorer on a new frontier. In the unpleasant moments, a more appropriate comparison is giving oneself repeated painful injections of distilled failure. The research topic was proving an improved upper bound on a distributed resource discovery algorithm, specifically the Name-Dropper algorithm. Here is a description of resource discovery and then Name Dropper. Suppose we have n people in a room, each with a different name. No person has knowledge of the what names the other people already know. We would like in the minimum amount of time and with minimum of communication to have each person know every other person's name. We can model this as a directed graph on n vertices, where we place a directed edge from a vertex u to a vertex v if u knows v's name. Implicitly each vertex knows it's own name. We also assume that the graph is weakly connected, ie if we ignore edge directions then there is a path from each vertex to every other vertex. Now to the description of Name Dropper. During each time step in a parallel manner, every vertex u chooses at random an outneighbor v, and then sends v it's list of names (including itself). Observe that Name Dropper is a probabalistic algorithm. It has been proven that Name Dropper completes a graph (ie all edges are present) in O(log^2 n) time with high probability (whp). By with high probability, we mean that the desired effect is acheived with probability greater than 1-n^-O(1). A conjecture was that Name Dropper actually only takes O(log n) time, whp. Our research project for the summer was to either prove this improved worst case bound, or disprove it. We were not successful, but we have a few fairly obvious special case results. However, cursed LaTex2HTML is not working for me, so I can only post them in LaTex format.
|