Search

The close link between cognitive decline and language has fostered long-standing collaboration between the NLP and medical communities in dementia research. To examine this, we reviewed over 200 papers applying NLP to dementia related efforts, drawing from medical, technological, and NLP-focused literature. We identify key research areas, including dementia detection, linguistic biomarker extraction, caregiver support, and patient assistance, showing that half of all papers focus solely on dementia detection using clinical data. However, many directions remain unexplored: artificially degraded language models, synthetic data, digital twins, and more. We highlight gaps and opportunities around trust, scientific rigor, applicability, and cross-community collaboration, and showcase the diverse datasets encountered throughout our review: recorded, written, structured, spontaneous, synthetic, clinical, social media based, and more. This review aims to inspire more creative approaches to dementia research within the medical and NLP communities.

Whole Slide Images (WSIs) are critical for various clinical applications, including histopathological analysis. However, current deep learning approaches in this field predominantly focus on individual tumor types, limiting model generalization and scalability. This relatively narrow focus ultimately stems from the inherent heterogeneity in histopathology and the diverse morphological and molecular characteristics of different tumors. To this end, we propose a novel approach for multi-cohort WSI analysis, designed to leverage the diversity of different tumor types. We introduce a Cohort-Aware Attention module, enabling the capture of both shared and tumor-specific pathological patterns, enhancing cross-tumor generalization. Furthermore, we construct an adversarial cohort regularization mechanism to minimize cohort-specific biases through mutual information minimization. Additionally, we develop a hierarchical sample balancing strategy to mitigate cohort imbalances and promote unbiased learning. Together, these form a cohesive framework for unbiased multi-cohort WSI analysis. Extensive experiments on a uniquely constructed multi-cancer dataset demonstrate significant improvements in generalization, providing a scalable solution for WSI classification across diverse cancer types. Our code for the experiments is publicly available at ., Comment: 11 pages, 5 figures

We show that a minor variant of the continuous Fr\'echet distance between polygonal curves can be computed using essentially the same algorithm used to solve the discrete version, thus dramatically simplifying the algorithm for computing it. The new variant is not necessarily monotone, but this shortcoming can be easily handled via refinement. Combined with a Dijkstra/Prim type algorithm, this leads to a realization of the Fr\'echet distance (i.e., a morphing) that is locally optimal (aka locally correct), that is both easy to compute, and in practice, takes near linear time on many inputs. The new morphing has the property that the leash is always as short-as-possible. We implemented the new algorithm, and developed various strategies to get a fast execution in practice. Among our new contributions is a new simplification strategy that is distance-sensitive, and enables us to compute the exact continuous Fr\'echet distance in near linear time in practice. We preformed extensive experiments on our new algorithm, and released Julia and Python packages with these new implementations.

Let $P$ be a set of $n$ points in $\mathbb{R}^d$, and let $\varepsilon,\psi \in (0,1)$ be parameters. Here, we consider the task of constructing a $(1+\varepsilon)$-spanner for $P$, where every edge might fail (independently) with probability $1-\psi$. For example, for $\psi=0.1$, about $90\%$ of the edges of the graph fail. Nevertheless, we show how to construct a spanner that survives such a catastrophe with near linear number of edges. The measure of reliability of the graph constructed is how many pairs of vertices lose $(1+\varepsilon)$-connectivity. Surprisingly, despite the spanner constructed being of near linear size, the number of failed pairs is close to the number of failed pairs if the underlying graph was a clique. Specifically, we show how to construct such an exact dependable spanner in one dimension of size $O(\tfrac{n}{\psi} \log n)$, which is optimal. Next, we build an $(1+\varepsilon)$-spanners for a set $P \subseteq \mathbb{R}^d$ of $n$ points, of size $O( C n \log n )$, where $C \approx 1/\bigl(\varepsilon^{d} \psi^{4/3}\bigr)$. Surprisingly, these new spanners also have the property that almost all pairs of vertices have a $\leq 4$-hop paths between them realizing this short path.

