51. 
 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.  02725428.  9781728196213  9781728196220 ; 2020November, s. 4349

Konferensbidrag (refereegranskat)abstract
 One of the major open problems in complexity theory is proving superlogarithmic 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 querytocommunication lifting theorem. This allows us to handle several new and wellstudied functions such as the stconnectivity, clique, and generation functions. In order to carry this progress back to the nonmonotone setting, we introduce a new notion of semimonotone composition, which combines the nonmonotone 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.


52. 
 de Rezende, Susanna F., 1989, et al.
(författare)

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

Annan publikation (övrigt vetenskapligt)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 greaterthan. We apply our generalized theorem to solve two 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 subpolynomialline 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 nonexplicit separation was known.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.


53. 
 de Rezende, Susanna F., et al.
(författare)

Nullstellensatz SizeDegree Tradeoffs from Reversible Pebbling
 2019

Ingår i: Proceedings of the 34th Annual Computational Complexity Conference (CCC ’19).  : Schloss Dagstuhl LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing.  9783959771160 ; , s. 18:118:16

Konferensbidrag (refereegranskat)abstract
 We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph G can be reversibly pebbled in time t and space s if an only if there is a Nullstellensatz refutation of the pebbling formula over G in size t + 1 and degree s (independently of the field in which the Nullstellensatz refutation is made). We use this correspondence to prove a number of strong sizedegree tradeoffs for Nullstellensatz, which to the best of our knowledge are the first such results for this proof system.


54. 
 De Rezende, Susanna F., et al.
(författare)

Nullstellensatz SizeDegree Tradeoffs from Reversible Pebbling
 2021

Ingår i: Computational Complexity.  : Birkhäuser Verlag.  10163328. ; 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 sizedegree tradeoffs for Nullstellensatz,which to the best of our knowledge are the first such results for thisproof system.


55. 
 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.  02725428.  9781728196213  9781728196220 ; 2020November, s. 2430

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 greaterthan. 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 nonexplicit separation was known. •We give the strongest separation todate between monotone Boolean formulas and monotone Boolean circuits. Namely, we show that the classical GEN problem, which has polynomialsize 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.


56. 
 de Savigny, Don, et al.
(författare)

Integrating communitybased verbal autopsy into civil registration and vital statistics (CRVS) : systemlevel considerations
 2017

Ingår i: Global Health Action.  16549716 . 16549880. ; 10

Tidskriftsartikel (refereegranskat)abstract
 Background: Reliable and representative cause of death (COD) statistics are essential to inform public health policy, respond to emerging health needs, and document progress towards Sustainable Development Goals. However, less than onethird of deaths worldwide are assigned a cause. Civil registration and vital statistics (CRVS) systems in lowand lowermiddleincome countries are failing to provide timely, complete and accurate vital statistics, and it will still be some time before they can provide physiciancertified COD for every death.Proposals: Verbal autopsy (VA) is a method to ascertain the probable COD and, although imperfect, it is the best alternative in the absence of medical certification. There is extensive experience with VA in research settings but only a few examples of its use on a large scale. Data collection using electronic questionnaires on mobile devices and computer algorithms to analyse responses and estimate probable COD have increased the potential for VA to be routinely applied in CRVS systems. However, a number of CRVS and health system integration issues should be considered in planning, piloting and implementing a systemwide intervention such as VA. These include addressing the multiplicity of stakeholders and subsystems involved, integration with existing CRVS work processes and information flows, linking VA results to civil registration records, information technology requirements and data quality assurance.Conclusions: Integrating VA within CRVS systems is not simply a technical undertaking. It will have profound systemwide effects that should be carefully considered when planning for an effective implementation. This paper identifies and discusses the major systemlevel issues and emerging practices, provides a planning checklist of systemlevel considerations and proposes an overview for how VA can be integrated into routine CRVS systems.


57. 
 Dilday, Benjamin, et al.
(författare)

A Measurement of the Rate of Type Ia Supernovae in Galaxy Clusters from the SDSSII Supernova Survey
 2010

Ingår i: Astrophysical Journal.  0004637X . 15384357. ; 715, s. 10211035

Tidskriftsartikel (refereegranskat)abstract
 We present measurements of the Type Ia supernova (SN) rate in galaxy clusters based on data from the Sloan Digital Sky SurveyII (SDSSII) Supernova Survey. The cluster SN Ia rate is determined from 9 SN events in a set of 71 C4 clusters at z <= 0.17 and 27 SN events in 492 maxBCG clusters at 0.1 <= z <= 0.3. We find values for the cluster SN Ia rate of (0.37+0.17+0.01 0.120.01) SNur h 2 and (0.55+0.13+0.02 0.110.01) SNur h 2 (SNux = 1012 L 1 xsun yr1) in C4 and maxBCG clusters, respectively, where the quoted errors are statistical and systematic, respectively. The SN rate for earlytype galaxies is found to be (0.31+0.18+0.01 0.120.01) SNur h 2 and (0.49+0.15+0.02 0.110.01) SNur h 2 in C4 and maxBCG clusters, respectively. The SN rate for the brightest cluster galaxies (BCG) is found to be (2.04+1.99+0.07 1.110.04) SNur h 2 and (0.36+0.84+0.01 0.300.01) SNur h 2 in C4 and maxBCG clusters, respectively. The ratio of the SN Ia rate in cluster earlytype galaxies to that of the SN Ia rate in field earlytype galaxies is 1.94+1.31+0.043 0.910.015 and 3.02+1.31+0.062 1.030.048, for C4 and maxBCG clusters, respectively. The SN rate in galaxy clusters as a function of redshift, which probes the late time SN Ia delay distribution, shows only weak dependence on redshift. Combining our current measurements with previous measurements, we fit the cluster SN Ia rate data to a linear function of redshift, and find rL = [(0.49+0.15 0.14)+(0.91+0.85 0.81) × z] SNuB h 2. A comparison of the radial distribution of SNe in cluster to field earlytype galaxies shows possible evidence for an enhancement of the SN rate in the cores of cluster earlytype galaxies. With an observation of at most three hostless, intracluster SNe Ia, we estimate the fraction of cluster SNe that are hostless to be (9.4+8.3 5.1)%.


