Search

Two celebrated extensions of the classical Helly's theorem are the fractional Helly theorem and the colorful Helly theorem. Bulavka, Goodarzi, and Tancer recently established the optimal bound for the unified generalization of the fractional and the colorful Helly theorems using a colored extension of the exterior algebra. In this paper, we combinatorially reduce both the fractional Helly theorem and its colorful version to a classical problem in extremal combinatorics known as {weak saturation}. No such results connecting the fractional Helly theorem and weak saturation are known in the long history of literature. These reductions, along with basic linear algebraic arguments for the reduced weak saturation problems, let us give new short proofs of the optimal bounds for both the fractional Helly theorem and its colorful version without using exterior algebra., Comment: 5 pages, 1 figure

We study the concept of star clusters in simplicial complexes, which was introduced by Barmak in 2013, by relating it with the structure of hypergraphs that correspond to the simplicial complexes. This implies that for a hypergraph $H$ with a vertex $v$ that is not isolated and not contained in an induced Berge cycle of length $3$, there exists a hypergraph $H'$ with fewer vertices than $H$ such that the independence complex of $H$ is homotopy equivalent to the suspension of the independence complex of $H'$. As an application, we also prove that if a hypergraph has no Berge cycle of length $0$ mod $3$, then the sum of all reduced Betti numbers of its independence complex is at most $1$., Comment: 15 pages, 5 figures

Motivated by the decentralized power grid, we consider a synchronization transition (ST) of the Kuramoto model (KM) with a mixture of first- and second-order type oscillators with fractions $p$ and $1-p$, respectively. Discontinuous ST with forward-backward hysteresis is found in the mean-field limit. A critical exponent $\beta$ is noticed in the spinodal drop of the order parameter curve at the backward ST. We find critical damping inertia $m_*(p)$ of the oscillator mixture, where the system undergoes a characteristic change from overdamped to underdamped. When underdamped, the hysteretic area also becomes multistable. This contrasts an overdamped system, which is bistable at hysteresis. We also notice that $\beta(p)$ continuously varies with $p$ along the critical damping line $m_*(p)$. Further, we find a single-cluster to multi-cluster phase transition at $m_{**}(p)$. We also discuss the effect of those features on the stability of the power grid, which is increasingly threatened as more electric power is produced from inertia-free generators.

We propose the Swish-T family, an enhancement of the existing non-monotonic activation function Swish. Swish-T is defined by adding a Tanh bias to the original Swish function. This modification creates a family of Swish-T variants, each designed to excel in different tasks, showcasing specific advantages depending on the application context. The Tanh bias allows for broader acceptance of negative values during initial training stages, offering a smoother non-monotonic curve than the original Swish. We ultimately propose the Swish-T$_{\textbf{C}}$ function, while Swish-T and Swish-T$_{\textbf{B}}$, byproducts of Swish-T$_{\textbf{C}}$, also demonstrate satisfactory performance. Furthermore, our ablation study shows that using Swish-T$_{\textbf{C}}$ as a non-parametric function can still achieve high performance. The superiority of the Swish-T family has been empirically demonstrated across various models and benchmark datasets, including MNIST, Fashion MNIST, SVHN, CIFAR-10, and CIFAR-100. The code is publicly available at https://github.com/ictseoyoungmin/Swish-T-pytorch., Comment: 11 pages, 6 figures Revised the derivative of the sigmoid function from 1-sigmoid to sigmoid(1-sigmoid) for correctness.Updated related equations in Section 3.2. Conclusions to Conclusion in Section 6

