Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut.

In this paper, we consider two fundamental cut approximation problems on large graphs. We prove new lower bounds for both problems that are optimal up to logarithmic factors. The first problem is to approximate cuts in balanced directed graphs.

Learning-Augmented Sketching Offers Improved Performance for Privacy Preserving and Secure GWAS.

The introduction of trusted execution environments (TEEs), such as secure enclaves provided by the Intel SGX technology has enabled secure and privacy-preserving computation on the cloud. The stringent resource limitations, such as memory constraints, required by some TEEs necessitates the development of computational approaches with reduced memory usage, such as sketching. One example is the SkSES method for GWAS on a cohort of case and control samples from multiple institutions, which identifies the most significant SNPs in a privacy-preserving manner without disclosing sensitive genotype information to other institutions or the cloud service provider.

-Regression in the Arbitrary Partition Model of Communication.

We consider the randomized communication complexity of the distributed -regression problem in the coordinator model, for . In this problem, there is a coordinator and servers. The -th server receives and and the coordinator would like to find a -approximate solution to .

Improved Algorithms for White-Box Adversarial Streams.

We study streaming algorithms in the white-box adversarial stream model, where the internal state of the streaming algorithm is revealed to an adversary who adaptively generates the stream updates, but the algorithm obtains fresh randomness unknown to the adversary at each time step. We incorporate cryptographic assumptions to construct robust algorithms against such adversaries. We propose efficient algorithms for sparse recovery of vectors, low rank recovery of matrices and tensors, as well as low rank plus sparse recovery of matrices, i.

The complexity of biological disturbance agents, fuels heterogeneity, and fire in coniferous forests of the western United States.

Forest biological disturbance agents (BDAs) are insects, pathogens, and parasitic plants that affect tree decline, mortality, and forest ecosystems processes. BDAs are commonly thought to increase the likelihood and severity of fire by converting live standing trees to more flammable, dead and downed fuel. However, recent research indicates that BDAs do not necessarily increase, and can reduce, the likelihood or severity of fire.

A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World.

Principal component analysis (PCA) is a widely used dimensionality reduction technique in machine learning and multivariate statistics. To improve the interpretability of PCA, various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis (SPCA). In this paper, we present ThreSPCA, a provably accurate algorithm based on thresholding the Singular Value Decomposition for the SPCA problem, without imposing any restrictive assumptions on the input covariance matrix.

How to reduce dimension with PCA and random projections?

In our "big data" age, the size and complexity of data is steadily increasing. Methods for dimension reduction are ever more popular and useful. Two distinct types of dimension reduction are "data-oblivious" methods such as random projections and sketching, and "data-aware" methods such as principal component analysis (PCA).

Cross-biome synthesis of source versus sink limits to tree growth.

Uncertainties surrounding tree carbon allocation to growth are a major limitation to projections of forest carbon sequestration and response to climate change. The prevalence and extent to which carbon assimilation (source) or cambial activity (sink) mediate wood production are fundamentally important and remain elusive. We quantified source-sink relations across biomes by combining eddy-covariance gross primary production with extensive on-site and regional tree ring observations.

Thermodynamic Driving Forces for Substrate Atom Extraction by Adsorption of Strong Electron Acceptor Molecules.

A quantitative structural investigation is reported, aimed at resolving the issue of whether substrate adatoms are incorporated into the monolayers formed by strong molecular electron acceptors deposited onto metallic electrodes. A combination of normal-incidence X-ray standing waves, low-energy electron diffraction, scanning tunnelling microscopy, and X-ray photoelectron spectroscopy measurements demonstrate that the systems TCNQ and FTCNQ on Ag(100) lie at the boundary between these two possibilities and thus represent ideal model systems with which to study this effect. A room-temperature commensurate phase of adsorbed TCNQ is found not to involve Ag adatoms, but to adopt an inverted bowl configuration, long predicted but not previously identified experimentally.

Hutch++: Optimal Stochastic Trace Estimation.

