Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTwenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten)
89
0
0.0
(
0
)
Added by
Peter Schneider-Kamp
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper describes a computer-assisted non-existence proof of nine-input sorting networks consisting of 24 comparators, hence showing that the 25-comparator sorting network found by Floyd in 1964 is optimal. As a corollary, we obtain that the 29-comparator network found by Waksman in 1969 is optimal when sorting ten inputs. This closes the two smallest open instances of the optimal size sorting network problem, which have been open since the results of Floyd and Knuth from 1966 proving optimality for sorting networks of up to eight inputs. The proof involves a combination of two methodologies: one based on exploiting the abundance of symmetries in sorting networks, and the other, based on an encoding of the problem to that of satisfiability of propositional logic. We illustrate that, while each of these can single handed solve smaller instances of the problem, it is their combination which leads to an efficient solution for nine inputs.
rate research
Read More
In the distributional Twenty Questions game, Bob chooses a number $x$ from $1$ to $n$ according to a distribution $mu$, and Alice (who knows $mu$) attempts to identify $x$ using Yes/No questions, which Bob answers truthfully. Her goal is to minimize the expected number of questions. The optimal strategy for the Twenty Questions game corresponds to a Huffman code for $mu$, yet this strategy could potentially uses all $2^n$ possible questions. Dagan et al. constructed a set of $1.25^{n+o(n)}$ questions which suffice to construct an optimal strategy for all $mu$, and showed that this number is optimal (up to sub-exponential factors) for infinitely many $n$. We determine the optimal size of such a set of questions for all $n$ (up to sub-exponential factors), answering an open question of Dagan et al. In addition, we generalize the results of Dagan et al. to the $d$-ary setting, obtaining similar results with $1.25$ replaced by $1 + (d-1)/d^{d/(d-1)}$.
In 1995, C. I. Christov and M. G. Velarde introduced the concept of a dissipative soliton in a long-wave thin-film equation [Physica D 86, 323--347]. In the 25 years since, the subject has blossomed to include many related phenomena. The focus of this short note is to survey the conceptual influence of the concept of a production-dissipation (input-output) energy balance that they identified. Our recent results on nonlinear periodic waves as dissipative solitons (in a model equation for a ferrofluid interface in a parallel-flow rectangular geometry subject to an inhomogeneous magnetic field) have shown that the classical concept also applies to nonlocalized (specifically, spatially periodic) nonlinear coherent structures. Thus, we revisit the so-called KdV-KSV equation studied by C. I. Christov and M. G. Velarde to demonstrate that it also possesses spatially periodic dissipative soliton solutions. These coherent structures arise when the linearly unstable flat film state evolves to sufficiently large amplitude. The linear instability is then arrested when the nonlinearity saturates, leading to permanent traveling waves. Although the two model equations considered in this short note feature the same prototypical linear long-wave instability mechanism, along with similar linear dispersion, their nonlinearities are fundamentally different. These nonlinear terms set the shape and eventual dynamics of the nonlinear periodic waves. Intriguingly, the nonintegrable equations discussed in this note also exhibit multiperiodic nonlinear wave solutions, akin to the polycnoidal waves discussed by J. P. Boyd in the context of the completely integrable KdV equation.
Type-IIB supergravity in ten dimensions admits two consistent $Z_2$ truncations. After the insertion of D9-branes, one of them leads to the low-energy action of type-I string theory, and it can be performed in two different ways, in correspondence with the fact that there are two different consistent ten-dimensional type-I string theories, namely the SO(32) superstring and the $USp(32)$ model, in which supersymmetry is broken on the D9-branes. We derive here the same results for Type-IIA theory compactified on a circle in the presence of D8-branes. We also analyze the $kappa$-symmetric action for a brane charged with respect to the S-dual of the RR 10-form of type-IIB, and we find that the tension of such an object has to scale like $g_S^{-2}$ in the string frame. We give an argument to explain why this result is in disagreement with the one obtained using Weyl rescaling of the brane action, and we argue that this brane can only be consistently introduced if the other $Z_2$ truncation of type-IIB is performed. Moreover, we find that one can include a 10-form in type-IIA supersymmetry algebra, and also in this case the corresponding $kappa$-symmetric brane has a tension scaling like $g_S^{-2}$ in the string frame.
Multi-band photometric and multi-object spectroscopic surveys of merging galaxy clusters allow for the characterization of the distributions of constituent dark matter and galaxy populations, constraints on the dynamics of the merging subclusters, and an understanding of galaxy evolution of member galaxies. We present deep photometric observations from Subaru/SuprimeCam and a catalog of $sim$5400 spectroscopic cluster members from Keck/DEIMOS across 29 merging galaxy clusters ranging in redshift from $z=0.07$ to $0.55$. The ensemble is compiled based on the presence of radio relics, which highlight cluster scale collisionless shocks in the intra-cluster medium. Together with the spectroscopic and photometric information, the velocities, timescales, and geometries of the respective merging events may be tightly constrained. In this preliminary analysis, the velocity distributions of 28 of the 29 clusters are shown to be well fit by single Gaussians. This indicates that radio relic mergers largely occur transverse to the line of sight and/or near apocenter. In this paper, we present our optical and spectroscopic surveys, preliminary results, and a discussion of the value of radio relic mergers for developing accurate dynamical models of each system.
We study the progress of the theory of accretion disks around black holes in last twenty five years and explain why advective disks are the best bet in explaining varied stationary and non-stationary observations from black hole candidates. We show also that the recently proposed advection dominated flows are incorrect.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
