9607 research outputs found
Sort by
Extended reality for rehabilitation of people living with Parkinson’s disease: protocol for a scoping review
No full textLanguage-Based Testing for Knowledge Graphs
No full textKnowledge graphs rely on a vast ecosystem of software tools, such as parsers, APIs and reasoners. Yet, tool developers have little support to ensure tool reliability. Here, we demonstrate how recent advantages in test case generation for highly structured and constrained inputs can support software developers in the semantic web field. We develop input generators for RDF Turtle and the OWL EL profile, and report on numerous bugs we found in parsers, reasoners and APIs of widely used tools and libraries, as well as imprecisions in standards and documentation. We provide actionable insights on using automated testing to increase the reliability of software tools for knowledge graphs
#SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank
No full textThere is a large body of work that shows how to leverage lower bound techniques for circuit classes to obtain satisfiability algorithms that run in better than brute-force time [24, 38]. For circuits with threshold gates, there are several such algorithms based on either Probabilistic Representations by low-degree polynomials, which allow for the use of fast polynomial evaluation algorithms, or Low rank, which allows for an efficient reduction to rectangular matrix multiplication. In this paper, we use a related notion of probabilistic rank to obtain satisfiability algorithms for circuit classes contained in ACC0 ◦ 3-PTF, i.e. constant-depth circuits with modular counting gates and a single layer of degree-3 polynomial threshold functions. Even for the special case of a single 3-PTF, it is not clear how to use either of the above two strategies to get a non-trivial satisfiability algorithm. The best known algorithm in this case previously was based on memoization and yields worse guarantees than our algorithm
New Bounds for the Ideal Proof System in Positive Characteristic.
No full textIn this work, we prove upper and lower bounds over fields of positive characteristics for several fragments of the Ideal Proof System (IPS), an algebraic proof system introduced by Grochow and Pitassi (J. ACM 2018). Our results extend the works of Forbes, Shpilka, Tzameret, and Wigderson (Theory of Computing 2021) and also of Govindasamy, Hakoniemi, and Tzameret (FOCS 2022). These works primarily focused on proof systems over fields of characteristic 0, and we are able to extend these results to positive characteristic. The question of proving general IPS lower bounds over positive characteristic is motivated by the important question of proving AC0[p]-Frege lower bounds. This connection was observed by Grochow and Pitassi (J. ACM 2018). Additional motivation comes from recent developments in algebraic complexity theory due to Forbes (CCC 2024) who showed how to extend previous lower bounds over characteristic 0 to positive characteristic. In our work, we adapt the functional lower bound method of Forbes et al. (Theory of Computing 2021) to prove exponential-size lower bounds for various subsystems of IPS. In order to establish these size lower bounds, we first prove a tight degree lower bound for a variant of Subset Sum over positive characteristic. This forms the core of all our lower bounds. Additionally, we derive upper bounds for the instances presented above. We show that they have efficient constant-depth IPS refutations. This demonstrates that constant-depth IPS refutations are stronger than the proof systems considered above even in positive characteristic. We also show that constant-depth IPS can efficiently refute a general class of instances, namely all symmetric instances, thereby further uncovering the strength of these algebraic proofs in positive characteristic
What Is Programming?
No full textTWO YEARS AGO, when visiting research colleagues in Uppsala, Sweden, we were asked a deceptively simple question: "What does it mean to program?" For context, one of us had just completed academic education and training in computer science and was already deeply involved in actually teaching introductory programming (CS1). Arguably, he was (and still is) capable of programming. The other completed his Ph.D. degree in 2003 and has been teaching programming (in various forms) ever since. Yet, the question took us by surprise; after all: "What is programming?" To the reader, it may appear a ridiculous question to ask for two reasons. You may find yourself having a very clear and succinct definition and conceptualization of (the idea of) programming. Or, you may question what value it brings to discuss such a trivial question. However, we believe the answers to this question may shed light on the future of programming in the age of generative artificial intelligence (AI). We approach an answer to the question by an exploration of the history of computing as well as opinions among contemporary introductory programming educators
Extensibility in Programming Languages: An overview
No full textI here conduct an exploration of programming language extensibility, making an argument for an often overlooked component of conventional language design. Now, this is not a technical detailing of these components, rather, I attempt to provide an overview as I myself have lacked during my time investigating programming languages. Thus, read this as an introduction to the magical world of extensibility. Through a literature review, I identify key extensibility themes - Macros, Modules, Types, and Reflection - highlighting diverse strategies for fostering extensibility. The analysis extends to cross-theme properties such as Parametricism and First-class citizen behaviour, introducing layers of complexity by highlighting the importance of customizability and flexibility in programming language constructs. By outlining these facets of existing programming languages and research, I aim to inspire future language designers to assess and consider the extensibility of their creations critically
Voting Under Pressure: Perceptions of Counter-Strategies in Internet Voting
Get PDFWhile internet voting can enhance democratic participation, concerns about voter coercion have emerged due to the uncontrolled voting environment. To mitigate this, researchers have proposed different types of counter-strategies, allowing voters to cast their intended vote despite being coerced. We conduct semi-structured interviews (N = 26) to investigate voters’ perceptions of six types of counter-strategies concerning their effectiveness. Our findings show that the voter’s perception of the effectiveness of counter-strategies depends on both the technical and personal skills of voters, concrete risks, and ease of use. Overall, our findings pave the way for future research aimed at developing user-friendly solutions that are effective against voter coercion.<br/
Apache Wayang in Action: Enabling Data Systems Integration via a Unified Data Analytics Framework.
No full textApache Wayang is an open-source framework, which provides a systematic and efficient solution for unifying data analytics over disparate data sources and via integrating multiple heterogeneous data systems. It achieves that by decoupling applications from the underlying systems. In addition, it provides an optimizer so that users do not have to specify the platforms on which their pipeline should run but the optimizer can determine the best way given a cost metric. In this demonstration, we showcase how the flexible architecture of Wayang enables seamless integration with multiple heterogeneous data systems and how the query optimizer can lead to better performance
Dream content discovery from social media using natural language processing
Get PDFDreaming is a fundamental but not fully understood part of human experience. Traditional dream content analysis practices, while popular and aided by over 130 unique scales and rating systems, have limitations. Often based on retrospective surveys or lab studies, and sometimes on in-home dream reports collected over some days, they struggle to be applied on a large scale or to show the importance and connections between different dream themes. To overcome these issues, we conducted data-driven mixed-method analysis identifying topics in free-form dream reports through natural language processing. We applied this analysis on 44,213 dream reports from Reddit’s r/Dreams subreddit, where we uncovered 217 topics, grouped into 22 larger themes: the most extensive collection of dream topics to date. We validated our topics by comparing it to the widely-used Hall and van de Castle scale. Going beyond traditional scales, our method can find unique patterns in different dream types (like nightmares or recurring dreams), understand topic importance and connections (like finding a greater predominance of indoor location settings in Reddit dreams than what was in general stipulated by previous work), and observe changes in collective dream experiences over time and around major events (like the COVID-19 pandemic and the recent Russo-Ukrainian war). We envision that the applications of our method will provide valuable insights into the complex nature of dreaming and its interplay with our waking experiences
Counting Small Induced Subgraphs: Hardness via Fourier Analysis
No full textFor a fixed graph property Φ and integer k ≥ 1, consider the problem of counting the induced k-vertex subgraphs satisfying Φ in an input graph G. This problem can be solved by brute-force in time O (nk ). Under ETH, we prove several lower bounds on the optimal exponent in this running time.If Φ is edge-monotone (i.e., closed under deleting edges), then ETH rules out no(k ) time algorithms for this problem. This strengthens a recent lower bound by Döring, Marx and Wellnitz [STOC 2024]. Our result also holds for counting modulo fixed primes. If at most graphs on k vertices satisfy Φ, for some ε > 0, then ETH rules out an exponent of . This holds even when the graphs in Φ have arbitrary individual weights, generalizing previous results for hereditary properties by Focke and Roth [SIAM J. Comput. 2024] up to a factor in the exponent.If Φ only depends on the number of edges, then the optimal exponent under ETH is Ω(k ). This improves on an lower bound by Roth, Schmitt and Wellnitz [FOCS 2020].In all cases, we also obtain #W[1]-hardness if k is part of the input and considered as the parameter. We also obtain lower bounds on the Weisfeiler-Leman dimension.Our results follow from relatively straightforward Fourier analysis, as opposed to the nontrivial techniques from combinatorics, group theory, and simplicial topology used in previous papers. Our paper subsumes most of the known #W[1]-hardness results known in the area, often with tighter lower bounds under ETH