Search

Computing the crossing number of a graph is one of the most classical problems in computational geometry. Both it and numerous variations of the problem have been studied, and overcoming their frequent computational difficulty is an active area of research. Particularly recently, there has been increased effort to show and understand the parameterized tractability of various crossing number variants. While many results in this direction use a similar approach, a general framework remains elusive. We suggest such a framework that generalizes important previous results, and can even be used to show the tractability of deciding crossing number variants for which this was stated as an open problem in previous literature. Our framework targets variants that prescribe a partial predrawing and some kind of topological restrictions on crossings. Additionally, to provide evidence for the non-generalizability of previous approaches for the partially crossing number problem to allow for geometric restrictions, we show a new more constrained hardness result for partially predrawn rectilinear crossing number. In particular, we show W-hardness of deciding Straight-Line Planarity Extension parameterized by the number of missing edges.

We present an algorithm for growing the denominator $r$ polygons containing a fixed number of lattice points and enumerate such polygons containing few lattice points for small $r$. We describe the Ehrhart quasi-polynomial of a rational polygon in terms of boundary and interior point counts. Using this, we bound the coefficients of Ehrhart quasi-polynomials of denominator 2 polygons. In particular, we completely classify such polynomials in the case of zero interior points., Comment: 21 pages, 7 figures

Current AI-assisted skin image diagnosis has achieved dermatologist-level performance in classifying skin cancer, driven by rapid advancements in deep learning architectures. However, unlike traditional vision tasks, skin images in general present unique challenges due to the limited availability of well-annotated datasets, complex variations in conditions, and the necessity for detailed interpretations to ensure patient safety. Previous segmentation methods have sought to reduce image noise and enhance diagnostic performance, but these techniques require fine-grained, pixel-level ground truth masks for training. In contrast, with the rise of foundation models, the Segment Anything Model (SAM) has been introduced to facilitate promptable segmentation, enabling the automation of the segmentation process with simple yet effective prompts. Efforts applying SAM predominantly focus on dermatoscopy images, which present more easily identifiable lesion boundaries than clinical photos taken with smartphones. This limitation constrains the practicality of these approaches to real-world applications. To overcome the challenges posed by noisy clinical photos acquired via non-standardized protocols and to improve diagnostic accessibility, we propose a novel Cross-Attentive Fusion framework for interpretable skin lesion diagnosis. Our method leverages SAM to generate visual concepts for skin diseases using prompts, integrating local visual concepts with global image features to enhance model performance. Extensive evaluation on two skin disease datasets demonstrates our proposed method's effectiveness on lesion diagnosis and interpretability.

Parametrizing energy functions for ionic systems can be challenging. Here, the total energy function for an eutectic system consisting of water, SCN$^-$, K$^+$ and acetamide is improved vis-a-vis experimentally measured properties. Given the importance of electrostatic interactions, two different types of models are considered: the first (model M0) uses atom-centered multipole whereas the other two (models M1 and M2) are based on fluctuating minimal distributed charges (fMDCM) that respond to geometrical changes of SCN$^-$. The Lennard-Jones parameters of the anion are adjusted to best reproduce experimentally known hydration free energies and densities which are matched to within a few percent for the final models irrespective of the electrostatic model. Molecular dynamics simulations of the eutectic mixtures with varying water content (between 0% and 100%) yield radial distribution functions and frequency correlation functions for the CN-stretch vibration. Comparison with experiments indicate that models based on fMDCM are considerably more consistent that those using multipoles. Computed viscosities from models M1 and M2 are within 30% of measured values and their change with increasing water content is consistent with experiments. This is not the case for model M0.

Through comprehensive data analysis, we demonstrate that a ${\chi}^{(2)}$-induced artifact, arising from imperfect balancing in the conventional electro-optic sampling (EOS) detection scheme, contributes significantly to the measured signal in 2D Raman-THz spectroscopy of non-centrosymmetric materials. The artifact is a product of two 1D responses, overwhelming the desired 2D response. We confirm that by analyzing the 2D Raman-THz response of a x-cut beta barium borate (BBO) crystal. We furthermore show that this artifact can be effectively suppressed by implementing a special detection scheme. We successfully isolate the desired third-order 2D Raman-THz response, revealing a distinct cross-peak feature, whose frequency position suggests the coupling between two crystal phonons.

