Search

Understanding how linguistic knowledge is encoded in language models is crucial for improving their generalisation capabilities. In this paper, we investigate the processing of morphosyntactic phenomena, by leveraging a recently proposed method for probing language models via Shapley Head Values (SHVs). Using the English language BLiMP dataset, we test our approach on two widely used models, BERT and RoBERTa, and compare how linguistic constructions such as anaphor agreement and filler-gap dependencies are handled. Through quantitative pruning and qualitative clustering analysis, we demonstrate that attention heads responsible for processing related linguistic phenomena cluster together. Our results show that SHV-based attributions reveal distinct patterns across both models, providing insights into how language models organize and process linguistic information. These findings support the hypothesis that language models learn subnetworks corresponding to linguistic theory, with potential implications for cross-linguistic model analysis and interpretability in Natural Language Processing (NLP).

Query optimization is crucial for every database management system (DBMS) to enable fast execution of declarative queries. Most DBMS designs include cost-based query optimization. However, MongoDB implements a different approach to choose an execution plan that we call "first past the post" (FPTP) query optimization. FPTP does not estimate costs for each execution plan, but rather partially executes the alternative plans in a round-robin race and observes the work done by each relative to the number of records returned. In this paper, we analyze the effectiveness of MongoDB's FPTP query optimizer. We see whether the optimizer chooses the best execution plan among the alternatives and measure how the chosen plan compares to the optimal plan. We also show how to visualize the effectiveness and identify situations where the MongoDB 7.0.1 query optimizer chooses suboptimal query plans. Through experiments, we conclude that FPTP has a preference bias, choosing index scans even in many cases where collection scans would run faster. We identify the reasons for the preference bias, which can lead MongoDB to choose a plan with more than twice the runtime compared to the optimal plan for the query.

We study Multi-Agent Path Finding for arrangements of labeled agents in the interior of a simply connected domain: Given a unique start and target position for each agent, the goal is to find a sequence of parallel, collision-free agent motions that minimizes the overall time (the makespan) until all agents have reached their respective targets. A natural case is that of a simply connected polygonal domain with axis-parallel boundaries and integer coordinates, i.e., a simple polyomino, which amounts to a simply connected union of lattice unit squares or cells. We focus on the particularly challenging setting of densely packed agents, i.e., one per cell, which strongly restricts the mobility of agents, and requires intricate coordination of motion. We provide a variety of novel results for this problem, including (1) a characterization of polyominoes in which a reconfiguration plan is guaranteed to exist; (2) a characterization of shape parameters that induce worst-case bounds on the makespan; (3) a suite of algorithms to achieve asymptotically worst-case optimal performance with respect to the achievable stretch for cases with severely limited maneuverability. This corresponds to bounding the ratio between obtained makespan and the lower bound provided by the max-min distance between the start and target position of any agent and our shape parameters. Our results extend findings by Demaine et al. (SIAM Journal on Computing, 2019) who investigated the problem for solid rectangular domains, and in the closely related field of Permutation Routing, as presented by Alpert et al. (Computational Geometry, 2022) for convex pieces of grid graphs., Comment: 21 pages, 14 figures, full version of an extended abstract that is to appear in the proceedings of the 35th International Symposium on Algorithms and Computation (ISAAC 2024)

We predict Bose-Einstein condensation and superfluidity of dipolar excitons, formed by electron-hole pairs in spatially separated gapped hexagonal $\alpha-T_{3}$ (GHAT3) layers. In the $\alpha-T_{3}$ model, the AB-honeycomb lattice structure is supplemented with C atoms located at the centers of the hexagons in the lattice. We considered the $\alpha-T_{3}$ model in the presence of a mass term which opens a gap in the energy dispersive spectrum. The gap opening mass term, caused by a weak magnetic field, plays the role of Zeeman splitting at low magnetic fields for this pseudospin-1 system. The band structure of GHAT3 monolayers leads to the formation of two distinct types of excitons in the GHAT3 double layer. We consider two types of dipolar excitons in double-layer GHAT3: (a) ``A excitons'', which are bound states of electrons in the conduction band (CB) and holes in the intermediate band (IB) and (b) ``B excitons'', which are bound states of electrons in the CB and holes in the valence band (VB). The binding energy of A and B dipolar excitons is calculated. For a two-component weakly interacting Bose gas of dipolar excitons in a GHAT3 double layer, we obtain the energy dispersion of collective excitations, the sound velocity, the superfluid density, and the mean-field critical temperature $T_{c}$ for superfluidity., Comment: 17 pages, 14 figures