We study the problem of estimating the trace of a matrix that can only be accessed through matrix-vector multiplication. We introduce a new randomized algorithm, Hutch++, which computes a (1 ± ) approximation to tr( ) for any positive semidefinite (PSD) using just (1) matrix-vector products. This improves on the ubiquitous , which requires (1 ) matrix-vector products.

Subspace exploration: Bounds on Projected Frequency Estimation.

Given an × dimensional dataset , a projection query specifies a subset ⊆ [] of columns which yields a new × || array. We study the space complexity of computing data analysis functions over such subspaces, including heavy hitters and norms, when the subspaces are revealed only after observing the data. We show that this important class of problems is typically hard: for many problems, we show 2 lower bounds.

An Ecological Perspective on Living with Fire in Ponderosa Pine Forests of Oregon and Washington: Resistance, Gone but not Forgotten.

Wildland fires (WLF) have become more frequent, larger, and severe with greater impacts to society and ecosystems and dramatic increases in firefighting costs. Forests throughout the range of ponderosa pine in Oregon and Washington are jeopardized by the interaction of anomalously dense forest structure, a warming and drying climate, and an expanding human population. These forests evolved with frequent interacting disturbances including low-severity surface fires, droughts, and biological disturbance agents (BDAs).

Alkali Doping Leads to Charge-Transfer Salt Formation in a Two-Dimensional Metal-Organic Framework.

Efficient charge transfer across metal-organic interfaces is a key physical process in modern organic electronics devices, and characterization of the energy level alignment at the interface is crucial to enable a rational device design. We show that the insertion of alkali atoms can significantly change the structure and electronic properties of a metal-organic interface. Coadsorption of tetracyanoquinodimethane (TCNQ) and potassium on a Ag(111) surface leads to the formation of a two-dimensional charge transfer salt, with properties quite different from those of the two-dimensional Ag adatom TCNQ metal-organic framework formed in the absence of K doping.

Sketching algorithms for genomic data analysis and querying in a secure enclave.

Genome-wide association studies (GWAS), especially on rare diseases, may necessitate exchange of sensitive genomic data between multiple institutions. Since genomic data sharing is often infeasible due to privacy concerns, cryptographic methods, such as secure multiparty computation (SMC) protocols, have been developed with the aim of offering privacy-preserving collaborative GWAS. Unfortunately, the computational overhead of these methods remain prohibitive for human-genome-scale data.

Near Optimal Linear Algebra in the Online and Sliding Window Models.

We initiate the study of numerical linear algebra in the sliding window model, where only the most recent updates in a stream form the underlying data set. Although many existing algorithms in the sliding window model use or borrow elements from the smooth histogram framework (Braverman and Ostrovsky, FOCS 2007), we show that many interesting linear-algebraic problems, including spectral and vector induced matrix norms, generalized regression, and lowrank approximation, are not amenable to this approach in the row-arrival model. To overcome this challenge, we first introduce a unified row-sampling based framework that gives algorithms for spectral approximation, low-rank approximation/projection-cost preservation, and -subspace embeddings in the sliding window model, which often use nearly optimal space and achieve nearly input sparsity runtime.

Water potential control of turgor-driven tracheid enlargement in Scots pine at its xeric distribution edge.

The extent to which water availability can be used to predict the enlargement and final dimensions of xylem conduits remains an open issue. We reconstructed the time course of tracheid enlargement in Pinus sylvestris trees in central Spain by repeated measurements of tracheid diameter on microcores sampled weekly during a 2 yr period. We analyzed the role of water availability in these dynamics empirically through time-series correlation analysis and mechanistically by building a model that simulates daily tracheid enlargement rate and duration based on Lockhart's equation and water potential as the sole input.

Coordination and trade-offs between leaf and stem hydraulic traits and stomatal regulation along a spectrum of isohydry to anisohydry.