Motion planning in modified environments is a challenging task, as it compounds the innate difficulty of the motion planning problem with a changing environment. This renders some algorithmic methods such as probabilistic roadmaps less viable, as nodes and edges may become invalid as a result of these changes. In this paper, we present a method of transforming any configuration space graph, such as a roadmap, to a dynamic data structure capable of updating the validity of its nodes and edges in response to discrete changes in obstacle positions. We use methods from computational geometry to compute 3D swept volume approximations of configuration space points and curves to achieve 10-40 percent faster updates and up to 60 percent faster motion planning queries than previous algorithms while requiring a significantly shorter pre-processing phase, requiring minutes instead of hours needed by the competing method to achieve somewhat similar update times.

$ \newcommand{\cardin}[1]{\left| {#1} \right|}% \newcommand{\Graph}{\Mh{\mathsf{G}}}% \providecommand{\G}{\Graph}% \renewcommand{\G}{\Graph}% \providecommand{\GA}{\Mh{H}}% \renewcommand{\GA}{\Mh{H}}% \newcommand{\VV}{\Mh{\mathsf{V}}}% \newcommand{\VX}[1]{\VV\pth{#1}}% \providecommand{\EE}{\Mh{\mathsf{E}}}% \renewcommand{\EE}{\Mh{\mathsf{E}}}% \newcommand{\Re}{\mathbb{R}} \newcommand{\reals}{\mathbb{R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\Mh}[1]{#1} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\pts}{s}$ For an undirected graph $\mathsf{G}=(\mathsf{V}, \mathsf{E})$, with $n$ vertices and $m$ edges, the \emph{densest subgraph} problem, is to compute a subset $S \subseteq \mathsf{V}$ which maximizes the ratio $|\mathsf{E}_S| / |S|$, where $\mathsf{E}_S \subseteq \mathsf{E}$ is the set of all edges of $\mathsf{G}$ with endpoints in $S$. The densest subgraph problem is a well studied problem in computer science. Existing exact and approximation algorithms for computing the densest subgraph require $\Omega(m)$ time. We present near-linear time (in $n$) approximation algorithms for the densest subgraph problem on \emph{implicit} geometric intersection graphs, where the vertices are explicitly given but not the edges. As a concrete example, we consider $n$ disks in the plane with arbitrary radii and present two different approximation algorithms.

In the classical prophet inequality settings, a gambler is given a sequence of $n$ random variables $X_1, \dots, X_n$, taken from known distributions, observes their values in this (potentially adversarial) order, and select one of them, immediately after it is being observed, so that its value is as high as possible. The classical \emph{prophet inequality} shows a strategy that guarantees a value at least half of that an omniscience prophet that picks the maximum, and this ratio is optimal. Here, we generalize the prophet inequality, allowing the gambler some additional information about the future that is otherwise privy only to the prophet. Specifically, at any point in the process, the gambler is allowed to query an oracle $\mathcal{O}$. The oracle responds with a single bit answer: YES if the current realization is greater than the remaining realizations, and NO otherwise. We show that the oracle model with $m$ oracle calls is equivalent to the \textsc{Top-$1$-of-$(m+1)$} model when the objective is maximizing the probability of selecting the maximum. This equivalence fails to hold when the objective is maximizing the competitive ratio, but we still show that any algorithm for the oracle model implies an equivalent competitive ratio for the \textsc{Top-$1$-of-$(m+1)$} model. We resolve the oracle model for any $m$, giving tight lower and upper bound on the best possible competitive ratio compared to an almighty adversary. As a consequence, we provide new results as well as improvements on known results for the \textsc{Top-$1$-of-$m$} model.

In this paper, we present a novel digital twin prototype for a learning-enabled self-driving vehicle. The primary objective of this digital twin is to perform traffic sign recognition and lane keeping. The digital twin architecture relies on co-simulation and uses the Functional Mock-up Interface and SystemC Transaction Level Modeling standards. The digital twin consists of four clients, i) a vehicle model that is designed in Amesim tool, ii) an environment model developed in Prescan, iii) a lane-keeping controller designed in Robot Operating System, and iv) a perception and speed control module developed in the formal modeling language of BIP (Behavior, Interaction, Priority). These clients interface with the digital twin platform, PAVE360-Veloce System Interconnect (PAVE360-VSI). PAVE360-VSI acts as the co-simulation orchestrator and is responsible for synchronization, interconnection, and data exchange through a server. The server establishes connections among the different clients and also ensures adherence to the Ethernet protocol. We conclude with illustrative digital twin simulations and recommendations for future work.

