9607 research outputs found
Sort by
Which Graph Motif Parameters Count?
No full textFor a fixed graph H, the function #Ind(H → ⋆) maps graphs G to the count of induced H-copies in G; this function obviously "counts something" in that it has a combinatorial interpretation. Linear combinations of such functions are called graph motif parameters and have recently received significant attention in counting complexity after a seminal paper by Curticapean, Dell and Marx (STOC'17). We show that, among linear combinations of functions #Ind(H → ⋆) involving only graphs H without isolated vertices, precisely those with positive integer coefficients maintain a combinatorial interpretation. It is important to note that graph motif parameters can be nonnegative for all inputs G, even when some coefficients are negative.Formally, we show that evaluating any graph motif parameter with a negative coefficient is impossible in an oracle variant of #P, where an implicit graph is accessed by oracle queries. Our proof follows the classification of the relativizing closure properties of #P by Hertrampf, Vollmer, and Wagner (SCT'95) and the framework developed by Ikenmeyer and Pak (STOC'22), but our application of the required Ramsey theorem turns out to be more subtle, as graphs do not have the required Ramsey property.Our techniques generalize from graphs to relational structures, including colored graphs. Vastly generalizing this, we introduce motif parameters over categories that count occurrences of sub-objects in the category. We then prove a general dichotomy theorem that characterizes which such parameters have a combinatorial interpretation. Using known results in Ramsey theory for categories, we obtain a dichotomy for motif parameters of finite vector spaces as well as parameter sets
The Cultural Complexity of Carbon
No full textThis volume discusses the transformational role that carbon – both as a concept and as a distinct set of material forms and effects – has come to play in social and cultural life.As a proxy for greenhouse gas emission data, carbon has grown to become a phenomenon that can no longer be accounted for solely within the technoscientific vocabulary of climate scientists. The Cultural Complexity of Carbon examines the extent to which our knowledge of carbon affects the way that human beings relate to each other and to the climate and/or the environment. It draws on case studies from a diverse range of topics including peatland restoration, religion and energy systems to explore questions that have so far been under-explored in the current literature. These questions include whether the recognition of carbon’s role in climate change leads to an incremental adaptation of lifestyles or to cultural or existential transformations, but also more concretely how carbon is made meaningful, and how these meanings are attached to ideals of cultural change or continuity. Spanning multiple perspectives and disciplinary positions, this volume provides a go-to point for the next generation of ethnographic studies of carbon and climate change. It cuts across what has hitherto been largely separate literatures in anthropology, geography and sociology to provide a meta-level orientation to how contemporary narratives of the role of carbon are being told.By addressing the intimate social and cultural changes that stem from humanity’s involvement with its natural and climatic resources, this volume is of interest to students and scholars of climate change within the social sciences and environmental humanities
Attuning to Global Health: Health Data Infrastructuring, Epidemiological Accountability and Digital Labor in Ghana
No full textDrawing on ethnographic fieldwork among Ghanaian officials and international developers in the field of health information systems, we investigate how innovations in health data infrastructures are aligned with global practices of epidemiological accountability. The digital health information system DHIS2 has been adopted in various low- and middle-income countries, including Ghana. While global stakeholders render public health a matter of efficiency and accountability, public health professionals attune at various levels to emerging global health priorities and data practices, e.g. the translation of standard case definitions and quantitative measures into local contexts, or innovations in reporting channels of key public health indicators
Crossing Domains without Labels: Distant Supervision for Term Extraction
No full textAbstractAutomatic Term Extraction (ATE) is a critical component in downstream NLP tasks such as document tagging, ontology construction and patent analysis. Current state-of-the-art methods require expensive human annotation and struggle with domain transfer, limiting their practical deployment. This highlights the need for more robust, scalable solutions and realistic evaluation settings. To address this, we introduce a comprehensive benchmark spanning seven diverse domains, enabling performance evaluation at both the document- and corpus-levels. Furthermore, we propose a robust LLM-based model that outperforms both supervised cross-domain encoder models and few-shot learning baselines and performs competitively with its GPT-4o teacher on this benchmark.The first step of our approach is generating psuedo-labels with this black-box LLM on general and scientific domains to ensure generalizability. Building on this data, we fine-tune the first LLMs for ATE. To further enhance document-level consistency, oftentimes needed for downstream tasks, we introduce lightweight post-hoc heuristics. Our approach exceeds previous approaches on 5/7 domains with an average improvement of 10 percentage points. We release our dataset and fine-tuned models to support future research in this area
Local Differences, Global Lessons: Insights from Organisation Policies for Legislation
No full textThe rapid adoption of AI across diverse domains has led to the development oforganisational guidelines that vary significantly, even within the same sector. Thispaper examines AI policies in two domains, news organisations and universities, to understand how bottom-up governance approaches shape AI usage and oversight. By analysing these policies, we identify key areas of convergence and divergence in how organisations address risks such as bias, privacy, misinformation, and accountability. We then explore the implications of these findings for AI legislation, particularly the EU AI Act, highlighting gaps where practical policy insights could inform regulatory refinements. Our analysis reveals that organisational policies often address issues such as AI literacy, disclosure practices, and environmental impact, areas that are underdeveloped in existing legislative frameworks. We argue that lessons from domain-specific AI policies can contribute to more adaptive and effective AI governance at the global level. This study provides actionable recommendations for policymakers seeking to bridge the gap between local AIpractices and regulation
Distributed Computation with Local Advice
No full textAlgorithms with advice have received ample attention in the distributed and online settings, and they have recently proven useful also in dynamic settings. In this work we study local computation with advice: the goal is to solve a graph problem Π with a distributed algorithm in T(Δ) communication rounds, for some function T that only depends on the maximum degree Δ of the graph, and the key question is how many bits of advice per node are needed. Some of our results regard Locally Checkable Labeling problems (LCLs), which is an important family of problems that includes various coloring and orientation problems on finite-degree graphs. These are constraint-satisfaction graph problems that can be defined with a finite set of valid input/output-labeled neighborhoods.Our main results are: 1) Any locally checkable labeling problem can be solved with only 1 bit of advice per node in graphs with sub-exponential growth (the number of nodes within radius r is sub-exponential in r; for example, grids are such graphs). Moreover, we can make the set of nodes that carry advice bits arbitrarily sparse. As a corollary, any locally checkable labeling problem admits a locally checkable proof with 1 bit per node in graphs with sub-exponential growth. 2) The assumption of sub-exponential growth is complemented by a conditional lower bound: assuming the Exponential-Time Hypothesis, there are locally checkable labeling problems that cannot be solved in general with any constant number of bits per node. 3) In any graph we can find an almost-balanced orientation (indegrees and outdegrees differ by at most one) with 1 bit of advice per node, and again we can make the advice arbitrarily sparse. As a corollary, we can also compress an arbitrary subset of edges so that a node of degree d stores only d/2 + 2 bits, and we can decompress it locally, in T(Δ) rounds. 4) In any graph of maximum degree Δ, we can find a Δ-coloring (if it exists) with 1 bit of advice per node, and again, we can make the advice arbitrarily sparse. 5) In any 3-colorable graph, we can find a 3-coloring with 1 bit of advice per node. As a corollary, in bounded-degree graphs there is a locally checkable proof that certifies 3-colorability with 1 bit of advice per node, while prior work shows that this is not possible with a proof labeling scheme (PLS), which is a more restricted setting where the verifier can only see up to distance 1. Our work shows that for many problems the key threshold is not whether we can achieve 1 bit of advice per node, but whether we can make the advice arbitrarily sparse. To formalize this idea, we develop a general framework of composable schemas that enables us to build algorithms for local computation with advice in a modular fashion: once we have (1) a schema for solving Π₁ and (2) a schema for solving Π₂ assuming an oracle for Π₁, we can also compose them and obtain (3) a schema that solves Π₂ without the oracle. It turns out that many natural problems admit composable schemas, all of them can be solved with only 1 bit of advice, and we can make the advice arbitrarily sparse
On the Notion that Language Models Reason
No full textLanguage models (LMs) are said to be exhibiting reasoning, but what does this entail? We assess definitions of reasoning and how key papers in the field of natural language processing (NLP) use the notion and argue that the definitions provided are not consistent with how LMs are trained, process information, and generate new tokens. To illustrate this incommensurability we assume the view that transformer-based LMs implement an implicit finite-order Markov kernel mapping contexts to conditional token distributions. In this view, reasoning-like outputs correspond to statistical regularities and approximate statistical invariances in the learned kernel rather than the implementation of explicit logical mechanisms. This view is illustrative of the claim that LMs are "statistical pattern matchers"" and not genuine reasoners and provides a perspective that clarifies why reasoning-like outputs arise in LMs without any guarantees of logical consistency. This distinction is fundamental to how epistemic uncertainty is evaluated in LMs. We invite a discussion on the importance of how the computational processes of the systems we build and analyze in NLP research are described
When Less Human Is More: Introducing Stigma Sensitivity to Anthropomorphism Research in AI
No full textHow Creative Practitioners Use Tools to Capture Ideas: A Cross-Domain Study
No full textCreative practitioners rely on tools to capture and manage ideas as a foundational aspect of their work. However, we have little knowledge about how idea management practices vary in different creative domains. Combining insights from qualitative surveys (N 200) and follow-up in-depth interviews (n 60) with creative professionals from four domains (interaction design, research, music, and graphics) of creative work, we report on (1) how ideas are externalized in practitioners’ archives, (2) what they consider important when choosing tools to capture ideas, and (3) how these tool collections resemble and differ from each other. Our cross-domain study demonstrates that participants’ tool use reflects idea capture characteristic needs as well as domain-specific views about the creative process. We conclude with a discussion about capturing as an externalizing activity, practitioners’ use of the term ideas, and four suggestions for directions in the design of creativity support tools
The HCI GenAI CO2ST Calculator: Calculating and Offsetting the Carbon Footprint of Generative AI Use in Human-Computer Interaction Research
No full textIncreased usage of generative AI (GenAI) in Human-Computer Interaction (HCI) research has caused a sustainability crisis in computing, due to the excessive power consumption of developing and running these models. Energy consumption causes a massive carbon footprint. The exact energy usage and and subsequent carbon emissions are difficult to estimate in HCI research because HCI researchers most often use cloud-based services where the hardware and its energy consumption are hidden from plain view. The HCI GenAI CO2st Calculator is a tool designed specifically for the HCI research pipeline, to help researchers estimate the energy consumption and carbon footprint of using generative AI in their research, either a priori (allowing for mitigation strategies or experimental redesign) or post hoc (allowing for transparent documentation of carbon footprint in written reports of the research)