Waveguide-integrated mid-infrared (MIR) photodetectors are pivotal components for developing molecular spectroscopy applications, leveraging mature photonic integrated circuit (PIC) technologies. Despite various strategies, critical challenges still remain in achieving broadband photoresponse, cooling-free operation, and large-scale complementary-metal-oxide-semiconductor (CMOS)-compatible manufacturability. To leap beyond these limitations, the bolometric effect - a thermal detection mechanism - is introduced into the waveguide platform. More importantly, we pursue a free-carrier absorption (FCA) process in germanium (Ge) to create an efficient light-absorbing medium, providing a pragmatic solution for full coverage of the MIR spectrum without incorporating exotic materials into CMOS. Here, we present an uncooled waveguide-integrated photodetector based on a Ge-on-insulator (Ge-OI) PIC architecture, exploiting the bolometric effect combined with FCA. Notably, our device exhibits a broadband responsivity of ~12 mA/W across 4030-4360 nm (and potentially beyond), challenging the state of the art, while achieving a noise-equivalent power of 3.4x10^-9 W/Hz^0.5 at 4180 nm. We further demonstrate label-free sensing of carbon dioxide using our integrated photodetector and sensing waveguide on a single chip. This approach to room-temperature waveguide-integrated MIR photodetection, harnessing bolometry with FCA in Ge, not only facilitates the realization of fully integrated lab-on-a-chip systems with wavelength flexibility but also provides a blueprint for MIR PICs with CMOS-foundry-compatibility., Comment: 6 figures for the main manuscript and 14 figures for the supplementary information

Recent advancements in contrastive learning have revolutionized self-supervised representation learning and achieved state-of-the-art performance on benchmark tasks. While most existing methods focus on applying contrastive learning to input data modalities such as images, natural language sentences, or networks, they overlook the potential of utilizing outputs from previously trained encoders. In this paper, we introduce SIMSKIP, a novel contrastive learning framework that specifically refines input embeddings for downstream tasks. Unlike traditional unsupervised learning approaches, SIMSKIP takes advantage of the output embeddings of encoder models as its input. Through theoretical analysis, we provide evidence that applying SIMSKIP does not result in larger upper bounds on downstream task errors than those of the original embeddings, which serve as SIMSKIP's input. Experimental results on various open datasets demonstrate that the embeddings produced by SIMSKIP improve performance on downstream tasks.

While there have been considerable advancements in machine learning driven by extensive datasets, a significant disparity still persists in the availability of data across various sources and populations. This inequality across domains poses challenges in modeling for those with limited data, which can lead to profound practical and ethical concerns. In this paper, we address a representative case of data inequality problem across domains termed Semi-Supervised Domain Generalization (SSDG), in which only one domain is labeled while the rest are unlabeled. We propose a novel algorithm, ProUD, which can effectively learn domain-invariant features via domain-aware prototypes along with progressive generalization via uncertainty-adaptive mixing of labeled and unlabeled domains. Our experiments on three different benchmark datasets demonstrate the effectiveness of ProUD, outperforming all baseline models including single domain generalization and semi-supervised learning. Source code will be released upon acceptance of the paper., Comment: 20 pages, 4 figures

This study assesses the performance of a global Local Climate Zone (LCZ) product. We examined the built-type classes of LCZs in three major metropolitan areas within the U.S. A reference LCZ was constructed using a simple rule-based method based on high-resolution 3D building maps. Our evaluation demonstrated that the global LCZ product struggles to differentiate classes that demand precise building footprint information (Classes 6 and 9), and classes that necessitate the identification of subtle differences in building elevation (Classes 4-6). Additionally, we identified inconsistent tendencies, where the distribution of classes skews differently across different cities, suggesting the presence of a data distribution shift problem in the machine learning-based LCZ classifier. Our findings shed light on the uncertainties in global LCZ maps, help identify the LCZ classes that are the most challenging to distinguish, and offer insight into future plans for LCZ development and validation.

The Leray number of an abstract simplicial complex is the minimal integer $d$ where its induced subcomplexes have trivial homology groups in dimension $d$ or greater. We give an upper bound on the Leray number of a complex in terms of how the facets are attached to each other. We also describe the structure of complexes for the equality of the bound that we found. Through the Stanley-Reisner correspondence, our results give an Eisenbud-Goto type inequality for any square-free monomial ideals. This generalizes Terai's result., Comment: 18 pages, 1 figure

