arXiv Computer Science @arxiv_cs@qoto.org

Answer Set Programming (ASP) is a prominent problem-modeling and solving framework, whose solutions are called answer sets. Epistemic logic programs (ELP) extend ASP to reason about all or some answer sets. Solutions to an ELP can be seen as consequences over multiple collections of answer sets, known as world views. While the complexity of propositional programs is well studied, the non-ground case remains open. This paper establishes the complexity of non-ground ELPs. We provide a comprehensive picture for well-known program fragments, which turns out to be complete for the class NEXPTIME with access to oracles up to Σ^P_2. In the quantitative setting, we establish complexity results for counting complexity beyond #EXP. To mitigate high complexity, we establish results in case of bounded predicate arity, reaching up to the fourth level of the polynomial hierarchy. Finally, we provide ETH-tight runtime results for the parameter treewidth, which has applications in quantitative reasoning, where we reason on (marginal) probabilities of epistemic literals.

This article presents an ongoing research aiming to develop an effective methodology for teaching programming, focusing on participation in the Brazilian Informatics Olympiad (OBI), for elementary and high school students. The training conducted with students from the Federal Institute and state schools, demonstrates the importance of programming training programs as a way to promote interest in computing, stimulate the development of computational skills, and increase participation in competitions such as the OBI. The next steps of the research include conducting more training cycles and analyzing the results obtained in the competitions.

Generative AI enables automated, effective manipulation at scale. Despite the growing general ethical discussion around generative AI, the specific manipulation risks remain inadequately investigated. This article outlines essential inquiries encompassing conceptual, empirical, and design dimensions of manipulation, pivotal for comprehending and curbing manipulation risks. By highlighting these questions, the article underscores the necessity of an appropriate conceptualisation of manipulation to ensure the responsible development of Generative AI technologies.

Food systems are responsible for a third of human-caused greenhouse gas emissions. We investigate what Large Language Models (LLMs) can contribute to reducing the environmental impacts of food production. We define a typology of design and prediction tasks based on the sustainable food literature and collaboration with domain experts, and evaluate six LLMs on four tasks in our typology. For example, for a sustainable protein design task, food science experts estimated that collaboration with an LLM can reduce time spent by 45% on average, compared to 22% for collaboration with another expert human food scientist. However, for a sustainable menu design task, LLMs produce suboptimal solutions when instructed to consider both human satisfaction and climate impacts. We propose a general framework for integrating LLMs with combinatorial optimization to improve reasoning capabilities. Our approach decreases emissions of food choices by 79% in a hypothetical restaurant while maintaining participants' satisfaction with their set of choices. Our results demonstrate LLMs' potential, supported by optimization techniques, to accelerate sustainable food development and adoption.

Large Language Models (LLMs) are increasingly deployed as autonomous agents, necessitating a deeper understanding of their decision-making behaviour under risk. This study investigates the relationship between LLMs' personality traits and risk propensity, employing cumulative prospect theory (CPT) and the Big Five personality framework. We focus on GPT-4o, comparing its behaviour to human baselines and earlier models. Our findings reveal that GPT-4o exhibits higher Conscientiousness and Agreeableness traits compared to human averages, while functioning as a risk-neutral rational agent in prospect selection. Interventions on GPT-4o's Big Five traits, particularly Openness, significantly influence its risk propensity, mirroring patterns observed in human studies. Notably, Openness emerges as the most influential factor in GPT-4o's risk propensity, aligning with human findings. In contrast, legacy models like GPT-4-Turbo demonstrate inconsistent generalization of the personality-risk relationship. This research advances our understanding of LLM behaviour under risk and elucidates the potential and limitations of personality-based interventions in shaping LLM decision-making. Our findings have implications for the development of more robust and predictable AI systems such as financial modelling.

Technical standards, or simply standards, are established documented guidelines and rules that facilitate the interoperability, quality, and accuracy of systems and processes. In recent years, we have witnessed an emerging paradigm shift where the adoption of generative AI (GenAI) models has increased tremendously, spreading implementation interests across standard-driven industries, including engineering, legal, healthcare, and education. In this paper, we assess the criticality levels of different standards across domains and sectors and complement them by grading the current compliance capabilities of state-of-the-art GenAI models. To support the discussion, we outline possible challenges and opportunities with integrating GenAI for standard compliance tasks while also providing actionable recommendations for entities involved with developing and using standards. Overall, we argue that aligning GenAI with standards through computational methods can help strengthen regulatory and operational compliance. We anticipate this area of research will play a central role in the management, oversight, and trustworthiness of larger, more powerful GenAI-based systems in the near future.

