9607 research outputs found
Sort by
Algorithms for the Diverse-k-SAT Problem: The Geometry of Satisfying Assignments.
No full textGiven a k-CNF formula and an integer s ≥ 2, we study algorithms that obtain s solutions to the formula that are as dispersed as possible. For s = 2, this problem of computing the diameter of a k-CNF formula was initiated by Creszenzi and Rossi, who showed strong hardness results even for k = 2. The current best upper bound [Angelsmark and Thapper’04] goes to 4n as k → ∞. As our first result, we show that this quadratic blow up is not necessary by utilizing the Fast-Fourier transform (FFT) to give a O*(2n) time exact algorithm for computing the diameter of any k-CNF formula. For s > 2, the problem was raised in the SAT community (Nadel’11) and several heuristics have been proposed for it, but no algorithms with theoretical guarantees are known. We give exact algorithms using FFT and clique-finding that run in O*(2(s−1)n) and O*(s2|ΩF|ω⌈s/3⌉) respectively, where |ΩF| is the size of the solutions space of the formula F and ω is the matrix multiplication exponent. However, current SAT algorithms for finding one solution run in time O*(2εkn) for εk ≈ 1−Θ(1/k), which is much faster than all above run times. As our main result, we analyze two popular SAT algorithms - PPZ (Paturi, Pudlák, Zane’97) and Schöning’s (’02) algorithms, and show that in time poly(s)O*(2εkn), they can be used to approximate diameter as well as the dispersion (s > 2) problem. While we need to modify Schöning’s original algorithm for technical reasons, we show that the PPZ algorithm, without any modification, samples solutions in a geometric sense. We believe this geometric sampling property of PPZ may be of independent interest. Finally, we focus on diverse solutions to NP-complete optimization problems, and give bi-approximations running in time poly(s)O*(2εn) with ε < 1 for several problems such as Maximum Independent Set, Minimum Vertex Cover, Minimum Hitting Set, Feedback Vertex Set, Multicut on Trees and Interval Vertex Deletion. For all of these problems, all existing exact methods for finding optimal diverse solutions have a runtime with at least an exponential dependence on the number of solutions s. Our methods show that by relaxing to bi-approximations, this dependence on s can be made polynomial
Reminiscences on Influential Papers.
No full textThis issue's contributors cover papers that focus on different aspects of accessing data: RDFs, approximate nearest neighbor search, and compact hash tables. Furthermore, they all highlight the impact of the papers not only on their own research and career but also for the community in general. Enjoy reading!While I will keep inviting members of the data management community, and neighboring communities, to contribute to this column, I also welcome unsolicited contributions. Please contact me if you are interested
On Dependencies in Knowledge Graph Construction
No full textKnowledge graph construction (KGC) requires numerous assets, such as shapes or mappings, to interact correctly.However, maintenance and assessment of the quality of the pipeline implementing the construction is difficult, assoftware engineering analyses and quality measures do not address the technologies used in KGC. In this paper,we propose a syntactic, easy to compute notion of dependencies between assets, and show its capability to assesschange propagation. Furthermore, we discuss potential to use it for coupling and impact estimation. We evaluateour approach using a prototypical implementation and a case study from the literature, where we find two bugswhere missing dependencies indicated an error due to miscommunication during change propagation betweenthe developers of two different assets
De-centering the (Traditional) user: Multistakeholder evaluation of recommender systems
No full textMultistakeholder recommender systems are those that account for the impacts and preferences of multiple groups of individuals, not just the end users receiving recommendations. Due to their complexity, these systems cannot be evaluated strictly by the overall utility of a single stakeholder, as is often the case of more mainstream recommender system applications. In this article, we focus our discussion on the challenges of multistakeholder evaluation of recommender systems. We bring attention to the different aspects involved—from the range of stakeholders involved (including but not limited to providers and consumers) to the values and specific goals of each relevant stakeholder. We discuss how to move from theoretical principles to practical implementation, providing specific use case examples. Finally, we outline open research directions for the RecSys community to explore. We aim to provide guidance to researchers and practitioners about incorporating these complex and domain-dependent issues of evaluation in the course of designing, developing, and researching applications with multistakeholder aspects
Exploring the Zero-Shot Known-Item Retrieval Capabilities of LLMs for Casual Leisure Information Needs
No full textThe rapidly increasing popularity of LLM-powered chatbots has led to them being used for a increasing number of different tasks by the general public. One of these tasks is searching for information instead of using a search engine. Previous work has shown that complex search tasks can be problematic for traditional search engines to solve, but little is known about the capability of LLMs on the same task. We compared four LLMs on their capability to answer a specific type of complex search task: known-item requests from casual leisure domains. We constructed a test collection by gathering known-item requests for books, games and movies from online forums along with verified answers by the original requester. We prompted four LLMs multiple times with the same prompt and analyzed the results with respect to accuracy and the degree to which answers were fabricated by the LLM. Our results show that LLMs are not particularly effective in fulfilling these complex casual leisure needs, but there are are big differences between LLMs and across domains.<br/
Leadership in the Age of AI – Exploring Managerial AI-Enabled People Leadership in Practice
No full textThis poster abstract reports from a literature review on managerial use of AI for people leadership purposes identifying a research gap in our understanding of the lived practice of AI-usage for personnel related aspects of the leadership role in theory and practice. Although AI-assisted leadership is still in its infancy, larger corporations already adopt algorithmic leadership practices, emphasizing the need to explore and capture these developments in the expectation of widespread adoption in the (near) future. We report from the identification and analysis of a corpus of 66 research articles, identifying core themes including trust, flexibility, and correspondence with existing work tasks, pointing out limitations as well as highlighting implications for future research. We wish to ignite an all-inclusive debate on the exploration of AI-augmented leadership using our poster as a springboard for knowledge sharing and network building. We believe that the topic is interesting to both CTO-members and academy members generally. To lead traffic to our poster, small flyers will be handed out at the conference, and a short digital visitor survey will be administered to capture insights (accessible through QR code when poster is not staffed) and invite to post-poster networking.<br/
The Password You Hope You Never Use: Use Cases for Duress Authentication
Get PDFWhile passwords are the most widely used method of authentication, concerns about duress attacks have emerged because attackers are motivated to gain access to our sensitive data. To mitigate this, researchers have proposed duress passwords, allowing users to signal to a system that they are under duress silently. We conduct a survey ( = 281) to investigate users’ perceptions of potential use cases for duress passwords. Our findings show that users perceive critical societal systems and institutions as use cases due to potentially high consequences of a successful duress attack. Further, they consider personal accounts, such as banking, to benefit from implementing duress passwords. Overall, our findings pave the way for future research aimed at developing solutions effective against duress attacks
Causal modeling of climate activism on Reddit
Get PDFClimate activism is crucial in stimulating collective societal and behavioral change towards sustainable practices through political pressure. Although multiple factors contribute to the participation in activism, their complex relationships and the scarcity of data on their interactions have restricted most prior research to studying them in isolation, thus preventing the development of a quantitative, causal understanding of why people approach activism. In this work, we develop a comprehensive causal model of how and why Reddit users engage with activist communities driving mass climate protests (mainly the 2019 Earth Strike, Fridays for Future, and Extinction Rebellion). Our framework, based on Stochastic Variational Inference applied to Bayesian Networks, learns the causal pathways over multiple time periods. Distinct from previous studies, our approach uses large-scale and fine-grained longitudinal data (2016 to 2022) to jointly model the roles of sociodemographic makeup, experience of extreme weather events, exposure to climate-related news, and social influence through online interactions. We find that among users interested in climate change, participation in online activist communities is indeed influenced by direct interactions with activists and largely by recent exposure to media coverage of climate protests. Among people aware of climate change, left-leaning people from lower socioeconomic backgrounds are particularly represented in online activist groups. Our findings offer empirical validation for theories of media influence and critical mass, and lay the foundations to inform interventions and future studies to foster public participation in collective action
Multiparty Asynchronous Session Types: A Mechanised Proof of Subject Reduction.
No full textSession types offer a type-based approach to describing the message exchange protocols between participants in communication-based systems. Initially, they were introduced in a binary setting, specifying communication patterns between two components. With the advent of multiparty session types (MPST), the typing discipline was extended to arbitrarily many components. In MPST, communication patterns are given in terms of global types, an Alice-Bob notation that gives a global view of how components interact. A central theorem of MPST is subject reduction: a well-typed system remains well-typed after reduction. The literature contains some formulations of MPST with proofs of subject reduction that have later been shown to be incorrect. In this paper, we show that the subject reduction proof of the original formulation of MPST by Honda et al. contains some flaws. Additionally, we provide a restriction to the theory and show that, for this fragment, subject reduction does indeed hold. Finally, we use subject reduction to show that well-typed processes never go wrong. All of our proofs are mechanised using the Coq proof assistant
Can You Link Up With Treewidth?
No full textA central result by Marx [ToC '10] constructs k-vertex graphs H of maximum degree 3 such that n^o(k/log k) time algorithms for detecting colorful H-subgraphs would refute the Exponential-Time Hypothesis (ETH). This result is widely used to obtain almost-tight conditional lower bounds for parameterized problems under ETH.Our first contribution is a new and fully self-contained proof of this result that further simplifies a recent work by Karthik et al. [SOSA 2024]. In our proof, we introduce a novel graph parameter of independent interest, the linkage capacity γ(H), and show that detecting colorful H-subgraphs in time n^o(γ(H)) refutes ETH. Then, we use a simple construction of communication networks credited to Beneš to obtain k-vertex graphs of maximum degree 3 and linkage capacity Ω(k/log k), avoiding arguments involving expander graphs, which were required in previous papers. We also show that every graph H of treewidth t has linkage capacity Ω(t/log t), thus recovering a stronger result shown by Marx [ToC '10] with a simplified proof.Additionally, we obtain new tight lower bounds on the complexity of subgraph detection for certain types of patterns by analyzing their linkage capacity: We prove that almost all k-vertex graphs of polynomial average degree Ω(k^β) for β > 0 have linkage capacity Θ(k), which implies tight lower bounds for finding such patterns H. As an application of these results, we also obtain tight lower bounds for counting small induced subgraphs having a fixed property Φ, improving bounds from, e.g., [Roth et al., FOCS 2020]