Search

Anonymity is an important principle online. However, malicious actors have long used misleading identities to conduct fraud, spread disinformation, and carry out other deceptive schemes. With the advent of increasingly capable AI, bad actors can amplify the potential scale and effectiveness of their operations, intensifying the challenge of balancing anonymity and trustworthiness online. In this paper, we analyze the value of a new tool to address this challenge: "personhood credentials" (PHCs), digital credentials that empower users to demonstrate that they are real people -- not AIs -- to online services, without disclosing any personal information. Such credentials can be issued by a range of trusted institutions -- governments or otherwise. A PHC system, according to our definition, could be local or global, and does not need to be biometrics-based. Two trends in AI contribute to the urgency of the challenge: AI's increasing indistinguishability from people online (i.e., lifelike content and avatars, agentic activity), and AI's increasing scalability (i.e., cost-effectiveness, accessibility). Drawing on a long history of research into anonymous credentials and "proof-of-personhood" systems, personhood credentials give people a way to signal their trustworthiness on online platforms, and offer service providers new tools for reducing misuse by bad actors. In contrast, existing countermeasures to automated deception -- such as CAPTCHAs -- are inadequate against sophisticated AI, while stringent identity verification solutions are insufficiently private for many use-cases. After surveying the benefits of personhood credentials, we also examine deployment risks and design challenges. We conclude with actionable next steps for policymakers, technologists, and standards bodies to consider in consultation with the public., Comment: 63 pages, 7 figures, 5 tables; minor additions to acknowledgments and wording changes for clarity; corrected typo

BlueMUSE is a blue-optimised, medium spectral resolution, panoramic integral field spectrograph under development for the Very Large Telescope (VLT). With an optimised transmission down to 350 nm, spectral resolution of R$\sim$3500 on average across the wavelength range, and a large FoV (1 arcmin$^2$), BlueMUSE will open up a new range of galactic and extragalactic science cases facilitated by its specific capabilities. The BlueMUSE consortium includes 9 institutes located in 7 countries and is led by the Centre de Recherche Astrophysique de Lyon (CRAL). The BlueMUSE project development is currently in Phase A, with an expected first light at the VLT in 2031. We introduce here the Top Level Requirements (TLRs) derived from the main science cases, and then present an overview of the BlueMUSE system and its subsystems fulfilling these TLRs. We specifically emphasize the tradeoffs that are made and the key distinctions compared to the MUSE instrument, upon which the system architecture is built., Comment: 20 pages, 10 figures, proceedings of the SPIE astronomical telescopes and instrumentation conference, Yokohama, 16-21 June

Centaurs, distinguished by their volatile-rich compositions, play a pivotal role in understanding the formation and evolution of the early solar system, as they represent remnants of the primordial material that populated the outer regions. Stellar occultations offer a means to investigate their physical properties, including shape, rotational state, or the potential presence of satellites and rings. This work aims to conduct a detailed study of the centaur (54598) Bienor through stellar occultations and rotational light curves from photometric data collected during recent years. We successfully predicted three stellar occultations by Bienor, which were observed from Japan, Eastern Europe, and the USA. In addition, we organized observational campaigns from Spain to obtain rotational light curves. At the same time, we develop software to generate synthetic light curves from three-dimensional shape models, enabling us to validate the outcomes through computer simulations. We resolve Bienor's projected ellipse for December 26, 2022, determine a prograde sense of rotation, and confirm an asymmetric rotational light curve. We also retrieve the axes of its triaxial ellipsoid shape as a = (127 $\pm$ 5) km, b = (55 $\pm$ 4) km, and c = (45 $\pm$ 4) km. Moreover, we refine the rotation period to 9.1736 $\pm$ 0.0002 hours and determine a geometric albedo of (6.5 $\pm$ 0.5) %, higher than previously determined by other methods. Finally, by comparing our findings with previous results and simulated rotational light curves, we analyze whether an irregular or contact-binary shape, the presence of an additional element such as a satellite, or significant albedo variations on Bienor's surface, may be present.

We are concerned with the behaviour of stochastic systems with inputs and outputs, and how this might relate to the pursuit of a goal. We model this using what we term transducers, which are a mathematical object that captures only the external behaviour of such a system and not its internal state. We present a framework for reasoning about the optimality of such a process, when it is coupled to a 'teleo-environment' consisting of another transducer that also embodies a success criterion. We find that (globally) optimal transducers have a property closely related to Bellman's theorem: a transducer that is optimal in one time step will again be optimal in the next time step, but with respect to a different environment (obtained from the original one by a modified version of Bayesian filtering). We also consider bounded rationality and its relationship to constrained optimality, which in our framework means optimal within some subset of all transducers. We describe a condition that is sufficient for such a subset to have this Bellman property. Additionally, we show that a policy is deterministic if and only if there exists a teleo-envionment for which it is uniquely optimal among the set of all transducers; this is at least conceptually related to classical representation theorems from decision theory. This need not hold for constrained subsets; we give an example of this related to the so-called absent-minded driver problem. All of the formalism is defined using coinduction, following the style proposed by Czajka [9]., Comment: 54 pages, 1 figure

As Low Earth Orbit (LEO) satellite mega constellations continue to be deployed for satellite internet and recent successful experiments in satellite-based quantum entanglement distribution emerge, a natural question arises: How should we coordinate transmissions and design scalable scheduling policies for a quantum satellite internet? In this work, we consider the problem of transmission scheduling in quantum satellite networks subject to resource constraints at the satellites and ground stations. We show that the most general problem of assigning satellites to ground station pairs for entanglement distribution is NP-hard. We then propose four heuristic algorithms and evaluate their performance for Starlink mega constellation under various amount of resources and placements of the ground stations. We find that the maximum number of receivers necessary per ground station grows very slowly with the total number of deployed ground stations. Our proposed algorithms, leveraging optimal weighted b-matching and the global greedy heuristic, outperform others in entanglement distribution rate, entanglement fidelity, and handover cost metrics. While we develop these scheduling algorithms, we have also designed a software system to simulate, visualize, and evaluate satellite mega-constellations for entanglement distribution.