The balance of game content significantly impacts the gaming experience. Unbalanced game content diminishes engagement or increases frustration because of repetitive failure. Although game designers intend to adjust the difficulty of game content, this is a repetitive, labor-intensive, and challenging process, especially for commercial-level games with extensive content. To address this issue, the game research community has explored automated game balancing using artificial intelligence (AI) techniques. However, previous studies have focused on limited game content and did not consider the importance of the generalization ability of playtesting agents when encountering content changes. In this study, we propose RaidEnv, a new game simulator that includes diverse and customizable content for the boss raid scenario in MMORPG games. Additionally, we design two benchmarks for the boss raid scenario that can aid in the practical application of game AI. These benchmarks address two open problems in automatic content balancing, and we introduce two evaluation metrics to provide guidance for AI in automatic content balancing. This novel game research platform expands the frontiers of automatic game balancing problems and offers a framework within a realistic game production pipeline., Comment: 14 pages, 6 figures, 6 tables, 2 algorithms

Disk scrubbing is a process aimed at resolving read errors on disks by reading data from the disk. However, scrubbing the entire storage array at once can adversely impact system performance, particularly during periods of high input/output operations. Additionally, the continuous reading of data from disks when scrubbing can result in wear and tear, especially on larger capacity disks, due to the significant time and energy consumption involved. To address these issues, we propose a selective disk scrubbing method that enhances the overall reliability and power efficiency in data centers. Our method employs a Machine Learning model based on Mondrian Conformal prediction to identify specific disks for scrubbing, by proactively predicting the health status of each disk in the storage pool, forecasting n-days in advance, and using an open-source dataset. For disks predicted as non-healthy, we mark them for replacement without further action. For healthy drives, we create a set and quantify their relative health across the entire storage pool based on the predictor's confidence. This enables us to prioritize selective scrubbing for drives with established scrubbing frequency based on the scrub cycle. The method we propose provides an efficient and dependable solution for managing enterprise disk drives. By scrubbing just 22.7% of the total storage disks, we can achieve optimized energy consumption and reduce the carbon footprint of the data center., Comment: Conformal and Probabilistic Prediction with Applications (COPA 2023)

A stacked $d$-sphere $S$ is the boundary complex of a stacked $(d+1)$-ball, which is obtained by taking cone over a free $d$-face repeatedly from a $(d+1)$-simplex. A stacked sphere $S$ is called linear if every cone is taken over a face added in the previous step. In this paper, we study the transversal number of facets of stacked $d$-spheres, denoted by $\tau(S)$, which is the minimum number of vertices intersecting with all facets. Briggs, Dobbins and Lee showed that the transversal ratio of a stacked $d$-sphere is bounded above by $\frac{2}{d+2}+o(1)$ and can be as large as $\frac{2}{d+3}$. We improve the lower bound by constructing linear stacked $d$-spheres with transversal ratio $\frac{6}{3d+8}$ and general stacked $d$-spheres with transversal ratio $\frac{2d+3}{(d+2)^2}$. Finally, we show that $\frac{6}{3d+8}$ is optimal for linear stacked $2$-spheres, that is, the transversal ratio is at most $\frac{3}{7} + o(1)$ for linear stacked $2$-spheres., Comment: 12 pages, 4 figures

The advent of industrial robotics and autonomous systems endow human-robot collaboration in a massive scale. However, current industrial robots are restrained in co-working with human in close proximity due to inability of interpreting human agents' attention. Human attention study is non-trivial since it involves multiple aspects of the mind: perception, memory, problem solving, and consciousness. Human attention lapses are particularly problematic and potentially catastrophic in industrial workplace, from assembling electronics to operating machines. Attention is indeed complex and cannot be easily measured with single-modality sensors. Eye state, head pose, posture, and manifold environment stimulus could all play a part in attention lapses. To this end, we propose a pipeline to annotate multimodal dataset of human attention tracking, including eye tracking, fixation detection, third-person surveillance camera, and sound. We produce a pilot dataset containing two fully annotated phone assembly sequences in a realistic manufacturing environment. We evaluate existing fatigue and drowsiness prediction methods for attention lapse detection. Experimental results show that human attention lapses in production scenarios are more subtle and imperceptible than well-studied fatigue and drowsiness., Comment: 6 pages

