Acropolis Educational Resources Repository
Not a member yet
31278 research outputs found
Sort by
Counting small induced subgraphs satisfying monotone properties
No full textGiven a graph property Φ , we study the problem #INDSUB(Φ) which asks, on input a graph G and a positive integer k , to compute the number #IndSub(Φ,k→G) of induced subgraphs of size k in G that satisfy Φ . The search for explicit criteria on Φ ensuring that #INDSUB(Φ) is hard was initiated by Jerrum and Meeks [J. Comput. Syst. Sci. 15] and is part of the major line of research on counting small patterns in graphs. However, apart from an implicit result due to Curticapean, Dell and Marx [STOC 17] proving that a full classification into “easy” and “hard” properties is possible and some partial results on edge-monotone properties due to Meeks [Discret. Appl. Math. 16] and Dörfler et al. [MFCS 19], not much is known. In this work, we fully answer and explicitly classify the case of monotone, that is subgraph-closed, properties: We show that for any non-trivial monotone property Φ , the problem #INDSUB(Φ) cannot be solved in time f(k).|V(G)|o(k/log1/2(k)) for any function f , unless the Exponential Time Hypothesis fails. By this, we establish that any significant improvement over the brute-force approach is unlikely; in the language of parameterized complexity, we also obtain a #W[1] - completeness result
Causal effects of gallstone disease on risk of gastrointestinal cancer in Chinese
No full textBackground: Gallstone disease (GSD) is associated with a higher risk of gastrointestinal (GI) cancer. However, it is unclear whether the associations are causal.
Methods: The prospective China Kadoorie Biobank (CKB) recorded 17,598 cases of GI cancer among 510,137 participants without cancer at baseline during 10 years of follow-up. Cox regression was used to estimate hazard ratios (HRs) for specific cancer by GSD status and duration. Mendelian randomisation was conducted to assess the genetic associations of GSD with specific cancer.
Results: Overall 6% of participants had symptomatic GSD at baseline. Compared with those without GSD, individuals with symptomatic GSD had adjusted HRs of 1.13 (1.01–1.29) for colorectal, 2.01 (1.78–2.26) for liver, 3.70 (2.88–4.87) for gallbladder, 2.31 (1.78–3.07) for biliary tract, and 1.38 (1.18–1.74) for pancreatic cancer. Compared with participants without GSD, the risks of colorectal, liver, gallbladder, biliary tract, and pancreatic cancer were highest during 0 to <5 years following disease diagnosis. There was evidence of genetic associations of GSD with these cancers, with odds ratios per 1-SD genetic score of 1.08 (1.05–1.11) for colorectal, 1.22 (1.19–1.25) for liver, 1.56 (1.49–1.64) for gallbladder, 1.39 (1.31–1.46) for biliary tract, and 1.16 (1.10–1.22) for pancreatic cancer. When meta-analysing the genetic estimates in CKB and UK Biobank, there was evidence of causal associations of GSD with colon cancer, gallbladder and biliary tract cancer (GBTC), and total GI cancer (RR per 1-SD: 1.05 [0.99–1.11], 2.00 [1.91–2.09], and 1.09 [1.05–1.13]).
Conclusions: GSD was associated with higher risks of several GI cancers, warranting future studies on the underlying mechanisms
Educational disparities in ischaemic heart disease among 0.5 million Chinese adults: a cohort study
No full textBackground The relationship between educational attainment and ischaemic heart disease (IHD) is limited in evidence in middle-income countries like China. Exploring lifestyle-related mediators, which might be not universal between socioeconomic status and health outcomes in diverse regions, can contribute to interventions targeted at the Chinese to narrow the educational gap in IHD.
Methods Based on the China Kadoorie Biobank of 489 594 participants aged 30–79 years who did not have heart disease or stroke at baseline, this study examined the association of educational attainment with IHD. Total IHD cases were further divided into acute myocardial infarction (AMI) cases and non-AMI cases. The Cox proportional hazard model was performed to estimate the HRs and 95% CIs for mortality and incidence of IHD. Logistic regression was used to estimate the ORs and 95% CIs for case fatality.
Results During the median follow-up period of 11.1 years, this study documented 45 946 (6668) incident IHD (AMI) cases and 5948 (3689) deaths altogether. Lower educational attainment was associated with increased risk of incident AMI as well as death and fatality of total IHD including its subtypes (ptrend <0.001). Although the risk of incident non-AMI was greater for participants with higher levels of education in the whole population (ptrend <0.001), an inverse association of education with its incidence was found in participants from <50 years age group and rural areas. Smoking and dietary habits were the two most potent mediating factors in the associations of education with mortality and AMI incidence; whereas, physical activity was the major mediating factor for non-AMI incidence in the whole population.
Discussion Interventions targeting unhealthy lifestyles are ideal ways to narrow the educational gap in IHD while solving ‘upstream’ causes of health behaviours might be the most fundamental ones
The spectre of the present: Time, presentism and the writing of contemporary history
No full textPresentism used to be so simple. In the old vernacular it referred to a tendency to view the past from the perspective of the present (or, at its most extreme, maybe even use the past to illuminate the present). Historians disagreed furiously on the intellectual virtues of orienting their views of the past to the needs of the current day. But the content of the term itself was rarely disputed
Balancing accountability and effectiveness: a case for moderated parliamentarism
No full textIn this article, I bring two key issues in constitutional studies — institutional regime type and electoral system choice — in conversation with each other, and examine their interaction through a normative framework concerning the role that constitutions ought to play in shaping their party systems. The main goal is to offer a theoretical defense (ceteris paribus) of moderated parliamentarism — as superior to its alternatives such as presidentialism, semi-presidentialism, and other forms of parliamentarism
Initial limit Datalog: a new extensible class of decidable constrained Horn clauses
No full textWe present initial limit Datalog, a new extensible class of constrained Horn clauses for which the satisfiability problem is decidable. The class may be viewed as a generalisation to higher-order logic (with a simple restriction on types) of the first-order language limit Datalog Z (a fragment of Datalog modulo linear integer arithmetic), but can be instantiated with any suitable background theory. For example, the fragment is decidable over any countable well-quasi-order with a decidable first-order theory, such as natural number vectors under componentwise linear arithmetic, and words of a bounded, context-free language ordered by the subword relation. Formulas of initial limit Datalog have the property that, under some assumptions on the background theory, their satisfiability can be witnessed by a new kind of term model which we call entwined structures. Whilst the set of all models is typically uncountable, the set of all entwined structures is recursively enumerable, and model checking is decidable
Quantifying the heterogeneity of cognitive functioning in Alzheimer’s disease to extend the placebo-treatment dichotomy: Latent class analysis of individual-participant data from five pivotal randomized clinical trials of donepezil
No full textBackground
The extent and profiles of heterogeneity in cognitive functioning among participants in clinical trials of antidementia medication are unknown. We aimed to quantify and identify profiles of heterogeneity of cognition in Alzheimer’s disease.
Methods
Individual-level participant data were analyzed from five pivotal clinical trials of donepezil for Alzheimer’s disease (N = 2,919). Based on Alzheimer’s Disease Assessment Scale–Cognitive Subscale total scores from baseline up to week 12, a latent class model was used to identify heterogeneous groups. A logistic regression model was used to examine factors associated with group membership. Sensitivity analysis was conducted, restricted to the donepezil, and then the placebo arm.
Results
The latent class model identified three classes labeled as low scorers (i.e., least cognitive impairment; N = 1,666, 76.04%), improvers (N = 27, 1.23%), and high scorers (N = 498, 22.73%). Logistic modeling showed that donepezil compared to placebo was significantly (p < 0.05) positively associated with membership in the improvers class (OR = 6.88, 95% CI = 2.03, 42.95), and negatively with high scorers (OR = 0.79, 95% CI = 0.64, 0.98). Sensitivity analysis restricted to the placebo, then donepezil arms replicated similar heterogeneity patterns.
Conclusions
Our results inform clinicians regarding the extent of heterogeneity in cognitive functioning during treatment and contribute to trial design considerations
Reduced neutralisation of SARS-CoV-2 omicron B.1.1.529 variant by post-immunisation serum
No full text
