اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLinials Lower Bound Made Easy
199
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Linials seminal result shows that any deterministic distributed algorithm that finds a $3$-colouring of an $n$-cycle requires at least $log^*(n)/2 - 1$ communication rounds. We give a new simpler proof of this theorem.
قيم البحث
اقرأ أيضاً
Theoreticians have studied distributed algorithms in the radio network model for close to three decades. A significant fraction of this work focuses on lower bounds for basic communication problems such as wake-up (symmetry breaking among an unknown
set of nodes) and broadcast (message dissemination through an unknown network topology). In this paper, we introduce a new technique for proving this type of bound, based on reduction from a probabilistic hitting game, that simplifies and strengthens much of this existing work. In more detail, in this single paper we prove new expected time and high probability lower bounds for wake-up and global broadcast in single and multichann
We give a short proof of Gaos Quantum Union Bound and Gentle Sequential Measurement theorems.
One of the first and easy to use techniques for proving run time bounds for evolutionary algorithms is the so-called method of fitness levels by Wegener. It uses a partition of the search space into a sequence of levels which are traversed by the alg
orithm in increasing order, possibly skipping levels. An easy, but often strong upper bound for the run time can then be derived by adding the reciprocals of the probabilities to leave the levels (or upper bounds for these). Unfortunately, a similarly effective method for proving lower bounds has not yet been established. The strongest such method, proposed by Sudholt (2013), requires a careful choice of the viscosity parameters $gamma_{i,j}$, $0 le i < j le n$. In this paper we present two new variants of the method, one for upper and one for lower bounds. Besides the level leaving probabilities, they only rely on the probabilities that levels are visited at all. We show that these can be computed or estimated without greater difficulties and apply our method to reprove the following known results in an easy and natural way. (i) The precise run time of the (1+1) EA on textsc{LeadingOnes}. (ii) A lower bound for the run time of the (1+1) EA on textsc{OneMax}, tight apart from an $O(n)$ term. (iii) A lower bound for the run time of the (1+1) EA on long $k$-paths. We also prove a tighter lower bound for the run time of the (1+1) EA on jump functions by showing that, regardless of the jump size, only with probability $O(2^{-n})$ the algorithm can avoid to jump over the valley of low fitness.
We develop taggers for multi-pronged jets that are simple functions of jet substructure (so-called `subjettiness) variables. These taggers can be approximately decorrelated from the jet mass in a quite simple way. Specifically, we use a Logistic Regr
ession Design (LoRD) which, even being one of the simplest machine learning classifiers, shows a performance which surpasses that of simple variables used by the ATLAS and CMS Collaborations and is not far from more complex models based on neural networks. Contrary to the latter, our method allows for an easy implementation of tagging tasks by providing a simple and interpretable analytical formula with already optimised parameters.
We use a modified version of the Peak Patch excursion set formalism to compute the mass and size distribution of QCD axion miniclusters from a fully non-Gaussian initial density field obtained from numerical simulations of axion string decay. We find
strong agreement with N-Body simulations at a significantly lower computational cost. We employ a spherical collapse model and provide fitting functions for the modified barrier in the radiation era. The halo mass function at $z=629$ has a power-law distribution $M^{-0.6}$ for masses within the range $10^{-15}lesssim Mlesssim 10^{-10}M_{odot}$, with all masses scaling as $(m_a/50mumathrm{eV})^{-0.5}$. We construct merger trees to estimate the collapse redshift and concentration mass relation, $C(M)$, which is well described using analytical results from the initial power spectrum and linear growth. Using the calibrated analytic results to extrapolate to $z=0$, our method predicts a mean concentration $Csim mathcal{O}(text{few})times10^4$. The low computational cost of our method makes future investigation of the statistics of rare, dense miniclusters easy to achieve.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