We consider the problem of reconstructing an undirected graph $G$ on $n$ vertices given multiple random noisy subgraphs or "traces". Specifically, a trace is generated by sampling each vertex with probability $p_v$, then taking the resulting induced subgraph on the sampled vertices, and then adding noise in the form of either (a) deleting each edge in the subgraph with probability $1-p_e$, or (b) deleting each edge with probability $f_e$ and transforming a non-edge into an edge with probability $f_e$. We show that, under mild assumptions on $p_v$, $p_e$ and $f_e$, if $G$ is selected uniformly at random, then $O(p_e^{-1} p_v^{-2} \log n)$ or $O((f_e-1/2)^{-2} p_v^{-2} \log n)$ traces suffice to reconstruct $G$ with high probability. In contrast, if $G$ is arbitrary, then $\exp(\Omega(n))$ traces are necessary even when $p_v=1, p_e=1/2$., Comment: 6 pages, to appear in ISIT 2024

Recent clinical xenotransplantation and human decedent studies demonstrate that clinical hyperacute rejection of genetically engineered porcine organs can be reliably avoided but that antibody mediated rejection continues to limit graft survival. We previously identified porcine glycans and proteins which are immunogenic after cardiac xenotransplantation in nonhuman primates, but the clinical immune response to antigens present in glycan depleted triple knockout (TKO) donor pigs is poorly understood. In this study we use fluorescence barcoded HEK cells and HEK cell lines expressing porcine glycans (Gal and SDa) or proteins (CD9, CD46, CD59, PROCR and ANXA2) to screen antibody reactivity in human serum from 160 swine veterinarians, a serum source with potential occupational immune challenge from porcine tissues and pathogens. High levels of anti-Gal IgM were present in all samples and lower levels of anti-SDa IgM were present in 41% of samples. IgM binding to porcine proteins, primarily CD9 and CD46, previously identified as immunogenic in pig to non-human primate cardiac xenograft recipients, was detected in 28 of the 160 swine veterinarian samples. These results suggest that barcoded HEK cell lines expressing porcine protein antigens can be useful for screening human patient serum. A comprehensive analysis of sera from clinical xenotransplant recipients to define a panel of commonly immunogenic porcine antigens will likely be necessary to establish an array of porcine non-Gal antigens for effective monitoring of patient immune responses and allow earlier therapies to reverse antibody mediated rejection., Comment: 13 pages, 2 Tables, 3 Figures

This paper introduces v0.5 of the AI Safety Benchmark, which has been created by the MLCommons AI Safety Working Group. The AI Safety Benchmark has been designed to assess the safety risks of AI systems that use chat-tuned language models. We introduce a principled approach to specifying and constructing the benchmark, which for v0.5 covers only a single use case (an adult chatting to a general-purpose assistant in English), and a limited set of personas (i.e., typical users, malicious users, and vulnerable users). We created a new taxonomy of 13 hazard categories, of which 7 have tests in the v0.5 benchmark. We plan to release version 1.0 of the AI Safety Benchmark by the end of 2024. The v1.0 benchmark will provide meaningful insights into the safety of AI systems. However, the v0.5 benchmark should not be used to assess the safety of AI systems. We have sought to fully document the limitations, flaws, and challenges of v0.5. This release of v0.5 of the AI Safety Benchmark includes (1) a principled approach to specifying and constructing the benchmark, which comprises use cases, types of systems under test (SUTs), language and context, personas, tests, and test items; (2) a taxonomy of 13 hazard categories with definitions and subcategories; (3) tests for seven of the hazard categories, each comprising a unique set of test items, i.e., prompts. There are 43,090 test items in total, which we created with templates; (4) a grading system for AI systems against the benchmark; (5) an openly available platform, and downloadable tool, called ModelBench that can be used to evaluate the safety of AI systems on the benchmark; (6) an example evaluation report which benchmarks the performance of over a dozen openly available chat-tuned language models; (7) a test specification for the benchmark.

Dimension reduction techniques are among the most essential analytical tools in the analysis of high-dimensional data. Generalized principal component analysis (PCA) is an extension to standard PCA that has been widely used to identify low-dimensional features in high-dimensional discrete data, such as binary, multi-category and count data. For microbiome count data in particular, the multinomial PCA is a natural counterpart of the standard PCA. However, this technique fails to account for the excessive number of zero values, which is frequently observed in microbiome count data. To allow for sparsity, zero-inflated multivariate distributions can be used. We propose a zero-inflated probabilistic PCA model for latent factor analysis. The proposed model is a fully Bayesian factor analysis technique that is appropriate for microbiome count data analysis. In addition, we use the mean-field-type variational family to approximate the marginal likelihood and develop a classification variational approximation algorithm to fit the model. We demonstrate the efficiency of our procedure for predictions based on the latent factors and the model parameters through simulation experiments, showcasing its superiority over competing methods. This efficiency is further illustrated with two real microbiome count datasets. The method is implemented in R., Comment: 2 figures, 3 tables

South Africa is currently facing a critical situation in its power generation landscape, which is plagued by frequent power outages and the need to move from fossil fuels to renewable energy sources. This period emphasizes the importance of having firm-dispatchable power to balance out the intermittent nature of wind and solar energy sources. The paper proposes to repurpose old coal-fired power plants to generate firm-dispatchable energy in line with the principles of a Just Transition. Eskom's coal plants are approaching the end of their economic life, and their declining energy availability factor is becoming a challenge in meeting the country's energy needs. The study suggests that a comprehensive strategy that integrates wind, solar, and firm-dispatchable power can be cost-effective and reliable compared to the traditional coal-based approach or the nuclear alternative. The study emphasizes the necessity of a 25-year plan that would invest in flexible and modular dispatchable generation. It also highlights the strategic location of this generating capacity, including repurposing decommissioned coal plant sites. The proposed model integrates private investment, adheres to established best practices, and emphasizes adaptability to changing demand dynamics. The study provides a roadmap for enabling firm-dispatchable capacity for South Africa's energy transition, emphasizing economic prudence, environmental sustainability, and alignment with the principles of the Just Transition program.