AI-based diagnoses have demonstrated dermatologist-level performance in classifying skin cancer. However, such systems are prone to under-performing when tested on data from minority groups that lack sufficient representation in the training sets. Although data collection and annotation offer the best means for promoting minority groups, these processes are costly and time-consuming. Prior works have suggested that data from majority groups may serve as a valuable information source to supplement the training of diagnosis tools for minority groups. In this work, we propose an effective diffusion-based augmentation framework that maximizes the use of rich information from majority groups to benefit minority groups. Using groups with different skin types as a case study, our results show that the proposed framework can generate synthetic images that improve diagnostic results for the minority groups, even when there is little or no reference data from these target groups. The practical value of our work is evident in medical imaging analysis, where under-diagnosis persists as a problem for certain groups due to insufficient representation.

Continual Test-Time Adaptation (CTTA) seeks to adapt a source pre-trained model to continually changing, unlabeled target domains. Existing TTA methods are typically designed for environments where domain changes occur sequentially and can struggle in more dynamic scenarios, as illustrated in Figure \ref{fig:settings}. Inspired by the principles of online K-Means, we introduce a novel approach to CTTA through visual prompting. We propose a \emph{Dynamic Prompt Coreset} that not only preserves knowledge from previously visited domains but also accommodates learning from new potential domains. This is complemented by a distance-based \emph{Weight Updating Mechanism} that ensures the coreset remains current and relevant. Our approach employs a fixed model architecture alongside the coreset and an innovative updating system to effectively mitigate challenges such as catastrophic forgetting and error accumulation. Extensive testing on four widely-used benchmarks demonstrates that our method consistently outperforms state-of-the-art alternatives in both classification and segmentation CTTA tasks across the structured and dynamic CTTA settings, with $99\%$ fewer trainable parameters.

Vision Transformers (ViTs) have demonstrated remarkable capabilities in learning representations, but their performance is compromised when applied to unseen domains. Previous methods either engage in prompt learning during the training phase or modify model parameters at test time through entropy minimization. The former often overlooks unlabeled target data, while the latter doesn't fully address domain shifts. In this work, our approach, Optimal Transport-guided Test-Time Visual Prompting (OT-VP), handles these problems by leveraging prompt learning at test time to align the target and source domains without accessing the training process or altering pre-trained model parameters. This method involves learning a universal visual prompt for the target domain by optimizing the Optimal Transport distance.OT-VP, with only four learned prompt tokens, exceeds state-of-the-art performance across three stylistic datasets-PACS, VLCS, OfficeHome, and one corrupted dataset ImageNet-C. Additionally, OT-VP operates efficiently, both in terms of memory and computation, and is adaptable for extension to online settings., Comment: WACV2025

Gauging the performance of ML models on data from unseen domains at test-time is essential yet a challenging problem due to the lack of labels in this setting. Moreover, the performance of these models on in-distribution data is a poor indicator of their performance on data from unseen domains. Thus, it is essential to develop metrics that can provide insights into the model's performance at test time and can be computed only with the information available at test time (such as their model parameters, the training data or its statistics, and the unlabeled test data). To this end, we propose a metric based on Optimal Transport that is highly correlated with the model's performance on unseen domains and is efficiently computable only using information available at test time. Concretely, our metric characterizes the model's performance on unseen domains using only a small amount of unlabeled data from these domains and data or statistics from the training (source) domain(s). Through extensive empirical evaluation using standard benchmark datasets, and their corruptions, we demonstrate the utility of our metric in estimating the model's performance in various practical applications. These include the problems of selecting the source data and architecture that leads to the best performance on data from an unseen domain and the problem of predicting a deployed model's performance at test time on unseen domains. Our empirical results show that our metric, which uses information from both the source and the unseen domain, is highly correlated with the model's performance, achieving a significantly better correlation than that obtained via the popular prediction entropy-based metric, which is computed solely using the data from the unseen domain.

There are a number of hypotheses underlying the existence of adversarial examples for classification problems. These include the high-dimensionality of the data, high codimension in the ambient space of the data manifolds of interest, and that the structure of machine learning models may encourage classifiers to develop decision boundaries close to data points. This article proposes a new framework for studying adversarial examples that does not depend directly on the distance to the decision boundary. Similarly to the smoothed classifier literature, we define a (natural or adversarial) data point to be $(\gamma,\sigma)$-stable if the probability of the same classification is at least $\gamma$ for points sampled in a Gaussian neighborhood of the point with a given standard deviation $\sigma$. We focus on studying the differences between persistence metrics along interpolants of natural and adversarial points. We show that adversarial examples have significantly lower persistence than natural examples for large neural networks in the context of the MNIST and ImageNet datasets. We connect this lack of persistence with decision boundary geometry by measuring angles of interpolants with respect to decision boundaries. Finally, we connect this approach with robustness by developing a manifold alignment gradient metric and demonstrating the increase in robustness that can be achieved when training with the addition of this metric.