Continual domain shift poses a significant challenge in real-world applications, particularly in situations where labeled data is not available for new domains. The challenge of acquiring knowledge in this problem setting is referred to as unsupervised continual domain shift learning. Existing methods for domain adaptation and generalization have limitations in addressing this issue, as they focus either on adapting to a specific domain or generalizing to unseen domains, but not both. In this paper, we propose Complementary Domain Adaptation and Generalization (CoDAG), a simple yet effective learning framework that combines domain adaptation and generalization in a complementary manner to achieve three major goals of unsupervised continual domain shift learning: adapting to a current domain, generalizing to unseen domains, and preventing forgetting of previously seen domains. Our approach is model-agnostic, meaning that it is compatible with any existing domain adaptation and generalization algorithms. We evaluate CoDAG on several benchmark datasets and demonstrate that our model outperforms state-of-the-art models in all datasets and evaluation metrics, highlighting its effectiveness and robustness in handling unsupervised continual domain shift learning., Comment: ICCV 2023

A graph class $\mathcal{G}$ has the strong Erd\H{o}s-Hajnal property (SEH-property) if there is a constant $c=c(\mathcal{G}) > 0$ such that for every member $G$ of $\mathcal{G}$, either $G$ or its complement has $K_{m, m}$ as a subgraph where $m \geq \left\lfloor c|V(G)|\right\rfloor$. We prove that the class of chordal graphs satisfy SEH-property with constant $c = 2/9$. On the other hand, a strengthening of SEH-property which we call the colorful Erd\H{o}s-Hajnal property was discussed in geometric settings by Alon et al. (2005) and by Fox et al. (2012). Inspired by their results, we show that for every pair $F_1, F_2$ of subtree families of the same size in a tree $T$ with $k$ leaves, there exists subfamilies $F'_1 \subseteq F_1$ and $F'_2 \subseteq F_2$ of size $\theta \left( \frac{\ln k}{k} \left| F_1 \right|\right)$ such that either every pair of representatives from distinct subfamilies intersect or every such pair do not intersect. Our results are asymptotically optimal., Comment: 17 pages

Despite substantial technological advancements, the comprehensive mapping of surface water, particularly smaller bodies (<1ha), continues to be a challenge due to a lack of robust, scalable methods. Standard methods require either training labels or site-specific parameter tuning, which complicates automated mapping and introduces biases related to training data and parameters. The reliance on water's reflectance properties, including LiDAR intensity, further complicates the matter, as higher-resolution images inherently produce more noise. To mitigate these difficulties, we propose a unique method that focuses on the geometric characteristics of water instead of its variable reflectance properties. Unlike preceding approaches, our approach relies entirely on 3D coordinate observations from airborne LiDAR data, taking advantage of the principle that connected surface water remains flat due to gravity. By harnessing this natural law in conjunction with connectivity, our method can accurately and scalably identify small water bodies, eliminating the need for training labels or repetitive parameter tuning. Consequently, our approach enables the creation of comprehensive 3D topographic maps that include both water and terrain, all performed in an unsupervised manner using only airborne laser scanning data, potentially enhancing the process of generating reliable 3D topographic maps. We validated our method across extensive and diverse landscapes, while comparing it to highly competitive Normalized Difference Water Index (NDWI)-based methods and assessing it using a reference surface water map. In conclusion, our method offers a new approach to address persistent difficulties in robust, scalable surface water mapping and 3D topographic mapping, using solely airborne LiDAR data.