Detection of carelessness in digital learning platforms has relied on the contextual slip model, which leverages conditional probability and Bayesian Knowledge Tracing (BKT) to identify careless errors, where students make mistakes despite having the knowledge. However, this model cannot effectively assess carelessness in questions tagged with multiple skills due to the use of conditional probability. This limitation narrows the scope within which the model can be applied. Thus, we propose a novel model, the Beyond Knowledge Feature Carelessness (BKFC) model. The model detects careless errors using performance factor analysis (PFA) and behavioral features distilled from log data, controlling for knowledge when detecting carelessness. We applied the BKFC to detect carelessness in data from middle school students playing a learning game on decimal numbers and operations. We conducted analyses comparing the careless errors detected using contextual slip to the BKFC model. Unexpectedly, careless errors identified by these two approaches did not align. We found students' post-test performance was (corresponding to past results) positively associated with the carelessness detected using the contextual slip model, while negatively associated with the carelessness detected using the BKFC model. These results highlight the complexity of carelessness and underline a broader challenge in operationalizing carelessness and careless errors.

Online gambling platforms have transformed the gambling landscape, offering unprecedented accessibility and personalized experiences. However, these same characteristics have increased the risk of gambling-related harm, affecting individuals, families, and communities. Structural factors, including targeted marketing, shifting social norms, and gaps in regulation, further complicate the challenge. This narrative review examines how artificial intelligence, particularly multimodal generative models and foundation technologies, can address these issues by supporting prevention, early identification, and harm-reduction efforts. We detail applications such as synthetic data generation to overcome research barriers, customized interventions to guide safer behaviors, gamified tools to support recovery, and scenario modeling to inform effective policies. Throughout, we emphasize the importance of safeguarding privacy and ensuring that technological advances are responsibly aligned with public health objectives.

While neural lossy compression techniques have markedly advanced the efficiency of Channel State Information (CSI) compression and reconstruction for feedback in MIMO communications, efficient algorithms for more challenging and practical tasks-such as CSI compression for future channel prediction and reconstruction with relevant side information-remain underexplored, often resulting in suboptimal performance when existing methods are extended to these scenarios. To that end, we propose a novel framework for compression with side information, featuring an encoding process with fixed-rate compression using a trainable codebook for codeword quantization, and a decoding procedure modeled as a backward diffusion process conditioned on both the codeword and the side information. Experimental results show that our method significantly outperforms existing CSI compression algorithms, often yielding over twofold performance improvement by achieving comparable distortion at less than half the data rate of competing methods in certain scenarios. These findings underscore the potential of diffusion-based compression for practical deployment in communication systems.

We say that a measure of dependence between two random variables $X$ and $Y$, denoted as $ρ(X;Y)$, satisfies the data processing property if $ρ(X;Y)\geq ρ(X';Y')$ for every $X'\rightarrow X\rightarrow Y\rightarrow Y'$, and satisfies the tensorization property if $ρ(X_1X_2;Y_1Y_2)=\max\{ρ(X_1;Y_1),ρ(X_2;Y_2)\}$ when $(X_1,Y_1)$ is independent of $(X_2,Y_2)$. It is known that measures of dependence defined based on $Φ$-entropy satisfy these properties. These measures are important because they generalize R{é}nyi's maximal correlation and the hypercontractivity ribbon. The data processing and tensorization properties are special cases of monotonicity under wirings of non-local boxes. We show that ribbons defined using $Φ$-entropic measures of dependence are monotone under wiring of non-local no-signaling boxes, generalizing an earlier result. In addition, we also discuss the evaluation of $Φ$-strong data processing inequality constant for joint distributions obtained from a $Z$-channel.