The maximum coverage problem is to select $k$ sets from a collection of sets such that the cardinality of the union of the selected sets is maximized. We consider $(1-1/e-\epsilon)$-approximation algorithms for this NP-hard problem in three standard data stream models. 1. {\em Dynamic Model.} The stream consists of a sequence of sets being inserted and deleted. Our multi-pass algorithm uses $\epsilon^{-2} k \cdot \text{polylog}(n,m)$ space. The best previous result (Assadi and Khanna, SODA 2018) used $(n +\epsilon^{-4} k) \text{polylog}(n,m)$ space. While both algorithms use $O(\epsilon^{-1} \log n)$ passes, our analysis shows that when $\epsilon$ is a constant, it is possible to reduce the number of passes by a $1/\log \log n$ factor without incurring additional space. 2. {\em Random Order Model.} In this model, there are no deletions and the sets forming the instance are uniformly randomly permuted to form the input stream. We show that a single pass and $k \text{polylog}(n,m)$ space suffices for arbitrary small constant $\epsilon$. The best previous result, by Warneke et al.~(ESA 2023), used $k^2 \text{polylog}(n,m)$ space. 3. {\em Insert-Only Model.} Lastly, our results, along with numerous previous results, use a sub-sampling technique introduced by McGregor and Vu (ICDT 2017) to sparsify the input instance. We explain how this technique and others used in the paper can be implemented such that the amortized update time of our algorithm is polylogarithmic. This also implies an improvement of the state-of-the-art insert only algorithms in terms of the update time: $\text{polylog}(m,n)$ update time suffices whereas the best previous result by Jaud et al.~(SEA 2023) required update time that was linear in $k$.

Many countries have commenced a transition from fossil fuel-based electricity generation systems to sustainable systems based on wind and solar generation. It is often noted that the least cost approach would involve a massive scale-up in the building of variable renewables, supported by battery storage and gas peaking plants. The required backup should be firm-dispatchable generation rather than peaking power. The wind and solar generation aspects for this system are clearly defined and understood, however, the term firm-dispatchable power is not defined and the specific requirements are poorly understood. This study seeks to define firm-dispatchable power in this context and its requirement in the sustainable generation system. The study compares 100% renewable generation scenarios from South Africa, Texas, and the UK to demonstrate the requirement for this firm-dispatchable generation. The results indicate that firm-dispatchable generation must be available to replace the renewable generation completely. The required installed capacity for this firm-dispatchable generation does not vary with the distinct demand profiles of the different locations or their comparative renewable generation profiles. It also does not change significantly with the use of energy storage. The usage for this firm-dispatchable generation will vary due to the comparative economics of its use, but the requirement for its installation does not change.

We report on a three-day challenge during which five teams each programmed a nanodrone to be piloted through an obstacle course using bodily movement, in a 3D transposition of the '80s video-game Pacman. Using a bricolage approach to analyse interviews, field notes, video recordings, and inspection of each team's code revealed how participants were shaping and, in turn, became shaped in bodily ways by the drones' limitations. We observed how teams adapted to compete by: 1) shifting from aiming for seamless human-drone interaction, to seeing drones as fragile, wilful, and prone to crashes; 2) engaging with intimate, bodily interactions to more precisely understand, probe, and delimit each drone's capabilities; 3) adopting different strategies, emphasising either training the drone or training the pilot. We contribute with an empirical, somaesthetically focused account of current challenges in HDI and call for programming environments that support action-feedback loops for design and programming purposes.

In recent years, the CHIME (Canadian Hydrogen Intensity Mapping Experiment) interferometer has revealed a large number of Fast Radio Bursts (FRBs), including a sizable population that demonstrates repeating behavior. This transit facility, employing a real-time FRB search pipeline, continually scans the sky with declinations between $-10^{\circ}$ and $90^{\circ}$ for events with fluences $\gtrapprox 0.4$ Jy ms. We simulate a population of repeating FRBs by performing Monte Carlo simulations of underlying source populations processed through a mock CHIME/FRB observing pipeline. Assuming intrinsic repeater rates follow a Poisson distribution, we test assumptions about the burst populations of the repeater sample, and construct models of the FRB sample assuming various cosmological distributions. We infer the completeness of CHIME/FRB observations as a function of observing cadence and redshifts out to 0.5. We find that, if all simulated bursts have a fixed Poisson probability of repetition over their integrated time of observation, repeating burst detections across comoving volume should continue to grow near linearly on the order of decades. We predict that around 170 of the current CHIME/FRB one-off sources will ultimately repeat. We also make projections for FRB repeaters by future facilities and demonstrate that the number of repeaters they find could saturate on a $\sim$3 yr timescale., Comment: 10 pages, 7 figures

During software development, balancing security and non security issues is challenging. We focus on security awareness and approaches taken by non-security experts using software development issue trackers when considering security. We first analyse interfaces from prominent issue trackers to see how they support security communication and how they integrate security scoring. Then, we investigate through a small scale user study what criteria developers take when prioritising issues, in particular observing their attitudes to security. We find projects make reference to CVSS summaries (Common Vulnerability Scoring System), often alongside CVE reports (Common Vulnerabilities and Exposures), but issue trackers do not often have interfaces designed for this. Users in our study were not comfortable with CVSS analysis, though were able to reason in a manner compatible with CVSS. Detailed explanations and advice were seen as helpful in making security decisions. This suggests that adding improvements to communication through CVSS-like questioning in issue tracking software can elicit better security interactions., Comment: 9th Workshop on Security Information Workers WSIW 2023 - Co-located Workshop at SOUPS 2023, Anaheim, United States

