An official website of the United States government
We study search trees with 2-way comparisons (2WCST’s), which involve separate less-than and equal-to tests in their nodes, each test having two possible outcomes, yes and no. These trees have a much subtler structure than standard search trees with 3-way comparisons (3WCST’s) and are still not well understood, hampering progress towards designing an efficient algorithm for computing minimum-cost trees. One question that attracted attention in the past is whether there is an easy way to determine which type of comparison should be applied at any step of the search. Anderson, Kannan, Karloff and Ladner studied this in terms of the ratio between the maximum and total key weight, and defined two threshold values: λ− is the largest ratio that forces the less-than test, and λ+ is the smallest ratio that forces the equal-to test. They determined that λ− = 41 , but for the higher threshold they only showed that λ+ ∈ [ 3/7 , 4/9 ]. We give the tight bound for the higher threshold, by proving that in fact λ+ = 3/7 .
more »
« less
A Tight Threshold Bound for Search Trees with 2-Way Comparisons
We study search trees with 2-way comparisons (2WCST’s), which involve separate less-than and equal-to tests in their nodes, each test having two possible outcomes, yes and no. These trees have a much subtler structure than standard search trees with 3-way comparisons (3WCST’s) and are still not well understood, hampering progress towards designing an efficient algorithm for computing minimum-cost trees. One question that attracted attention in the past is whether there is an easy way to determine which type of comparison should be applied at any step of the search. Anderson, Kannan, Karloff and Ladner studied this in terms of the ratio between the maximum and total key weight, and defined two threshold values: λ− is the largest ratio that forces the less-than test, and λ+ −1 is the smallest ratio that forces the equal-to test. They determined that λ = 4 , but for the higher threshold they only showed that λ+ ∈ [ 37 , 49 ]. We give the tight +3 bound for the higher threshold, by proving that in fact λ = 7 .
more »
« less
- Award ID(s):
- 2153723
- PAR ID:
- 10598871
- Editor(s):
- Chen, Xujin; Li, Bo
- Publisher / Repository:
- Springer Nature Singapore
- Date Published:
- ISSN:
- 0302-9743
- ISBN:
- 978-981-97-2339-3
- Page Range / eLocation ID:
- 99 to 110
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)A bstract A search for nonresonant production of Higgs boson pairs via gluon-gluon and vector boson fusion processes in final states with two bottom quarks and two photons is presented. The search uses data from proton-proton collisions at a center-of-mass energy of $$ \sqrt{s} $$ s = 13 TeV recorded with the CMS detector at the LHC, corresponding to an integrated luminosity of 137 fb − 1 . No significant deviation from the background-only hypothesis is observed. An upper limit at 95% confidence level is set on the product of the Higgs boson pair production cross section and branching fraction into $$ \gamma \gamma \mathrm{b}\overline{\mathrm{b}} $$ γγ b b ¯ . The observed (expected) upper limit is determined to be 0.67 (0 . 45) fb, which corresponds to 7.7 (5.2) times the standard model prediction. This search has the highest sensitivity to Higgs boson pair production to date. Assuming all other Higgs boson couplings are equal to their values in the standard model, the observed coupling modifiers of the trilinear Higgs boson self-coupling κ λ and the coupling between a pair of Higgs bosons and a pair of vector bosons c 2V are constrained within the ranges − 3 . 3 < κ λ < 8 . 5 and − 1 . 3 < c 2V < 3 . 5 at 95% confidence level. Constraints on κ λ are also set by combining this analysis with a search for single Higgs bosons decaying to two photons, produced in association with top quark-antiquark pairs, and by performing a simultaneous fit of κ λ and the top quark Yukawa coupling modifier κ t .more » « less
-
We consider the problem of comparing two complex multivariate random signal realizations of unequal lengths, to ascertain whether they have identical power spectral densities. A binary hypothesis testing approach is formulated and a generalized likelihood ratio test (GLRT) is derived. An asymptotic analytical solution for calculating the test threshold is provided. The results are illustrated via computer simulations. Past work on this problem is limited to either complex or real signals of equal lengths, or to real-valued scalar signals of unequal lengths. The proposed test has applications in diverse areas including user authentication in wireless networks with multiantenna receivers.more » « less
-
The search space for automatic program repair approaches is vast and the search for mechanisms to help restrict this search are increasing. We make a granular analysis based on statement kinds to find which statements are more likely to be modified than others when fixing an error. We construct a corpus for analysis by delimiting debugging regions in the provided dataset and recursively analyze the differences between the Simplified Syntax Trees associated with EditEvent's. We build a distribution of statement kinds with their corresponding likelihood of being modified and we validate the usage of this distribution to guide the statement selection. We then build association rules with different confidence thresholds to describe statement kinds commonly modified together for multi-edit patch creation. Finally we evaluate association rule coverage over a held out test set and find that when using a 95% confidence threshold we can create less and more accurate rules that fully cover 93.8% of the testing instances.more » « less
-
Reading a visualization is like reading a paragraph. Each sentence is a comparison: the mean of these is higher than those; this difference is smaller than that. What determines which comparisons are made first? The viewer's goals and expertise matter, but the way that values are visually grouped together within the chart also impacts those comparisons. Research from psychology suggests that comparisons involve multiple steps. First, the viewer divides the visualization into a set of units. This might include a single bar or a grouped set of bars. Then the viewer selects and compares two of these units, perhaps noting that one pair of bars is longer than another. Viewers might take an additional third step and perform a second-order comparison, perhaps determining that the difference between one pair of bars is greater than the difference between another pair. We create a visual comparison taxonomy that allows us to develop and test a sequence of hypotheses about which comparisons people are more likely to make when reading a visualization. We find that people tend to compare two groups before comparing two individual bars and that second-order comparisons are rare. Visual cues like spatial proximity and color can influence which elements are grouped together and selected for comparison, with spatial proximity being a stronger grouping cue. Interestingly, once the viewer grouped together and compared a set of bars, regardless of whether the group is formed by spatial proximity or color similarity, they no longer consider other possible groupings in their comparisons.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Book Chapter:
- https://doi.org/10.1007/978-981-97-2340-9_9