A minimal surface in a random environment (MSRE) is a surface which minimizes the sum of its elastic energy and its environment potential energy, subject to prescribed boundary conditions. Apart from their intrinsic interest, such surfaces are further motivated by connections with disordered spin systems and first-passage percolation models. We wish to study the geometry of d-dimensional minimal surfaces in a (d+n)-dimensional random environment. Specializing to a model that we term harmonic MSRE, in an ``independent'' random environment, we rigorously establish bounds on the geometric and energetic fluctuations of the minimal surface, as well as a scaling relation that ties together these two types of fluctuations. In particular, we prove, for all values of $n$, that the surfaces are delocalized in dimensions $d\le 4$ and localized in dimensions $d\ge 5$. Moreover, the surface delocalizes with power-law fluctuations when $d\le 3$ and sub-power-law fluctuations when $d=4$. Our localization results apply also to harmonic minimal surfaces in a periodic random environment., Comment: 69 pages, 3 figures

Satellite systems are facing an ever-increasing amount of cybersecurity threats as their role in communications, navigation, and other services expands. Recent papers have examined attacks targeting satellites and space systems; however, they did not comprehensively analyze the threats to satellites and systematically identify adversarial techniques across the attack lifecycle. This paper presents a comprehensive taxonomy of adversarial tactics, techniques, and procedures explicitly targeting LEO satellites. First, we analyze the space ecosystem including the ground, space, Communication, and user segments, highlighting their architectures, functions, and vulnerabilities. Then, we examine the threat landscape, including adversary types, and capabilities, and survey historical and recent attacks such as jamming, spoofing, and supply chain. Finally, we propose a novel extension of the MITRE ATT&CK framework to categorize satellite attack techniques across the adversary lifecycle from reconnaissance to impact. The taxonomy is demonstrated by modeling high-profile incidents, including the Viasat attack that disrupted Ukraine's communications. The taxonomy provides the foundation for the development of defenses against emerging cyber risks to space assets. The proposed threat model will advance research in the space domain and contribute to the security of the space domain against sophisticated attacks.