The Graphical House Allocation problem asks: how can $n$ houses (each with a fixed non-negative value) be assigned to the vertices of an undirected graph $G$, so as to minimize the "aggregate local envy", i.e., the sum of absolute differences along the edges of $G$? This problem generalizes the classical Minimum Linear Arrangement problem, as well as the well-known House Allocation Problem from Economics, the latter of which has notable practical applications in organ exchanges. Recent work has studied the computational aspects of Graphical House Allocation and observed that the problem is NP-hard and inapproximable even on particularly simple classes of graphs, such as vertex disjoint unions of paths. However, the dependence of any approximations on the structural properties of the underlying graph had not been studied. In this work, we give a complete characterization of the approximability of the Graphical House Allocation problem. We present algorithms to approximate the optimal envy on general graphs, trees, planar graphs, bounded-degree graphs, bounded-degree planar graphs, and bounded-degree trees. For each of these graph classes, we then prove matching lower bounds, showing that in each case, no significant improvement can be attained unless P = NP. We also present general approximation ratios as a function of structural parameters of the underlying graph, such as treewidth; these match the aforementioned tight upper bounds in general, and are significantly better approximations for many natural subclasses of graphs. Finally, we present constant factor approximation schemes for the special classes of complete binary trees and random graphs.

The Gemini High-resolution Optical SpecTrograph (GHOST) is the newest high resolution spectrograph to be developed for a large aperture telescope, recently deployed and commissioned at the Gemini-South telescope. In this paper, we present the first science results from the GHOST spectrograph taking during its commissioning runs. We have observed the bright metal-poor benchmark star HD 122563, along with two stars in the ultra faint dwarf galaxy, Ret II, one of which was previously identified as a candidate member, but did not have a previous detailed chemical abundance analysis. This star (GDR3 0928) is found to be a bona fide member of Ret II, and from a spectral synthesis analysis, it is also revealed to be a CEMP-r star, with significant enhancements in the several light elements (C, N, O, Na, Mg, and Si), in addition to featuring an r-process enhancement like many other Ret II stars. The light-element enhancements in this star resemble the abundance patterns seen in the CEMP-no stars of other ultra faint dwarf galaxies, and are thought to have been produced by an independent source from the r-process. These unusual abundance patterns are thought to be produced by faint supernovae, which may be produced by some of the earliest generations of stars., Comment: 23 pages, 9 figures, 7 tables, submitted to the AAS Journals