We investigate algorithmic approaches for targeted drug delivery in a complex, maze-like environment, such as a vascular system. The basic scenario is given by a large swarm of micro-scale particles (''agents'') and a particular target region (''tumor'') within a system of passageways. Agents are too small to contain on-board power or computation and are instead controlled by a global external force that acts uniformly on all particles, such as an applied fluidic flow or electromagnetic field. The challenge is to deliver all agents to the target region with a minimum number of actuation steps. We provide a number of results for this challenge. We show that the underlying problem is NP-complete, which explains why previous work did not provide provably efficient algorithms. We also develop several algorithmic approaches that greatly improve the worst-case guarantees for the number of required actuation steps. We evaluate our algorithmic approaches by numerous simulations, both for deterministic algorithms and searches supported by deep learning, which show that the performance is practically promising., Comment: 21 pages, 11 figures; full version of an extended abstract that appeared in the proceedings of the 37th IEEE International Conference on Robotics and Automation (ICRA 2020)

Mitotic activity is an important feature for grading several cancer types. Counting mitotic figures (MFs) is a time-consuming, laborious task prone to inter-observer variation. Inaccurate recognition of MFs can lead to incorrect grading and hence potential suboptimal treatment. In this study, we propose an artificial intelligence (AI)-aided approach to detect MFs in digitised haematoxylin and eosin-stained whole slide images (WSIs). Advances in this area are hampered by the limited number and types of cancer datasets of MFs. Here we establish the largest pan-cancer dataset of mitotic figures by combining an in-house dataset of soft tissue tumours (STMF) with five open-source mitotic datasets comprising multiple human cancers and canine specimens (ICPR, TUPAC, CCMCT, CMC and MIDOG++). This new dataset identifies 74,620 MFs and 105,538 mitotic-like figures. We then employed a two-stage framework (the Optimised Mitoses Generator Network (OMG-Net) to classify MFs. The framework first deploys the Segment Anything Model (SAM) to automate the contouring of MFs and surrounding objects. An adapted ResNet18 is subsequently trained to classify MFs. OMG-Net reaches an F1-score of 0.84 on pan-cancer MF detection (breast carcinoma, neuroendocrine tumour and melanoma), largely outperforming the previous state-of-the-art MIDOG++ benchmark model on its hold-out testing set (e.g. +16% F1-score on breast cancer detection, p<0.001) thereby providing superior accuracy in detecting MFs on various types of tumours obtained with different scanners.

We study the Dispersive Art Gallery Problem with vertex guards: Given a polygon $\mathcal{P}$, with pairwise geodesic Euclidean vertex distance of at least $1$, and a rational number $\ell$; decide whether there is a set of vertex guards such that $\mathcal{P}$ is guarded, and the minimum geodesic Euclidean distance between any two guards (the so-called dispersion distance) is at least $\ell$. We show that it is NP-complete to decide whether a polygon with holes has a set of vertex guards with dispersion distance $2$. On the other hand, we provide an algorithm that places vertex guards in simple polygons at dispersion distance at least $2$. This result is tight, as there are simple polygons in which any vertex guard set has a dispersion distance of at most $2$., Comment: 13 pages, 14 figures; accepted at the 36th Canadian Conference on Computational Geometry (CCCG 2024)

We propose reconstruction advantage measures to audit label privatization mechanisms. A reconstruction advantage measure quantifies the increase in an attacker's ability to infer the true label of an unlabeled example when provided with a private version of the labels in a dataset (e.g., aggregate of labels from different users or noisy labels output by randomized response), compared to an attacker that only observes the feature vectors, but may have prior knowledge of the correlation between features and labels. We consider two such auditing measures: one additive, and one multiplicative. These incorporate previous approaches taken in the literature on empirical auditing and differential privacy. The measures allow us to place a variety of proposed privatization schemes -- some differentially private, some not -- on the same footing. We analyze these measures theoretically under a distributional model which encapsulates reasonable adversarial settings. We also quantify their behavior empirically on real and simulated prediction tasks. Across a range of experimental settings, we find that differentially private schemes dominate or match the privacy-utility tradeoff of more heuristic approaches.

With the advent of novel cancer treatment options such as immunotherapy, studying the tumour immune micro-environment is crucial to inform on prognosis and understand response to therapeutic agents. A key approach to characterising the tumour immune micro-environment may be through combining (1) digitised microscopic high-resolution optical images of hematoxylin and eosin (H&E) stained tissue sections obtained in routine histopathology examinations with (2) automated immune cell detection and classification methods. However, current individual immune cell classification models for digital pathology present relatively poor performance. This is mainly due to the limited size of currently available datasets of individual immune cells, a consequence of the time-consuming and difficult problem of manually annotating immune cells on digitised H&E whole slide images. In that context, we introduce Immunocto, a massive, multi-million automatically generated database of 6,848,454 human cells, including 2,282,818 immune cells distributed across 4 subtypes: CD4$^+$ T cell lymphocytes, CD8$^+$ T cell lymphocytes, B cell lymphocytes, and macrophages. For each cell, we provide a 64$\times$64 pixels H&E image at $\mathbf{40}\times$ magnification, along with a binary mask of the nucleus and a label. To create Immunocto, we combined open-source models and data to automatically generate the majority of contours and labels. The cells are obtained from a matched H&E and immunofluorescence colorectal dataset from the Orion platform, while contours are obtained using the Segment Anything Model. A classifier trained on H&E images from Immunocto produces an average F1 score of 0.74 to differentiate the 4 immune cell subtypes and other cells. Immunocto can be downloaded at: https://zenodo.org/uploads/11073373.

Azimuthal orientation and handedness dependence of the optical responses, accompanied by asymmetric transmission and asymmetric dichroism, were demonstrated on multilayers constructed with subwavelength periodic arrays of Babinet complementary miniarrays, illuminated by linearly and circularly polarized light. In case of single-sided illumination asymmetric optical responses were observed at the spectral location of maximal cross-polarization that is accompanied by radiative electric dipoles on the nano-objects; whereas negative index material phenomenon was demonstrated, where the electric and magnetic dipoles overlap both spatially and spectrally. The NIM is accompanied by electric multipoles that add up non-radiatively and correlates with the magnetic dipoles characteristic on the nano-entities. By illuminating the multilayer with two counter-propagating circularly polarized beams it was proven that asymmetrical normal component displacement currents at the bounding interfaces arising along flat and tilted bands accompany the asymmetric co-polarized and cross-polarized transmission, respectively. The latter correlates with the asymmetric dichroism in the cross-polarized signal observed in case of single-sided circularly polarized light illumination. The dispersion maps in the single-sided asymmetrical co-polarized reflectance and absorptance indicate flat bands of analogous and complementary extrema, proving the dichroic nature of the observed asymmetric phenomena. The multilayer is proposed as an ultrathin NIM and nonreciprocal nanophotonic element.

We explore the design space for the static visualization of datasets with quantitative attributes that vary over multiple orders of magnitude-we call these attributes Orders of Magnitude Values (OMVs)-and provide design guidelines and recommendations on effective visual encodings for OMVs. Current charts rely on linear or logarithmic scales to visualize values, leading to limitations in performing simple tasks for OMVs. In particular, linear scales prevent the reading of smaller magnitudes and their comparisons, while logarithmic scales are challenging for the general public to understand. Our design space leverages the approach of dividing OMVs into two different parts: mantissa and exponent, in a way similar to scientific notation. This separation allows for a visual encoding of both parts. For our exploration, we use four datasets, each with two attributes: an OMV, divided into mantissa and exponent, and a second attribute that is nominal, ordinal, time, or quantitative. We start from the original design space described by the Grammar of Graphics and systematically generate all possible visualizations for these datasets, employing different marks and visual channels. We refine this design space by enforcing integrity constraints from visualization and graphical perception literature. Through a qualitative assessment of all viable combinations, we discuss the most effective visualizations for OMVs, focusing on channel and task effectiveness. The article's main contributions are 1) the presentation of the design space of OMVs, 2) the generation of a large number of OMV visualizations, among which some are novel and effective, 3) the refined definition of a scale that we call E+M for OMVs, and 4) guidelines and recommendations for designing effective OMV visualizations. These efforts aim to enrich visualization systems to better support data with OMVs and guide future research.

We give an overview of the 2024 Computational Geometry Challenge targeting the problem \textsc{Maximum Polygon Packing}: Given a convex region $P$ in the plane, and a collection of simple polygons $Q_1, \ldots, Q_n$, each $Q_i$ with a respective value $c_i$, find a subset $S \subseteq \{1, \ldots,n\}$ and a feasible packing within $P$ of the polygons $Q_i$ (without rotation) for $i \in S$, maximizing $\sum_{i \in S} c_i$. Geometric packing problems, such as this, present significant computational challenges and are of substantial practical importance., Comment: 16 pages, 10 figures

Modern Web APIs allow developers to provide extensively customized experiences for website visitors, but the richness of the device information they provide also make them vulnerable to being abused to construct browser fingerprints, device-specific identifiers that enable covert tracking of users even when cookies are disabled. Previous research has established entropy, a measure of information, as the key metric for quantifying fingerprinting risk. However, earlier studies had two major limitations. First, their entropy estimates were based on either a single website or a very small sample of devices. Second, they did not adequately consider correlations among different Web APIs, potentially grossly overestimating their fingerprinting risk. We provide the first study of browser fingerprinting which addresses the limitations of prior work. Our study is based on actual visited pages and Web APIs reported by tens of millions of real Chrome browsers in-the-wild. We accounted for the dependencies and correlations among Web APIs, which is crucial for obtaining more realistic entropy estimates. We also developed a novel experimental design that accurately and efficiently estimates entropy while never observing too much information from any single user. Our results provide an understanding of the distribution of entropy for different website categories, confirm the utility of entropy as a fingerprinting proxy, and offer a method for evaluating browser enhancements which are intended to mitigate fingerprinting., Comment: A version of this report to appear in the proceedings of The Web Conference (WWW) 2024. This version contains additional material in the appendix

Science is and always has been based on data, but the terms "data-centric" and the "4th paradigm of" materials research indicate a radical change in how information is retrieved, handled and research is performed. It signifies a transformative shift towards managing vast data collections, digital repositories, and innovative data analytics methods. The integration of Artificial Intelligence (AI) and its subset Machine Learning (ML), has become pivotal in addressing all these challenges. This Roadmap on Data-Centric Materials Science explores fundamental concepts and methodologies, illustrating diverse applications in electronic-structure theory, soft matter theory, microstructure research, and experimental techniques like photoemission, atom probe tomography, and electron microscopy. While the roadmap delves into specific areas within the broad interdisciplinary field of materials science, the provided examples elucidate key concepts applicable to a wider range of topics. The discussed instances offer insights into addressing the multifaceted challenges encountered in contemporary materials research., Comment: Review, outlook, roadmap, perspective

In recent years, strong expectations have been raised for the possible power of quantum computing for solving difficult optimization problems, based on theoretical, asymptotic worst-case bounds. Can we expect this to have consequences for Linear and Integer Programming when solving instances of practically relevant size, a fundamental goal of Mathematical Programming, Operations Research and Algorithm Engineering? Answering this question faces a crucial impediment: The lack of sufficiently large quantum platforms prevents performing real-world tests for comparison with classical methods. In this paper, we present a quantum analog for classical runtime analysis when solving real-world instances of important optimization problems. To this end, we measure the expected practical performance of quantum computers by analyzing the expected gate complexity of a quantum algorithm. The lack of practical quantum platforms for experimental comparison is addressed by hybrid benchmarking, in which the algorithm is performed on a classical system, logging the expected cost of the various subroutines that are employed by the quantum versions. In particular, we provide an analysis of quantum methods for Linear Programming, for which recent work has provided asymptotic speedup through quantum subroutines for the Simplex method. We show that a practical quantum advantage for realistic problem sizes would require quantum gate operation times that are considerably below current physical limitations., Comment: 39 pages, 8 figures

Surface Enhanced Infrared Absorption (SEIRA) is an experimental method where trace amount of a compound can be detected with high sensibility. This high detection sensibility is the result of the interaction of the molecules with a localized plasmon, usually from a metallic nano-particle. In this study we numerically investigate by discrete dipole approximation the origin of the Fano-like response of the system, including the induced transparency when the plasmon resonance and the molecular vibrational mode coincide. The detailed analysis of the localization of the absorption show that the modification of the absorption cross-section when the molecule is present comes from a change of the plasmonic resonance, not from the direct molecular response which is negligible. This sheds a new light on the SEIRA mechanism. In particular, it demonstrates that the sensibility is associated with the influence of the molecule on the plasmon resonance rather than with the local field enhancement itself., Comment: 12 pages, 5 figures

Creoles represent an under-explored and marginalized group of languages, with few available resources for NLP research.While the genealogical ties between Creoles and a number of highly-resourced languages imply a significant potential for transfer learning, this potential is hampered due to this lack of annotated data. In this work we present CreoleVal, a collection of benchmark datasets spanning 8 different NLP tasks, covering up to 28 Creole languages; it is an aggregate of novel development datasets for reading comprehension, relation classification, and machine translation for Creoles, in addition to a practical gateway to a handful of preexisting benchmarks. For each benchmark, we conduct baseline experiments in a zero-shot setting in order to further ascertain the capabilities and limitations of transfer learning for Creoles. Ultimately, we see CreoleVal as an opportunity to empower research on Creoles in NLP and computational linguistics, and in general, a step towards more equitable language technology around the globe., Comment: Accepted to TACL

Here we present two novel contributions for achieving quantum advantage in solving difficult optimisation problems, both in theory and foreseeable practice. (1) We introduce the ''Quantum Tree Generator'', an approach to generate in superposition all feasible solutions of a given instance, yielding together with amplitude amplification the optimal solutions for $0$-$1$-Knapsack problems. The QTG offers exponential memory savings and enables competitive runtimes compared to the state-of-the-art Knapsack solver COMBO for instances involving as few as 600 variables. (2) By introducing a high-level simulation strategy that exploits logging data from COMBO, we can predict the runtime of our method way beyond the range of existing quantum platforms and simulators, for various benchmark instances with up to 1600 variables. Combining both of these innovations, we demonstrate the QTG's potential advantage for large-scale problems, indicating an effective approach for combinatorial optimisation problems., Comment: 6+9 pages, 7 figures