Social distance games have been extensively studied as a coalition formation model where the utilities of agents in each coalition were captured using a utility function $u$ that took into account distances in a given social network. In this paper, we consider a non-normalized score-based definition of social distance games where the utility function $u^s$ depends on a generic scoring vector $s$, which may be customized to match the specifics of each individual application scenario. As our main technical contribution, we establish the tractability of computing a welfare-maximizing partitioning of the agents into coalitions on tree-like networks, for every score-based function $u^s$. We provide more efficient algorithms when dealing with specific choices of $u^s$ or simpler networks, and also extend all of these results to computing coalitions that are Nash stable or individually rational. We view these results as a further strong indication of the usefulness of the proposed score-based utility function: even on very simple networks, the problem of computing a welfare-maximizing partitioning into coalitions remains open for the originally considered canonical function $u$., Comment: Short version appeared at TARK 2023. arXiv admin note: substantial text overlap with arXiv:2307.05061

Synchronous dynamic systems are well-established models that have been used to capture a range of phenomena in networks, including opinion diffusion, spread of disease and product adoption. We study the three most notable problems in synchronous dynamic systems: whether the system will transition to a target configuration from a starting configuration, whether the system will reach convergence from a starting configuration, and whether the system is guaranteed to converge from every possible starting configuration. While all three problems were known to be intractable in the classical sense, we initiate the study of their exact boundaries of tractability from the perspective of structural parameters of the network by making use of the more fine-grained parameterized complexity paradigm. As our first result, we consider treewidth - as the most prominent and ubiquitous structural parameter - and show that all three problems remain intractable even on instances of constant treewidth. We complement this negative finding with fixed-parameter algorithms for the former two problems parameterized by treedepth, a well-studied restriction of treewidth. While it is possible to rule out a similar algorithm for convergence guarantee under treedepth, we conclude with a fixed-parameter algorithm for this last problem when parameterized by treedepth and the maximum in-degree., Comment: Short version appeared at AAAI 2023

We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspond to the edges of a connected graph, every agent must be assigned a connected piece of this graph, and the fairness notion considered is the classical envy freeness. The problem is NP-complete, and we analyze its complexity with respect to two natural complexity measures: the number of agents and the number of edges in the graph. While the problem remains NP-hard even for instances with 2 agents, we provide a dichotomy characterizing the complexity of the problem when the number of agents is constant based on structural properties of the graph. For the latter case, we design a polynomial-time algorithm when the graph has a constant number of edges., Comment: Short version appeared at IJCAI 2022

This paper aims at building the theoretical foundations for manifold learning algorithms in the space of absolutely continuous probability measures on a compact and convex subset of $\mathbb{R}^d$, metrized with the Wasserstein-2 distance $\mathrm{W}$. We begin by introducing a construction of submanifolds $\Lambda$ of probability measures equipped with metric $\mathrm{W}_\Lambda$, the geodesic restriction of $W$ to $\Lambda$. In contrast to other constructions, these submanifolds are not necessarily flat, but still allow for local linearizations in a similar fashion to Riemannian submanifolds of $\mathbb{R}^d$. We then show how the latent manifold structure of $(\Lambda,\mathrm{W}_{\Lambda})$ can be learned from samples $\{\lambda_i\}_{i=1}^N$ of $\Lambda$ and pairwise extrinsic Wasserstein distances $\mathrm{W}$ only. In particular, we show that the metric space $(\Lambda,\mathrm{W}_{\Lambda})$ can be asymptotically recovered in the sense of Gromov--Wasserstein from a graph with nodes $\{\lambda_i\}_{i=1}^N$ and edge weights $W(\lambda_i,\lambda_j)$. In addition, we demonstrate how the tangent space at a sample $\lambda$ can be asymptotically recovered via spectral analysis of a suitable "covariance operator" using optimal transport maps from $\lambda$ to sufficiently close and diverse samples $\{\lambda_i\}_{i=1}^N$. The paper closes with some explicit constructions of submanifolds $\Lambda$ and numerical examples on the recovery of tangent spaces through spectral analysis.