Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLinials Lower Bound Made Easy
205
0
0.0
(
0
)
Added by
Jukka Suomela
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 algorithm 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 Regression 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
