Search

Expander decompositions have become one of the central frameworks in the design of fast algorithms. For an undirected graph $G=(V,E)$, a near-optimal $\phi$-expander decomposition is a partition $V_1, V_2, \ldots, V_k$ of the vertex set $V$ where each subgraph $G[V_i]$ is a $\phi$-expander, and only an $\widetilde{O}(\phi)$-fraction of the edges cross between partition sets. In this article, we give the first near-optimal \emph{parallel} algorithm to compute $\phi$-expander decompositions in near-linear work $\widetilde{O}(m/\phi^2)$ and near-constant span $\widetilde{O}(1/\phi^4)$. Our algorithm is very simple and likely practical. Our algorithm can also be implemented in the distributed Congest model in $\tilde{O}(1/\phi^4)$ rounds. Our results surpass the theoretical guarantees of the current state-of-the-art parallel algorithms [Chang-Saranurak PODC'19, Chang-Saranurak FOCS'20], while being the first to ensure that only an $\tilde{O}(\phi)$ fraction of edges cross between partition sets. In contrast, previous algorithms [Chang-Saranurak PODC'19, Chang-Saranurak FOCS'20] admit at least an $O(\phi^{1/3})$ fraction of crossing edges, a polynomial loss in quality inherent to their random-walk-based techniques. Our algorithm, instead, leverages flow-based techniques and extends the popular sequential algorithm presented in [Saranurak-Wang SODA'19]., Comment: To appear at SODA'25

Evaluating the output of generative large language models (LLMs) is challenging and difficult to scale. Most evaluations of LLMs focus on tasks such as single-choice question-answering or text classification. These tasks are not suitable for assessing open-ended question-answering capabilities, which are critical in domains where expertise is required, such as health, and where misleading or incorrect answers can have a significant impact on a user's health. Using human experts to evaluate the quality of LLM answers is generally considered the gold standard, but expert annotation is costly and slow. We present a method for evaluating LLM answers that uses ranking signals as a substitute for explicit relevance judgements. Our scoring method correlates with the preferences of human experts. We validate it by investigating the well-known fact that the quality of generated answers improves with the size of the model as well as with more sophisticated prompting strategies.

We give the first almost-linear total time algorithm for deciding if a flow of cost at most $F$ still exists in a directed graph, with edge costs and capacities, undergoing decremental updates, i.e., edge deletions, capacity decreases, and cost increases. This implies almost-linear time algorithms for approximating the minimum-cost flow value and $s$-$t$ distance on such decremental graphs. Our framework additionally allows us to maintain decremental strongly connected components in almost-linear time deterministically. These algorithms also improve over the current best known runtimes for statically computing minimum-cost flow, in both the randomized and deterministic settings. We obtain our algorithms by taking the dual perspective, which yields cut-based algorithms. More precisely, our algorithm computes the flow via a sequence of $m^{1+o(1)}$ dynamic min-ratio cut problems, the dual analog of the dynamic min-ratio cycle problem that underlies recent fast algorithms for minimum-cost flow. Our main technical contribution is a new data structure that returns an approximately optimal min-ratio cut in amortized $m^{o(1)}$ time by maintaining a tree-cut sparsifier. This is achieved by devising a new algorithm to maintain the dynamic expander hierarchy of [Goranci-R\"{a}cke-Saranurak-Tan, SODA 2021] that also works in capacitated graphs. All our algorithms are deterministc, though they can be sped up further using randomized techniques while still working against an adaptive adversary., Comment: 61 pages, Accepted to FOCS 2024

In this paper, we investigate the question of whether the electrical flow routing is a good oblivious routing scheme on an $m$-edge graph $G = (V, E)$ that is a $\Phi$-expander, i.e. where $\lvert \partial S \rvert \geq \Phi \cdot \mathrm{vol}(S)$ for every $S \subseteq V, \mathrm{vol}(S) \leq \mathrm{vol}(V)/2$. Beyond its simplicity and structural importance, this question is well-motivated by the current state-of-the-art of fast algorithms for $\ell_{\infty}$ oblivious routings that reduce to the expander-case which is in turn solved by electrical flow routing. Our main result proves that the electrical routing is an $O(\Phi^{-1} \log m)$-competitive oblivious routing in the $\ell_1$- and $\ell_\infty$-norms. We further observe that the oblivious routing is $O(\log^2 m)$-competitive in the $\ell_2$-norm and, in fact, $O(\log m)$-competitive if $\ell_2$-localization is $O(\log m)$ which is widely believed. Using these three upper bounds, we can smoothly interpolate to obtain upper bounds for every $p \in [2, \infty]$ and $q$ given by $1/p + 1/q = 1$. Assuming $\ell_2$-localization in $O(\log m)$, we obtain that in $\ell_p$ and $\ell_q$, the electrical oblivious routing is $O(\Phi^{-(1-2/p)}\log m)$ competitive. Using the currently known result for $\ell_2$-localization, this ratio deteriorates by at most a sublogarithmic factor for every $p, q \neq 2$. We complement our upper bounds with lower bounds that show that the electrical routing for any such $p$ and $q$ is $\Omega(\Phi^{-(1-2/p)}\log m)$-competitive. This renders our results in $\ell_1$ and $\ell_{\infty}$ unconditionally tight up to constants, and the result in any $\ell_p$- and $\ell_q$-norm to be tight in case of $\ell_2$-localization in $O(\log m)$., Comment: To appear in ICALP 2024

Optimal multi-layer device design requires consideration of fabrication uncertainties associated with inter-layer alignment and conformal layering. We present layer-restricted topology optimization (TO), a novel technique which mitigates the effects of unwanted conformal layering for multi-layer structures and enables TO in multi-etch material platforms. We explore several approaches to achieve this result compatible with density-based TO projection techniques and geometric constraints. Then, we present a robust TO formulation to design devices resilient to inter-layer misalignment. The novel constraint and robust formulation are demonstrated in 2D grating couplers and a 3D polarization rotator., Comment: 14 pages, 5 figures, 17 equations

Quantifying the semantic similarity between database queries is a critical challenge with broad applications, ranging from query log analysis to automated educational assessment of SQL skills. Traditional methods often rely solely on syntactic comparisons or are limited to checking for semantic equivalence. This paper introduces a novel graph-based approach to measure the semantic dissimilarity between SQL queries. Queries are represented as nodes in an implicit graph, while the transitions between nodes are called edits, which are weighted by semantic dissimilarity. We employ shortest path algorithms to identify the lowest-cost edit sequence between two given queries, thereby defining a quantifiable measure of semantic distance. A prototype implementation of this technique has been evaluated through an empirical study, which strongly suggests that our method provides more accurate and comprehensible grading compared to existing techniques. Moreover, the results indicate that our approach comes close to the quality of manual grading, making it a robust tool for diverse database query comparison tasks., Comment: 12 pages

In this work, we present the first algorithm to compute expander decompositions in an $m$-edge directed graph with near-optimal time $\tilde{O}(m)$. Further, our algorithm can maintain such a decomposition in a dynamic graph and again obtains near-optimal update times. Our result improves over previous algorithms of Bernstein-Probst Gutenberg-Saranurak (FOCS 2020), Hua-Kyng-Probst Gutenberg-Wu (SODA 2023) that only obtained algorithms optimal up to subpolynomial factors. At the same time, our algorithm is much simpler and more accessible than previous work. In order to obtain our new algorithm, we present a new push-pull-relabel flow framework that generalizes the classic push-relabel flow algorithm of Goldberg-Tarjan (JACM 1988), which was later dynamized for computing expander decompositions in undirected graphs by Henzinger-Rao-Wang (SIAM J. Comput. 2020), Saranurak-Wang (SODA 2019). We then show that the flow problems formulated in recent work of Hua-Kyng-Probst Gutenberg-Wu (SODA 2023) to decompose directed graphs can be solved much more efficiently in the push-pull-relabel flow framework.

A wealth of literature shows positive outcomes and experiences from arts learning, yet youth access to arts education has become significantly more inequitable over the past 30 years. Alongside the growing discourse around arts learning and equity issues, there is a recognized and persistent need for more research. We conducted a critical, qualitative study of out-of-school time (OST) arts organizations across the United States. Our primary research questions were: (1) How do community youth arts organizational leaders, teaching artists, and participants describe the leading ideas and practices in OST youth arts programming? (2) How can OST youth arts work center the cultural, historical, and geographic resources that artists and arts organizations bring to arts programming? We first developed a theoretical framework for understanding arts practices in education and summarize key learning outcomes associated with youth participation in the arts. We then talked with OST arts education experts across the United States to understand how their programs support and center youth in arts learning, particularly Black youth, Indigenous youth, and youth of color (BIPOC youth), youth from low-income backgrounds, and LGBTQIA+ youth. This report offers the concept of "cultural-regional scenes" to describe the critical, qualitative case studies we developed of OST youth arts practice. We describe four unique cultural-regional scenes--the Urban Midwest, the Bay Area, Texas-Mexico Border Towns, and the Indigenous Southwest--and provide examples of youth arts practice in each scene. We conclude with ideas that stretch across scenes and suggest that researchers and practitioners can take up this approach in the study of OST youth arts programs. [Written in collaboration with community artists and artist-leaders across the United States and Indigenous Nations.]

NGC 1566 is known for exhibiting recurrent outbursts, which are accompanied by changes in spectral type. The most recent transient event occurred from 2017 to 2019 and was reported to be accompanied by a change in Seyfert classification from Seyfert 1.8 to Seyfert 1.2. We analyze data from an optical spectroscopic variability campaign of NGC 1566 taken with the 9.2m SALT between July 2018 and October 2019 and supplement our data set with optical to near-infrared spectroscopic archival data taken by VLT/MUSE in September 2015 and October 2017. We observe the emergence and fading of a strong power-law-like blue continuum as well as strong variations in the Balmer, HeI, HeII lines and the coronal lines [FeVII], [FeX] and [FeXI]. Moreover, we detect broad double-peaked emission line profiles of OI 8446 and the CaII 8498,8542,8662 triplet. This is the first time that genuine double-peaked OI 8446 and CaII 8498,8542,8662 emission in AGN is reported in the literature. All broad lines show a clear redward asymmetry with respect to their central wavelength and we find indications for a significant blueward drift of the total line profiles during the transient event. We show that the double-peaked emission line profiles are well approximated by emission from a low-inclination, relativistic eccentric accretion disk, and that single-peaked profiles can be obtained by broadening due to scale-height dependent turbulence. Small-scale features in the OI and CaII lines suggest the presence of inhomogeneities in the broad-line region. We conclude that the broad-line region in NGC 1566 is dominated by the kinematics of a relativistic eccentric accretion disk. The broad-line region can be modeled to be vertically stratified with respect to scale-height turbulence. The observed blueward drift might be attributed to a low-optical-depth wind launched during the transient event., Comment: 22 pages, 17 figures. Published in Astronomy & Astrophysics (A&A 686, A17 (2024))

We present a general toolbox, based on new vertex sparsifiers, for designing data structures to maintain shortest paths in dynamic graphs. In an $m$-edge graph undergoing edge insertions and deletions, our data structures give the first algorithms for maintaining (a) $m^{o(1)}$-approximate all-pairs shortest paths (APSP) with \emph{worst-case} update time $m^{o(1)}$ and query time $\tilde{O}(1)$, and (b) a tree $T$ that has diameter no larger than a subpolynomial factor times the diameter of the underlying graph, where each update is handled in amortized subpolynomial time. In graphs undergoing only edge deletions, we develop a simpler and more efficient data structure to maintain a $(1+\epsilon)$-approximate single-source shortest paths (SSSP) tree $T$ in a graph undergoing edge deletions in amortized time $m^{o(1)}$ per update. Our data structures are deterministic. The trees we can maintain are not subgraphs of $G$, but embed with small edge congestion into $G$. This is in stark contrast to previous approaches and is useful for algorithms that internally use trees to route flow. To illustrate the power of our new toolbox, we show that our SSSP data structure gives simple deterministic implementations of flow-routing MWU methods in several contexts, where previously only randomized methods had been known. To obtain our toolbox, we give the first algorithm that, given a graph $G$ undergoing edge insertions and deletions and a dynamic terminal set $A$, maintains a vertex sparsifier $H$ that approximately preserves distances between terminals in $A$, consists of at most $|A|m^{o(1)}$ vertices and edges, and can be updated in worst-case time $m^{o(1)}$. Crucially, our vertex sparsifier construction allows us to maintain a low edge-congestion embedding of $H$ into $G$, which is needed for our applications.

We provide an algorithm which, with high probability, maintains a $(1-\epsilon)$-approximate maximum flow on an undirected graph undergoing $m$-edge additions in amortized $m^{o(1)} \epsilon^{-3}$ time per update. To obtain this result, we provide a more general algorithm that solves what we call the incremental, thresholded $p$-norm flow problem that asks to determine the first edge-insertion in an undirected graph that causes the minimum $\ell_p$-norm flow to decrease below a given threshold in value. Since we solve this thresholded problem, our data structure succeeds against an adaptive adversary that can only see the data structure's output. Furthermore, since our algorithm holds for $p = 2$, we obtain improved algorithms for dynamically maintaining the effective resistance between a pair of vertices in an undirected graph undergoing edge insertions. Our algorithm builds upon previous dynamic algorithms for approximately solving the minimum-ratio cycle problem that underlie previous advances on the maximum flow problem [Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva, FOCS '22] as well as recent dynamic maximum flow algorithms [v.d.Brand-Liu-Sidford, STOC '23]. Instead of using interior point methods, which were a key component of these recent advances, our algorithm uses an optimization method based on $\ell_p$-norm iterative refinement and the multiplicative weight update method. This ensures a monotonicity property in the minimum-ratio cycle subproblems that allows us to apply known data structures and bypass issues arising from adaptive queries., Comment: 25 pages, SODA 2024

We give a deterministic $m^{1+o(1)}$ time algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with $m$ edges and polynomially bounded integral demands, costs, and capacities. As a consequence, we obtain the first running time improvement for deterministic algorithms that compute maximum-flow in graphs with polynomial bounded capacities since the work of Goldberg-Rao [J.ACM '98]. Our algorithm builds on the framework of Chen-Kyng-Liu-Peng-Gutenberg-Sachdeva [FOCS '22] that computes an optimal flow by computing a sequence of $m^{1+o(1)}$-approximate undirected minimum-ratio cycles. We develop a deterministic dynamic graph data-structure to compute such a sequence of minimum-ratio cycles in an amortized $m^{o(1)}$ time per edge update. Our key technical contributions are deterministic analogues of the vertex sparsification and edge sparsification components of the data-structure from Chen et al. For the vertex sparsification component, we give a method to avoid the randomness in Chen et al. which involved sampling random trees to recurse on. For the edge sparsification component, we design a deterministic algorithm that maintains an embedding of a dynamic graph into a sparse spanner. We also show how our dynamic spanner can be applied to give a deterministic data structure that maintains a fully dynamic low-stretch spanning tree on graphs with polynomially bounded edge lengths, with subpolynomial average stretch and subpolynomial amortized time per edge update., Comment: Accepted to FOCS 2023

We introduce the elEmBERT model for chemical classification tasks. It is based on deep learning techniques, such as a multilayer encoder architecture. We demonstrate the opportunities offered by our approach on sets of organic, inorganic and crystalline compounds. In particular, we developed and tested the model using the Matbench and Moleculenet benchmarks, which include crystal properties and drug design-related benchmarks. We also conduct an analysis of vector representations of chemical compounds, shedding light on the underlying patterns in structural data. Our model exhibits exceptional predictive capabilities and proves universally applicable to molecular and material datasets. For instance, on the Tox21 dataset, we achieved an average precision of 96%, surpassing the previously best result by 10%., Comment: 26 pages, 16 figures, 6 tables, 50 references

The skeleton of a digital image is a compact representation of its topology, geometry, and scale. It has utility in many computer vision applications, such as image description, segmentation, and registration. However, skeletonization has only seen limited use in contemporary deep learning solutions. Most existing skeletonization algorithms are not differentiable, making it impossible to integrate them with gradient-based optimization. Compatible algorithms based on morphological operations and neural networks have been proposed, but their results often deviate from the geometry and topology of the true medial axis. This work introduces the first three-dimensional skeletonization algorithm that is both compatible with gradient-based optimization and preserves an object's topology. Our method is exclusively based on matrix additions and multiplications, convolutional operations, basic non-linear functions, and sampling from a uniform probability distribution, allowing it to be easily implemented in any major deep learning library. In benchmarking experiments, we prove the advantages of our skeletonization algorithm compared to non-differentiable, morphological, and neural-network-based baselines. Finally, we demonstrate the utility of our algorithm by integrating it with two medical image processing applications that use gradient-based optimization: deep-learning-based blood vessel segmentation, and multimodal registration of the mandible in computed tomography and magnetic resonance images., Comment: Accepted at ICCV 2023

Driver support systems that include human states in the support process is an active research field. Many recent approaches allow, for example, to sense the driver's drowsiness or awareness of the driving situation. However, so far, this rich information has not been utilized much for improving the effectiveness of support systems. In this paper, we therefore propose a warning system that uses human states in the form of driver errors and can warn users in some cases of upcoming risks several seconds earlier than the state of the art systems not considering human factors. The system consists of a behavior planner Risk Maps which directly changes its prediction of the surrounding driving situation based on the sensed driver errors. By checking if this driver's behavior plan is objectively safe, a more robust and foresighted driver warning is achieved. In different simulations of a dynamic lane change and intersection scenarios, we show how the driver's behavior plan can become unsafe, given the estimate of driver errors, and experimentally validate the advantages of considering human factors.

The optical intersite spin transfer (OISTR) effect was recently verified in Fe$_{50}$Ni$_{50}$ using magneto-optical Kerr measurements in the extreme ultraviolet range. However, one of the main experimental signatures analyzed in this work, namely a magnetic moment increase at a specific energy in Ni, was subsequently found also in pure Ni, where no transfer from one element to another is possible. Hence, it is a much-discussed issue whether OISTR in FeNi alloys is real and whether it can be verified experimentally or not. Here, we present a comparative study of spin transfer in Fe$_{50}$Ni$_{50}$, Fe$_{19}$Ni$_{81}$ and pure Ni. We conclusively show that an increase in the magneto-optical signal is indeed insufficient to verify OISTR. However, we also show how an extended data analysis overcomes this problem and allows to unambiguously identify spin transfer effects. Concomitantly, our work solves the long-standing riddle about the origin of delayed demagnetization behavior of Ni in FeNi alloys.

The magneto-optical Kerr effect (MOKE) in the extreme ultraviolet (EUV) regime has helped to elucidate some of the key processes that lead to the manipulation of magnetism on ultrafast timescales. However, as we show in this paper, the recently introduced spectrally-resolved analysis of such data can lead to surprising experimental observations, which might cause misinterpretations. Therefore, an extended analysis of the EUV magneto-optics is necessary. Via experimental determination of the dielectric tensor, we find here that the non-equilibrium excitation in an ultrafast magnetization experiment can cause a rotation of the off-diagonal element of the dielectric tensor in the complex plane. In direct consequence, the commonly analyzed magneto-optic asymmetry may show time-dependent behaviour that is not directly connected to the magnetic properties of the sample. We showcase such critical observations for the case of ultrafast magnetization dynamics in Ni, and give guidelines for the future analysis of spectrally-resolved magneto-optical data and its comparison with theory.