skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Smoothed counting of 0–1 points in polyhedra
Abstract Given a system of linear equations in an ‐vector of 0–1 variables, we compute the expectation of , where is a vector of independent Bernoulli random variables and are constants. The algorithm runs in quasi‐polynomial time under some sparseness condition on the matrix of the system. The result is based on the absence of the zeros of the analytic continuation of the expectation for complex probabilities, which can also be interpreted as the absence of a phase transition in the Ising model with a sufficiently strong external field. We discuss applications to perfect matchings in hypergraphs and randomized rounding in discrete optimization.  more » « less
Award ID(s):
1855428
PAR ID:
10418803
Author(s) / Creator(s):
 
Publisher / Repository:
Wiley Blackwell (John Wiley & Sons)
Date Published:
Journal Name:
Random Structures & Algorithms
Volume:
63
Issue:
1
ISSN:
1042-9832
Page Range / eLocation ID:
p. 27-60
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract BackgroundEffectively controlling heartworm disease—a major parasitic disease threatening animal health in the US and globally—requires understanding the local ecology of mosquito vectors involved in transmission. However, the key vector species in a given region are often unknown and challenging to identify. Here we investigate (i) the key vector species associated with transmission of the parasite,Dirofilaria immitis, in California and (ii) the climate and land cover drivers of vector presence. MethodsTo identify key mosquito vectors involved in transmission, we incorporated long-term, finely resolved mosquito surveillance data and dog heartworm case data in a statistical modeling approach (fixed-effects regression) that rigorously controls for other unobserved drivers of heartworm cases. We then used a flexible machine learning approach (gradient boosted machines) to identify the climate and land cover variables associated with the presence of each species. ResultsWe found significant, regionally specific, positive associations between dog heartworm cases and the abundance of four vector species:Aedes aegypti(Central California),Ae. albopictus(Southern California),Ae. sierrensis(Central California), andCuliseta incidens(Northern and Central California). The proportion of developed land cover was one of the most important ecological variables predicting the presence or absence of the putative vector species. ConclusionOur results implicate three previously under-recognized vectors of dog heartworm transmission in California and indicate the land cover types in which each putative vector species is commonly found. Efforts to target these species could prioritize surveillance in these land cover types (e.g. near human dwellings in less urbanized settings forAe. albopictusandCs. incidens) but further investigation on the natural infection prevalence and host-biting rates of these species, as well as the other local vectors, is needed. Graphical Abstract 
    more » « less
  2. A<sc>bstract</sc> A search for the production of a single top quark in association with invisible particles is performed using proton-proton collision data collected with the CMS detector at the LHC at$$\sqrt{s}=13$$TeV, corresponding to an integrated luminosity of 138 fb−1. In this search, a flavor-changing neutral current produces a single top quark or antiquark and an invisible state nonresonantly. The invisible state consists of a hypothetical spin-1 particle acting as a new mediator and decaying to two spin-1/2 dark matter candidates. The analysis searches for events in which the top quark or antiquark decays hadronically. No significant excess of events compatible with that signature is observed. Exclusion limits at 95% confidence level are placed on the masses of the spin-1 mediator and the dark matter candidates, and are compared to constraints from the dark matter relic density measurements. In a vector (axial-vector) coupling scenario, masses of the spin-1 mediator are excluded up to 1.85 (1.85) TeV with an expectation of 2.0 (2.0) TeV, whereas masses of the dark matter candidates are excluded up to 0.75 (0.55) TeV with an expectation of 0.85 (0.65) TeV. 
    more » « less
  3. Abstract The randomized Kaczmarz methods are a popular and effective family of iterative methods for solving large-scale linear systems of equations, which have also been applied to linear feasibility problems. In this work, we propose a new block variant of the randomized Kaczmarz method, B-MRK, for solving linear feasibility problems defined by matrices. We show that B-MRK converges linearly in expectation to the feasible region. Furthermore, we extend the method to solve tensor linear feasibility problems defined under the tensor t-product. A tensor randomized Kaczmarz (TRK) method, TRK-L, is proposed for solving linear feasibility problems that involve mixed equality and inequality constraints. Additionally, we introduce another TRK method, TRK-LB, specifically tailored for cases where the feasible region is defined by linear equality constraints coupled with bound constraints on the variables. We show that both of the TRK methods converge linearly in expectation to the feasible region. Moreover, the effectiveness of our methods is demonstrated through numerical experiments on various Gaussian random data and applications in image deblurring. 
    more » « less
  4. Abstract Properties of gene genealogies such as tree height (H), total branch length (L), total lengths of external (E) and internal (I) branches, mean length of basal branches (B), and the underlying coalescence times (T) can be used to study population-genetic processes and to develop statistical tests of population-genetic models. Uses of tree features in statistical tests often rely on predictions that depend on pairwise relationships among such features. For genealogies under the coalescent, we provide exact expressions for Taylor approximations to expected values and variances of ratios Xn/Yn, for all 15 pairs among the variables {Hn,Ln,En,In,Bn,Tk}, considering n leaves and 2≤k≤n. For expected values of the ratios, the approximations match closely with empirical simulation-based values. The approximations to the variances are not as accurate, but they generally match simulations in their trends as n increases. Although En has expectation 2 and Hn has expectation 2 in the limit as n→∞, the approximation to the limiting expectation for En/Hn is not 1, instead equaling π2/3−2≈1.28987. The new approximations augment fundamental results in coalescent theory on the shapes of genealogical trees. 
    more » « less
  5. null (Ed.)
    Abstract System reliability is quantified by the probability that a system performs its intended function in a period of time without failure. System reliability can be predicted if all the limit-state functions of the components of the system are available, and such a prediction is usually time consuming. This work develops a time-dependent system reliability method that is extended from the component time-dependent reliability method that uses the envelop method and second order reliability method. The proposed method is efficient and is intended for series systems with limit-state functions whose input variables include random variables and time. The component reliability is estimated by the existing second order component reliability method, which produces component reliability indexes. The covariance between components responses are estimated with the first order approximations, which are available from the second order approximations of the component reliability analysis. Then the joint probability of all the component responses is approximated by a multivariate normal distribution with its mean vector being component reliability indexes and covariance being those between component responses. The proposed method is demonstrated and evaluated by three examples. 
    more » « less