Quaoar is a classical Trans-Neptunian Object (TNO) with an area equivalent diameter of 1,100 km and an orbital semi-major axis of 43.3 astronomical units. Based on stellar occultations observed between 2018 and 2021, an inhomogeneous ring (Q1R, Quaoar's first ring) was detected around this body. Aims. A new stellar occultation by Quaoar was observed on August 9th, 2022 aiming to improve Quaoar's shape models and the physical parameters of Q1R while searching for additional material around the body. Methods. The occultation provided nine effective chords across Quaoar, pinning down its size, shape, and astrometric position. Large facilities, such as Gemini North and the Canada-France-Hawaii Telescope (CFHT), were used to obtain high acquisition rates and signal-to-noise ratios. The light curves were also used to characterize the Q1R ring (radial profiles and orbital elements). Results. Quaoar's elliptical fit to the occultation chords yields the limb with an apparent semi-major axis of $579.5\pm4.0$ km, apparent oblateness of $0.12\pm0.01$, and area-equivalent radius of $543\pm2$ km. Quaoar's limb orientation is consistent with Q1R and Weywot orbiting in Quaoar's equatorial plane. The orbital radius of Q1R is refined to a value of $4,057\pm6$ km. The radial opacity profile of the more opaque ring profile follows a Lorentzian shape that extends over 60 km, with a full width at half maximum (FWHM) of $\sim5$ km and a peak normal optical depth of 0.4. Besides the secondary events related to the already reported rings, new secondary events detected during the August 2022 occultation in three different data sets are consistent with another ring around Quaoar with a radius of $2,520\pm20$ km, assuming the ring is circular and co-planar with Q1R. This new ring has a typical width of 10 km and a normal optical depth of $\sim$0.004. Like Q1R, it also lies outside Quaoar's classical Roche limit., Comment: Accepted for publication in Astronomy & Astrophysics (17-April-2023). 18 pages, 12 figures

Twenty-six years ago a small committee report, building on earlier studies, expounded a compelling and poetic vision for the future of astronomy, calling for an infrared-optimized space telescope with an aperture of at least $4m$. With the support of their governments in the US, Europe, and Canada, 20,000 people realized that vision as the $6.5m$ James Webb Space Telescope. A generation of astronomers will celebrate their accomplishments for the life of the mission, potentially as long as 20 years, and beyond. This report and the scientific discoveries that follow are extended thank-you notes to the 20,000 team members. The telescope is working perfectly, with much better image quality than expected. In this and accompanying papers, we give a brief history, describe the observatory, outline its objectives and current observing program, and discuss the inventions and people who made it possible. We cite detailed reports on the design and the measured performance on orbit., Comment: Accepted by PASP for the special issue on The James Webb Space Telescope Overview, 29 pages, 4 figures

Artificial intelligence (AI) governance is the body of standards and practices used to ensure that AI systems are deployed responsibly. Current AI governance approaches consist mainly of manual review and documentation processes. While such reviews are necessary for many systems, they are not sufficient to systematically address all potential harms, as they do not operationalize governance requirements for system engineering, behavior, and outcomes in a way that facilitates rigorous and reproducible evaluation. Modern AI systems are data-centric: they act on data, produce data, and are built through data engineering. The assurance of governance requirements must also be carried out in terms of data. This work explores the systematization of governance requirements via datasets and algorithmic evaluations. When applied throughout the product lifecycle, data-centric governance decreases time to deployment, increases solution quality, decreases deployment risks, and places the system in a continuous state of assured compliance with governance requirements., Comment: 26 pages, 13 figures

Two years after publicly launching the AI Incident Database (AIID) as a collection of harms or near harms produced by AI in the world, a backlog of "issues" that do not meet its incident ingestion criteria have accumulated in its review queue. Despite not passing the database's current criteria for incidents, these issues advance human understanding of where AI presents the potential for harm. Similar to databases in aviation and computer security, the AIID proposes to adopt a two-tiered system for indexing AI incidents (i.e., a harm or near harm event) and issues (i.e., a risk of a harm event). Further, as some machine learning-based systems will sometimes produce a large number of incidents, the notion of an incident "variant" is introduced. These proposed changes mark the transition of the AIID to a new version in response to lessons learned from editing 2,000+ incident reports and additional reports that fall under the new category of "issue.", Comment: To be published in Human-Centered AI Workshop at NeurIPS 2022

Emerging artificial intelligence (AI) applications often balance the preferences and impacts among diverse and contentious stakeholder groups. Accommodating these stakeholder groups during system design, development, and deployment requires tools for the elicitation of disparate system interests and collaboration interfaces supporting negotiation balancing those interests. This paper introduces interactive visual "participation interfaces" for Markov Decision Processes (MDPs) and collaborative ranking problems as examples restoring a human-centered locus of control., Comment: 4 pages, 2 figures. To be published in Human-Centered AI Workshop at NeurIPS 2022

While certain industrial sectors (e.g., aviation) have a long history of mandatory incident reporting complete with analytical findings, the practice of artificial intelligence (AI) safety benefits from no such mandate and thus analyses must be performed on publicly known ``open source'' AI incidents. Although the exact causes of AI incidents are seldom known by outsiders, this work demonstrates how to apply expert knowledge on the population of incidents in the AI Incident Database (AIID) to infer the potential and likely technical causative factors that contribute to reported failures and harms. We present early work on a taxonomic system that covers a cascade of interrelated incident factors, from system goals (nearly always known) to methods / technologies (knowable in many cases) and technical failure causes (subject to expert analysis) of the implicated systems. We pair this ontology structure with a comprehensive classification workflow that leverages expert knowledge and community feedback, resulting in taxonomic annotations grounded by incident data and human expertise.

Learning causal structure is useful in many areas of artificial intelligence, including planning, robotics, and explanation. Constraint-based structure learning algorithms such as PC use conditional independence (CI) tests to infer causal structure. Traditionally, constraint-based algorithms perform CI tests with a preference for smaller-sized conditioning sets, partially because the statistical power of conventional CI tests declines rapidly as the size of the conditioning set increases. However, many modern conditional independence tests are model-based, and these tests use well-regularized models that maintain statistical power even with very large conditioning sets. This suggests an intriguing new strategy for constraint-based algorithms which may result in a reduction of the total number of CI tests performed: Test variable pairs with large conditioning sets first, as a pre-processing step that finds some conditional independencies quickly, before moving on to the more conventional strategy that favors small conditioning sets. We propose such a pre-processing step for the PC algorithm which relies on performing CI tests on a few randomly selected large conditioning sets. We perform an empirical analysis on directed acyclic graphs (DAGs) that correspond to real-world systems and both empirical and theoretical analyses for Erd\H{o}s-Renyi DAGs. Our results show that Pre-Processing Plus PC (P3PC) performs far fewer CI tests than the original PC algorithm, between 0.5% to 36%, and often less than 10%, of the CI tests that the PC algorithm alone performs. The efficiency gains are particularly significant for the DAGs corresponding to real-world systems., Comment: Accepted at NeurIPS 2022 Workshop on Causality for Real-world Impact; 8 pages of main text including references

We study the problem of estimating the number of edges in an $n$-vertex graph, accessed via the Bipartite Independent Set query model introduced by Beame et al. (ITCS '18). In this model, each query returns a Boolean, indicating the existence of at least one edge between two specified sets of nodes. We present a non-adaptive algorithm that returns a $(1\pm \epsilon)$ relative error approximation to the number of edges, with query complexity $\tilde O(\epsilon^{-5}\log^{5} n )$, where $\tilde O(\cdot)$ hides $\textrm{poly}(\log \log n)$ dependencies. This is the first non-adaptive algorithm in this setting achieving $\textrm{poly}(1/\epsilon,\log n)$ query complexity. Prior work requires $\Omega(\log^2 n)$ rounds of adaptivity. We avoid this by taking a fundamentally different approach, inspired by work on single-pass streaming algorithms. Moreover, for constant $\epsilon$, our query complexity significantly improves on the best known adaptive algorithm due to Bhattacharya et al. (STACS '22), which requires $O(\epsilon^{-2} \log^{11} n)$ queries. Building on our edge estimation result, we give the first non-adaptive algorithm for outputting a nearly uniformly sampled edge with query complexity $\tilde O(\epsilon^{-6} \log^{6} n)$, improving on the works of Dell et al. (SODA '20) and Bhattacharya et al. (STACS '22), which require $\Omega(\log^3 n)$ rounds of adaptivity. Finally, as a consequence of our edge sampling algorithm, we obtain a $\tilde O(n\log^ 8 n)$ query algorithm for connectivity, using two rounds of adaptivity. This improves on a three-round algorithm of Assadi et al. (ESA '21) and is tight; there is no non-adaptive algorithm for connectivity making $o(n^2)$ queries., Comment: European Symposium on Algorithms (ESA) 2022

We introduce a new class of Hamiltonian Monte Carlo (HMC) algorithm called Conservative Hamiltonian Monte Carlo (CHMC), where energy-preserving integrators, derived from the Discrete Multiplier Method, are used instead of symplectic integrators. Due to the volume being no longer preserved under such a proposal map, a correction involving the determinant of the Jacobian of the proposal map is introduced within the acceptance probability of HMC. For a $p$-th order accurate energy-preserving integrator using a time step size $\tau$, we show that CHMC satisfies stationarity without detailed balance. Moreover, we show that CHMC satisfies approximate stationarity with an error of $\mathcal{O}(\tau^{(m+1)p})$ if the determinant of the Jacobian is truncated to its first $m+1$ terms of its Taylor polynomial in $\tau^p$. We also establish a lower bound on the acceptance probability of CHMC which depends only on the desired tolerance $\delta$ for the energy error and approximate determinant. In particular, a cost-effective and gradient-free version of CHMC is obtained by approximating the determinant of the Jacobian as unity, leading to an $\mathcal{O}(\tau^p)$ error to the stationary distribution and a lower bound on the acceptance probability depending only on $\delta$. Furthermore, numerical experiments show increased performance in acceptance probability and convergence to the stationary distribution for the Gradient-free CHMC over HMC in high dimensional problems., Comment: 24 pages, 18 figures

Recent work of Acharya et al. (NeurIPS 2019) showed how to estimate the entropy of a distribution $\mathcal D$ over an alphabet of size $k$ up to $\pm\epsilon$ additive error by streaming over $(k/\epsilon^3) \cdot \text{polylog}(1/\epsilon)$ i.i.d. samples and using only $O(1)$ words of memory. In this work, we give a new constant memory scheme that reduces the sample complexity to $(k/\epsilon^2)\cdot \text{polylog}(1/\epsilon)$. We conjecture that this is optimal up to $\text{polylog}(1/\epsilon)$ factors.

Given an $n$-point metric space $(\mathcal{X},d)$ where each point belongs to one of $m=O(1)$ different categories or groups and a set of integers $k_1, \ldots, k_m$, the fair Max-Min diversification problem is to select $k_i$ points belonging to category $i\in [m]$, such that the minimum pairwise distance between selected points is maximized. The problem was introduced by Moumoulidou et al. [ICDT 2021] and is motivated by the need to down-sample large data sets in various applications so that the derived sample achieves a balance over diversity, i.e., the minimum distance between a pair of selected points, and fairness, i.e., ensuring enough points of each category are included. We prove the following results: 1. We first consider general metric spaces. We present a randomized polynomial time algorithm that returns a factor $2$-approximation to the diversity but only satisfies the fairness constraints in expectation. Building upon this result, we present a $6$-approximation that is guaranteed to satisfy the fairness constraints up to a factor $1-\epsilon$ for any constant $\epsilon$. We also present a linear time algorithm returning an $m+1$ approximation with exact fairness. The best previous result was a $3m-1$ approximation. 2. We then focus on Euclidean metrics. We first show that the problem can be solved exactly in one dimension. For constant dimensions, categories and any constant $\epsilon>0$, we present a $1+\epsilon$ approximation algorithm that runs in $O(nk) + 2^{O(k)}$ time where $k=k_1+\ldots+k_m$. We can improve the running time to $O(nk)+ poly(k)$ at the expense of only picking $(1-\epsilon) k_i$ points from category $i\in [m]$. Finally, we present algorithms suitable to processing massive data sets including single-pass data stream algorithms and composable coresets for the distributed processing., Comment: To appear in ICDT 2022

A central concept in active inference is that the internal states of a physical system parametrise probability measures over states of the external world. These can be seen as an agent's beliefs, expressed as a Bayesian prior or posterior. Here we begin the development of a general theory that would tell us when it is appropriate to interpret states as representing beliefs in this way. We focus on the case in which a system can be interpreted as performing either Bayesian filtering or Bayesian inference. We provide formal definitions of what it means for such an interpretation to exist, using techniques from category theory., Comment: 11 pages + 26 pages appendix, to be published in the proceedings of the 2nd International Workshop on Active Inference 2021

This paper presents the design of a cooperative multi-player betting game, Trust-ya, as a model of some elements of status processes in human groups. The game is designed to elicit status-driven leader-follower behaviours as a means to observe and influence social hierarchy. It involves a Bach/Stravinsky game of deference in a group, in which people on each turn can either invest with another player or hope someone invests with them. Players who receive investment capital are able to gamble for payoffs from a central pool which then can be shared back with those who invested (but a portion of it may be kept, including all of it). The bigger gambles (people with more investors) get bigger payoffs. Thus, there is a natural tendency for players to coalesce as investors around a 'leader' who gambles, but who also shares sufficiently from their winnings to keep the investors 'hanging on'. The 'leader' will want to keep as much as possible for themselves, however. The game is played anonymously, but a set of 'status symbols' can be purchased which have no value in the game itself, but can serve as a 'cheap talk' communication device with other players. This paper introduces the game, relates it to status theory in social psychology, and shows some simple simulated and human experiments that demonstrate how the game can be used to study status processes and dynamics in human groups., Comment: 5 pages, 3 figures

We consider directed graph algorithms in a streaming setting, focusing on problems concerning orderings of the vertices. This includes such fundamental problems as topological sorting and acyclicity testing. We also study the related problems of finding a minimum feedback arc set (edges whose removal yields an acyclic graph), and finding a sink vertex. We are interested in both adversarially-ordered and randomly-ordered streams. For arbitrary input graphs with edges ordered adversarially, we show that most of these problems have high space complexity, precluding sublinear-space solutions. Some lower bounds also apply when the stream is randomly ordered: e.g., in our most technical result we show that testing acyclicity in the $p$-pass random-order model requires roughly $n^{1+1/p}$ space. For other problems, random ordering can make a dramatic difference: e.g., it is possible to find a sink in an acyclic tournament in the one-pass random-order model using polylog$(n)$ space whereas under adversarial ordering roughly $n^{1/p}$ space is necessary and sufficient given $\Theta(p)$ passes. We also design sublinear algorithms for the feedback arc set problem in tournament graphs; for random graphs; and for randomly ordered streams. In some cases, we give lower bounds establishing that our algorithms are essentially space-optimal. Together, our results complement the much maturer body of work on algorithms for undirected graph streams., Comment: Appeared in SODA 2020

Additive manufacturing (AM) of titanium (Ti) and Ti-6Al-4V lattices has been proposed for bone implants and augmentation devices. Ti and Ti-6Al-4V have favourable biocompatibility, corrosion resistance and fatigue strength for bone applications; yet, the optimal parameters for Ti-6Al-4V lattice designs corresponding to the natural micro- and meso-scale architecture of human trabecular and cortical bone are not well understood. A comprehensive review was completed to compare the natural lattice architecture properties in human bone to Ti and Ti-6Al-4V lattice structures for bone replacement and repair. Ti and Ti-6Al-4V lattice porosity has varied from 15% to 97% with most studies reporting a porosity between 50-70%. Cortical bone is roughly 5-15% porous and lattices with 50-70% porosity are able to achieve comparable stiffness, compressive strength, and yield strength. Trabecular bone has a reported porosity range from 70-90%, with trabecular thickness varying from 120-200 {\mu}m. Existing powder bed fusion technologies have produced strut and wall thicknesses ranging from 200-1669 {\mu}m. This suggests limited overlap between current AM of Ti and Ti-6Al-4V lattice structures and trabecular bone architecture, indicating that replicating natural trabecular bone parameters with latticing is prohibitively challenging. This review contributes to the body of knowledge by identifying the correspondence of Ti and Ti-6Al-4V lattices to the natural parameters of bone microarchitectures, and provides further guidance on the design and AM recommendations towards addressing recognized performance gaps with powder bed fusion technologies.

In this paper we present an analysis of the spin behavior of electrons propagating through a laser field. We present an experimentally realizable scenario in which spin-dependent effects of the interaction between the laser and the electrons are dominant. The laser interaction strength and incident electron velocity are in the nonrelativistic domain. This analysis may thus lead to novel methods of creating and characterizing spin-polarized nonrelativistic femtosecond electron pulses.

We study the effects of physical distancing measures for the spread of COVID-19 in regional areas within British Columbia, using the reported cases of the five provincial Health Authorities. Building on the Bayesian epidemiological model of Anderson et al. (2020), we propose a hierarchical regional Bayesian model with time-varying regional parameters between March to December of 2020. In the absence of COVID-19 variants and vaccinations during this period, we examine the regionalized basic reproduction number, modelled prevalence, relative reduction in contact due to physical distancing, and proportion of anticipated cases that have been tested and reported. We observe significant differences between the regional and provincial-wide models and demonstrate the hierarchical regional model can better estimate regional prevalence, especially in rural regions. These results indicate that it can be useful to apply similar regional models to other parts of Canada or other countries., Comment: 35 pages, 16 figures

We present algorithms for the Max-Cover and Max-Unique-Cover problems in the data stream model. The input to both problems are $m$ subsets of a universe of size $n$ and a value $k\in [m]$. In Max-Cover, the problem is to find a collection of at most $k$ sets such that the number of elements covered by at least one set is maximized. In Max-Unique-Cover, the problem is to find a collection of at most $k$ sets such that the number of elements covered by exactly one set is maximized. Our goal is to design single-pass algorithms that use space that is sublinear in the input size. Our main algorithmic results are: If the sets have size at most $d$, there exist single-pass algorithms using $\tilde{O}(d^{d+1} k^d)$ space that solve both problems exactly. This is optimal up to polylogarithmic factors for constant $d$. If each element appears in at most $r$ sets, we present single pass algorithms using $\tilde{O}(k^2 r/\epsilon^3)$ space that return a $1+\epsilon$ approximation in the case of Max-Cover. We also present a single-pass algorithm using slightly more memory, i.e., $\tilde{O}(k^3 r/\epsilon^{4})$ space, that $1+\epsilon$ approximates Max-Unique-Cover. In contrast to the above results, when $d$ and $r$ are arbitrary, any constant pass $1+\epsilon$ approximation algorithm for either problem requires $\Omega(\epsilon^{-2}m)$ space but a single pass $O(\epsilon^{-2}mk)$ space algorithm exists. In fact any constant-pass algorithm with an approximation better than $e/(e-1)$ and $e^{1-1/k}$ for Max-Cover and Max-Unique-Cover respectively requires $\Omega(m/k^2)$ space when $d$ and $r$ are unrestricted. En route, we also obtain an algorithm for a parameterized version of the streaming Set-Cover problem., Comment: Conference version to appear at ICDT 2021

Synthetic media detection technologies label media as either synthetic or non-synthetic and are increasingly used by journalists, web platforms, and the general public to identify misinformation and other forms of problematic content. As both well-resourced organizations and the non-technical general public generate more sophisticated synthetic media, the capacity for purveyors of problematic content to adapt induces a \newterm{detection dilemma}: as detection practices become more accessible, they become more easily circumvented. This paper describes how a multistakeholder cohort from academia, technology platforms, media entities, and civil society organizations active in synthetic media detection and its socio-technical implications evaluates the detection dilemma. Specifically, we offer an assessment of detection contexts and adversary capacities sourced from the broader, global AI and media integrity community concerned with mitigating the spread of harmful synthetic media. A collection of personas illustrates the intersection between unsophisticated and highly-resourced sponsors of misinformation in the context of their technical capacities. This work concludes that there is no "best" approach to navigating the detector dilemma, but derives a set of implications from multistakeholder input to better inform detection process decisions and policies, in practice., Comment: 11 pages, 8 Figures

Although there is a rapidly growing literature on dynamic connectivity methods, the primary focus has been on separate network estimation for each individual, which fails to leverage common patterns of information. We propose novel graph-theoretic approaches for estimating a population of dynamic networks that are able to borrow information across multiple heterogeneous samples in an unsupervised manner and guided by covariate information. Specifically, we develop a Bayesian product mixture model that imposes independent mixture priors at each time scan and uses covariates to model the mixture weights, which results in time-varying clusters of samples designed to pool information. The computation is carried out using an efficient Expectation-Maximization algorithm. Extensive simulation studies illustrate sharp gains in recovering the true dynamic network over existing dynamic connectivity methods. An analysis of fMRI block task data with behavioral interventions reveal sub-groups of individuals having similar dynamic connectivity, and identifies intervention-related dynamic network changes that are concentrated in biologically interpretable brain regions. In contrast, existing dynamic connectivity approaches are able to detect minimal or no changes in connectivity over time, which seems biologically unrealistic and highlights the challenges resulting from the inability to systematically borrow information across samples., Comment: 52 pages, 4 figures

We study the problem of learning the causal relationships between a set of observed variables in the presence of latents, while minimizing the cost of interventions on the observed variables. We assume access to an undirected graph $G$ on the observed variables whose edges represent either all direct causal relationships or, less restrictively, a superset of causal relationships (identified, e.g., via conditional independence tests or a domain expert). Our goal is to recover the directions of all causal or ancestral relations in $G$, via a minimum cost set of interventions. It is known that constructing an exact minimum cost intervention set for an arbitrary graph $G$ is NP-hard. We further argue that, conditioned on the hardness of approximate graph coloring, no polynomial time algorithm can achieve an approximation factor better than $\Theta(\log n)$, where $n$ is the number of observed variables in $G$. To overcome this limitation, we introduce a bi-criteria approximation goal that lets us recover the directions of all but $\epsilon n^2$ edges in $G$, for some specified error parameter $\epsilon > 0$. Under this relaxed goal, we give polynomial time algorithms that achieve intervention cost within a small constant factor of the optimal. Our algorithms combine work on efficient intervention design and the design of low-cost separating set systems, with ideas from the literature on graph property testing., Comment: To appear, International Conference on Algorithmic Learning Theory(ALT) 2021

Mature industrial sectors (e.g., aviation) collect their real world failures in incident databases to inform safety improvements. Intelligent systems currently cause real world harms without a collective memory of their failings. As a result, companies repeatedly make the same mistakes in the design, development, and deployment of intelligent systems. A collection of intelligent system failures experienced in the real world (i.e., incidents) is needed to ensure intelligent systems benefit people and society. The AI Incident Database is an incident collection initiated by an industrial/non-profit cooperative to enable AI incident avoidance and mitigation. The database supports a variety of research and development use cases with faceted and full text search on more than 1,000 incident reports archived to date., Comment: 6 pages, 7 figures, Pre-print accepted to Innovative Applications of Artificial Intelligence (IAAI-21)

Diversity is an important principle in data selection and summarization, facility location, and recommendation systems. Our work focuses on maximizing diversity in data selection, while offering fairness guarantees. In particular, we offer the first study that augments the Max-Min diversification objective with fairness constraints. More specifically, given a universe $U$ of $n$ elements that can be partitioned into $m$ disjoint groups, we aim to retrieve a $k$-sized subset that maximizes the pairwise minimum distance within the set (diversity) and contains a pre-specified $k_i$ number of elements from each group $i$ (fairness). We show that this problem is NP-complete even in metric spaces, and we propose three novel algorithms, linear in $n$, that provide strong theoretical approximation guarantees for different values of $m$ and $k$. Finally, we extend our algorithms and analysis to the case where groups can be overlapping.

The physical mechanism driving mass ejection during a nova eruption is still poorly understood. Possibilities include ejection in a single ballistic event, a common envelope interaction, a continuous wind, or some combination of these processes. Here we present a study of 12 Galactic novae, for which we have pre-maximum high-resolution spectroscopy. All 12 novae show the same spectral evolution. Before optical peak, they show a slow P Cygni component. After peak a fast component quickly arises, while the slow absorption remains superimposed on top of it, implying the presence of at least two physically distinct flows. For novae with high-cadence monitoring, a third, intermediate-velocity component is also observed. These observations are consistent with a scenario where the slow component is associated with the initial ejection of the accreted material and the fast component with a radiation-driven wind from the white dwarf. When these flows interact, the slow flow is swept up by the fast flow, producing the intermediate component. These colliding flows may produce the gamma-ray emission observed in some novae. Our spectra also show that the transient heavy element absorption lines seen in some novae have the same velocity structure and evolution as the other lines in the spectrum, implying an association with the nova ejecta rather than a pre-existing circumbinary reservoir of gas or material ablated from the secondary. While this basic scenario appears to qualitatively reproduce multi-wavelength observations of classical novae, substantial theoretical and observational work is still needed to untangle the rich diversity of nova properties., Comment: 39 pages, 35 figures, submitted to ApJ

Geospatial analysis is crucial for addressing many of the world's most pressing challenges. Given this, there is immense value in improving and expanding the visualization techniques used to communicate geospatial data. In this work, we explore this important intersection -- between geospatial analytics and visualization -- by examining a set of recent IEEE VIS Conference papers (a selection from 2017-2019) to assess the inclusion of geospatial data and geospatial analyses within these papers. After removing the papers with no geospatial data, we organize the remaining literature into geospatial data domain categories and provide insight into how these categories relate to VIS Conference paper types. We also contextualize our results by investigating the use of geospatial terms in IEEE Visualization publications over the last 30 years. Our work provides an understanding of the quantity and role of geospatial subject matter in recent IEEE VIS publications and supplies a foundation for future meta-analytical work around geospatial analytics and geovisualization that may shed light on opportunities for innovation., Comment: 5 pages, 4 figures, IEEE VIS Short Paper Proceedings 2020

As part of formative and summative assessments in programming courses, students work on developing programming artifacts following a given specification. These artifacts are evaluated by the teachers. At the end of this evaluation, the students receive feedback and marks. Providing feedback on programming artifacts is time demanding and could make feedback to arrive too late for it to be effective for the students' learning. We propose to combine software testing with peer feedback which has been praised for offering a timely and effective learning activity with program testing. In this paper we report on the development of a Web platform for peer feedback on programming artifacts through program testing. We discuss the development process of our peer-testing platform informed by teachers and students., Comment: 8th Workshop on Evaluation and Usability of Programming Languages and Tools (PLATEAU) at SPLASH 2017

We consider recovering a causal graph in presence of latent variables, where we seek to minimize the cost of interventions used in the recovery process. We consider two intervention cost models: (1) a linear cost model where the cost of an intervention on a subset of variables has a linear form, and (2) an identity cost model where the cost of an intervention is the same, regardless of what variables it is on, i.e., the goal is just to minimize the number of interventions. Under the linear cost model, we give an algorithm to identify the ancestral relations of the underlying causal graph, achieving within a $2$-factor of the optimal intervention cost. This approximation factor can be improved to $1+\epsilon$ for any $\epsilon > 0$ under some mild restrictions. Under the identity cost model, we bound the number of interventions needed to recover the entire causal graph, including the latent variables, using a parameterization of the causal graph through a special type of colliders. In particular, we introduce the notion of $p$-colliders, that are colliders between pair of nodes arising from a specific type of conditioning in the causal graph, and provide an upper bound on the number of interventions as a function of the maximum number of $p$-colliders between any two nodes in the causal graph., Comment: International Conference on Machine Learning 2020