58. 
 Dilday, Benjamin, et al.
(författare)

Measurements of the Rate of Type Ia Supernovae at Redshift lsim0.3 from the Sloan Digital Sky Survey II Supernova Survey
 2010

Ingår i: Astrophysical Journal.  0004637X . 15384357. ; 713, s. 10261036

Tidskriftsartikel (refereegranskat)abstract
 We present a measurement of the volumetric Type Ia supernova (SN Ia) rate based on data from the Sloan Digital Sky Survey II (SDSSII) Supernova Survey. The adopted sample of supernovae (SNe) includes 516 SNe Ia at redshift z <~ 0.3, of which 270(52%) are spectroscopically identified as SNe Ia. The remaining 246 SNe Ia were identified through their light curves; 113 of these objects have spectroscopic redshifts from spectra of their host galaxy, and 133 have photometric redshifts estimated from the SN light curves. Based on consideration of 87 spectroscopically confirmed nonIa SNe discovered by the SDSSII SN Survey, we estimate that 2.04+1.61 0.95% of the photometric SNe Ia may be misidentified. The sample of SNe Ia used in this measurement represents an order of magnitude increase in the statistics for SN Ia rate measurements in the redshift range covered by the SDSSII Supernova Survey. If we assume an SN Ia rate that is constant at low redshift (z < 0.15), then the SN observations can be used to infer a value of the SN rate of rV = (2.69+0.34+0.21 0.300.01)×105 SNe yr1 Mpc3 (H 0/(70 km s1 Mpc1))3 at a mean redshift of ~0.12, based on 79 SNe Ia of which 72 are spectroscopically confirmed. However, the large sample of SNe Ia included in this study allows us to place constraints on the redshift dependence of the SN Ia rate based on the SDSSII Supernova Survey data alone. Fitting a powerlaw model of the SN rate evolution, rV (z) = Ap × ((1 + z)/(1 + z 0))ν, over the redshift range 0.0 < z < 0.3 with z 0 = 0.21, results in Ap = (3.43+0.15 0.15) × 105 SNe yr1 Mpc3 (H 0/(70 km s1 Mpc1))3 and ν = 2.04+0.90 0.89.


59. 
 Egerstedt, Anna, et al.
(författare)

Profiling of the plasma proteome across different stages of human heart failure
 2019

Ingår i: Nature Communications.  : Nature Publishing Group.  20411723. ; 10:1

Tidskriftsartikel (refereegranskat)abstract
 Heart failure (HF) is a major public health problem characterized by inability of the heart to maintain sufficient output of blood. The systematic characterization of circulating proteins across different stages of HF may provide pathophysiological insights and identify therapeutic targets. Here we report application of aptamerbased proteomics to identify proteins associated with prospective HF incidence in a populationbased cohort, implicating modulation of immunological, complement, coagulation, natriuretic and matrix remodeling pathways up to two decades prior to overt disease onset. We observe further divergence of these proteins from the general population in advanced HF, and regression after heart transplantation. By leveraging coronary sinus samples and transcriptomic tools, we describe likely cardiac and specific cellular origins for several of the proteins, including NtproBNP, thrombospondin2, interleukin18 receptor, gelsolin, and activated C5. Our findings provide a broad perspective on both cardiac and systemic factors associated with HF development.


60. 
 Fenhammar, Johan, et al.
(författare)

Renal effects of treatment with a TLR4inhibitor in conscious septic sheep
 2014

Ingår i: Critical Care.  13648535 . 1466609X. ; 18:5, s. 488

Tidskriftsartikel (refereegranskat)abstract
 Introduction: Acute kidney injury (AKI) is a common and feared complication of sepsis. The pathogenesis of sepsisinduced AKI is largely unknown, and therapeutic interventions are mainly supportive. In the present study, we tested the hypothesis that pharmacological inhibition of Tolllike receptor 4 (TLR4) would improve renal function and reduce renal damage in experimental sepsis, even after AKI had already developed. Methods: Sheep were surgically instrumented and subjected to a 36hour intravenous infusion of live Escherichia coli. After 12 hours, they were randomized to treatment with a selective TLR4 inhibitor (TAK242) or vehicle. Results: The E. coli caused normotensive sepsis characterized by fever, increased cardiac index, hyperlactemia, oliguria, and decreased creatinine clearance. TAK242 significantly improved creatinine clearance and urine output. The increase in NacetylbetaDglucosaminidas, a marker of tubular damage, was attenuated. Furthermore, TAK242 reduced the renal neutrophil accumulation and glomerular endothelial swelling caused by sepsis. These effects were independent of changes in renal artery blood flow and renal microvascular perfusion in both cortex and medulla. TAK242 had no effect per se on the measured parameters. Conclusions: These results show that treatment with a TLR4 inhibitor is able to reverse a manifest impairment in renal function caused by sepsis. In addition, the results provide evidence that the mechanism underlying the effect of TAK242 on renal function does not involve improved macrocirculation or microcirculation, enhanced renal oxygen delivery, or attenuation of tubular necrosis. TLR4mediated inflammation resulting in glomerular endothelial swelling may be an important part of the pathogenesis underlying Gramnegative septic acute kidney injury.