Cameras capture sensor RAW images and transform them into pleasant RGB images, suitable for the human eyes, using their integrated Image Signal Processor (ISP). Numerous low-level vision tasks operate in the RAW domain (e.g. image denoising, white balance) due to its linear relationship with the scene irradiance, wide-range of information at 12bits, and sensor designs. Despite this, RAW image datasets are scarce and more expensive to collect than the already large and public RGB datasets. This paper introduces the AIM 2022 Challenge on Reversed Image Signal Processing and RAW Reconstruction. We aim to recover raw sensor images from the corresponding RGBs without metadata and, by doing this, "reverse" the ISP transformation. The proposed methods and benchmark establish the state-of-the-art for this low-level vision inverse problem, and generating realistic raw sensor readings can potentially benefit other tasks such as denoising and super-resolution., Comment: ECCV 2022 Advances in Image Manipulation (AIM) workshop

With the advent of deep learning methods replacing the ISP in transforming sensor RAW readings into RGB images, numerous methodologies solidified into real-life applications. Equally potent is the task of inverting this process which will have applications in enhancing computational photography tasks that are conducted in the RAW domain, addressing lack of available RAW data while reaping from the benefits of performing tasks directly on sensor readings. This paper's proposed methodology is a state-of-the-art solution to the task of RAW reconstruction, and the multi-step refinement process integrating an overexposure mask is novel in three ways: instead of from RGB to bayer, the pipeline trains from RGB to demosaiced RAW allowing use of perceptual loss functions; the multi-step processes has greatly enhanced the performance of the baseline U-Net from start to end; the pipeline is a generalizable process of refinement that can enhance other high performance methodologies that support end-to-end learning., Comment: 15 pages, 8 figures, ECCV

The digital terrain model (DTM) is fundamental geospatial data for various studies in urban, environmental, and Earth science. The reliability of the results obtained from such studies can be considerably affected by the errors and uncertainties of the underlying DTM. Numerous algorithms have been developed to mitigate the errors and uncertainties of DTM. However, most algorithms involve tricky parameter selection and complicated procedures that make the algorithm's decision rule obscure, so it is often difficult to explain and predict the errors and uncertainties of the resulting DTM. Also, previous algorithms often consider the local neighborhood of each point for distinguishing non-ground objects, which limits both search radius and contextual understanding and can be susceptible to errors particularly if point density varies. This study presents an open-source DTM generation algorithm for airborne LiDAR data that can consider beyond the local neighborhood and whose results are easily explainable, predictable, and reliable. The key assumption of the algorithm is that grounds are smoothly connected while non-grounds are surrounded by areas having sharp elevation changes. The robustness and uniqueness of the proposed algorithm were evaluated in geographically complex environments through tiling evaluation compared to other state-of-the-art algorithms.

Let $\mathcal{F}$ be a family of graphs, and let $p,r$ be nonnegative integers. The \textsc{$(p,r,\mathcal{F})$-Covering} problem asks whether for a graph $G$ and an integer $k$, there exists a set $D$ of at most $k$ vertices in $G$ such that $G^p\setminus N_G^r[D]$ has no induced subgraph isomorphic to a graph in $\mathcal{F}$, where $G^p$ is the $p$-th power of $G$. The \textsc{$(p,r,\mathcal{F})$-Packing} problem asks whether for a graph $G$ and an integer $k$, $G^p$ has $k$ induced subgraphs $H_1,\ldots,H_k$ such that each $H_i$ is isomorphic to a graph in $\mathcal{F}$, and for distinct $i,j\in \{1, \ldots, k\}$, the distance between $V(H_i)$ and $V(H_j)$ in $G$ is larger than $r$. We show that for every fixed nonnegative integers $p,r$ and every fixed nonempty finite family $\mathcal{F}$ of connected graphs, the \textsc{$(p,r,\mathcal{F})$-Covering} problem with $p\leq2r+1$ and the \textsc{$(p,r,\mathcal{F})$-Packing} problem with $p\leq2\lfloor r/2\rfloor+1$ admit almost linear kernels on every nowhere dense class of graphs, and admit linear kernels on every class of graphs with bounded expansion, parameterized by the solution size $k$. We obtain the same kernels for their annotated variants. As corollaries, we prove that \textsc{Distance-$r$ Vertex Cover}, \textsc{Distance-$r$ Matching}, \textsc{$\mathcal{F}$-Free Vertex Deletion}, and \textsc{Induced-$\mathcal{F}$-Packing} for any fixed finite family $\mathcal{F}$ of connected graphs admit almost linear kernels on every nowhere dense class of graphs and linear kernels on every class of graphs with bounded expansion. Our results extend the results for \textsc{Distance-$r$ Dominating Set} by Drange et al. (STACS 2016) and Eickmeyer et al. (ICALP 2017), and the result for \textsc{Distance-$r$ Independent Set} by Pilipczuk and Siebertz (EJC 2021)., Comment: 38 pages

