More Like this

1. Singularity of sparse random matrices: simple proofs

   https://doi.org/10.1017/S0963548321000146  

   Ferber, Asaf; Kwan, Matthew; Sauermann, Lisa (January 2020, Combinatorics, Probability and Computing)

   null (Ed.)

   Consider a random n×n zero-one matrix with ‘sparsity’ p, sampled according to one of the following two models: either every entry is independently taken to be one with probability p (the ‘Bernoulli’ model) or each row is independently uniformly sampled from the set of all length-n zero-one vectors with exactly pn ones (the ‘combinatorial’ model). We give simple proofs of the (essentially best-possible) fact that in both models, if min (p, 1− p) ≥ (1+ε) log n/n for any constant ε >0, then our random matrix is nonsingular with probability 1− o(1). In the Bernoulli model, this fact was already well known, but in the combinatorial model this resolves a conjecture of Aigner-Horev and Person. 

   more » « less
2. Benchmarking embedded chain breaking in quantum annealing ^*

   https://doi.org/10.1088/2058-9565/ac26d2  

   Thinh V. Le, Manh V. (March 2022, Quantum Science and Technology)

   Abstract Quantum annealing solves combinatorial optimization problems by finding the energetic ground states of an embedded Hamiltonian. However, quantum annealing dynamics under the embedded Hamiltonian may violate the principles of adiabatic evolution and generate excitations that correspond to errors in the computed solution. Here we empirically benchmark the probability of chain breaks and identify sweet spots for solving a suite of embedded Hamiltonians. We further correlate the physical location of chain breaks in the quantum annealing hardware with the underlying embedding technique and use these localized rates in a tailored post-processing strategies. Our results demonstrate how to use characterization of the quantum annealing hardware to tune the embedded Hamiltonian and remove computational errors. 

   more » « less
3. New perspectives on the evolution of women's cooperation

   https://doi.org/10.1098/rstb.2021.0424  

   Fox, Stephanie A; Scelza, Brooke; Silk, Joan; Kramer, Karen L (January 2023, Philosophical Transactions of the Royal Society B: Biological Sciences)

   A holistic, evolutionary framework about human cooperation must incorporate information about women's cooperative behaviour. Yet, most empirical research on human cooperation has centered on men's behaviour or been derived from experimental studies conducted in western, industrialized populations. These bodies of data are unlikely to accurately represent human behavioural diversity. To address this gap and provide a more balanced view of human cooperation, this issue presents substantial new data and multi-disciplinary perspectives to document the complexity of women's cooperative behaviour. Research in this issue 1) challenges narratives about universal gender differences in cooperation, 2) reconsiders patrilocality and access to kin as constraints on women's cooperation, 3) reviews evidence for a connection between social support and women's health and 4) examines the phylogenetic roots of female cooperation. Here, we discuss the steps taken in this issue toward a more complete and evidence-based understanding of the role that cooperation plays in women's and girls' lives and in building human sociality. This article is part of the theme issue ‘Cooperation among women: evolutionary and cross-cultural perspectives’. 

   more » « less
4. Socio-hydrological modeling of the tradeoff between flood control and hydropower provided by the Columbia River Treaty

   https://doi.org/10.5194/hess-26-4893-2022  

   Shrestha, Ashish; Souza, Felipe Augusto; Park, Samuel; Cherry, Charlotte; Garcia, Margaret; Yu, David J.; Mendiondo, Eduardo Mario (January 2022, Hydrology and Earth System Sciences)

   Abstract. The Columbia River Treaty (CRT) signed between the United States and Canada in 1961 is known as one of the most successful transboundary watertreaties. Under continued cooperation, both countries equitably share collective responsibilities of reservoir operations and flood control andhydropower benefits from treaty dams. As the balance of benefits is the key factor of cooperation, future cooperation could be challenged byexternal social and environmental factors which were not originally anticipated or change in the social preferences of the two actors. To understandthe robustness of cooperation dynamics, we address two research questions. (i) How does social and environmental change influence cooperationdynamics? (ii) How do social preferences influence the probability of cooperation for both actors? We analyzed infrastructural, hydrological,economic, social, and environmental data to inform the development of a socio-hydrological system dynamics model. The model simulates the dynamicsof flood control and hydropower benefit sharing as a function of the probability to cooperate, which in turn is affected by the share ofbenefits. The model is used to evaluate scenarios that represent environmental and institutional change and changes in political characteristicsbased on social preferences. Our findings show that stronger institutional capacity ensures equitable sharing of benefits over the long term. Under the current CRT, the utility of cooperation is always higher for Canada than non-cooperation, which is in contrast to the United States. The probability tocooperate for each country is lowest when they are self-interested but fluctuates in other social preference scenarios. 

   more » « less
5. OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport

   https://doi.org/10.1145/3654963  

   Pirhadi, Alireza; Moslemi, Mohammad Hossein; Cloninger, Alexander; Milani, Mostafa; Salimi, Babak (May 2024, Proceedings of the ACM on Management of Data (SIGMOD))

   Ensuring Conditional Independence (CI) constraints is pivotal for the development of fair and trustworthy machine learning models. In this paper, we introduce OTClean, a framework that harnesses optimal transport theory for data repair under CI constraints. Optimal transport theory provides a rigorous framework for measuring the discrepancy between probability distributions, thereby ensuring control over data utility. We formulate the data repair problem concerning CIs as a Quadratically Constrained Linear Program (QCLP) and propose an alternating method for its solution. However, this approach faces scalability issues due to the computational cost associated with computing optimal transport distances, such as the Wasserstein distance. To overcome these scalability challenges, we reframe our problem as a regularized optimization problem, enabling us to develop an iterative algorithm inspired by Sinkhorn's matrix scaling algorithm, which efficiently addresses high-dimensional and large-scale data. Through extensive experiments, we demonstrate the efficacy and efficiency of our proposed methods, showcasing their practical utility in real-world data cleaning and preprocessing tasks. Furthermore, we provide comparisons with traditional approaches, highlighting the superiority of our techniques in terms of preserving data utility while ensuring adherence to the desired CI constraints. 

   more » « less