Search

The topic of algorithmic fairness is of increasing importance to the Human–Computer Interaction research community following accumulating concerns regarding the use and deployment of Artificial Intelligence-based systems. How we conduct research on algorithmic fairness directly influences our inferences and conclusions regarding algorithmic fairness. To better understand the methodological decisions of studies focused on people's perceptions of algorithmic fairness, we systematic analysed relevant papers from the CHI and FAccT conferences. We identified 200 relevant papers published between 1993 and 2022 and assessed their study design, participant sample, and geographical location of participants and authors. Our results highlight that studies are predominantly cross-sectional, cover a wide range of participant roles, and that both authors and participants are primarily from the United States. Based on these findings, we reflect on the potential pitfalls and shortcomings in how the community studies algorithmic fairness. • Mapping of CHI and FAccT papers on algorithmic fairness published 1993–2022. • Over one-third of papers miss details on participant locality and compensation. • Algorithmic fairness research largely restricted to US and other Western countries. • Limited cross-country collaboration, most study samples from a single country. • Remote studies are most common, longitudinal studies are relatively rare. [ABSTRACT FROM AUTHOR]

Abstract: This paper investigates a graph enumeration problem, called the maximal -subgraphs problem, where is a hereditary or connected-hereditary graph property. Formally, given a graph G, the maximal -subgraphs problem is to generate all maximal induced subgraphs of G that satisfy . This problem differs from the well-known node-deletion problem, studied by Yannakakis and Lewis [J. Lewis, On the complexity of the maximum subgraph problem, in: Proc. 10th Annual ACM Symposium on Theory of Computing, ACM Press, New York, USA, 1978, pp. 265–274; M. Yannakakis, Node- and edge-deletion NP-complete problems, in: Proc. 10th Annual ACM Symposium on Theory of Computing, ACM Press, New York, USA, 1978, pp. 253–264; J. Lewis, M. Yannakakis, The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci. 20 (2) (1980) 219–230]. In the maximal -subgraphs problem, the goal is to produce all (locally) maximal subgraphs of a graph that have property , whereas in the node-deletion problem, the goal is to find a single (globally) maximum size subgraph with property . Algorithms are presented that reduce the maximal -subgraphs problem to an input-restricted version of this problem. These algorithms imply that when attempting to efficiently solve the maximal -subgraphs problem for a specific , it is sufficient to solve the restricted case. The main contributions of this paper are characterizations of when the maximal -subgraphs problem is in a complexity class C (e.g., polynomial delay, total polynomial time). [Copyright &y& Elsevier]

Abstract: In [J. Halton, Sequential Monte Carlo, Proc. Comb. Phil. Soc. 58 (1962), J. Halton, Sequential Monte Carlo Techniques for the Solution of Linear Systems, J. Sci. Comp. 9 (1994) 213–257] Halton introduced a strategy to be used in Monte Carlo algorithms for the efficient solution of certain matrix problems. We showed in [R. Kong, J. Spanier, Sequential correlated sampling methods for some transport problems, in: Harold Niederreiter, Jerome Spanier (Eds.), Monte-Carlo and Quasi Monte-Carlo Methods 1998: Proceedings of a Conference at the Claremont Graduate University, Springer-Verlag, New York, 2000, R. Kong, J. Spanier, Error analysis of sequential Monte Carlo methods for transport problems, in: Harold Niederreiter, Jerome Spanier (Eds.), Monte-Carlo and Quasi Monte-Carlo Methods 1998: Proceedings of a Conference at the Claremont Graduate University, Springer-Verlag, New York, 2000] how Halton’s method based on correlated sampling can be extended to continuous transport problems and established their geometric convergence for a family of transport problems in slab geometry. In our algorithm, random walks are processed in batches, called stages, each stage producing a small correction that is added to the approximate solution developed from the previous stages. In this paper, we demonstrate that strict error reduction from stage to stage can be assured under rather general conditions and we illustrate this rapid convergence numerically for a simple family of two dimensional transport problems. [Copyright &y& Elsevier]