9607 research outputs found
Sort by
Monotone Bounded-Depth Complexity of Homomorphism Polynomials
No full textFor every fixed graph H, it is known that homomorphism counts from H and colorful H-subgraph counts can be determined in O(n^{t+1}) time on n-vertex input graphs G, where t is the treewidth of H. On the other hand, a running time of n^{o(t / log t)} would refute the exponential-time hypothesis. Komarath, Pandey, and Rahul (Algorithmica, 2023) studied algebraic variants of these counting problems, i.e., homomorphism and subgraph polynomials for fixed graphs H. These polynomials are weighted sums over the objects counted above, where each object is weighted by the product of variables corresponding to edges contained in the object. As shown by Komarath et al., the monotone circuit complexity of the homomorphism polynomial for H is Θ(n^{tw(H)+1}).In this paper, we characterize the power of monotone bounded-depth circuits for homomorphism and colorful subgraph polynomials. This leads us to discover a natural hierarchy of graph parameters tw_Δ(H), for fixed Δ ∈ ℕ, which capture the width of tree-decompositions for H when the underlying tree is required to have depth at most Δ. We prove that monotone circuits of product-depth Δ computing the homomorphism polynomial for H require size Θ(n^{tw_Δ(H^{†})+1}), where H^{†} is the graph obtained from H by removing all degree-1 vertices. This allows us to derive an optimal depth hierarchy theorem for monotone bounded-depth circuits through graph-theoretic arguments
Three-dimensional directivity measurement of acoustic diffusers using regularized holography and sound field separation
No full textCharacterizing acoustic diffusers poses significant challenges due to the complex space-time dependence of the scattered sound fields they generate. This study proposes using regularized plane wave expansion to measure real-sized rigid diffusers in free-field. The formulated inverse problem enables the separation of incident and scattered sound fields in the wave-number domain. Furthermore, a tailored wave-number grid facilitates the computation of three-dimensional directivities directly identified in the wave-number spectrum. The proposed technique is validated through measurements conducted in the near field of three diffusers with distinct geometries. The results obtained from regularized plane wave expansion were compared against reference simulations using the Boundary Element Method. The unique directivity characteristics of different diffusers are accurately characterized, and good agreement is found with the reference simulations. The use of finer spatial resolution and -octave band averaging further improves the reliability of directivity and diffusion coefficient estimates. Thus, the method provides an alternative path for a robust and more practical characterization of acoustic diffusers
Heterogeneous object manipulation on nonlinear soft surface through linear controller
No full textManipulation surfaces indirectly control and reposition objects by actively modifying their shape or properties rather than directly gripping objects. These surfaces, equipped with dense actuator arrays, generate dynamic deformations. However, a high-density actuator array introduces considerable complexity due to increased degrees of freedom (DOF), complicating control tasks. High DOF restrict the implementation and utilization of manipulation surfaces in real-world applications as the maintenance and control of such systems exponentially increase with array/surface size. Learning-based control approaches may ease the control complexity, but they require extensive training samples and struggle to generalize for heterogeneous objects. In this study, we introduce a simple, precise and robust PID-based linear close-loop feedback control strategy for heterogeneous object manipulation on MANTA-RAY (Manipulation with Adaptive Non-rigid Textile Actuation with Reduced Actuation density). Our approach employs a geometric transformation-driven PID controller, directly mapping tilt angle control outputs(1D/2D) to actuator commands to eliminate the need for extensive black-box training. We validate the proposed method through simulations and experiments on a physical system, successfully manipulating objects with diverse geometries, weights and textures, including fragile objects like eggs and apples. The outcomes demonstrate that our approach is highly generalized and offers a practical and reliable solution for object manipulation on soft robotic manipulation, facilitating real-world implementation without prohibitive training demands
Impact of the Perceived System Bias and Type of AI Explanations on Decision-Making Effectiveness in Explainable AI Systems: Cognitive and Emotional Mechanisms
No full textArtificial intelligence (AI)-based decision-making systems have been shown to outperform humans. However, in critical decision-making domains like healthcare, human decision-makers often mistrust and are reluctant to follow the recommendations of black-box AI systems because they perceive the system to be biased. This study aims to advance AI for social good by illuminating the mechanisms by which perceived bias in AI systems affects users’ decision-making effectiveness and how different explanation types mitigate these effects. Drawing from Dual-Process Theory and Theory of Effective Use, we propose two mechanisms that mediate the effects of perceived system bias in explainable AI systems: a cognitive mechanism of learning and an emotional mechanism of anticipated regret. Our study found that the cognitive mechanism of learning primarily mediates the relationship between perceived system bias and decision-making effectiveness, and feature importance explanations mitigate the negative effects of perceived system bias more effectively than counterfactual explanations
Bridging the Information Systems Literature on Digital Sourcing, Platforms, and Ecosystems
Get PDFThis chapter bridges two foundational streams in Information Systems (IS) research: digital sourcing and digital platform ecosystems. Historically treated as distinct, these domains are increasingly converging due to shifts in technology, organizational strategy, and ecosystem dynamics. Digital sourcing has evolved from cost-efficiency and capability access toward innovation and agility, while digital platforms have matured into orchestrated ecosystems enabling third-party value creation. The chapter outlines key theoretical foundations shared across both streams and identifies three core areas of convergence: governance, relationships, and knowledge and innovation. The chapter proposes future research directions, including hybrid governance models, algorithmic orchestration, and integrative learning frameworks, and lays the groundwork for a unified perspective on how organizations leverage external actors and technologies in the digital age. This conceptual bridge offers a foundation for advancing theory and informing practice in increasingly platform-based and sourcing-dependent ecosystems
Urban Mobility
No full textIn this chapter, we discuss urban mobility from a complexity science perspective. First, we give an overview of the datasets that enable this approach, such as mobile phone records, location-based social network traces, or GPS trajectories from sensors installed on vehicles. We then review the empirical and theoretical understanding of the properties of human movements, including the distribution of travel distances and times, the entropy of trajectories, and the interplay between exploration and exploitation of locations. Next, we explain generative and predictive models of individual mobility, and their limitations due to intrinsic limits of predictability. Finally, we discuss urban transport from a systemic perspective, including system-wide challenges like ridesharing, multimodality, and sustainable transport
Declarative Dynamic Object Reclassification
No full textIn object-oriented languages, dynamic object reclassification is a technique to change the class binding of an object at runtime. Current approaches express when and how to reclassify inside the program’s business code, while maintaining internal consistency. These approaches are less suited for programs that need to be consistent with an external context, such as autonomous systems interacting with a knowledge base. This paper proposes declarative dynamic object reclassification, a novel technique that provides a separation of concerns between a program’s business code and its adaptation logic for reclassification, expressed via a knowledge base. We present Featherweight Semantically Reflected Java, a minimal calculus for declarative dynamic object reclassification that enables the programmer to define consistency both internally (using a type system) and externally (using declarative classification queries). We use this calculus to study how internal and external consistency interact for declarative dynamic object reclassification. We further implement the technique by extending SMOL, a language for reflective programming via external knowledge bases
Proceedings of 23th EUSSET Conference on Computer-Supported Cooperative Work
Get PDFThe ‘Reports of the European Society for Socially Embedded Technologies’ are an online report series of the European Society for Socially Embedded Technologies (EUSSET). They aim to contribute to current research discourses in the fields of ‘Computer-Supported Cooperative Work’, ‘Human-Computer-Interaction’ and ‘Computers and Society’. The ‘Reports of the European Society for Socially Embedded Technologies’ appear at least one time per year and are exclusively published in the Digital Library of EUSSET (https://dl.eusset.eu/). The main language of publication is English
Exploring Socio-Visual Dimensions of Input Visualization
No full textWe introduce the concept of socio-visual dimensions in data visualization, referring to the nuanced interplay between social and visual dimensions in people’s interactions with visualizations. From this, we discuss how input visualizations include implicit social dimensions that can be further explored and leveraged as part of a socially motivated research agenda for data visualization. Visualization researchers and designers create visual representations of data, often with the intent to inspire people to act for the greater good. Yet, research has only engaged in a limited sense with how to design with such intent and how people respond to these socially motivated visualizations. Understanding the socio-visual dimensions is crucial for addressing global challenges like climate change and public health crises, where collective action depends on fostering togetherness, a sense of community, and pro-social behaviour
