| 11. |
- De Rezende, Susanna F., et al.
(författare)
-
Automating algebraic proof systems is NP-hard
- 2021
-
Ingår i: STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. - New York, NY, USA : Association for Computing Machinery (ACM). - 0737-8017. - 9781450380539 ; , s. 209-222
-
Konferensbidrag (refereegranskat)abstract
- We show that algebraic proofs are hard to find: Given an unsatisfiable CNF formula F, it is NP-hard to find a refutation of F in the Nullstellensatz, Polynomial Calculus, or Sherali-Adams proof systems in time polynomial in the size of the shortest such refutation. Our work extends, and gives a simplified proof of, the recent breakthrough of Atserias and Müller (JACM 2020) that established an analogous result for Resolution.
|
|
| 12. |
- De Rezende, Susanna F., et al.
(författare)
-
KRW composition theorems via lifting
- 2020
-
Ingår i: Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. - : IEEE Computer Society. - 0272-5428. - 9781728196220 - 9781728196213 ; 2020-November, s. 43-49
-
Konferensbidrag (refereegranskat)abstract
- One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., mathrm{P} nsubseteq text{NC}{1}). Karchmer, Raz, and Wigderson [13] suggested to approach this problem by proving that depth complexity behaves'as expected' with respect to the composition of functions f diamond g. They showed that the validity of this conjecture would imply that mathrm{P} nsubseteq text{NC}{1}. Several works have made progress toward resolving this conjecture by proving special cases. In particular, these works proved the KRW conjecture for every outer function, but only for few inner functions. Thus, it is an important challenge to prove the KRW conjecture for a wider range of inner functions. In this work, we extend significantly the range of inner functions that can be handled. First, we consider the monotone version of the KRW conjecture. We prove it for every monotone inner function whose depth complexity can be lower bounded via a query-to-communication lifting theorem. This allows us to handle several new and well-studied functions such as the s-t-connectivity, clique, and generation functions. In order to carry this progress back to the non-monotone setting, we introduce a new notion of semi-monotone composition, which combines the non-monotone complexity of the outer function with the monotone complexity of the inner function. In this setting, we prove the KRW conjecture for a similar selection of inner functions, but only for a specific choice of the outer function f.
|
|
| 13. |
- De Rezende, Susanna F., et al.
(författare)
-
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
- 2021
-
Ingår i: Computational Complexity. - : Birkhäuser Verlag. - 1016-3328 .- 1420-8954. ; 30:1
-
Tidskriftsartikel (refereegranskat)abstract
- We establish an exactly tight relation between reversiblepebblings of graphs and Nullstellensatz refutations of pebbling formulas,showing that a graph G can be reversibly pebbled in time t and space s if and only if there is a Nullstellensatz refutation of the pebbling formulaover G in size t + 1 and degree s (independently of the field in whichthe Nullstellensatz refutation is made). We use this correspondenceto prove a number of strong size-degree trade-offs for Nullstellensatz,which to the best of our knowledge are the first such results for thisproof system.
|
|
| 14. |
- De Rezende, Susanna, et al.
(författare)
-
Lifting with simple gadgets and applications to circuit and proof complexity
- 2020
-
Ingår i: Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. - : IEEE Computer Society. - 0272-5428. - 9781728196220 - 9781728196213 ; 2020-November, s. 24-30
-
Konferensbidrag (refereegranskat)abstract
- We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We apply our generalized theorem to solve three open problems: •We present the first result that demonstrates a separation in proof power for cutting planes with unbounded versus polynomially bounded coefficients. Specifically, we exhibit CNF formulas that can be refuted in quadratic length and constant line space in cutting planes with unbounded coefficients, but for which there are no refutations in subexponential length and subpolynomial line space if coefficients are restricted to be of polynomial magnitude. •We give the first explicit separation between monotone Boolean formulas and monotone real formulas. Specifically, we give an explicit family of functions that can be computed with monotone real formulas of nearly linear size but require monotone Boolean formulas of exponential size. Previously only a non-explicit separation was known. •We give the strongest separation to-date between monotone Boolean formulas and monotone Boolean circuits. Namely, we show that the classical GEN problem, which has polynomial-size monotone Boolean circuits, requires monotone Boolean formulas of size 2{Omega(n text{polylog}(n))}. An important technical ingredient, which may be of independent interest, is that we show that the Nullstellensatz degree of refuting the pebbling formula over a DAG G over any field coincides exactly with the reversible pebbling price of G. In particular, this implies that the standard decision tree complexity and the parity decision tree complexity of the corresponding falsified clause search problem are equal. This is an extended abstract. The full version of the paper is available at https://arxiv.org/abs/2001.02144.
|
|
| 15. |
- Hagsäter, S Melker, et al.
(författare)
-
A Complex Impact of Systemically Administered 5-HT2A Receptor Ligands on Conditioned Fear
- 2021
-
Ingår i: International Journal of Neuropsychopharmacology. - : Oxford University Press (OUP). - 1461-1457 .- 1469-5111. ; 24:9, s. 749-757
-
Tidskriftsartikel (refereegranskat)abstract
- Background: Though drugs binding to serotonergic 5-HT2A receptors have long been claimed to influence human anxiety, it remains unclear if this receptor subtype is best described as anxiety promoting or anxiety dampening. Whereas conditioned fear expressed as freezing in rats is modified by application of 5-HT2A-acting drugs locally into different brain regions, reports on the effect of systemic administration of 5-HT2A receptor agonists and 5-HT2A antagonists or inverse agonists on this behavior remain sparse. Methods: We assessed the possible impact of systemic administration of 5-HT2A receptor agonists, 5-HT2A receptor inverse agonists, and a selective serotonin reuptake inhibitor (SSRI)-per se or in combination-on the freezing displayed by male rats when re-exposed to a conditioning chamber in which they received foot shocks 7 days earlier. Results: The 5-HT2A receptor agonists psilocybin and 25CN-NBOH induced a reduction in conditioned fear that was countered by pretreatment with 5-HT2A receptor inverse agonist MDL 100907. While both MDL 100907 and another 5-HT2A receptor inverse agonist, pimavanserin, failed to impact freezing per se, both compounds unmasked a robust fear-reducing effect of an SSRI, escitalopram, which by itself exerted no such effect. Conclusions: The results indicate that 5-HT2A receptor activation is not a prerequisite for normal conditioned freezing in rats but that this receptor subtype, when selectively over-activated prior to expression, exerts a marked fear-reducing influence. However, in the presence of an SSRI, the 5-HT2A receptor, on the contrary, appears to counter an anti-freezing effect of the enhanced extracellular serotonin levels following reuptake inhibition.
|
|
| 16. |
- Ji, Xuemei, et al.
(författare)
-
Protein-altering germline mutations implicate novel genes related to lung cancer development
- 2020
-
Ingår i: Nature Communications. - : Springer Science and Business Media LLC. - 2041-1723. ; 11:1
-
Tidskriftsartikel (refereegranskat)abstract
- Few germline mutations are known to affect lung cancer risk. We performed analyses of rare variants from 39,146 individuals of European ancestry and investigated gene expression levels in 7,773 samples. We find a large-effect association with an ATM L2307F (rs56009889) mutation in adenocarcinoma for discovery (adjusted Odds Ratio=8.82, P=1.18x10(-15)) and replication (adjusted OR=2.93, P=2.22x10(-3)) that is more pronounced in females (adjusted OR=6.81 and 3.19 and for discovery and replication). We observe an excess loss of heterozygosity in lung tumors among ATM L2307F allele carriers. L2307F is more frequent (4%) among Ashkenazi Jewish populations. We also observe an association in discovery (adjusted OR=2.61, P=7.98x10(-22)) and replication datasets (adjusted OR=1.55, P=0.06) with a loss-of-function mutation, Q4X (rs150665432) of an uncharacterized gene, KIAA0930. Our findings implicate germline genetic variants in ATM with lung cancer susceptibility and suggest KIAA0930 as a novel candidate gene for lung cancer risk. In lung cancer, relatively few germline mutations are known to impact risk. Here the authors looked at rare variants in 39,146 individuals and find novel germline mutations associated with risk, as well as implicating ATM and a new candidate gene for lung cancer risk.
|
|
| 17. |
- Lindqvist, Karin, et al.
(författare)
-
Affect-Focused Psychodynamic Internet-Based Therapy for Adolescent Depression : Randomized Controlled Trial
- 2020
-
Ingår i: Journal of Medical Internet Research. - Toronto, ON, Canada : JMIR Publications Inc.. - 1438-8871. ; 22:3
-
Tidskriftsartikel (refereegranskat)abstract
- BACKGROUND: Adolescent depression is one of the largest health issues in the world and there is a pressing need for effective and accessible treatments. OBJECTIVE: This trial examines whether affect-focused internet-based psychodynamic therapy (IPDT) with therapist support is more effective than an internet-based supportive control condition on reducing depression in adolescents. METHODS: The trial included 76 adolescents (61/76, 80% female; mean age 16.6 years), self-referred via an open access website and fulfilling criteria for major depressive disorder. Adolescents were randomized to 8 weeks of IPDT (38/76, 50%) or supportive control (38/76, 50%). The primary outcome was self-reported depressive symptoms, measured with the Quick Inventory of Depressive Symptomatology for Adolescents (QIDS-A17-SR). Secondary outcomes were anxiety severity, emotion regulation, self-compassion, and an additional depression measure. Assessments were made at baseline, postassessment, and at 6 months follow-up, in addition to weekly assessments of the primary outcome measure as well as emotion regulation during treatment. RESULTS: IPDT was significantly more effective than the control condition in reducing depression (d=0.82, P=.01), the result of which was corroborated by the second depression measure (d=0.80, P<.001). IPDT was also significantly more effective in reducing anxiety (d=0.78, P<.001) and increasing emotion regulation (d=0.97, P<.001) and self-compassion (d=0.65, P=.003). Significantly more patients in the IPDT group compared to the control group met criteria for response (56% vs 21%, respectively) and remission (35% vs 8%, respectively). Results on depression and anxiety symptoms were stable at 6 months follow-up. On average, participants completed 5.8 (SD 2.4) of the 8 modules. CONCLUSIONS: IPDT may be an effective intervention to reduce adolescent depression. Further research is needed, including comparisons with other treatments.
|
|
| 18. |
- Luiken, Ina, et al.
(författare)
-
Pleuropulmonary pathologies in the early phase of acute pancreatitis correlate with disease severity
- 2022
-
Ingår i: PLoS ONE. - : Public Library of Science (PLoS). - 1932-6203. ; 17:2 February
-
Tidskriftsartikel (refereegranskat)abstract
- Background Respiratory failure worsens the outcome of acute pancreatitis (AP) and underlying factors might be early detectable. Aims To evaluate the prevalence and prognostic relevance of early pleuropulmonary pathologies and pre-existing chronic lung diseases (CLD) in AP patients. Methods Multicentre retrospective cohort study. Caudal sections of the thorax derived from abdominal contrast enhanced computed tomography (CECT) performed in the early phase of AP were assessed. Independent predictors of severe AP were identified by binary logistic regression analysis. A one-year survival analysis using Kaplan-Meier curves and log rank test was performed. Results 358 patients were analysed, finding pleuropulmonary pathologies in 81%. CECTs were performed with a median of 2 days (IQR 1–3) after admission. Multivariable analysis identified moderate to severe or bilateral pleural effusions (PEs) (OR = 4.16, 95%CI 2.05–8.45, p<0.001) and pre-existing CLD (OR = 2.93, 95%CI 1.17–7.32, p = 0.022) as independent predictors of severe AP. Log rank test showed a significantly worse one-year survival in patients with bilateral compared to unilateral PEs in a subgroup. Conclusions Increasing awareness of the prognostic impact of large and bilateral PEs and pre-existing CLD could facilitate the identification of patients at high risk for severe AP in the early phase and thus improve their prognosis.
|
|
| 19. |
- Mechler, Jakob, et al.
(författare)
-
Internet-based psychodynamic versus cognitive behaviour therapy for adolescents with depression : Study protocol for a non-inferiority randomized controlled trial (the ERiCA study)
- 2020
-
Ingår i: Trials. - : BioMed Central (BMC). - 1745-6215. ; 21:1
-
Tidskriftsartikel (refereegranskat)abstract
- Background: Adolescent depression is a common mental health problem and there is an urgent need for effective and accessible treatments. Internet-based interventions solve many obstacles for seeking and receiving treatment, thus increasing access to effective treatments. Internet-based cognitive behavioural therapy (ICBT) for adolescent depression has demonstrated efficacy in previous trials. In order to broaden the range of evidence-based treatments for young people, we evaluated a newly developed affect-focused Internet-based psychodynamic treatment (IPDT) in a previous study with promising results. The purpose of the planned study is to evaluate the efficacy of IPDT for adolescent depression in a non-inferiority trial, comparing it to ICBT. Methods: The study will employ a parallel randomized non-inferiority design (ratio 1:1; n = 270). Eligible participants are adolescents 15-19 years suffering from depression. The primary hypothesis is that IPDT will be non-inferior to ICBT in reducing depressive symptoms from pre-treatment to end of treatment. Secondary research questions include comparing outcomes of IPDT and ICBT regarding anxiety symptoms, emotion regulation and self-compassion. Additional data will be collected to evaluate cost-effectiveness as well as investigating predictors, moderators and mediators of outcome. In addition, we will examine long-term outcome up to 1 year after end of treatment. Diagnostic interviews with MINI 7.0 will be used to establish primary diagnosis of depression as well as ruling out any exclusion criteria. Both treatments consist of eight modules over 10 weeks, complemented with therapist support through text messages and weekly chat sessions. Primary outcome measure is the Quick Inventory of Depressive Symptomatology in Adolescents Self-Rated (QIDS-A17-SR). Primary outcome will be analysed using data from all participants entering the study using a multilevel growth curve strategy based on the weekly measurements of QIDS-A17-SR. The non-inferiority margin is defined as d = 0.30. Discussion: This trial will demonstrate whether IPDT is non-inferior to ICBT in the treatment of adolescent depression. The study might therefore broaden the range of evidence-based treatment alternatives for young people struggling with depression. Further analyses of data from this trial may increase our knowledge about "what works for whom"and the pathways of change for two distinct types of interventions. Trial registration: ISRCTN12552584, Registered on 13 August 2019.
|
|
| 20. |
- Mechler, Jakob, et al.
(författare)
-
Therapist-guided internet-based psychodynamic therapy versus cognitive behavioural therapy for adolescent depression in Sweden : a randomised, clinical, non-inferiority trial
- 2022
-
Ingår i: The Lancet Digital Health. - : Elsevier. - 2589-7500. ; 4:8, s. e594-e603
-
Tidskriftsartikel (refereegranskat)abstract
- Background: Adolescent major depressive disorder (MDD) is highly prevalent and associated with lifelong adversity. Evidence-based treatments exist, but accessible treatment alternatives are needed. We aimed to compare internet-based psychodynamictherapy (IPDT) with an established evidence-based treatment (internet-based cognitive behavioural therapy [ICBT]) for the treatment of adolescents with depression.Methods: In this randomised, clinical trial, we tested whether IPDT was non-inferior to ICBT in the treatment of adolescent MDD. Eligible participants were 15–19 years old, presenting with a primary diagnosis of MDD according to DSM-5. Participants were recruited nationwide in Sweden through advertisements on social media, as well as contacts with junior and senior high schools, youth associations, social workers, and health-care providers. Adolescents who scored 9 or higher on the Quick Inventory of Depressive Symptomatology for Adolescents (QIDS-A17-SR) in an initial online screening were contacted by telephone for a diagnostic assessment using the Mini International Neuropsychiatric Interview. Participants were randomly assigned to ICBT or IPDT. Both interventions comprised eight self-help modules delivered over 10 weeks on a secure online platform. The primary outcome was change in depression severity measured weekly by the QIDS-A17-SR. Primary analyses were based on an intention-to-treat sample including all participants randomly assigned. A non-inferiority margin of Cohen's d=0·30 was predefined. The study is registered at ISRCTN, ISRCTN12552584.Findings: Between Aug 19, 2019, and Oct 7, 2020, 996 young people completed screening; 516 (52%) were contacted for a diagnostic interview. 272 participants were eligible and randomly assigned to ICBT (n=136) or IPDT (n=136). In the ICBT group, 51 (38%) of 136 participants were classified as remitted, and 54 (40%) of 136 participants were classified as remitted in the IPDT group. Within-group effects were large (ICBT: within-group d=1·75, 95% CI 1·49 to 2·01; IPDT: within-group d=1·93, 1·67 to 2·20; both p<0·0001). No statistically significant treatment difference was found in the intention-to-treat analysis. Non-inferiority for IPDT was shown for the estimated change in depression during treatment (d=–0·18, 90% CI –0·49 to 0·13; p=0·34). All secondary outcomes showed non-significant between-group differences.Interpretation: IPDT was non-inferior to ICBT in terms of change in depression for the treatment of adolescents with MDD. This finding increases the range of accessible and effective treatment alternatives for adolescents with depression.
|
|
