9607 research outputs found
Sort by
A Combinatorial Proof of Universal Optimality for Computing a Planar Convex Hull.
No full textFor a planar point set P, its convex hull is the smallest convex polygon that encloses all points in P. The construction of the convex hull from an array I_P containing P is a fundamental problem in computational geometry. By sorting I_P in lexicographical order, one can construct the convex hull of P in O(n log n) time which is worst-case optimal. Standard worst-case analysis, however, has been criticized as overly coarse or pessimistic, and researchers search for more refined analyses.For an algorithm A, worst-case analysis fixes n, and considers the maximum running time of A across all size-n point sets P and permutations I_P of P. Output-sensitive analysis fixes n and k, and considers the maximum running time across all size-n points sets P with k hull points and permutations I_P of P. Universal analysis provides an even stronger guarantee. It fixes a point set P and considers the maximum running time across all permutations I_P of P. Kirkpatrick, McQueen, and Seidel [SICOMP'86] consider output-sensitive analysis. If the convex hull of P contains k points, then their algorithm runs in O(n log k) time. Afshani, Barbay, Chan [FOCS'07] prove that the algorithm by Kirkpatrick, McQueen, and Seidel is also universally optimal. Their proof restricts the model of computation to any algebraic decision tree model where the test functions have at most constant degree and at most a constant number of arguments. They rely upon involved algebraic arguments to construct a lower bound for each point set P that matches the universal running time of [SICOMP'86].We provide a different proof of universal optimality. Instead of restricting the computational model, we further specify the output. We require as output (1) the convex hull, and (2) for each internal point of P a witness for it being internal. Our argument is shorter, perhaps simpler, and applicable in more general models of computation
DistaLs: a Comprehensive Collection of Language Distance Measures
No full textLanguages vary along a wide variety of dimensions. In Natural Language Processing (NLP), it is useful to know how “distant” languages are from each other, so that we can inform NLP models about these differences or predict good transfer languages. Furthermore, it can inform us about how diverse language samples are. However, there are many different perspectives on how distances across languages could be measured, and previous work has predominantly focused on either intuition or a single type of distance, like genealogical or typological distance. Therefore, we propose DistaLs, a toolkit that is designed to provide users with easy access to a wide variety of language distance measures. We also propose a filtered subset, which contains less redundant and more reliable features. DistaLs is designed to be accessible for a variety of use cases, and offers a Python, CLI, and web interface. It is easily updateable, and available as a pip package. Finally, we provide a case-study in which we use DistaLs to measure correlations of distance measures with performance on four different morphosyntactic tasks
On the evolution of agile software team work arrangements
No full textThe IT industry has undergone a significant transformation over the past years, and many companies and software teams have been experimenting with different policies and work arrangements. In this multiple-case study, we explore the evolution of organizational policies and the work arrangements of 28 agile teams, and report on their effects, based on interviews with seven individuals in leadership and support roles, from six companies. Our findings reveal the emergence of a dynamic and evolving spectrum of work arrangements and organizational policies, reflecting an increased flexibility in accommodating diverse work schedules and locations. We identified complex and interrelated impacts at the organizational, leadership, and team levels. At the organizational level, underutilized office spaces pose new challenges for resource management and strategic planning. At the leadership level, managers and team leaders reported diminished visibility and awareness of team activities under certain arrangements. At the team level, policies reshaped the physical and virtual workspace, influencing creativity, communication patterns, and coordination demands, with some arrangements requiring enhanced mechanisms for coordination. Our findings further substantiate concerns raised by both scholars and managers about the impacts of evolving organizational policies and work arrangements
User Misconceptions of LLM-Based Conversational Programming Assistants.
No full textProgramming assistants powered by large language models (LLMs) have become widely available, with conversational assistants like ChatGPT proving particularly accessible to less experienced programmers. However, the varied capabilities of these tools across model versions and the mixed availability of extensions that enable web search, code execution, or retrieval-augmented generation create opportunities for user misconceptions about what systems can and cannot do. Such misconceptions may lead to over-reliance, unproductive practices, or insufficient quality control in LLM-assisted programming. Here, we aim to characterize misconceptions that users of conversational LLM-based assistants may have in programming contexts. Using a two-phase approach, we first brainstorm and catalog user misconceptions that may occur, and then conduct a qualitative analysis to examine whether these conceptual issues surface in naturalistic Python-programming conversations with an LLM-based chatbot drawn from an openly available dataset. Indeed, we see evidence that some users have misplaced expectations about the availability of LLM-based chatbot features like web access, code execution, or non-text output generation. We also see potential evidence for deeper conceptual issues around the scope of information required to debug, validate, and optimize programs. Our findings reinforce the need for designing LLM-based tools that more clearly communicate their programming capabilities to users.<br/
Emergent social conventions and collective bias in LLM populations
No full textSocial conventions are the backbone of social coordination, shaping how individuals form a group. As growing populations of artificial intelligence (AI) agents communicate through natural language, a fundamental question is whether they can bootstrap the foundations of a society. Here, we present experimental results that demonstrate the spontaneous emergence of universally adopted social conventions in decentralized populations of large language model (LLM) agents. We then show how strong collective biases can emerge during this process, even when agents exhibit no bias individually. Last, we examine how committed minority groups of adversarial LLM agents can drive social change by imposing alternative social conventions on the larger population. Our results show that AI systems can autonomously develop social conventions without explicit programming and have implications for designing AI systems that align, and remain aligned, with human values and societal goals
A consistency management framework for Digital Twin models
No full textDigital twins (DTs) encapsulate the concept of a real-world entity (RE) and corresponding bidirectionally connected virtual one (VE) mimicking certain aspects of the former in order to facilitate various use-cases such as predictive maintenance. DTs typically encompass various models that are often developed by experts from different domains using diverse tools. To maintain consistency among these models and ensure the continued functioning of the system, effective identification of any consistency issues and addressing them whenever necessary is imperative. In this paper, we investigate the concept of consistency management and propose a consistency management framework that addresses various characteristics of DT models. Subsequently, we present three working examples that implement the proposed framework with graph-based techniques. Taking the working examples into account, we demonstrate and argue that our consistency management framework can provide crucial assistance in the consistency management of DT models
DP-Morph: Improving the Privacy-Utility-Performance Trade-off for Differentially Private OCT Segmentation
No full textOptical Coherence Tomography (OCT) images show a cross-section of the retina and are used for early detection of retinal diseases and glaucoma through analysis of the retinal layers. Advances in deep learning have enabled state-of-the-art OCT segmentation models to support this analysis. However, using medical data to train these models raises concerns about patient privacy. For example, membership inference attacks allow an adversary to determine whether a particular data point was included in the training data. Differentially Private Stochastic Gradient Descent (DPSGD) improves the privacy of deep learning models by ensuring that these models do not disclose sensitive information about individual data points. However, implementing DPSGD may cause decreased model accuracy and/or increased computational demands. In this paper, we evaluate the privacy, utility, and computational performance of five OCT segmentation models trained using DPSGD on graphics processing units (GPUs). To improve utility, we then propose DP-Morph, a novel privacy-preserving modification of DPSGD based on morphology. We show that DP-Morph improves segmentation performance, for example, increasing the Dice coefficient of LFUNet from 0.50 to 0.70 for a privacy budget of 200
Challenges in Conducting Theory-Informed Empirical Player Experience Research
No full textEmpirical player experience (PX) research has seen increased calls for more and better theoryuse. Theory drives research programs, allows to synthesize research and can inform design.These calls, however, rarely discuss the actual practice of doing theory-informed research. Howdo we work effectively with theory in PX research? What challenges do we face; and, shouldwe not overcome them, what does it mean for empirical PX research to fail? In this thesis, Iapproach these questions by presenting five research projects and reflecting on their respectiveresearch processes, challenges, and failures.Publication I is a systematic literature review of the reporting practices of Null HypothesisSignificance Testing at CHI PLAY. A method commonly used to test theories and widely used inempirical PX research. Based on the findings of Publication I, and a discussion of confirmatory,theory-testing methods, I highlight the role of exploratory methods in PX research.Publication II is an exploratory mixed-methods study on art experiences in videogames. The study utilizes empirical aesthetics to understand what players consider art experiences. It highlights the importance of epistemic emotions — i.e., Interest and Insight — as well as a range ofshort and long term impacts the experiences had on players. As this paper employs a theorydevised to explain and predict the art experience of people, I reflect on the process of bringingthe theory over to player experience research by discussing how we used it in this paper andhow it guided the study design and codebook-based analysis.Publication III studies empowering and disempowering player experiences. While empowerment is a common, desirable goal for HCI and HCI games research, it has a multitude ofconceptualizations and can overlap with other commonly used PX constructs such as emotionalplay experiences and basic need satisfaction. I reflect on the overlap of different PX constructswith empowerment and disempowerment and how theory guided the choice of behavioral measures and thematic analysis.The last two projects I discuss have not been published. In this thesis I reflect on the processof each project, the challenges they encountered, and what to learn from them. The first projectiiisought to experimentally evoke emotional challenge and compare if Self-Determination Theoryor an art appraisal theory better predict the enjoyment and appreciation. After conducting thestudy, results revealed mostly non-significant results, with further Bayesian analyses indicatingthat the desired experimental manipulation was unreliable, throwing into question what can belearned from the results. The second project is an ongoing exploratory experiment, investigatingthe player experience of rewards through the lens of Cognitive Evaluation Theory. A pre-studyraised concerns about measuring the functional significance and reliability of the study manipulation, leading to a reassessment of the feasibility of the study design. I will reflect on how thesetwo studies were designed highlighting difficulties in translating theories into both testable hypotheses and experimental manipulations. I further discuss issues when measuring conceptsand when attempting to decide between the study being wrong, or the theory.This thesis contributes to PX research in the following ways. First, this thesis highlights tangible opportunities and approaches to better theory-informed PX research. Second, it describesconcrete barriers and pitfalls to creating informative theory-informed PX research. Third, I givea personal account on failure in my research practice, something that otherwise is scarcely talkedabout, in the hope of sparking more reflection and discussion about HCI and PX research practic
Do Syntactic Categories Help in Developmentally Motivated Curriculum Learning for Language Models?
No full textWe examine the syntactic properties of BabyLM corpus, and age-groups within CHILDES. While we find that CHILDES does not exhibit strong syntactic differentiation by age, we show that the syntactic knowledge about the training data can be helpful in interpreting model performance on linguistic tasks. For curriculum learning, we explore developmental and several alternative cognitively inspired curriculum approaches. We find that some curricula help with reading tasks, but the main performance improvement come from using the subset of syntactically categorizable data, rather than the full noisy corpus