93 research outputs found
Certification with an NP Oracle
No full textIn the certification problem, the algorithm is given a function with
certificate complexity and an input , and the goal is to find a
certificate of size for 's value at . This
problem is in , and assuming , is not in . Prior works, dating back to Valiant in
1984, have therefore sought to design efficient algorithms by imposing
assumptions on such as monotonicity.
Our first result is a algorithm for the general
problem. The key ingredient is a new notion of the balanced influence of
variables, a natural variant of influence that corrects for the bias of the
function. Balanced influences can be accurately estimated via uniform
generation, and classic algorithms are known for
the latter task.
We then consider certification with stricter instance-wise guarantees: for
each , find a certificate whose size scales with that of the smallest
certificate for . In sharp contrast with our first result, we show
that this problem is -hard even to approximate. We
obtain an optimal inapproximability ratio, adding to a small handful of
problems in the higher levels of the polynomial hierarchy for which optimal
inapproximability is known. Our proof involves the novel use of bit-fixing
dispersers for gap amplification.Comment: 25 pages, 2 figures, ITCS 202
Multiple gap symmetries for the order parameter of cuprate superconductors from penetration depth measurements
No full textThe temperature dependence of the London penetration depth λ was measured for an untwinned single crystal of YBa2Cu3O7-δ along the three principal crystallographic directions (a, b, and c). Both in-plane components (λa-2 and λb-2) show an inflection point in their temperature dependence which is absent in the component along the c direction (λc-2). The data provide convincing evidence that the in-plane superconducting order parameter is a mixture of (s+d)-wave symmetry whereas it is mainly s wave along the c direction. In conjunction with previous results it is concluded that coupled s+d-order parameters are universal and intrinsic to cuprate superconductors
Superpolynomial Lower Bounds for Learning Monotone Classes
No full textKoch, Strassle, and Tan [SODA 2023], show that, under the randomized exponential time hypothesis, there is no distribution-free PAC-learning algorithm that runs in time n^Õ(log log s) for the classes of n-variable size-s DNF, size-s Decision Tree, and log s-Junta by DNF (that returns a DNF hypothesis). Assuming a natural conjecture on the hardness of set cover, they give the lower bound n^Ω(log s). This matches the best known upper bound for n-variable size-s Decision Tree, and log s-Junta.
In this paper, we give the same lower bounds for PAC-learning of n-variable size-s Monotone DNF, size-s Monotone Decision Tree, and Monotone log s-Junta by DNF. This solves the open problem proposed by Koch, Strassle, and Tan and subsumes the above results.
The lower bound holds, even if the learner knows the distribution, can draw a sample according to the distribution in polynomial time, and can compute the target function on all the points of the support of the distribution in polynomial time
Hopelessness and high risk parenting attitudes in relation to child abuse and neglect
No full textPlan BA review of the literature indicates the relationship between hopelessness and depression in adolescent females is significant. The problem of hopelessness as a component of depression is explored in this study, as is the correlation between hopelessness and high risk parenting attitudes in teenage girls. According to a study by Lamb and Nitz (1991), approximately one million teenage girls become pregnant each year. Adolescents who become parents may experience added stress, which may result in child abuse and neglect. Child abuse and neglect is at an all time high in our country, and is surely a national crisis. The Child Abuse Prevention, Adoption and Family Services Act of 1988 (Public Law 93-247) defines abuse and neglect as “the physical or mental injury, sexual abuse or exploitation, negligent treatment or maltreatment of a child under the age of 18 by a person who is responsible for the child’s welfare under circumstances which indicate that the child’s health or welfare is harmed or threatened” (Bavolek, 1990). This study will acknowledge and discuss the importance of identifying and treating hopelessness in teenage mothers. Rust (1999) indicates teenage mothers are at increased risk for depression and high risk parenting attitudes in relation to child physical abuse. Therefore, the purpose of this study is to correlate hopelessness and high risk parenting attitudes in teenage parents. There is a great amount that can be learned from this study, and research suggests that child abuse and neglect and the problems associated with this issue are not going away, they are at epidemic proportions, despite the increased interventions of the last ten years. This study is pertinent in today’s world and can provide insight into reducing the incidents of child abuse and neglect. The purpose of this study is to assess the degree of correlation between hopelessness in adolescent females and high risk parenting attitudes. For the purpose of this study, thirty adolescent females were asked to complete the Beck’s Hopelessness Scale and Adult-Adolescent Parenting Inventory (AAPI-2), [Bavolek,1999]. Upon completion of the study, a significant degree of correlation was not found between hopelessness in adolescent females and high risk parenting attitudes
Regional differences in right versus left congenital heart disease diagnoses in neonates in the United States
No full textPressure dependence of Morin transition in α-Fe2O3 hematite
No full textInternational audienceWe report high-pressure neutron diffraction data on the Morin-transition TM in α- Fe2O3 hematite, up to 8GPa and under hydrostatic conditions. We find a strictly linear pressure coefficient of ∂TM/∂P = +27 ± 1K/GPa with no evidence for intermediate magnetic states as indicated by all previous non-hydrostatic measurements. The behaviour of TM is highly regular and can well be explained within the framework of Artman et al.'s single-ion model if a change of the single-ion anisotropy energy by +1%/GPa is assumed. Such a value seems not to be unusual for iron oxides
Mechanisms of heteroresistance in methicillin-resistant Staphylococcus aureus
No full textCharacteristic for methicillin-resistant (Mcr) staphylococci is the heterogeneous expression of the intrinsic methicillin resistance. The majority of the cells express resistance to low concentrations of methicillin, and a minority of the cells express resistance to much higher concentrations. We show here (i) that the presence of the mecA encoding region on plasmid pBBB79 was sufficient to render a methicillin-susceptible (Mcs) Staphylococcus aureus strain heteroresistant and (ii) that this Mcr strain segregated highly resistant subclones which retained the high-resistance phenotype under nonselective growth conditions. The Mcr strain with only mecA on plasmid pBBB79 thus behaved identically to a Mcr strain carrying the complete mec determinant integrated at its proper chromosomal site. (iii) Curing a such highly resistant subclone from plasmid pBBB79 yielded an Mcs strain that was as susceptible as the original Mcs parent strain. (iv) Comparisons were made between the original parent and the cured Mcs strain by backcrossing pBBB79 into them and looking at their progeny. Transductants derived from the formerly highly resistant cured strain became resistant to high concentrations of methicillin, whereas transductants derived from the original parent strain were resistant to lower concentrations of methicillin and showed the typical heterogeneous resistance. We deduced therefrom that the high-level resistance expressed by the minority of the population of Mcr S. aureus was due to a chromosomal mutation(s) (chr*) involving neither mecA nor the additional 30 kb of mec-associated DNA
High pressure neutron diffraction to beyond 20 GPa and below 1.8 K using Paris-Edinburgh load frames
No full textEquation of state of lead from high-pressure neutron diffraction up to 8.9 GPa and its implication for the NaCl pressure scale
No full textInternational audienceFrom high-resolution neutron-diffraction experiments we present equation-of-state (EOS) data of elemental lead as functions of both temperature (80-298 K) and applied pressure (up to 8.9 GPa), with the pressure values derived from the NaCl pressure gauge. Based on Brown's 1999 NaCl EOS we find the bulk modulus of lead of B0 = 41.2(2) GPa at 298 K to increase by 14% to B0 = 47.0(5) GPa by 80 K. The ambient temperature value coincides within 0.35 GPa (1.7%) of the value determined from published ultrasonic data. The good agreement between the neutron and ultrasonic data deteriorates if pressure values are derived from Decker's 1971 scale. Our results hence lend significant support to Brown's revised NaCl pressure standard. Furthermore, the experimental results are compared with T = 0 K first-principles calculation
COVID-19 vaccination willingness and uptake among low-income Black/African American, Latino, and White adults living in the U.S
No full textThe purpose of this study was to assess differences in COVID-19 vaccine willingness and uptake between low-income and non-low-income adults and across race-ethnicity. We utilized data from the COVID-19′s Unequal Racial Burden online survey, which included baseline (12/17/2020–2/11/2021) and 6-month follow-up (8/13/2021–9/9/2021) surveys. The sample included 1,500 Black/African American, Latino, and White low-income adults living in the U.S. (N = 500 each). A non-low-income cohort was created for comparison (n = 1,188). Multinomial logistic regression was used to assess differences in vaccine willingness and uptake between low-income and non-low-income adults, as well as across race-ethnicity (low-income adults only). Only low-income White adults were less likely to be vaccinated compared to their non-low-income counterparts (extremely willing vs. not at all: OR = 0.58, 95% CI = 0.39–0.86); low-income Black/African American and Latino adults were just as willing or more willing to vaccinate. At follow-up, only 30.2% of low-income adults who reported being unwilling at baseline were vaccinated at follow-up. White low-income adults (63.6%) appeared less likely to be vaccinated, compared to non-low-income White adults (80.9%), low-income Black/African American (70.7%), and low-income Latino adults (72.4%). Distrust in the government (46.6), drug companies (44.5%), and vaccine contents (52.1%) were common among those unwilling to vaccinate. This prospective study among a diverse sample of low-income adults found that low-income White adults were less willing and less likely to vaccinate than their non-low-income counterparts, but this difference was not observed for Black/African American or Latino adults. Distrust and misinformation were prevalent among those who remained unvaccinated at follow-up
- …
