The random walk Xt = Xt-1 + Po [special characters omitted]- 1 can be viewed as a simplification of a neuron firing model if we reset Xt = 1 whenever Xt = 0 happens. The Last Crash is the last time such a reset occurs. We show that the critical window for that time is n ±αn 2/3 and bound, as a function of α, the probability that the last crash has occurred by that time.
The Propp Machine is a de-randomization of a random walk by indivisible chips being routed in a specific order from each position. Here we study it in [special characters omitted] The walk is considered Proppian if the difference between the number of chips at each position at each time and the expected number of chips by the random walk is bounded by a constant independent of the initial configuration. This was previously known to be true for some specific walks on [special characters omitted] Here we show that it is true for all zero drift walks on [special characters omitted]
A packing in a Steiner Triple System is a maximal set of non-overlapping edges. A packing is perfect if it uses all vertices in the case n = 6k + 3 or all but one vertex in the case n = 6k + 1. It is known that every STS with n vertices has a packing using all but at most [special characters omitted] vertices. A random greedy packing gives results on this order. Appending a randomized end-game strategy, we find perfect packings.
|Commitee:||Chudnovsky, Maria, Khot, Subhash, Pach, Janos, Peskin, Charles|
|School:||New York University|
|School Location:||United States -- New York|
|Source:||DAI-B 70/07, Dissertation Abstracts International|
|Keywords:||Critical window, Derandomization, Propp machine, Random greedy algorithm, Random walks, Steiner triple systems|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be