Despite the substantial demand for high-quality, large-area building maps, no established open-source workflow for generating 2D and 3D maps currently exists. This study introduces an automated, open-source workflow for large-scale 2D and 3D building mapping utilizing airborne LiDAR data. Uniquely, our workflow operates entirely unsupervised, eliminating the need for any training procedures. We have integrated a specifically tailored DTM generation algorithm into our workflow to prevent errors in complex urban landscapes, especially around highways and overpasses. Through fine rasterization of LiDAR point clouds, we've enhanced building-tree differentiation, reduced errors near water bodies, and augmented computational efficiency by introducing a new planarity calculation. Our workflow offers a practical and scalable solution for the mass production of rasterized 2D and 3D building maps from raw airborne LiDAR data. Also, we elaborate on the influence of parameters and potential error sources to provide users with practical guidance. Our method's robustness has been rigorously optimized and tested using an extensive dataset (> 550 km$^2$), and further validated through comparison with deep learning-based and hand-digitized products. Notably, through these unparalleled, large-scale comparisons, we offer a valuable analysis of large-scale building maps generated via different methodologies, providing insightful evaluations of the effectiveness of each approach. We anticipate that our highly scalable building mapping workflow will facilitate the production of reliable 2D and 3D building maps, fostering advances in large-scale urban analysis. The code will be released upon publication.

Graph neural networks (GNNs) can extract features by learning both the representation of each objects (i.e., graph nodes) and the relationship across different objects (i.e., the edges that connect nodes), achieving state-of-the-art performance in various graph-based tasks. Despite its strengths, utilizing these algorithms in a production environment faces several challenges as the number of graph nodes and edges amount to several billions to hundreds of billions scale, requiring substantial storage space for training. Unfortunately, state-of-the-art ML frameworks employ an in-memory processing model which significantly hampers the productivity of ML practitioners as it mandates the overall working set to fit within DRAM capacity. In this work, we first conduct a detailed characterization on a state-of-the-art, large-scale GNN training algorithm, GraphSAGE. Based on the characterization, we then explore the feasibility of utilizing capacity-optimized NVM SSDs for storing memory-hungry GNN data, which enables large-scale GNN training beyond the limits of main memory size. Given the large performance gap between DRAM and SSD, however, blindly utilizing SSDs as a direct substitute for DRAM leads to significant performance loss. We therefore develop SmartSAGE, our software/hardware co-design based on an in-storage processing (ISP) architecture. Our work demonstrates that an ISP based large-scale GNN training system can achieve both high capacity storage and high performance, opening up opportunities for ML practitioners to train large GNN datasets without being hampered by the physical limitations of main memory size., Comment: Accepted for publication at the 49th IEEE/ACM International Symposium on Computer Architecture (ISCA-49), 2022

An independent dominating set of a graph, also known as a maximal independent set, is a set $S$ of pairwise non-adjacent vertices such that every vertex not in $S$ is adjacent to some vertex in $S$. We prove that for $\Delta=4$ or $\Delta\ge 6$, every connected $n$-vertex graph of maximum degree at most $\Delta$ has an independent dominating set of size at most $(1-\frac{\Delta}{\lfloor\Delta^2/4\rfloor+\Delta})(n-1)+1$. In addition, we characterize all connected graphs having the equality and we show that other connected graphs have an independent dominating set of size at most $(1-\frac{\Delta}{ \lfloor\Delta^2/4\rfloor+\Delta})n$., Comment: 14 pages