Online public opinion is increasingly becoming a significant factor affecting the stability of the internet and society, particularly as the frequency of online public opinion crises has risen in recent years. Enhancing the capability for early warning of online public opinion crises is urgent. The most effective approach is to identify potential crises in their early stages and implement corresponding management measures. This study establishes a preliminary indicator system for online public opinion early warning, based on the principles of indicator system construction and the characteristics and evolution patterns of online public opinion. Subsequently, data-driven methodologies were employed to collect and preprocess public opinion indicator data. Utilizing grey relational analysis and the K-Means clustering algorithm, we classified online public opinion events into three levels: slight, warning, and severe. Furthermore, we constructed an online topic evolution model using the online Hierarchical Dirichlet Process model to analyze the thematic changes of online public opinion events across different warning levels. Finally, we developed an online public opinion early warning model using a Backpropagation (BP) neural network. The test results of early warning samples show that the model achieves high accuracy. Thus, in practical early warning applications, the BP neural network can be effectively utilized for predicting online public opinion events.

Accurate speech emotion recognition is essential for developing human-facing systems. Recent advancements have included finetuning large, pretrained transformer models like Wav2Vec 2.0. However, the finetuning process requires substantial computational resources, including high-memory GPUs and significant processing time. As the demand for accurate emotion recognition continues to grow, efficient finetuning approaches are needed to reduce the computational burden. Our study focuses on dimensional emotion recognition, predicting attributes such as activation (calm to excited) and valence (negative to positive). We present various finetuning techniques, including full finetuning, partial finetuning of transformer layers, finetuning with mixed precision, partial finetuning with caching, and low-rank adaptation (LoRA) on the Wav2Vec 2.0 base model. We find that partial finetuning with mixed precision achieves performance comparable to full finetuning while increasing training speed by 67%. Caching intermediate representations further boosts efficiency, yielding an 88% speedup and a 71% reduction in learnable parameters. We recommend finetuning the final three transformer layers in mixed precision to balance performance and training efficiency, and adding intermediate representation caching for optimal speed with minimal performance trade-offs. These findings lower the barriers to finetuning speech emotion recognition systems, making accurate emotion recognition more accessible to a broader range of researchers and practitioners.

Probability theory is fundamental for modeling uncertainty, with traditional probabilities being real and non-negative. Complex probability extends this concept by allowing complex-valued probabilities, opening new avenues for analysis in various fields. This paper explores the information-theoretic aspects of complex probability, focusing on its definition, properties, and applications. We extend Shannon entropy to complex probability and examine key properties, including maximum entropy, joint entropy, conditional entropy, equilibration, and cross entropy. These results offer a framework for understanding entropy in complex probability spaces and have potential applications in fields such as statistical mechanics and information theory.

Wireless networks in a room are strongly affected by interferences. To alleviate these effects and enhance the performance of the wireless networks, some optimization was carried out. In this work, an analytical study was introduced to determine the optimal number of access points with their positions on the ground floor at the Architecture Engineering department building - University of Mosul. The implementation has been done using a web-based Wi-Fi and IoT design tool called Hamina Network Planner, and a Wi-Fi Network Planning and Site Survey Software called NetSpot. The experimental results show that the simulation values of the available APs are approximately matched with the real time manual values, achieving the best rates of -22dBm and -31dBm respectively. However, the number of currently available Access Points is not sufficient to cover the building area, so that two scenarios were suggested to overcome this issue. In the first scenario, two access points have been added at different positions in the building depending on the Hamina Network Planner, and in the second one, the transmitted power has been increased. The simulation results demonstrate that the overall coverage rate enhanced and can include most of the building area.

The main objective of this work is to show, through counterexamples, that some of the theorems presented in the papers of Sharma \textit{et al.} (2018) and Chauhan \textit{et al.} ( 2021) are incorrect. Although they used these theorems to establish a sufficient condition for a multi-twisted (MT) code to be linear complementary dual (LCD), we show that this condition itself remains valid. We further improve this condition by removing the restrictions on the shift constants and relaxing the required coprimality condition. We show that compared to the previous condition, the modified condition is able to identify more LCD MT codes. Furthermore, without the need for a normalized set of generators, we develop a formula to determine the dimension of any $ρ$-generator MT code.

