26838 research outputs found
Sort by
Solving equations using Khovanskii bases
Get PDFWe develop a new eigenvalue method for solving structured polynomial equations over any field. The equations are defined on a projective algebraic variety which admits a rational parameterization by a Khovanskii basis, e.g., a Grassmannian in its Plücker embedding. This generalizes established algorithms for toric varieties, and introduces the effective use of Khovanskii bases in computer algebra. We investigate regularity questions and discuss several applications
Marrying math and mind: towards production planning systems for industry 5.0
Get PDFHow can a sophisticated Production Planning (PP) system help planners? To answer this question, we study the PP literature and focus on human-system interaction. We find that the PP literature mainly focuses on designing sophisticated algorithms. By synthesising forecasting and information system (IS) literature, we provide findings for designing a human-centred PP system. From the forecasting literature, we learn that certain biases and heuristics become relevant when humans work with systems. We categorise this literature into three system elements: information received, delivery system, and decision aid provided, as well as two human factors: cognitive limitations and capabilities. From the IS literature, we learn that different factors impact behaviour over the system acceptance and continued use phases. Behaviour is mainly impacted by the Perceived Ease of Use in the acceptance phase. The Perceived Usefulness mainly determines interventions to the solutions in the continued use phase. We combine the two phases distinguished in the IS literature with the three system elements distinguished in the forecasting literature and thus propose a two-phase × three-element matrix for designing human-centred systems, obtain findings that serve as guidelines for designing human-centred PP systems, and propose an agenda for future research in PP
Static X-ray CT of various brands of spaghetti noodles
No full textThe dataset consists of a scan of 4 various pasta bundles of different brands (Albert Heijn - Spelt, Albert Heijn - Durum, DeCecco, Gran Italia) placed inside a bottle. The pasta was suspended at the bottleneck using a sponge to hold it in position. Scanning was focused on the bottleneck region. This scan was performed under static conditions: the pasta is suspended in air. The dynamic counterpart of a spaghetti pasta can be found here: https://zenodo.org/records/15688351">10.5281/zenodo.1568835
Faster approximate elastic-degenerate string matching – Part B
Get PDFWe revisit the complexity of approximate pattern matching in an elastic-degenerate string. Such a string is a sequence of finite sets of strings of total length , and compactly describes a collection of strings obtained by first choosing exactly one string in every set, and then concatenating them together. This is motivated by the need of storing a collection of highly similar DNA sequences. The basic algorithmic question on elastic-degenerate strings is pattern matching: given such an elastic-degenerate string and a standard pattern of length , check if the pattern occurs in one of the strings in the described collection. Bernardini et al. [SICOMP 2022] showed how to leverage fast matrix multiplication to obtain an -time complexity for this problem, where is the matrix multiplication exponent. However, from the point of view of possible applications, it is more desirable to work with approximate pattern matching, where we seek approximate occurrences of the pattern. This generalization has been considered in a few papers already, but the best result so far for occurrences with mismatches, where is a constant, is the -time algorithm presented in Part A [CPM 2025]. This brings the question whether increasing the dependency on from to quadratic is necessary when moving from to larger (but still constant) . We design an -time algorithm for pattern matching with mismatches in an elastic-degenerate string, for any constant . To obtain this time bound, we leverage the structural characterization of occurrences with mismatches of Charalampopoulos, Kociumaka, and Wellnitz [FOCS 2020] together with fast Fourier transform. We need to work with multiple patterns at the same time, instead of a single pattern, which requires refining the original characterization. This might be of independent interest
Image analysis of patient data from the hybrid photoacoustic-ultrasound tomography system PAM3
Get PDFThe PAM3 system is a hybrid photoacoustic-ultrasound system for imaging the breast. The ultrasound mode enables extraction of speed-of-sound (SOS) maps that can be used to improve photoacoustic (PA) reconstruction. SOS holds information that can be used potentially for tissue characterization and discrimination. PA computed tomography images were reconstructed using an iterative model-based optimization framework. An image analysis pipeline has been developed to analyze the PA/US images and compare them with contrast-enhanced Magnetic Resonance (ceMR) images. We imaged patients using PAM3 in a study approved by the Medical Ethics Review Board. Patients with a tumor suspicious for malignancy, based on conventional diagnostic imaging, were asked to participate. All patients received X-ray mammography, ultrasound imaging and ceMR imaging. The preliminary results on a patient with a fibroadenoma demonstrate that combining multi-wavelength PA and sound speed imaging is potentially valuable for visualizing breast cancer. From PA we obtain functional information with sound speed providing structural information
Scalable reinforcement learning for large-scale coordination of electric vehicles using graph neural networks
Get PDFAs the adoption of electric vehicles (EVs) accelerates, addressing the challenges of large-scale, city-wide optimization becomes critical in ensuring efficient use of charging infrastructure and maintaining electrical grid stability. This study introduces EV-GNN, a novel graph-based solution that addresses scalability challenges and captures uncertainties in EV behavior from a Charging Point Operator’s (CPO) perspective. We prove that EV-GNN enhances classic Reinforcement Learning (RL) algorithms’ scalability and sample efficiency by combining an end-to-end Graph Neural Network (GNN) architecture with RL and employing a branch pruning technique. We further demonstrate that the proposed architecture’s flexibility allows it to be combined with most state-of-the-art deep RL algorithms to solve a wide range of problems, including those with continuous, multi-discrete, and discrete action spaces. Extensive experimental evaluations show that EV-GNN significantly outperforms state-of-the-art RL algorithms in scalability and generalization across diverse EV charging scenarios, delivering notable improvements in both small- and large-scale problems
Indexing strings with utilities
No full textApplications in domains ranging from bioinformatics to advertising feature strings (sequences of letters over some alphabet) that come with numerical scores (utilities). The utilities quantify the importance, interest, profit, or risk of the letters occurring at every position of a string. For instance, DNA fragments generated by sequencing machines come with a confidence score per position. Motivated by the ever-increasing rate of generating such data, as well as by their importance in several domains, we introduce Useful String Indexing (USI), a natural generalization of the classic String Indexing problem. Given a string (the text) of length , USI asks for preprocessing into a compact data structure supporting the following queries efficiently: given a shorter string (the pattern), return the global utility of in , where is a function that maps any string to a utility score based on the utilities of the letters of every occurrence of in . Our work also makes the following contributions: (1) We propose a novel and efficient data structure for USI based on finding the top- frequent substrings of . (2) We propose a linear-space data structure that can be used to mine the top- frequent substrings of or to tune the parameters of the USI data structure. (3) We propose a novel space-efficient algorithm for estimating the set of the top- frequent substrings of , thus improving the construction space of the data structure for USI. (4) We show that popular space-efficient top- frequent item mining strategies employed by state-of-the-art algorithms do not smoothly translate from items to substrings. (5) Using billion-letter datasets, we experimentally demonstrate that: (i) our top- frequent substring mining algorithms are accurate and scalable, unlike two state-of-the-art methods; and (ii) our USI data structures are up to 15 times faster in querying than 4 nontrivial baselines while occupying the same space with them
Solving free fermion problems on a quantum computer
Get PDFSimulating noninteracting fermion systems is a common task in computational many-body physics. In the absence of translational symmetries, modeling free fermions on N modes usually requires poly(N) computational resources. While often moderate, these costs can be prohibitive in practice when large systems are considered. We present several free fermion problems that can be solved by a quantum algorithm with substantially reduced computational costs. The memory costs are exponentially improved, polylog(N). The run-time improvement, compared to the best known classical algorithms, is either exponential or significantly polynomial, depending on the geometry of the problem. The simulation of free fermion dynamics belongs to the BQP-hard complexity class (i.e., as hard as any (decision) problem that can be solved on a quantum computer). This implies (under standard assumptions) that our algorithm yields an exponential speedup for any classical algorithm at least for some geometries. The key technique in our algorithm is the block encoding of objects such as correlation matrices and Green's functions into a unitary. We demonstrate how such unitaries can be efficiently realized as quantum circuits, in the context of dynamics and thermal states of tight-binding Hamiltonians. The special cases of disordered and inhomogeneous lattices, as well as large nonlattice graphs, are presented in detail. Finally, we show that our simulation algorithm generalizes to other promising targets, including free-boson systems
Haptic biosignals affect proxemics toward virtual reality agents
Get PDFEncounters with virtual agents currently lack the haptic viscerality of human contact. While digital biosignal communication can mediate such virtual social interactions, how artificial haptic biosignals influence users’ personal space during Virtual Reality (VR) experiences is unknown. Designing vibrotactile heartbeats and thermally-actuated body temperature, we ran a within-subjects study (N=31) to investigate feedback (Thermal, Vibration, Thermal+Vibration, None) and agent stories (Negative, Neutral, Positive) on objective and subjective interpersonal distance (IPD), perceived arousal and comfort, presence, and post-experience responses. Findings showed that thermal feedback decreased objective but not subjective IPD, whereas vibrotactile heartbeats (signaling agent’s closeness) increased both while heightening arousal and discomfort. Agents’ stories did not affect IPD, arousal, or comfort. Our qualitative findings shed light on signal ambiguity and presence constructs within VR-based haptic stimulation. We contribute insights into artificial biosignals and their influence on VR proxemics, with cautionary considerations should the boundaries blur between physical and virtual touch