The degree of plant iso/anisohydry, a widely used framework for classifying species-specific hydraulic strategies, integrates multiple components of the whole-plant hydraulic pathway. However, little is known about how it associates with coordination of functional and structural traits within and across different organs. We examined stem and leaf hydraulic capacitance and conductivity/conductance, stem xylem anatomical features, stomatal regulation of daily minimum leaf and stem water potential (Ψ), and the kinetics of stomatal responses to vapour pressure deficit (VPD) in six diverse woody species differing markedly in their degree of iso/anisohydry.

Co-occurring woody species have diverse hydraulic strategies and mortality rates during an extreme drought.

From 2011 to 2013, Texas experienced its worst drought in recorded history. This event provided a unique natural experiment to assess species-specific responses to extreme drought and mortality of four co-occurring woody species: Quercus fusiformis, Diospyros texana, Prosopis glandulosa, and Juniperus ashei. We examined hypothesized mechanisms that could promote these species' diverse mortality patterns using postdrought measurements on surviving trees coupled to retrospective process modelling.

Interactions of predominant insects and diseases with climate change in Douglas-fir forests of western Oregon and Washington, U.S.A.

Forest disturbance regimes are beginning to show evidence of climate-mediated changes, such as increasing severity of droughts and insect outbreaks. We review the major insects and pathogens affecting the disturbance regime for coastal Douglas-fir forests in western Oregon and Washington State, USA, and ask how future climate changes may influence their role in disturbance ecology. Although the physiological constraints of light, temperature, and moisture largely control tree growth, episodic and chronic disturbances interacting with biological factors have substantial impacts on the structure and functioning of forest ecosystems in this region.

Stomatal kinetics and photosynthetic gas exchange along a continuum of isohydric to anisohydric regulation of plant water status.

Species' differences in the stringency of stomatal control of plant water potential represent a continuum of isohydric to anisohydric behaviours. However, little is known about how quasi-steady-state stomatal regulation of water potential may relate to dynamic behaviour of stomata and photosynthetic gas exchange in species operating at different positions along this continuum. Here, we evaluated kinetics of light-induced stomatal opening, activation of photosynthesis and features of quasi-steady-state photosynthetic gas exchange in 10 woody species selected to represent different degrees of anisohydry.

Thermotolerance and heat stress responses of Douglas-fir and ponderosa pine seedling populations from contrasting climates.

Temperature and the frequency and intensity of heat waves are predicted to increase throughout the 21st century. Germinant seedlings are expected to be particularly vulnerable to heat stress because they are in the boundary layer close to the soil surface where intense heating occurs in open habitats. We quantified leaf thermotolerance and whole-plant physiological responses to heat stress in first-year germinant seedlings in two populations each of Pinus ponderosa P.

True Randomness from Big Data.

Generating random bits is a difficult task, which is important for physical systems simulation, cryptography, and many applications that rely on high-quality random bits. Our contribution is to show how to generate provably random bits from uncertain events whose outcomes are routinely recorded in the form of massive data sets. These include scientific data sets, such as in astronomics, genomics, as well as data produced by individuals, such as internet search logs, sensor networks, and social network feeds.

Mapping 'hydroscapes' along the iso- to anisohydric continuum of stomatal regulation of plant water status.

The concept of iso- vs. anisohydry has been used to describe the stringency of stomatal regulation of plant water potential (ψ). However, metrics that accurately and consistently quantify species' operating ranges along a continuum of iso- to anisohydry have been elusive.

Reliance on shallow soil water in a mixed-hardwood forest in central Pennsylvania.

We investigated depth of water uptake of trees on shale-derived soils in order to assess the importance of roots over a meter deep as a driver of water use in a central Pennsylvania catchment. This information is not only needed to improve basic understanding of water use in these forests but also to improve descriptions of root function at depth in hydrologic process models. The study took place at the Susquehanna Shale Hills Critical Zone Observatory in central Pennsylvania.

Non-structural carbohydrates in woody plants compared among laboratories.

Non-structural carbohydrates (NSC) in plant tissue are frequently quantified to make inferences about plant responses to environmental conditions. Laboratories publishing estimates of NSC of woody plants use many different methods to evaluate NSC. We asked whether NSC estimates in the recent literature could be quantitatively compared among studies.