Distributed quantum networks are not merely information conduits but intricate systems that embody the principles of quantum mechanics. In our study, we examine the underlying mechanisms of quantum connectivity within a distributed framework by exploring phenomena such as superposition and entanglement and their influence on information propagation. We investigate how these fundamental quantum effects interact with routing strategies that, while inspired by classical methods, must contend with quantum decoherence and measurement uncertainties. By simulating distributed networks of 10, 20, 50 and 100 nodes, we assess the performance of routing mechanisms through metrics that reflect both quantum fidelity and operational efficiency. Our findings reveal that the quantum coherence inherent in entangled states can enhance routing fidelity under specific conditions, yet also introduce challenges such as increased computational overhead and sensitivity to network scale. This work bridges the gap between the underlying principles of quantum systems and practical routing implementations, offering new insights into the design of robust distributed quantum networks.

Integrated sensing and communication (ISAC) represents a pivotal advancement for future wireless networks. This paper introduces a novel ISAC beamforming method for enhancing sensing performance while preserving communication quality by leveraging the ambiguity function (AF). We formulate an optimization problem to minimize the integrated sidelobe level ratio (ISLR) of the AF subject to the constraints of transmission power, communication signalto-interference-plus-noise ratio, and sensing gain. To address the non-convexity of the optimization problem, semidefinite relaxation is adopted. Numerical results show that our method significantly reduces range sidelobes and achieves a lower ISLR in the rangeangle domain compared to other approaches.

In recent years, Large Language Models (LLMs) rapidly gained popularity across all parts of society, including education. After initial skepticism and bans, many schools have chosen to embrace this new technology by integrating it into their curricula in the form of virtual tutors and teaching assistants. However, neither the companies developing this technology nor the public institutions involved in its implementation have set up a formal system to collect feedback from the stakeholders impacted by them. In this paper, we argue that understanding the perceptions of those directly affected by LLMS in the classroom, such as students and teachers, as well as those indirectly impacted, like parents and school staff, is essential for ensuring responsible use of AI in this critical domain. Our contributions are two-fold. First, we present results of a literature review focusing on the perceptions of LLM-based chatbots in education. We highlight important gaps in the literature, such as the exclusion of key educational agents (e.g., parents or school administrators) when analyzing the role of stakeholders, and the frequent omission of the learning contexts in which the AI systems are implemented. Thus, we present a taxonomy that organizes existing literature on stakeholder perceptions. Second, we propose the Contextualized Perceptions for the Adoption of Chatbots in Education (Co-PACE) framework, which can be used to systematically elicit perceptions and inform whether and how LLM-based chatbots should be designed, developed, and deployed in the classroom.

Building on recent work studying content in the online advertising ecosystem, including our own prior study of political ads on the web during the 2020 U.S. elections, we analyze political ad content appearing on websites leading up to and during the 2024 U.S. elections. Crawling a set of 745 news and media websites several times from three different U.S. locations (Atlanta, Seattle, and Los Angeles), we collect a dataset of over 15000 ads, including (at least) 315 political ads, and we analyze it quantitatively and qualitatively. Among our findings: a prevalence of clickbait political news ads, echoing prior work; a seemingly new emphasis (compared to 2020) on voting safety and eligibility ads, particularly in Atlanta; and non-election related political ads around the Israel-Palestine conflict, particularly in Seattle. We join prior work in calling for more oversight and transparency of political-related ads on the web. Our dataset is available at https://ad-archive.cs.washington.edu.

Digital networks have profoundly transformed the ways in which individuals interact, exchange information, and establish connections, leading to the emergence of phenomena such as virality, misinformation cascades, and online polarization. This review conducts a thorough examination of the micro-macro linkages within digital social networks, analyzing how individual actions like liking, sharing, and commenting coalesce into broader systemic patterns and how these interactions are influenced by algorithmic mediation. Utilizing a multidisciplinary literature base, this study explores the interaction among user behaviors, network structures, and platform algorithms that intensify biases, strengthen homophily, and foster echo chambers. We delve into crucial dynamics including the scalability's impact on weak tie propagation, the amplification effects on influencers, and the rise of digital inequalities, employing both theoretical and empirical approaches. By synthesizing insights from sociology, network theory, and computational social science, this paper underscores the necessity for novel frameworks that integrate algorithmic processes into established micro-macro models. The conclusion presents practical strategies aimed at promoting fairer digital networks through decentralized architectures, algorithmic fairness, and improved digital inclusion, tackling significant challenges such as polarization and misinformation within networked societies.