$ \newcommand{\Re}{\mathbb{R}} \newcommand{\reals}{\mathbb{R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\Mh}[1]{#1} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\pts}{s}$ A set $P$ of $n$ points in the plane, induces a set of Delaunay-type axis-parallel rectangles $\mathcal{R}$, potentially of quadratic size, where an axis-parallel rectangle is in $\mathcal{R}$, if it has two points of $P$ as corners, and no other point of $P$ in it. We study various algorithmic problems related to this set of rectangles, including how to compute it, in near linear time, and handle various algorithmic tasks on it, such as computing its union and depth. The set of rectangles $\mathcal{R}$ induces the rectangle influence graph $G = (P,\mathcal{R})$, which we also study. Potentially our most interesting result is showing that this graph can be described as the union of $O(n)$ bicliques, where the total weight of the bicliques is $O(n \log^2 n)$. Here, the weight of a bicliques is the cardinality of its vertices.

$ \newcommand{\Re}{\mathbb{R}} \newcommand{\BX}{\mathcal{B}} \newcommand{\bb}{\mathsf{b}} \newcommand{\eps}{\varepsilon} \newcommand{\polylog}{\mathrm{polylog}} $ Let $\BX=\{\bb_1, \ldots ,\bb_n\}$ be a set of $n$ axis-aligned boxes in $\Re^d$ where $d\geq2$ is a constant. The piercing problem is to compute a smallest set of points $N \subset \Re^d$ that hits every box in $\BX$, i.e., $N\cap \bb_i\neq \emptyset$, for $i=1,\ldots, n$. The problem is known to be NP-Hard. Let $\psi:=\psi(\BX)$, the \emph{piercing number} be the minimum size of a piercing set of $\BX$. We first present a randomized $O(\log\log \psi)$-approximation algorithm with expected running time $O(n^{d/2}\polylog (n))$. Next, we show that the expected running time can be improved to near-linear using a sampling-based technique, if $\psi = O(n^{1/(d-1)})$. Specifically, in the plane, the improved running time is $O(n \log \psi)$, assuming $\psi < n/\log^{\Omega(1)} n$. Finally, we study the dynamic version of the piercing problem where boxes can be inserted or deleted. For boxes in $\Re^2$, we obtain a randomized $O(\log\log\psi)$-approximation algorithm with $O(n^{1/2}\polylog (n))$ amortized expected update time for insertion or deletion of boxes. For squares in $\Re^2$, the update time can be improved to $O(n^{1/3}\polylog (n))$. Our algorithms are based on the multiplicative weight-update (MWU) method and require the construction of a weak $\eps$-net for a point set with respect to boxes. A key idea of our work is to exploit the duality between the piercing set and independent set (for boxes) to speed up our MWU. We also present a simpler and slightly more efficient algorithm for constructing a weak $\eps$-net than in [Ezr10], which is of independent interest. Our approach also yields a simpler algorithm for constructing (regular) $\eps$-nets with respect to boxes for $d=2,3$., Comment: To appear in SODA 2024

$ \newcommand{\Re}{\mathbb{R}} \newcommand{\reals}{\mathbb{R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\Eps}{\Mh{\mathcal{E}}} \newcommand{\p}{\Mh{p}} \newcommand{\q}{\Mh{q}} \newcommand{\Mh}[1]{#1} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\pts}{s}$ For a parameter $\eps \in (0,1)$, we present a new construction of $\eps$-locality-sensitive orderings (

The disordered ferromagnet is a disordered version of the ferromagnetic Ising model in which the coupling constants are non-negative quenched random. A ground configuration is an infinite-volume configuration whose energy cannot be reduced by finite modifications. It is a long-standing challenge to ascertain whether the disordered ferromagnet on the $\mathbb{Z}^D$ lattice admits non-constant ground configurations. We answer this affirmatively in dimensions $D\ge 4$, when the coupling constants are sampled independently from a sufficiently concentrated distribution. The obtained ground configurations are further shown to be translation-covariant with respect to $\mathbb{Z}^{D-1}$ translations of the disorder. Our result is proved by showing that the finite-volume interface formed by Dobrushin boundary conditions is localized, and converges to an infinite-volume interface. This may be expressed in purely combinatorial terms, as a result on the fluctuations of certain minimal cutsets in the lattice $\mathbb{Z}^D$ endowed with independent edge capacities., Comment: A combinatorial interpretation was added; some additional minor changes to the presentation

$\newcommand{\eps}{\varepsilon}$ We observe that a $(1-\eps)$-approximation algorithm to Independent Set, that works for any induced subgraph of the input graph, can be used, via a polynomial time reduction, to provide a $(1+\eps)$-approximation to Vertex Cover. This basic observation was made before, see [BHR11]. As a consequence, we get a PTAS for VC for unweighted pseudo-disks, QQPTAS for VC for unweighted axis-aligned rectangles in the plane, and QPTAS for MWVC for weighted polygons in the plane. To the best of our knowledge all these results are new.

We study first-passage percolation on $\mathbb Z^d$, $d\ge 2$, with independent weights whose common distribution is compactly supported in $(0,\infty)$ with a uniformly-positive density. Given $\epsilon>0$ and $v\in\mathbb Z^d$, which edges have probability at least $\epsilon$ to lie on the geodesic between the origin and $v$? It is expected that all such edges lie at distance at most some $r(\epsilon)$ from either the origin or $v$, but this remains open in dimensions $d\ge 3$. We establish the closely-related fact that the number of such edges is at most some $C(\epsilon)$, uniformly in $v$. In addition, we prove a quantitative bound, allowing $\epsilon$ to tend to zero as $\|v\|$ tends to infinity, showing that there are at most $O\big(\epsilon^{-\frac{2d}{d-1}}(\log \|v\|)^C\big)$ such edges, uniformly in $\epsilon$ and $v$. The latter result addresses a problem raised by Benjamin-Kalai-Schramm (2003). Our technique further yields a strengthened version of a lower bound on transversal fluctuations due to Licea-Newman-Piza (1996).

We study the noise sensitivity of the minimum spanning tree (MST) of the $n$-vertex complete graph when edges are assigned independent random weights. It is known that when the graph distance is rescaled by $n^{1/3}$ and vertices are given a uniform measure, the MST converges in distribution in the Gromov-Hausdorff-Prokhorov (GHP) topology. We prove that if the weight of each edge is resampled independently with probability $\varepsilon\gg n^{-1/3}$, then the pair of rescaled minimum spanning trees -- before and after the noise -- converges in distribution to independent random spaces. Conversely, if $\varepsilon\ll n^{-1/3}$, the GHP distance between the rescaled trees goes to $0$ in probability. This implies the noise sensitivity and stability for every property of the MST that corresponds to a continuity set of the random limit. The noise threshold of $n^{-1/3}$ coincides with the critical window of the Erd\H{o}s-R\'enyi random graphs. In fact, these results follow from an analog theorem we prove regarding the minimum spanning forest of critical random graphs.

$ \newcommand{\Re}{\mathbb{R}} \newcommand{\reals}{\mathbb{R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\optX}[1]{#1^\star} \newcommand{\Qopt}{\Mh{\optX{Q}}} \newcommand{\rad}{r} \newcommand{\Mh}[1]{#1} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{Polygon}{\mathsf{P}} \newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\RunningTime}{O\bigl(n^{3/2} \sqrt{k} \log^{3/2} n + kn \log^2 n\bigr)} \newcommand{\pts}{s}$ Given a set $P$ of $n$ points in the plane, and a parameter $k$, we present an algorithm, whose running time is $\RunningTime$, with high probability, that computes a subset $\Qopt \subseteq P$ of $k$ points, that minimizes the Hausdorff distance between the convex-hulls of $\Qopt$ and $P$. This is the first subquadratic algorithm for this problem if $k$ is small., Comment: To appear in CCCG 23

$ \newcommand{\epsA}{\Mh{\delta}} \newcommand{\Re}{\mathbb{R}} \newcommand{\reals}{\mathbb{R}} \newcommand{\SetX}{\mathsf{X}} \renewcommand{\P}{P} \newcommand{\diam}{\Delta} \newcommand{\Mh}[1]{#1} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|} \newcommand{\PP}{P} \newcommand{\ptq}{q} \newcommand{\pts}{s}$Given a set $P \subset \Re^d$ of $n$ points, with diameter $\diam$, and a parameter $\epsA \in (0,1)$, it is known that there is a partition of $P$ into sets $P_1, \ldots, P_t$, each of size $O(1/\epsA^2)$, such that their convex-hulls all intersect a common ball of radius $\epsA \diam$. We prove that a random partition, with a simple alteration step, yields the desired partition, resulting in a (randomized) linear time algorithm. We also provide a deterministic algorithm with running time $O( dn \log n)$. Previous proofs were either existential (i.e., at least exponential time), or required much bigger sets. In addition, the algorithm and its proof of correctness are significantly simpler than previous work, and the constants are slightly better. We also include a number of applications and extensions using the same central ideas. For example, we provide a linear time algorithm for computing a ``fuzzy'' centerpoint, and prove a no-dimensional weak $\eps$-net theorem with an improved constant.

Jord\'an and Tanigawa recently introduced the $d$-dimensional algebraic connectivity $a_d(G)$ of a graph $G$. This is a quantitative measure of the $d$-dimensional rigidity of $G$ which generalizes the well-studied notion of spectral expansion of graphs. We present a new lower bound for $a_d(G)$ defined in terms of the spectral expansion of certain subgraphs of $G$ associated with a partition of its vertices into $d$ parts. In particular, we obtain a new sufficient condition for the rigidity of a graph $G$. As a first application, we prove the existence of an infinite family of $k$-regular $d$-rigidity-expander graphs for every $d\ge 2$ and $k\ge 2d+1$. Conjecturally, no such family of $2d$-regular graphs exists. Second, we show that $a_d(K_n)\geq \frac{1}{2}\left\lfloor\frac{n}{d}\right\rfloor$, which we conjecture to be essentially tight. In addition, we study the extremal values $a_d(G)$ attained if $G$ is a minimally $d$-rigid graph.