31,533 research outputs found
Cover Time and Broadcast Time
No full textWe introduce a new technique for bounding the cover time of random walks by relating it to the runtime of randomized broadcast. In particular, we strongly confirm for dense graphs the intuition of Chandra et al. (1997) that ``the cover time of the graph is an appropriate metric for the performance of certain kinds of randomized broadcast algorithms''. In more detail, our results are as follows:
\begin{itemize}
\item For any graph of size and minimum degree , we have , where denotes the quotient of the cover time and broadcast time. This bound is tight for binary trees and tight up to logarithmic factors for many graphs including hypercubes, expanders and lollipop graphs.
\item For any -regular (or almost -regular) graph it holds that . Together with our upper bound on , this lower bound strongly confirms the intuition of Chandra et al.~for graphs with minimum degree , since then the cover time equals the broadcast time multiplied by (neglecting logarithmic factors).
\item Conversely, for any we construct almost -regular graphs that satisfy . Since any regular expander satisfies , the strong relationship given above does not hold if is polynomially smaller than .
\end{itemize}
Our bounds also demonstrate that the relationship between cover time and broadcast time is much stronger than the known relationships between any of them and the mixing time (or the closely related spectral gap)
Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities
No full textWe establish and generalise several bounds for various random walk quantities including the mixing time and the maximum hitting time. Unlike previous analyses, our derivations are based on rather intuitive notions of local expansion properties which allow us to capture the progress the random walk makes through t-step probabilities.
We apply our framework to dynamically changing graphs, where the set of vertices is fixed while the set of edges changes in each round. For random walks on dynamic connected graphs for which the stationary distribution does not change over time, we show that their behaviour is in a certain sense similar to static graphs. For example, we show that the mixing and hitting times of any sequence of d-regular connected graphs is O(n^2), generalising a well-known result for static graphs. We also provide refined bounds depending on the isoperimetric dimension of the graph, matching again known results for static graphs. Finally, we investigate properties of random walks on dynamic graphs that are not always connected: we relate their convergence to stationarity to the spectral properties of an average of transition matrices and provide some examples that demonstrate strong discrepancies between static and dynamic graphs
Balanced Allocations with Incomplete Information: The Power of Two Queries
No full textWe consider the allocation of m balls into n bins with incomplete information. In the classical Two-Choice process a ball first queries the load of two randomly chosen bins and is then placed in the least loaded bin. In our setting, each ball also samples two random bins but can only estimate a bin's load by sending binary queries of the form “Is the load at least the median?” or “Is the load at least 100?”. For the lightly loaded case m = O(n), Feldheim and Gurel-Gurevich (2021) showed that with one query it is possible to achieve a maximum load of (Equation presented), and they also pose the question whether a maximum load of (Equation presented) is possible for any m = Ω(n). In this work, we resolve this open problem by proving a lower bound of m/n + Ω(√log n) for a fixed m = Θ(n√log n), and a lower bound of m/n + Ω(log n/log log n) for some m depending on the used strategy. We complement this negative result by proving a positive result for multiple queries. In particular, we show that with only two binary queries per chosen bin, there is an oblivious strategy which ensures a maximum load of m/n + O(√log n) for any m ≥ 1. Further, for any number of k = O(log log n) binary queries, the upper bound on the maximum load improves to m/n + O(k(log n)1/k) for any m ≥ 1. This result for k queries has several interesting consequences: (i) it implies new bounds for the (1 + β)-process introduced by Peres, Talwar and Wieder (2015), (ii) it leads to new bounds for the graphical balanced allocation process on dense expander graphs, and (iii) it recovers and generalizes the bound of m/n + O(log log n) on the maximum load achieved by the Two-Choice process, including the heavily loaded case m = Ω(n) which was derived in previous works by Berenbrink et al. (2006) as well as Talwar and Wieder (2014). One novel aspect of our proofs is the use of multiple super-exponential potential functions, which might be of use in future work
Tight Bounds for Repeated Balls-into-Bins
No full textWe study the repeated balls-into-bins process introduced by Becchetti,
Clementi, Natale, Pasquale and Posta (2019). This process starts with balls
arbitrarily distributed across bins. At each round , one ball
is selected from each non-empty bin, and then placed it into a bin chosen
independently and uniformly at random. We prove the following results:
For any , we prove a lower
bound of on the maximum load. For the special case
, this matches the upper bound of , as shown in [BCNPP19]. It
also provides a positive answer to the conjecture in [BCNPP19] that for
the maximum load is at least once in a
polynomially large time interval. For , our new lower
bound disproves the conjecture in [BCNPP19] that the maximum load remains
.
For any , we prove an upper
bound of on the maximum load for all steps of a
polynomially large time interval. This matches our lower bound up to
multiplicative constants.
For any , our analysis also implies an
waiting time to reach a configuration with a maximum load,
even for worst-case initial distributions.
For any , we show that every ball visits every bin
in rounds. For , this improves the previous upper bound of
in [BCNPP19]. We also prove that the upper bound is tight up to
multiplicative constants for any .Comment: Full version of STACS 2023 paper; 38 pages, 5 figure
Randomized Load Balancing on Networks with Stochastic Inputs
No full textIterative load balancing algorithms for indivisible tokens have been studied intensively in the past. Complementing previous worst-case analyses, we study an average-case scenario where the load inputs are drawn from a fixed probability distribution. For cycles, tori, hypercubes and expanders, we obtain almost matching upper and lower bounds on the discrepancy, the difference between the maximum and the minimum load. Our bounds hold for a variety of probability distributions including the uniform and binomial distribution but also distributions with unbounded range such as the Poisson and geometric distribution. For graphs with slow convergence like cycles and tori, our results demonstrate a substantial difference between the convergence in the worst- and average-case. An important ingredient in our analysis is a new upper bound on the t-step transition probability of a general Markov chain, which is derived by invoking the evolving set process
Thomas Grisell letter to Thomas Rotch, 2nd mo 19th 1823
No full textThomas Grisell's letter reached the Rotch household several months before the unexpected death of Thomas Rotch in August, 1823. This is the last letter of the series and presumably the author learned of his friend's death before another letter was penned. 7.95" x 10" (20.2 by 25.5 cm
The Support of Open Versus Closed Random Walks
No full textA closed random walk of length on an undirected and connected graph G = (V,E) is a random walk that returns to the start vertex at step , and its properties have been recently related to problems in different mathematical fields, e.g., geometry and combinatorics (Jiang et al., Annals of Mathematics '21) and spectral graph theory (McKenzie et al., STOC '21). For instance, in the context of analyzing the eigenvalue multiplicity of graph matrices, McKenzie et al. show that, with high probability, the support of a closed random walk of length ⩾ 1 is Ω(^{1/5}) on any bounded-degree graph, and leaves as an open problem whether a stronger bound of Ω(^{1/2}) holds for any regular graph.
First, we show that the support of a closed random walk of length is at least Ω(^{1/2} / √{log n}) for any regular or bounded-degree graph on n vertices. Secondly, we prove for every ⩾ 1 the existence of a family of bounded-degree graphs, together with a start vertex such that the support is bounded by O(^{1/2}/√{log n}). Besides addressing the open problem of McKenzie et al., these two results also establish a subtle separation between closed random walks and open random walks, for which the support on any regular (or bounded-degree) graph is well-known to be Ω(^{1/2}) for all ⩾ 1. For irregular graphs, we prove that even if the start vertex is chosen uniformly, the support of a closed random walk may still be O(log ). This rules out a general polynomial lower bound in for all graphs. Finally, we apply our results on random walks to obtain new bounds on the multiplicity of the second largest eigenvalue of the adjacency matrices of graphs
Failed Censures: Ecclesiastical Regulation of Women’s Clothing in Late Medieval Italy
No full textChurchmen in the late thirteenth and early fourteenth centuries tried to regulate the costume of Italian women. These efforts failed, and regulation was largely left thereafter to civic authorities.The published version was published as Chapter 3 in Medieval Clothing and Textiles 5Izbicki, Thomas M. (2009), "Failed Censures: Ecclesiastical Regulation of Women’s Clothing in Late Medieval Italy" in Netherton, Robin and Owen-Crocker, Gale R., eds., Medieval Clothing and Textiles 5 (Boydell Press), 37-53ISBN: 9781843834519 (published book)Peer reviewe
Western medieval legal manuscripts in the collections of the University of Pennsylvania
No full textWestern legal manuscripts of the Middle Ages in North American collections are among the least known to scholars. The University of Pennsylvania has a rich collection of these texts, several of which were in the collection of the historian Henry Charles Lea. Included are works of civil law and canon law, as well as collections of papal letters and guides to pastoral care. The descriptions of most of these manuscripts in the catalog of Norman P. Zacour and Rudolf Hirsch are perfunctory, sometimes erring or omitting valuable information. Other manuscripts were added in recent years in the Lawrence J. Schoenberg Collection. Much of this material is being added to the Franklin online catalog of the University’s libraries, but researchers frequently do not search these digital resources. This article provides more complete guidance to the University’s medieval legal manuscripts than any of the existing catalogs offers, whether in print or online. It also provides updated bibliographic information in print or online. Every manuscript has been examined by the author in situ. Among the important works represented in the collection is the Panormia (a work of canon law often attributed to Ivo of Chartres). Authors present include the curialist Thomas of Capua, canonists Petrus de Braco, William of Pagula, Bernardus Raimundi, Adam of Aldersbach, Raymond of Peñafort, and civil lawyers Baldus de Ubaldis, and Bartolus de Saxoferrato. Three of these manuscripts were owned in the past by Sir Thomas Phillipps
- …
