Showing 1–50 of 178 results for author: Chan, T

cDP-MIL: Robust Multiple Instance Learning via Cascaded Dirichlet Process

Authors: Yihang Chen, Tsai Hor Chan, Guosheng Yin, Yuming Jiang, Lequan Yu

Abstract: Multiple instance learning (MIL) has been extensively applied to whole slide histopathology image (WSI) analysis. The existing aggregation strategy in MIL, which primarily relies on the first-order distance (e.g., mean difference) between instances, fails to accurately approximate the true feature distribution of each instance, leading to biased slide-level representations. Moreover, the scarcity… ▽ More Multiple instance learning (MIL) has been extensively applied to whole slide histopathology image (WSI) analysis. The existing aggregation strategy in MIL, which primarily relies on the first-order distance (e.g., mean difference) between instances, fails to accurately approximate the true feature distribution of each instance, leading to biased slide-level representations. Moreover, the scarcity of WSI observations easily leads to model overfitting, resulting in unstable testing performance and limited generalizability. To tackle these challenges, we propose a new Bayesian nonparametric framework for multiple instance learning, which adopts a cascade of Dirichlet processes (cDP) to incorporate the instance-to-bag characteristic of the WSIs. We perform feature aggregation based on the latent clusters formed by the Dirichlet process, which incorporates the covariances of the patch features and forms more representative clusters. We then perform bag-level prediction with another Dirichlet process model on the bags, which imposes a natural regularization on learning to prevent overfitting and enhance generalizability. Moreover, as a Bayesian nonparametric method, the cDP model can accurately generate posterior uncertainty, which allows for the detection of outlier samples and tumor localization. Extensive experiments on five WSI benchmarks validate the superior performance of our method, as well as its generalizability and ability to estimate uncertainties. Codes are available at https://github.com/HKU-MedAI/cDPMIL. △ Less

Submitted 16 July, 2024; originally announced July 2024.

Symmetric Splendor: Unraveling Universally Closest Refinements and Fisher Market Equilibrium through Density-Friendly Decomposition

Authors: T-H. Hubert Chan, Quan Xue

Abstract: We present a comprehensive framework that unifies several research areas within the context of vertex-weighted bipartite graphs, providing deeper insights and improved solutions. The fundamental solution concept for each problem involves refinement, where vertex weights on one side are distributed among incident edges. The primary objective is to identify a refinement pair with specific optimality… ▽ More We present a comprehensive framework that unifies several research areas within the context of vertex-weighted bipartite graphs, providing deeper insights and improved solutions. The fundamental solution concept for each problem involves refinement, where vertex weights on one side are distributed among incident edges. The primary objective is to identify a refinement pair with specific optimality conditions that can be verified locally. This framework connects existing and new problems that are traditionally studied in different contexts. We explore three main problems: (1) density-friendly hypergraph decomposition, (2) universally closest distribution refinements problem, and (3) symmetric Fisher Market equilibrium. Our framework presents a symmetric view of density-friendly hypergraph decomposition, wherein hyperedges and nodes play symmetric roles. This symmetric decomposition serves as a tool for deriving precise characterizations of optimal solutions for other problems and enables the application of algorithms from one problem to another. △ Less

Submitted 25 June, 2024; originally announced June 2024.

Effective Clustering on Large Attributed Bipartite Graphs

Authors: Renchi Yang, Yidu Wu, Xiaoyang Lin, Qichen Wang, Tsz Nam Chan, Jieming Shi

Abstract: Attributed bipartite graphs (ABGs) are an expressive data model for describing the interactions between two sets of heterogeneous nodes that are associated with rich attributes, such as customer-product purchase networks and author-paper authorship graphs. Partitioning the target node set in such graphs into k disjoint clusters (referred to as k-ABGC) finds widespread use in various domains, inclu… ▽ More Attributed bipartite graphs (ABGs) are an expressive data model for describing the interactions between two sets of heterogeneous nodes that are associated with rich attributes, such as customer-product purchase networks and author-paper authorship graphs. Partitioning the target node set in such graphs into k disjoint clusters (referred to as k-ABGC) finds widespread use in various domains, including social network analysis, recommendation systems, information retrieval, and bioinformatics. However, the majority of existing solutions towards k-ABGC either overlook attribute information or fail to capture bipartite graph structures accurately, engendering severely compromised result quality. The severity of these issues is accentuated in real ABGs, which often encompass millions of nodes and a sheer volume of attribute data, rendering effective k-ABGC over such graphs highly challenging. In this paper, we propose TPO, an effective and efficient approach to k-ABGC that achieves superb clustering performance on multiple real datasets. TPO obtains high clustering quality through two major contributions: (i) a novel formulation and transformation of the k-ABGC problem based on multi-scale attribute affinity specialized for capturing attribute affinities between nodes with the consideration of their multi-hop connections in ABGs, and (ii) a highly efficient solver that includes a suite of carefully-crafted optimizations for sidestepping explicit affinity matrix construction and facilitating faster convergence. Extensive experiments, comparing TPO against 19 baselines over 5 real ABGs, showcase the superior clustering quality of TPO measured against ground-truth labels. Moreover, compared to the state of the arts, TPO is often more than 40x faster over both small and large ABGs. △ Less

Submitted 20 May, 2024; originally announced May 2024.

Comments: The technical report for the paper was accepted to KDD 2024. 14 pages

VS-Assistant: Versatile Surgery Assistant on the Demand of Surgeons

Authors: Zhen Chen, Xingjian Luo, Jinlin Wu, Danny T. M. Chan, Zhen Lei, Jinqiao Wang, Sebastien Ourselin, Hongbin Liu

Abstract: The surgical intervention is crucial to patient healthcare, and many studies have developed advanced algorithms to provide understanding and decision-making assistance for surgeons. Despite great progress, these algorithms are developed for a single specific task and scenario, and in practice require the manual combination of different functions, thus limiting the applicability. Thus, an intellige… ▽ More The surgical intervention is crucial to patient healthcare, and many studies have developed advanced algorithms to provide understanding and decision-making assistance for surgeons. Despite great progress, these algorithms are developed for a single specific task and scenario, and in practice require the manual combination of different functions, thus limiting the applicability. Thus, an intelligent and versatile surgical assistant is expected to accurately understand the surgeon's intentions and accordingly conduct the specific tasks to support the surgical process. In this work, by leveraging advanced multimodal large language models (MLLMs), we propose a Versatile Surgery Assistant (VS-Assistant) that can accurately understand the surgeon's intention and complete a series of surgical understanding tasks, e.g., surgical scene analysis, surgical instrument detection, and segmentation on demand. Specifically, to achieve superior surgical multimodal understanding, we devise a mixture of projectors (MOP) module to align the surgical MLLM in VS-Assistant to balance the natural and surgical knowledge. Moreover, we devise a surgical Function-Calling Tuning strategy to enable the VS-Assistant to understand surgical intentions, and thus make a series of surgical function calls on demand to meet the needs of the surgeons. Extensive experiments on neurosurgery data confirm that our VS-Assistant can understand the surgeon's intention more accurately than the existing MLLM, resulting in overwhelming performance in textual analysis and visual tasks. Source code and models will be made public. △ Less

Submitted 13 May, 2024; originally announced May 2024.

SAM3D: Zero-Shot Semi-Automatic Segmentation in 3D Medical Images with the Segment Anything Model

Authors: Trevor J. Chan, Aarush Sahni, Jie Li, Alisha Luthra, Amy Fang, Alison Pouch, Chamith S. Rajapakse

Abstract: We introduce SAM3D, a new approach to semi-automatic zero-shot segmentation of 3D images building on the existing Segment Anything Model. We achieve fast and accurate segmentations in 3D images with a four-step strategy comprising: volume slicing along non-orthogonal axes, efficient prompting in 3D, slice-wise inference using the pretrained SAM, and recoposition and refinement in 3D. We evaluated… ▽ More We introduce SAM3D, a new approach to semi-automatic zero-shot segmentation of 3D images building on the existing Segment Anything Model. We achieve fast and accurate segmentations in 3D images with a four-step strategy comprising: volume slicing along non-orthogonal axes, efficient prompting in 3D, slice-wise inference using the pretrained SAM, and recoposition and refinement in 3D. We evaluated SAM3D performance qualitatively on an array of imaging modalities and anatomical structures and quantify performance for specific organs in body CT and tumors in brain MRI. By enabling users to create 3D segmentations of unseen data quickly and with dramatically reduced manual input, these methods have the potential to aid surgical planning and education, diagnostic imaging, and scientific research. △ Less

Submitted 10 May, 2024; originally announced May 2024.

Reverse Forward Curriculum Learning for Extreme Sample and Demonstration Efficiency in Reinforcement Learning

Authors: Stone Tao, Arth Shukla, Tse-kai Chan, Hao Su

Abstract: Reinforcement learning (RL) presents a promising framework to learn policies through environment interaction, but often requires an infeasible amount of interaction data to solve complex tasks from sparse rewards. One direction includes augmenting RL with offline data demonstrating desired tasks, but past work often require a lot of high-quality demonstration data that is difficult to obtain, espe… ▽ More Reinforcement learning (RL) presents a promising framework to learn policies through environment interaction, but often requires an infeasible amount of interaction data to solve complex tasks from sparse rewards. One direction includes augmenting RL with offline data demonstrating desired tasks, but past work often require a lot of high-quality demonstration data that is difficult to obtain, especially for domains such as robotics. Our approach consists of a reverse curriculum followed by a forward curriculum. Unique to our approach compared to past work is the ability to efficiently leverage more than one demonstration via a per-demonstration reverse curriculum generated via state resets. The result of our reverse curriculum is an initial policy that performs well on a narrow initial state distribution and helps overcome difficult exploration problems. A forward curriculum is then used to accelerate the training of the initial policy to perform well on the full initial state distribution of the task and improve demonstration and sample efficiency. We show how the combination of a reverse curriculum and forward curriculum in our method, RFCL, enables significant improvements in demonstration and sample efficiency compared against various state-of-the-art learning-from-demonstration baselines, even solving previously unsolvable tasks that require high precision and control. △ Less

Submitted 6 May, 2024; originally announced May 2024.

Comments: Accepted at The Twelfth International Conference on Learning Representations (ICLR 2024). Website: https://reverseforward-cl.github.io/

Learning the Domain Specific Inverse NUFFT for Accelerated Spiral MRI using Diffusion Models

Authors: Trevor J. Chan, Chamith S. Rajapakse

Abstract: Deep learning methods for accelerated MRI achieve state-of-the-art results but largely ignore additional speedups possible with noncartesian sampling trajectories. To address this gap, we created a generative diffusion model-based reconstruction algorithm for multi-coil highly undersampled spiral MRI. This model uses conditioning during training as well as frequency-based guidance to ensure consis… ▽ More Deep learning methods for accelerated MRI achieve state-of-the-art results but largely ignore additional speedups possible with noncartesian sampling trajectories. To address this gap, we created a generative diffusion model-based reconstruction algorithm for multi-coil highly undersampled spiral MRI. This model uses conditioning during training as well as frequency-based guidance to ensure consistency between images and measurements. Evaluated on retrospective data, we show high quality (structural similarity > 0.87) in reconstructed images with ultrafast scan times (0.02 seconds for a 2D image). We use this algorithm to identify a set of optimal variable-density spiral trajectories and show large improvements in image quality compared to conventional reconstruction using the non-uniform fast Fourier transform. By combining efficient spiral sampling trajectories, multicoil imaging, and deep learning reconstruction, these methods could enable the extremely high acceleration factors needed for real-time 3D imaging. △ Less

Submitted 10 May, 2024; v1 submitted 18 April, 2024; originally announced April 2024.

Automating REST API Postman Test Cases Using LLM

Authors: S Deepika Sri, Mohammed Aadil S, Sanjjushri Varshini R, Raja CSP Raman, Gopinath Rajagopal, S Taranath Chan

Abstract: In the contemporary landscape of technological advancements, the automation of manual processes is crucial, compelling the demand for huge datasets to effectively train and test machines. This research paper is dedicated to the exploration and implementation of an automated approach to generate test cases specifically using Large Language Models. The methodology integrates the use of Open AI to en… ▽ More In the contemporary landscape of technological advancements, the automation of manual processes is crucial, compelling the demand for huge datasets to effectively train and test machines. This research paper is dedicated to the exploration and implementation of an automated approach to generate test cases specifically using Large Language Models. The methodology integrates the use of Open AI to enhance the efficiency and effectiveness of test case generation for training and evaluating Large Language Models. This formalized approach with LLMs simplifies the testing process, making it more efficient and comprehensive. Leveraging natural language understanding, LLMs can intelligently formulate test cases that cover a broad range of REST API properties, ensuring comprehensive testing. The model that is developed during the research is trained using manually collected postman test cases or instances for various Rest APIs. LLMs enhance the creation of Postman test cases by automating the generation of varied and intricate test scenarios. Postman test cases offer streamlined automation, collaboration, and dynamic data handling, providing a user-friendly and efficient approach to API testing compared to traditional test cases. Thus, the model developed not only conforms to current technological standards but also holds the promise of evolving into an idea of substantial importance in future technological advancements. △ Less

Submitted 16 April, 2024; originally announced April 2024.

Convex Polygon Containment: Improving Quadratic to Near Linear Time

Authors: Timothy M. Chan, Isaac M. Hair

Abstract: We revisit a standard polygon containment problem: given a convex $k$-gon $P$ and a convex $n$-gon $Q$ in the plane, find a placement of $P$ inside $Q$ under translation and rotation (if it exists), or more generally, find the largest copy of $P$ inside $Q$ under translation, rotation, and scaling. Previous algorithms by Chazelle (1983), Sharir and Toledo (1994), and Agarwal, Amenta, and Sharir… ▽ More We revisit a standard polygon containment problem: given a convex $k$-gon $P$ and a convex $n$-gon $Q$ in the plane, find a placement of $P$ inside $Q$ under translation and rotation (if it exists), or more generally, find the largest copy of $P$ inside $Q$ under translation, rotation, and scaling. Previous algorithms by Chazelle (1983), Sharir and Toledo (1994), and Agarwal, Amenta, and Sharir (1998) all required $Ω(n^2)$ time, even in the simplest $k=3$ case. We present a significantly faster new algorithm for $k=3$ achieving $O(n$polylog $n)$ running time. Moreover, we extend the result for general $k$, achieving $O(k^{O(1/\varepsilon)}n^{1+\varepsilon})$ running time for any $\varepsilon>0$. Along the way, we also prove a new $O(k^{O(1)}n$polylog $n)$ bound on the number of similar copies of $P$ inside $Q$ that have 4 vertices of $P$ in contact with the boundary of $Q$ (assuming general position input), disproving a conjecture by Agarwal, Amenta, and Sharir (1998). △ Less

Submitted 20 March, 2024; originally announced March 2024.

Comments: To appear in SoCG 2024

Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane

Authors: Timothy M. Chan, Pingan Cheng, Da Wei Zheng

Abstract: Polynomial partitioning techniques have recently led to improved geometric data structures for a variety of fundamental problems related to semialgebraic range searching and intersection searching in 3D and higher dimensions (e.g., see [Agarwal, Aronov, Ezra, and Zahl, SoCG 2019; Ezra and Sharir, SoCG 2021; Agarwal, Aronov, Ezra, Katz, and Sharir, SoCG 2022]). They have also led to improved algori… ▽ More Polynomial partitioning techniques have recently led to improved geometric data structures for a variety of fundamental problems related to semialgebraic range searching and intersection searching in 3D and higher dimensions (e.g., see [Agarwal, Aronov, Ezra, and Zahl, SoCG 2019; Ezra and Sharir, SoCG 2021; Agarwal, Aronov, Ezra, Katz, and Sharir, SoCG 2022]). They have also led to improved algorithms for offline versions of semialgebraic range searching in 2D, via lens-cutting [Sharir and Zahl (2017)]. In this paper, we show that these techniques can yield new data structures for a number of other 2D problems even for online queries: 1. Semialgebraic range stabbing. We present a data structure for $n$ semialgebraic ranges in 2D of constant description complexity with $O(n^{3/2+\varepsilon})$ preprocessing time and space, so that we can count the number of ranges containing a query point in $O(n^{1/4+\varepsilon})$ time, for an arbitrarily small constant $\varepsilon>0$. 2. Ray shooting amid algebraic arcs. We present a data structure for $n$ algebraic arcs in 2D of constant description complexity with $O(n^{3/2+\varepsilon})$ preprocessing time and space, so that we can find the first arc hit by a query (straight-line) ray in $O(n^{1/4+\varepsilon})$ time. 3. Intersection counting amid algebraic arcs. We present a data structure for $n$ algebraic arcs in 2D of constant description complexity with $O(n^{3/2+\varepsilon})$ preprocessing time and space, so that we can count the number of intersection points with a query algebraic arc of constant description complexity in $O(n^{1/2+\varepsilon})$ time. In particular, this implies an $O(n^{3/2+\varepsilon})$-time algorithm for counting intersections between two sets of $n$ algebraic arcs in 2D. △ Less

Submitted 18 March, 2024; originally announced March 2024.

Comments: SOCG 2024

HDLdebugger: Streamlining HDL debugging with Large Language Models

Authors: Xufeng Yao, Haoyang Li, Tsz Ho Chan, Wenyi Xiao, Mingxuan Yuan, Yu Huang, Lei Chen, Bei Yu

Abstract: In the domain of chip design, Hardware Description Languages (HDLs) play a pivotal role. However, due to the complex syntax of HDLs and the limited availability of online resources, debugging HDL codes remains a difficult and time-intensive task, even for seasoned engineers. Consequently, there is a pressing need to develop automated HDL code debugging models, which can alleviate the burden on har… ▽ More In the domain of chip design, Hardware Description Languages (HDLs) play a pivotal role. However, due to the complex syntax of HDLs and the limited availability of online resources, debugging HDL codes remains a difficult and time-intensive task, even for seasoned engineers. Consequently, there is a pressing need to develop automated HDL code debugging models, which can alleviate the burden on hardware engineers. Despite the strong capabilities of Large Language Models (LLMs) in generating, completing, and debugging software code, their utilization in the specialized field of HDL debugging has been limited and, to date, has not yielded satisfactory results. In this paper, we propose an LLM-assisted HDL debugging framework, namely HDLdebugger, which consists of HDL debugging data generation via a reverse engineering approach, a search engine for retrieval-augmented generation, and a retrieval-augmented LLM fine-tuning approach. Through the integration of these components, HDLdebugger can automate and streamline HDL debugging for chip design. Our comprehensive experiments, conducted on an HDL code dataset sourced from Huawei, reveal that HDLdebugger outperforms 13 cutting-edge LLM baselines, displaying exceptional effectiveness in HDL code debugging. △ Less

Submitted 18 March, 2024; originally announced March 2024.

Comments: 13 pages,5 figures

IB-Net: Initial Branch Network for Variable Decision in Boolean Satisfiability

Authors: Tsz Ho Chan, Wenyi Xiao, Junhua Huang, Huiling Zhen, Guangji Tian, Mingxuan Yuan

Abstract: Boolean Satisfiability problems are vital components in Electronic Design Automation, particularly within the Logic Equivalence Checking process. Currently, SAT solvers are employed for these problems and neural network is tried as assistance to solvers. However, as SAT problems in the LEC context are distinctive due to their predominantly unsatisfiability nature and a substantial proportion of UN… ▽ More Boolean Satisfiability problems are vital components in Electronic Design Automation, particularly within the Logic Equivalence Checking process. Currently, SAT solvers are employed for these problems and neural network is tried as assistance to solvers. However, as SAT problems in the LEC context are distinctive due to their predominantly unsatisfiability nature and a substantial proportion of UNSAT-core variables, existing neural network assistance has proven unsuccessful in this specialized domain. To tackle this challenge, we propose IB-Net, an innovative framework utilizing graph neural networks and novel graph encoding techniques to model unsatisfiable problems and interact with state-of-the-art solvers. Extensive evaluations across solvers and datasets demonstrate IB-Net's acceleration, achieving an average runtime speedup of 5.0% on industrial data and 8.3% on SAT competition data empirically. This breakthrough advances efficient solving in LEC workflows. △ Less

Submitted 6 March, 2024; originally announced March 2024.

Comments: 7 pages, 12 figures

Enclosing Points with Geometric Objects

Authors: Timothy M. Chan, Qizheng He, Jie Xue

Abstract: Let $X$ be a set of points in $\mathbb{R}^2$ and $\mathcal{O}$ be a set of geometric objects in $\mathbb{R}^2$, where $|X| + |\mathcal{O}| = n$. We study the problem of computing a minimum subset $\mathcal{O}^* \subseteq \mathcal{O}$ that encloses all points in $X$. Here a point $x \in X$ is enclosed by $\mathcal{O}^*$ if it lies in a bounded connected component of… ▽ More Let $X$ be a set of points in $\mathbb{R}^2$ and $\mathcal{O}$ be a set of geometric objects in $\mathbb{R}^2$, where $|X| + |\mathcal{O}| = n$. We study the problem of computing a minimum subset $\mathcal{O}^* \subseteq \mathcal{O}$ that encloses all points in $X$. Here a point $x \in X$ is enclosed by $\mathcal{O}^*$ if it lies in a bounded connected component of $\mathbb{R}^2 \backslash (\bigcup_{O \in \mathcal{O}^*} O)$. We propose two algorithmic frameworks to design polynomial-time approximation algorithms for the problem. The first framework is based on sparsification and min-cut, which results in $O(1)$-approximation algorithms for unit disks, unit squares, etc. The second framework is based on LP rounding, which results in an $O(α(n)\log n)$-approximation algorithm for segments, where $α(n)$ is the inverse Ackermann function, and an $O(\log n)$-approximation algorithm for disks. △ Less

Submitted 1 March, 2024; v1 submitted 27 February, 2024; originally announced February 2024.

Comments: In SoCG'24

Design and Visual Servoing Control of a Hybrid Dual-Segment Flexible Neurosurgical Robot for Intraventricular Biopsy

Authors: Jian Chen, Mingcong Chen, Qingxiang Zhao, Shuai Wang, Yihe Wang, Ying Xiao, Jian Hu, Danny Tat Ming Chan, Kam Tong Leo Yeung, David Yuen Chung Chan, Hongbin Liu

Abstract: Traditional rigid endoscopes have challenges in flexibly treating tumors located deep in the brain, and low operability and fixed viewing angles limit its development. This study introduces a novel dual-segment flexible robotic endoscope MicroNeuro, designed to perform biopsies with dexterous surgical manipulation deep in the brain. Taking into account the uncertainty of the control model, an imag… ▽ More Traditional rigid endoscopes have challenges in flexibly treating tumors located deep in the brain, and low operability and fixed viewing angles limit its development. This study introduces a novel dual-segment flexible robotic endoscope MicroNeuro, designed to perform biopsies with dexterous surgical manipulation deep in the brain. Taking into account the uncertainty of the control model, an image-based visual servoing with online robot Jacobian estimation has been implemented to enhance motion accuracy. Furthermore, the application of model predictive control with constraints significantly bolsters the flexible robot's ability to adaptively track mobile objects and resist external interference. Experimental results underscore that the proposed control system enhances motion stability and precision. Phantom testing substantiates its considerable potential for deployment in neurosurgery. △ Less

Submitted 23 February, 2024; v1 submitted 14 February, 2024; originally announced February 2024.

Comments: Accepted by IEEE International Conference on Robotics and Automation (ICRA) 2024, 7 pages, 9 figures

Mechanism Design for Automated Market Makers

Authors: T-H. Hubert Chan, Ke Wu, Elaine Shi

Abstract: Blockchains have popularized automated market makers (AMMs). An AMM exchange is an application running on a blockchain which maintains a pool of crypto-assets and automatically trades assets with users governed by some pricing function that prices the assets based on their relative demand/supply. AMMs have created an important challenge commonly known as the Miner Extractable Value (MEV). In parti… ▽ More Blockchains have popularized automated market makers (AMMs). An AMM exchange is an application running on a blockchain which maintains a pool of crypto-assets and automatically trades assets with users governed by some pricing function that prices the assets based on their relative demand/supply. AMMs have created an important challenge commonly known as the Miner Extractable Value (MEV). In particular, the miners who control the contents and ordering of transactions in a block can extract value by front-running and back-running users' transactions, leading to arbitrage opportunities that guarantee them risk-free returns. In this paper, we consider how to design AMM mechanisms that eliminate MEV opportunities. Specifically, we propose a new AMM mechanism that processes all transactions contained within a block in a batch. We show that our new mechanism satisfies two tiers of guarantees. First, for legacy blockchains where each block is proposed by a single (possibly rotating) miner, we prove that our mechanism satisfies arbitrage resilience, i.e., a miner cannot gain risk-free profit. Moreover, we also guarantee fair treatment among all transactions within the same block, such that the miner is unable to sell off favorable positions in the block to users or arbitragers. Second, for blockchains where the block proposal process is decentralized and offers sequencing-fairness, we prove a stronger notion called incentive compatibility -- roughly speaking, we guarantee that any individual user's best response is to follow the honest strategy. △ Less

Submitted 21 April, 2024; v1 submitted 14 February, 2024; originally announced February 2024.

Comments: 1 title page and 23 pages for the main body

Fully Dynamic Geometric Vertex Cover and Matching

Authors: Sujoy Bhore, Timothy M. Chan

Abstract: In this work, we study two fundamental graph optimization problems, minimum vertex cover (MVC) and maximum-cardinality matching (MCM), for intersection graphs of geometric objects, e.g., disks, rectangles, hypercubes, etc., in $d$-dimensional Euclidean space. We consider the problems in fully dynamic settings, allowing insertions and deletions of objects. We develop a general framework for dynam… ▽ More In this work, we study two fundamental graph optimization problems, minimum vertex cover (MVC) and maximum-cardinality matching (MCM), for intersection graphs of geometric objects, e.g., disks, rectangles, hypercubes, etc., in $d$-dimensional Euclidean space. We consider the problems in fully dynamic settings, allowing insertions and deletions of objects. We develop a general framework for dynamic MVC in intersection graphs, achieving sublinear amortized update time for most natural families of geometric objects. In particular, we show that - - For a dynamic collection of disks in $\mathbb{R}^2$ or hypercubes in $\mathbb{R}^d$ (for constant $d$), it is possible to maintain a $(1+\varepsilon)$-approximate vertex cover in polylog amortized update time. These results also hold in the bipartite case. - For a dynamic collection of rectangles in $\mathbb{R}^2$, it is possible to maintain a $(\frac{3}{2}+\varepsilon)$-approximate vertex cover in polylog amortized update time. Along the way, we obtain the first near-linear time static algorithms for MVC in the above two cases with the same approximation factors. Next, we turn our attention to the MCM problem. Although our MVC algorithms automatically allow us to approximate the size of the MCM in bipartite geometric intersection graphs, they do not produce a matching. We give another general framework to maintain an approximate maximum matching, and further extend the approach to handle non-bipartite intersection graphs. In particular, we show that - - For a dynamic collection of (bichromatic or monochromatic) disks in $\mathbb{R}^2$ or hypercubes in $\mathbb{R}^d$ (for constant $d$), it is possible to maintain a $(1+\varepsilon)$-approximate matching in polylog amortized update time. △ Less

Submitted 13 February, 2024; v1 submitted 12 February, 2024; originally announced February 2024.

Comments: 25 Pages

Dynamic Geometric Connectivity in the Plane with Constant Query Time

Authors: Timothy M. Chan, Zhengcheng Huang

Abstract: We present the first fully dynamic connectivity data structures for geometric intersection graphs achieving constant query time and sublinear amortized update time for most types of geometric objects in 2D. Our data structures can answer connectivity queries between two objects, as well as "global" connectivity queries (e.g., deciding whether the entire graph is connected). Previously, the data st… ▽ More We present the first fully dynamic connectivity data structures for geometric intersection graphs achieving constant query time and sublinear amortized update time for most types of geometric objects in 2D. Our data structures can answer connectivity queries between two objects, as well as "global" connectivity queries (e.g., deciding whether the entire graph is connected). Previously, the data structure by Afshani and Chan (ESA'06) achieved such bounds only in the special case of axis-aligned line segments or rectangles but did not work for arbitrary line segments or disks, whereas the data structures by Chan, Pătraşcu and Roditty (FOCS'08) worked for more general classes of geometric objects but required $n^{Ω(1)}$ query time and could not handle global connectivity queries. Specifically, we obtain new data structures with $O(1)$ query time and amortized update time near $n^{4/5}$, $n^{7/8}$, and $n^{20/21}$ for axis-aligned line segments, disks, and arbitrary line segments respectively. Besides greatly reducing the query time, our data structures also improve the previous update times for axis-aligned line segments by Afshani and Chan (from near $n^{10/11}$ to $n^{4/5}$) and for disks by Chan, Pătraşcu, and Roditty (from near $n^{20/21}$ to $n^{7/8}$). △ Less

Submitted 20 March, 2024; v1 submitted 7 February, 2024; originally announced February 2024.

Privacy Amplification by Iteration for ADMM with (Strongly) Convex Objective Functions

Authors: T-H. Hubert Chan, Hao Xie, Mengshi Zhao

Abstract: We examine a private ADMM variant for (strongly) convex objectives which is a primal-dual iterative method. Each iteration has a user with a private function used to update the primal variable, masked by Gaussian noise for local privacy, without directly adding noise to the dual variable. Privacy amplification by iteration explores if noises from later iterations can enhance the privacy guarantee… ▽ More We examine a private ADMM variant for (strongly) convex objectives which is a primal-dual iterative method. Each iteration has a user with a private function used to update the primal variable, masked by Gaussian noise for local privacy, without directly adding noise to the dual variable. Privacy amplification by iteration explores if noises from later iterations can enhance the privacy guarantee when releasing final variables after the last iteration. Cyffers et al. [ICML 2023] explored privacy amplification by iteration for the proximal ADMM variant, where a user's entire private function is accessed and noise is added to the primal variable. In contrast, we examine a private ADMM variant requiring just one gradient access to a user's function, but both primal and dual variables must be passed between successive iterations. To apply Balle et al.'s [NeurIPS 2019] coupling framework to the gradient ADMM variant, we tackle technical challenges with novel ideas. First, we address the non-expansive mapping issue in ADMM iterations by using a customized norm. Second, because the dual variables are not masked with any noise directly, their privacy guarantees are achieved by treating two consecutive noisy ADMM iterations as a Markov operator. Our main result is that the privacy guarantee for the gradient ADMM variant can be amplified proportionally to the number of iterations. For strongly convex objective functions, this amplification exponentially increases with the number of iterations. These amplification results align with the previously studied special case of stochastic gradient descent. △ Less

Submitted 14 December, 2023; originally announced December 2023.

Fully Dynamic Algorithms for Euclidean Steiner Tree

Authors: T-H. Hubert Chan, Gramoz Goranci, Shaofeng H. -C. Jiang, Bo Wang, Quan Xue

Abstract: The Euclidean Steiner tree problem asks to find a min-cost metric graph that connects a given set of \emph{terminal} points $X$ in $\mathbb{R}^d$, possibly using points not in $X$ which are called Steiner points. Even though near-linear time $(1 + ε)$-approximation was obtained in the offline setting in seminal works of Arora and Mitchell, efficient dynamic algorithms for Steiner tree is still ope… ▽ More The Euclidean Steiner tree problem asks to find a min-cost metric graph that connects a given set of \emph{terminal} points $X$ in $\mathbb{R}^d$, possibly using points not in $X$ which are called Steiner points. Even though near-linear time $(1 + ε)$-approximation was obtained in the offline setting in seminal works of Arora and Mitchell, efficient dynamic algorithms for Steiner tree is still open. We give the first algorithm that (implicitly) maintains a $(1 + ε)$-approximate solution which is accessed via a set of tree traversal queries, subject to point insertion and deletions, with amortized update and query time $O(\poly\log n)$ with high probability. Our approach is based on an Arora-style geometric dynamic programming, and our main technical contribution is to maintain the DP subproblems in the dynamic setting efficiently. We also need to augment the DP subproblems to support the tree traversal queries. △ Less

Submitted 30 November, 2023; originally announced November 2023.

A Privacy-preserving Central Bank Ledger for Central Bank Digital Currency

Authors: Wang Mong Tikvah Chan

Abstract: Retail central bank digital currency (rCBDC) is seen as a key upgrade of the monetary system in the 21st century. However, privacy concerns are the main impediment to rCBDC's development and roll-out. On the one hand, the rights of people to keep their transactions private should be protected, including against central bank surveillance. On the other hand, the central bank needs to ensure that no… ▽ More Retail central bank digital currency (rCBDC) is seen as a key upgrade of the monetary system in the 21st century. However, privacy concerns are the main impediment to rCBDC's development and roll-out. On the one hand, the rights of people to keep their transactions private should be protected, including against central bank surveillance. On the other hand, the central bank needs to ensure that no over-issuance of money or other frauds occur, demanding a certain form of knowledge of rCBDC transactions to safeguard against malicious users. This work focuses on rCBDC architectures based on the unspent transaction output (UTXO) data model and tackles the research problem of preserving a sufficient degree of privacy for UTXO transaction records while allowing the central bank to verify their correctness. User privacy is not adequately addressed in the UTXO-based rCBDC architectures. Using evolving public keys as pseudonyms to hide the real identities of users only solves the privacy issue partially. Some information could still be leaked out. This work investigates techniques to address the shortcomings of the pseudonym approach. First, a Pedersen commitment scheme is applied to hide the transaction values of a UTXO transaction while allowing the central bank to verify that no over-issuance of rCBDC has occurred in the transaction.This work uses a Schnorr signature to prove no over-issuance of money, which reduces overheads and enables a non-interactive proof. Then, Coinjoin is applied to aggregate UTXO transactions from different users into one larger UTXO transaction to obfuscate the payer-payee relationship while preserving the correctness of the amount of money flow. This work applies k-anonymity to analyse the privacy guarantee of Coinjoin. By modelling the transaction traffic by a Poisson process, the trade-off between anonymity and transaction confirmation time of Coinjoin is analysed. △ Less

Submitted 16 August, 2023; originally announced November 2023.

Comments: 37 pages, 9 figures

ACM Class: E.3; G.3; K.4.1; K.4.4

Early detection of inflammatory arthritis to improve referrals using multimodal machine learning from blood testing, semi-structured and unstructured patient records

Authors: Bing Wang, Weizi Li, Anthony Bradlow, Antoni T. Y. Chan, Eghosa Bazuaye

Abstract: Early detection of inflammatory arthritis (IA) is critical to efficient and accurate hospital referral triage for timely treatment and preventing the deterioration of the IA disease course, especially under limited healthcare resources. The manual assessment process is the most common approach in practice for the early detection of IA, but it is extremely labor-intensive and inefficient. A large a… ▽ More Early detection of inflammatory arthritis (IA) is critical to efficient and accurate hospital referral triage for timely treatment and preventing the deterioration of the IA disease course, especially under limited healthcare resources. The manual assessment process is the most common approach in practice for the early detection of IA, but it is extremely labor-intensive and inefficient. A large amount of clinical information needs to be assessed for every referral from General Practice (GP) to the hospitals. Machine learning shows great potential in automating repetitive assessment tasks and providing decision support for the early detection of IA. However, most machine learning-based methods for IA detection rely on blood testing results. But in practice, blood testing data is not always available at the point of referrals, so we need methods to leverage multimodal data such as semi-structured and unstructured data for early detection of IA. In this research, we present fusion and ensemble learning-based methods using multimodal data to assist decision-making in the early detection of IA, and a conformal prediction-based method to quantify the uncertainty of the prediction and detect any unreliable predictions. To the best of our knowledge, our study is the first attempt to utilize multimodal data to support the early detection of IA from GP referrals. △ Less

Submitted 3 November, 2023; v1 submitted 30 October, 2023; originally announced October 2023.

Comments: Accepted in The 57th Hawaii International Conference on System Sciences, 3-6 Jan 2024, Hawaii

Adaptive Uncertainty Estimation via High-Dimensional Testing on Latent Representations

Authors: Tsai Hor Chan, Kin Wai Lau, Jiajun Shen, Guosheng Yin, Lequan Yu

Abstract: Uncertainty estimation aims to evaluate the confidence of a trained deep neural network. However, existing uncertainty estimation approaches rely on low-dimensional distributional assumptions and thus suffer from the high dimensionality of latent features. Existing approaches tend to focus on uncertainty on discrete classification probabilities, which leads to poor generalizability to uncertainty… ▽ More Uncertainty estimation aims to evaluate the confidence of a trained deep neural network. However, existing uncertainty estimation approaches rely on low-dimensional distributional assumptions and thus suffer from the high dimensionality of latent features. Existing approaches tend to focus on uncertainty on discrete classification probabilities, which leads to poor generalizability to uncertainty estimation for other tasks. Moreover, most of the literature requires seeing the out-of-distribution (OOD) data in the training for better estimation of uncertainty, which limits the uncertainty estimation performance in practice because the OOD data are typically unseen. To overcome these limitations, we propose a new framework using data-adaptive high-dimensional hypothesis testing for uncertainty estimation, which leverages the statistical properties of the feature representations. Our method directly operates on latent representations and thus does not require retraining the feature encoder under a modified objective. The test statistic relaxes the feature distribution assumptions to high dimensionality, and it is more discriminative to uncertainties in the latent representations. We demonstrate that encoding features with Bayesian neural networks can enhance testing performance and lead to more accurate uncertainty estimation. We further introduce a family-wise testing procedure to determine the optimal threshold of OOD detection, which minimizes the false discovery rate (FDR). Extensive experiments validate the satisfactory performance of our framework on uncertainty estimation and task-specific prediction over a variety of competitors. The experiments on the OOD detection task also show satisfactory performance of our method when the OOD data are unseen in the training. Codes are available at https://github.com/HKU-MedAI/bnn_uncertainty. △ Less

Submitted 25 October, 2023; originally announced October 2023.

Comments: NeurIPS 2023

An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism

Authors: Timothy M. Chan, Pingan Cheng, Da Wei Zheng

Abstract: We present the first optimal randomized algorithm for constructing the order-$k$ Voronoi diagram of $n$ points in two dimensions. The expected running time is $O(n\log n + nk)$, which improves the previous, two-decades-old result of Ramos (SoCG'99) by a $2^{O(\log^*k)}$ factor. To obtain our result, we (i) use a recent decision-tree technique of Chan and Zheng (SODA'22) in combination with Ramos's… ▽ More We present the first optimal randomized algorithm for constructing the order-$k$ Voronoi diagram of $n$ points in two dimensions. The expected running time is $O(n\log n + nk)$, which improves the previous, two-decades-old result of Ramos (SoCG'99) by a $2^{O(\log^*k)}$ factor. To obtain our result, we (i) use a recent decision-tree technique of Chan and Zheng (SODA'22) in combination with Ramos's cutting construction, to reduce the problem to verifying an order-$k$ Voronoi diagram, and (ii) solve the verification problem by a new divide-and-conquer algorithm using planar-graph separators. We also describe a deterministic algorithm for constructing the $k$-level of $n$ lines in two dimensions in $O(n\log n + nk^{1/3})$ time, and constructing the $k$-level of $n$ planes in three dimensions in $O(n\log n + nk^{3/2})$ time. These time bounds (ignoring the $n\log n$ term) match the current best upper bounds on the combinatorial complexity of the $k$-level. Previously, the same time bound in two dimensions was obtained by Chan (1999) but with randomization. △ Less

Submitted 23 October, 2023; originally announced October 2023.

Comments: To appear in SODA 2024. 16 pages, 1 figure

Faster Algorithms for Text-to-Pattern Hamming Distances

Authors: Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams, Yinzhan Xu

Abstract: We study the classic Text-to-Pattern Hamming Distances problem: given a pattern $P$ of length $m$ and a text $T$ of length $n$, both over a polynomial-size alphabet, compute the Hamming distance between $P$ and $T[i\, .\, . \, i+m-1]$ for every shift $i$, under the standard Word-RAM model with $Θ(\log n)$-bit words. - We provide an $O(n\sqrt{m})$ time Las Vegas randomized algorithm for this prob… ▽ More We study the classic Text-to-Pattern Hamming Distances problem: given a pattern $P$ of length $m$ and a text $T$ of length $n$, both over a polynomial-size alphabet, compute the Hamming distance between $P$ and $T[i\, .\, . \, i+m-1]$ for every shift $i$, under the standard Word-RAM model with $Θ(\log n)$-bit words. - We provide an $O(n\sqrt{m})$ time Las Vegas randomized algorithm for this problem, beating the decades-old $O(n \sqrt{m \log m})$ running time [Abrahamson, SICOMP 1987]. We also obtain a deterministic algorithm, with a slightly higher $O(n\sqrt{m}(\log m\log\log m)^{1/4})$ running time. Our randomized algorithm extends to the $k$-bounded setting, with running time $O\big(n+\frac{nk}{\sqrt{m}}\big)$, removing all the extra logarithmic factors from earlier algorithms [Gawrychowski and Uznański, ICALP 2018; Chan, Golan, Kociumaka, Kopelowitz and Porat, STOC 2020]. - For the $(1+ε)$-approximate version of Text-to-Pattern Hamming Distances, we give an $\tilde{O}(ε^{-0.93}n)$ time Monte Carlo randomized algorithm, beating the previous $\tilde{O}(ε^{-1}n)$ running time [Kopelowitz and Porat, FOCS 2015; Kopelowitz and Porat, SOSA 2018]. Our approximation algorithm exploits a connection with $3$SUM, and uses a combination of Fredman's trick, equality matrix product, and random sampling; in particular, we obtain new results on approximate counting versions of $3$SUM and Exact Triangle, which may be of independent interest. Our exact algorithms use a novel combination of hashing, bit-packed FFT, and recursion; in particular, we obtain a faster algorithm for computing the sumset of two integer sets, in the regime when the universe size is close to quadratic in the number of elements. We also prove a fine-grained equivalence between the exact Text-to-Pattern Hamming Distances problem and a range-restricted, counting version of $3$SUM. △ Less

Submitted 21 December, 2023; v1 submitted 19 October, 2023; originally announced October 2023.

Comments: Appeared in FOCS 2023. Abstract shortened to fit arXiv requirements. v2: added reference and discussion related to Lemma 2.2 and Appendix B

StoryAnalogy: Deriving Story-level Analogies from Large Language Models to Unlock Analogical Understanding

Authors: Cheng Jiayang, Lin Qiu, Tsz Ho Chan, Tianqing Fang, Weiqi Wang, Chunkit Chan, Dongyu Ru, Qipeng Guo, Hongming Zhang, Yangqiu Song, Yue Zhang, Zheng Zhang

Abstract: Analogy-making between narratives is crucial for human reasoning. In this paper, we evaluate the ability to identify and generate analogies by constructing a first-of-its-kind large-scale story-level analogy corpus, \textsc{StoryAnalogy}, which contains 24K story pairs from diverse domains with human annotations on two similarities from the extended Structure-Mapping Theory. We design a set of tes… ▽ More Analogy-making between narratives is crucial for human reasoning. In this paper, we evaluate the ability to identify and generate analogies by constructing a first-of-its-kind large-scale story-level analogy corpus, \textsc{StoryAnalogy}, which contains 24K story pairs from diverse domains with human annotations on two similarities from the extended Structure-Mapping Theory. We design a set of tests on \textsc{StoryAnalogy}, presenting the first evaluation of story-level analogy identification and generation. Interestingly, we find that the analogy identification tasks are incredibly difficult not only for sentence embedding models but also for the recent large language models (LLMs) such as ChatGPT and LLaMa. ChatGPT, for example, only achieved around 30% accuracy in multiple-choice questions (compared to over 85% accuracy for humans). Furthermore, we observe that the data in \textsc{StoryAnalogy} can improve the quality of analogy generation in LLMs, where a fine-tuned FlanT5-xxl model achieves comparable performance to zero-shot ChatGPT. △ Less

Submitted 23 October, 2023; v1 submitted 19 October, 2023; originally announced October 2023.

Comments: Accepted by EMNLP 2023 main conference

Simpler Reductions from Exact Triangle

Authors: Timothy M. Chan, Yinzhan Xu

Abstract: In this paper, we provide simpler reductions from Exact Triangle to two important problems in fine-grained complexity: Exact Triangle with Few Zero-Weight $4$-Cycles and All-Edges Sparse Triangle. Exact Triangle instances with few zero-weight $4$-cycles was considered by Jin and Xu [STOC 2023], who used it as an intermediate problem to show $3$SUM hardness of All-Edges Sparse Triangle with few… ▽ More In this paper, we provide simpler reductions from Exact Triangle to two important problems in fine-grained complexity: Exact Triangle with Few Zero-Weight $4$-Cycles and All-Edges Sparse Triangle. Exact Triangle instances with few zero-weight $4$-cycles was considered by Jin and Xu [STOC 2023], who used it as an intermediate problem to show $3$SUM hardness of All-Edges Sparse Triangle with few $4$-cycles (independently obtained by Abboud, Bringmann and Fischer [STOC 2023]), which is further used to show $3$SUM hardness of a variety of problems, including $4$-Cycle Enumeration, Offline Approximate Distance Oracle, Dynamic Approximate Shortest Paths and All-Nodes Shortest Cycles. We provide a simple reduction from Exact Triangle to Exact Triangle with few zero-weight $4$-cycles. Our new reduction not only simplifies Jin and Xu's previous reduction, but also strengthens the conditional lower bounds from being under the $3$SUM hypothesis to the even more believable Exact Triangle hypothesis. As a result, all conditional lower bounds shown by Jin and Xu [STOC 2023] and by Abboud, Bringmann and Fischer [STOC 2023] using All-Edges Sparse Triangle with few $4$-cycles as an intermediate problem now also hold under the Exact Triangle hypothesis. We also provide two alternative proofs of the conditional lower bound of the All-Edges Sparse Triangle problem under the Exact Triangle hypothesis, which was originally proved by Vassilevska Williams and Xu [FOCS 2020]. Both of our new reductions are simpler, and one of them is also deterministic -- all previous reductions from Exact Triangle or 3SUM to All-Edges Sparse Triangle (including Pătraşcu's seminal work [STOC 2010]) were randomized. △ Less

Submitted 17 October, 2023; originally announced October 2023.

Comments: To appear in SOSA 2024

Self-Consistent Narrative Prompts on Abductive Natural Language Inference

Authors: Chunkit Chan, Xin Liu, Tsz Ho Chan, Jiayang Cheng, Yangqiu Song, Ginny Wong, Simon See

Abstract: Abduction has long been seen as crucial for narrative comprehension and reasoning about everyday situations. The abductive natural language inference ($α$NLI) task has been proposed, and this narrative text-based task aims to infer the most plausible hypothesis from the candidates given two observations. However, the inter-sentential coherence and the model consistency have not been well exploited… ▽ More Abduction has long been seen as crucial for narrative comprehension and reasoning about everyday situations. The abductive natural language inference ($α$NLI) task has been proposed, and this narrative text-based task aims to infer the most plausible hypothesis from the candidates given two observations. However, the inter-sentential coherence and the model consistency have not been well exploited in the previous works on this task. In this work, we propose a prompt tuning model $α$-PACE, which takes self-consistency and inter-sentential coherence into consideration. Besides, we propose a general self-consistent framework that considers various narrative sequences (e.g., linear narrative and reverse chronology) for guiding the pre-trained language model in understanding the narrative context of input. We conduct extensive experiments and thorough ablation studies to illustrate the necessity and effectiveness of $α$-PACE. The performance of our method shows significant improvement against extensive competitive baselines. △ Less

Submitted 15 September, 2023; originally announced September 2023.

Comments: Accepted at IJCNLP-AACL 2023 main track

AutoLTS: Automating Cycling Stress Assessment via Contrastive Learning and Spatial Post-processing

Authors: Bo Lin, Shoshanna Saxe, Timothy C. Y. Chan

Abstract: Cycling stress assessment, which quantifies cyclists' perceived stress imposed by the built environment and motor traffics, increasingly informs cycling infrastructure planning and cycling route recommendation. However, currently calculating cycling stress is slow and data-intensive, which hinders its broader application. In this paper, We propose a deep learning framework to support accurate, fas… ▽ More Cycling stress assessment, which quantifies cyclists' perceived stress imposed by the built environment and motor traffics, increasingly informs cycling infrastructure planning and cycling route recommendation. However, currently calculating cycling stress is slow and data-intensive, which hinders its broader application. In this paper, We propose a deep learning framework to support accurate, fast, and large-scale cycling stress assessments for urban road networks based on street-view images. Our framework features i) a contrastive learning approach that leverages the ordinal relationship among cycling stress labels, and ii) a post-processing technique that enforces spatial smoothness into our predictions. On a dataset of 39,153 road segments collected in Toronto, Canada, our results demonstrate the effectiveness of our deep learning framework and the value of using image data for cycling stress assessment in the absence of high-quality road geometry and motor traffic data. △ Less

Submitted 15 August, 2023; originally announced August 2023.

Source-Aware Embedding Training on Heterogeneous Information Networks

Authors: Tsai Hor Chan, Chi Ho Wong, Jiajun Shen, Guosheng Yin

Abstract: Heterogeneous information networks (HINs) have been extensively applied to real-world tasks, such as recommendation systems, social networks, and citation networks. While existing HIN representation learning methods can effectively learn the semantic and structural features in the network, little awareness was given to the distribution discrepancy of subgraphs within a single HIN. However, we find… ▽ More Heterogeneous information networks (HINs) have been extensively applied to real-world tasks, such as recommendation systems, social networks, and citation networks. While existing HIN representation learning methods can effectively learn the semantic and structural features in the network, little awareness was given to the distribution discrepancy of subgraphs within a single HIN. However, we find that ignoring such distribution discrepancy among subgraphs from multiple sources would hinder the effectiveness of graph embedding learning algorithms. This motivates us to propose SUMSHINE (Scalable Unsupervised Multi-Source Heterogeneous Information Network Embedding) -- a scalable unsupervised framework to align the embedding distributions among multiple sources of an HIN. Experimental results on real-world datasets in a variety of downstream tasks validate the performance of our method over the state-of-the-art heterogeneous information network embedding algorithms. △ Less

Submitted 10 July, 2023; originally announced July 2023.

Comments: Published in Data Intelligence 2023

Histopathology Whole Slide Image Analysis with Heterogeneous Graph Representation Learning

Authors: Tsai Hor Chan, Fernando Julio Cendra, Lan Ma, Guosheng Yin, Lequan Yu

Abstract: Graph-based methods have been extensively applied to whole-slide histopathology image (WSI) analysis due to the advantage of modeling the spatial relationships among different entities. However, most of the existing methods focus on modeling WSIs with homogeneous graphs (e.g., with homogeneous node type). Despite their successes, these works are incapable of mining the complex structural relations… ▽ More Graph-based methods have been extensively applied to whole-slide histopathology image (WSI) analysis due to the advantage of modeling the spatial relationships among different entities. However, most of the existing methods focus on modeling WSIs with homogeneous graphs (e.g., with homogeneous node type). Despite their successes, these works are incapable of mining the complex structural relations between biological entities (e.g., the diverse interaction among different cell types) in the WSI. We propose a novel heterogeneous graph-based framework to leverage the inter-relationships among different types of nuclei for WSI analysis. Specifically, we formulate the WSI as a heterogeneous graph with "nucleus-type" attribute to each node and a semantic similarity attribute to each edge. We then present a new heterogeneous-graph edge attribute transformer (HEAT) to take advantage of the edge and node heterogeneity during massage aggregating. Further, we design a new pseudo-label-based semantic-consistent pooling mechanism to obtain graph-level features, which can mitigate the over-parameterization issue of conventional cluster-based pooling. Additionally, observing the limitations of existing association-based localization methods, we propose a causal-driven approach attributing the contribution of each node to improve the interpretability of our framework. Extensive experiments on three public TCGA benchmark datasets demonstrate that our framework outperforms the state-of-the-art methods with considerable margins on various tasks. Our codes are available at https://github.com/HKU-MedAI/WSI-HGNN. △ Less

Submitted 9 July, 2023; originally announced July 2023.

Comments: Accepted by CVPR 2023

Reconfigurable Intelligent Surface Assisted Semantic Communication Systems

Authors: Jiajia Shi, Tse-Tin Chan, Haoyuan Pan, Tat-Ming Lok

Abstract: Semantic communication, which focuses on conveying the meaning of information rather than exact bit reconstruction, has gained considerable attention in recent years. Meanwhile, reconfigurable intelligent surface (RIS) is a promising technology that can achieve high spectral and energy efficiency by dynamically reflecting incident signals through programmable passive components. In this paper, we… ▽ More Semantic communication, which focuses on conveying the meaning of information rather than exact bit reconstruction, has gained considerable attention in recent years. Meanwhile, reconfigurable intelligent surface (RIS) is a promising technology that can achieve high spectral and energy efficiency by dynamically reflecting incident signals through programmable passive components. In this paper, we put forth a semantic communication scheme aided by RIS. Using text transmission as an example, experimental results demonstrate that the RIS-assisted semantic communication system outperforms the point-to-point semantic communication system in terms of bilingual evaluation understudy (BLEU) scores in Rayleigh fading channels, especially at low signal-to-noise ratio (SNR) regimes. In addition, the RIS-assisted semantic communication system exhibits superior robustness against channel estimation errors compared to its point-to-point counterpart. RIS can improve performance as it provides extra line-of-sight (LoS) paths and enhances signal propagation conditions compared to point-to-point systems. △ Less

Submitted 29 June, 2023; v1 submitted 16 June, 2023; originally announced June 2023.

SWIFT: A modern highly-parallel gravity and smoothed particle hydrodynamics solver for astrophysical and cosmological applications

Authors: Matthieu Schaller, Josh Borrow, Peter W. Draper, Mladen Ivkovic, Stuart McAlpine, Bert Vandenbroucke, Yannick Bahé, Evgenii Chaikin, Aidan B. G. Chalk, Tsang Keung Chan, Camila Correa, Marcel van Daalen, Willem Elbers, Pedro Gonnet, Loïc Hausammann, John Helly, Filip Huško, Jacob A. Kegerreis, Folkert S. J. Nobels, Sylvia Ploeckinger, Yves Revaz, William J. Roper, Sergio Ruiz-Bonilla, Thomas D. Sandnes, Yolan Uyttenhove , et al. (2 additional authors not shown)

Abstract: Numerical simulations have become one of the key tools used by theorists in all the fields of astrophysics and cosmology. The development of modern tools that target the largest existing computing systems and exploit state-of-the-art numerical methods and algorithms is thus crucial. In this paper, we introduce the fully open-source highly-parallel, versatile, and modular coupled hydrodynamics, gra… ▽ More Numerical simulations have become one of the key tools used by theorists in all the fields of astrophysics and cosmology. The development of modern tools that target the largest existing computing systems and exploit state-of-the-art numerical methods and algorithms is thus crucial. In this paper, we introduce the fully open-source highly-parallel, versatile, and modular coupled hydrodynamics, gravity, cosmology, and galaxy-formation code SWIFT. The software package exploits hybrid shared- and distributed-memory task-based parallelism, asynchronous communications, and domain-decomposition algorithms based on balancing the workload, rather than the data, to efficiently exploit modern high-performance computing cluster architectures. Gravity is solved for using a fast-multipole-method, optionally coupled to a particle mesh solver in Fourier space to handle periodic volumes. For gas evolution, multiple modern flavours of Smoothed Particle Hydrodynamics are implemented. SWIFT also evolves neutrinos using a state-of-the-art particle-based method. Two complementary networks of sub-grid models for galaxy formation as well as extensions to simulate planetary physics are also released as part of the code. An extensive set of output options, including snapshots, light-cones, power spectra, and a coupling to structure finders are also included. We describe the overall code architecture, summarise the consistency and accuracy tests that were performed, and demonstrate the excellent weak-scaling performance of the code using a representative cosmological hydrodynamical problem with $\approx$$300$ billion particles. The code is released to the community alongside extensive documentation for both users and developers, a large selection of example test problems, and a suite of tools to aid in the analysis of large simulations run with SWIFT. △ Less

Submitted 29 March, 2024; v1 submitted 22 May, 2023; originally announced May 2023.

Comments: 43 pages, 20 figures, accepted for publication in MNRAS. Code, documentation, and examples available at www.swiftsim.com

Journal ref: MNRAS, Volume 530, Issue 2, May 2024, Pages 2378-2419

On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete $k$-Center for Small $k$

Authors: Timothy M. Chan, Qizheng He, Yuancheng Yu

Abstract: We study the time complexity of the discrete $k$-center problem and related (exact) geometric set cover problems when $k$ or the size of the cover is small. We obtain a plethora of new results: - We give the first subquadratic algorithm for rectilinear discrete 3-center in 2D, running in $\widetilde{O}(n^{3/2})$ time. - We prove a lower bound of $Ω(n^{4/3-δ})$ for rectilinear discrete 3-center… ▽ More We study the time complexity of the discrete $k$-center problem and related (exact) geometric set cover problems when $k$ or the size of the cover is small. We obtain a plethora of new results: - We give the first subquadratic algorithm for rectilinear discrete 3-center in 2D, running in $\widetilde{O}(n^{3/2})$ time. - We prove a lower bound of $Ω(n^{4/3-δ})$ for rectilinear discrete 3-center in 4D, for any constant $δ>0$, under a standard hypothesis about triangle detection in sparse graphs. - Given $n$ points and $n$ weighted axis-aligned unit squares in 2D, we give the first subquadratic algorithm for finding a minimum-weight cover of the points by 3 unit squares, running in $\widetilde{O}(n^{8/5})$ time. We also prove a lower bound of $Ω(n^{3/2-δ})$ for the same problem in 2D, under the well-known APSP Hypothesis. For arbitrary axis-aligned rectangles in 2D, our upper bound is $\widetilde{O}(n^{7/4})$. - We prove a lower bound of $Ω(n^{2-δ})$ for Euclidean discrete 2-center in 13D, under the Hyperclique Hypothesis. This lower bound nearly matches the straightforward upper bound of $\widetilde{O}(n^ω)$, if the matrix multiplication exponent $ω$ is equal to 2. - We similarly prove an $Ω(n^{k-δ})$ lower bound for Euclidean discrete $k$-center in $O(k)$ dimensions for any constant $k\ge 3$, under the Hyperclique Hypothesis. This lower bound again nearly matches known upper bounds if $ω=2$. - We also prove an $Ω(n^{2-δ})$ lower bound for the problem of finding 2 boxes to cover the largest number of points, given $n$ points and $n$ boxes in 12D. This matches the straightforward near-quadratic upper bound. △ Less

Submitted 3 May, 2023; originally announced May 2023.

Comments: Accepted to ICALP'23

Game-Theoretically Secure Protocols for the Ordinal Random Assignment Problem

Authors: T-H. Hubert Chan, Ting Wen, Hao Xie, Quan Xue

Abstract: We study game-theoretically secure protocols for the classical ordinal assignment problem (aka matching with one-sided preference), in which each player has a total preference order on items. To achieve the fairness notion of equal treatment of equals, conventionally the randomness necessary to resolve conflicts between players is assumed to be generated by some trusted authority. However, in a di… ▽ More We study game-theoretically secure protocols for the classical ordinal assignment problem (aka matching with one-sided preference), in which each player has a total preference order on items. To achieve the fairness notion of equal treatment of equals, conventionally the randomness necessary to resolve conflicts between players is assumed to be generated by some trusted authority. However, in a distributed setting, the mutually untrusted players are responsible for generating the randomness themselves. In addition to standard desirable properties such as fairness and Pareto-efficiency, we investigate the game-theoretic notion of maximin security, which guarantees that an honest player following a protocol will not be harmed even if corrupted players deviate from the protocol. Our main contribution is an impossibility result that shows no maximin secure protocol can achieve both fairness and ordinal efficiency. Specifically, this implies that the well-known probabilistic serial (PS) mechanism by Bogomolnaia and Moulin cannot be realized by any maximin secure protocol. On the other hand, we give a maximin secure protocol that achieves fairness and stability (aka ex-post Pareto-efficiency). Moreover, inspired by the PS mechanism, we show that a variant known as the OnlinePSVar (varying rates) protocol can achieve fairness, stability and uniform dominance, which means that an honest player is guaranteed to receive an item distribution that is at least as good as a uniformly random item. In some sense, this is the best one can hope for in the case when all players have the same preference order. △ Less

Submitted 26 April, 2023; originally announced April 2023.

Minimizing Age of Collection for Multiple Access in Wireless Industrial Internet of Things

Authors: Jiaxin Liang, Tse-Tin Chan, Haoyuan Pan

Abstract: This paper investigates the information freshness of Industrial Internet of Things (IIoT) systems, where each IoT device makes a partial observation of a common target and transmits the information update to a central receiver to recover the complete observation. We consider the age of collection (AoC) performance as a measure of information freshness. Unlike the conventional age of information (A… ▽ More This paper investigates the information freshness of Industrial Internet of Things (IIoT) systems, where each IoT device makes a partial observation of a common target and transmits the information update to a central receiver to recover the complete observation. We consider the age of collection (AoC) performance as a measure of information freshness. Unlike the conventional age of information (AoI) metric, the instantaneous AoC decreases only when all cooperative packets for a common observation are successfully received. Hence, effectively allocating wireless time-frequency resources among IoT devices to achieve a low average AoC at the central receiver is paramount. Three multiple access schemes are considered in this paper: time-division multiple access (TDMA) without retransmission, TDMA with retransmission, and frequency-division multiple access (FDMA). First, our theoretical analysis indicates that TDMA with retransmission outperforms the other two schemes in terms of average AoC. Subsequently, we implement information update systems based on the three schemes on software-defined radios. Experimental results demonstrate that considering the medium access control (MAC) overhead in practice, FDMA achieves a lower average AoC than TDMA with or without retransmission in the high signal-to-noise ratio (SNR) regime. In contrast, TDMA with retransmission provides a stable and relatively low average AoC over a wide SNR range, which is favorable for IIoT applications. Overall, we present a theoretical-plus-experimental investigation of AoC in IIoT information update systems. △ Less

Submitted 10 April, 2023; originally announced April 2023.

Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size

Authors: Timothy M. Chan, Zhengcheng Huang

Abstract: In SoCG 2022, Conroy and Tóth presented several constructions of sparse, low-hop spanners in geometric intersection graphs, including an $O(n\log n)$-size 3-hop spanner for $n$ disks (or fat convex objects) in the plane, and an $O(n\log^2 n)$-size 3-hop spanner for $n$ axis-aligned rectangles in the plane. Their work left open two major questions: (i) can the size be made closer to linear by allow… ▽ More In SoCG 2022, Conroy and Tóth presented several constructions of sparse, low-hop spanners in geometric intersection graphs, including an $O(n\log n)$-size 3-hop spanner for $n$ disks (or fat convex objects) in the plane, and an $O(n\log^2 n)$-size 3-hop spanner for $n$ axis-aligned rectangles in the plane. Their work left open two major questions: (i) can the size be made closer to linear by allowing larger constant stretch? and (ii) can near-linear size be achieved for more general classes of intersection graphs? We address both questions simultaneously, by presenting new constructions of constant-hop spanners that have almost linear size and that hold for a much larger class of intersection graphs. More precisely, we prove the existence of an $O(1)$-hop spanner for arbitrary string graphs with $O(nα_k(n))$ size for any constant $k$, where $α_k(n)$ denotes the $k$-th function in the inverse Ackermann hierarchy. We similarly prove the existence of an $O(1)$-hop spanner for intersection graphs of $d$-dimensional fat objects with $O(nα_k(n))$ size for any constant $k$ and $d$. We also improve on some of Conroy and Tóth's specific previous results, in either the number of hops or the size: we describe an $O(n\log n)$-size 2-hop spanner for disks (or more generally objects with linear union complexity) in the plane, and an $O(n\log n)$-size 3-hop spanner for axis-aligned rectangles in the plane. Our proofs are all simple, using separator theorems, recursion, shifted quadtrees, and shallow cuttings. △ Less

Submitted 28 March, 2023; originally announced March 2023.

Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More

Authors: Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu

Abstract: In this paper we carefully combine Fredman's trick [SICOMP'76] and Matoušek's approach for dominance product [IPL'91] to obtain powerful results in fine-grained complexity: - Under the hypothesis that APSP for undirected graphs with edge weights in $\{1, 2, \ldots, n\}$ requires $n^{3-o(1)}$ time (when $ω=2$), we show a variety of conditional lower bounds, including an $n^{7/3-o(1)}$ lower bound… ▽ More In this paper we carefully combine Fredman's trick [SICOMP'76] and Matoušek's approach for dominance product [IPL'91] to obtain powerful results in fine-grained complexity: - Under the hypothesis that APSP for undirected graphs with edge weights in $\{1, 2, \ldots, n\}$ requires $n^{3-o(1)}$ time (when $ω=2$), we show a variety of conditional lower bounds, including an $n^{7/3-o(1)}$ lower bound for unweighted directed APSP and an $n^{2.2-o(1)}$ lower bound for computing the Minimum Witness Product between two $n \times n$ Boolean matrices, even if $ω=2$, improving upon their trivial $n^2$ lower bounds. Our techniques can also be used to reduce the unweighted directed APSP problem to other problems. In particular, we show that (when $ω= 2$), if unweighted directed APSP requires $n^{2.5-o(1)}$ time, then Minimum Witness Product requires $n^{7/3-o(1)}$ time. - We show that, surprisingly, many central problems in fine-grained complexity are equivalent to their natural counting versions. In particular, we show that Min-Plus Product and Exact Triangle are subcubically equivalent to their counting versions, and 3SUM is subquadratically equivalent to its counting version. - We obtain new algorithms using new variants of the Balog-Szemerédi-Gowers theorem from additive combinatorics. For example, we get an $O(n^{3.83})$ time deterministic algorithm for exactly counting the number of shortest paths in an arbitrary weighted graph, improving the textbook $\widetilde{O}(n^{4})$ time algorithm. We also get faster algorithms for 3SUM in preprocessed universes, and deterministic algorithms for 3SUM on monotone sets in $\{1, 2, \ldots, n\}^d$. △ Less

Submitted 25 March, 2023; originally announced March 2023.

Comments: To appear at STOC'23

Timely Status Update in Relay-Assisted Cooperative Communications

Authors: Haoyuan Pan, Jian Feng, Tse-Tin Chan, Victor C. M. Leung, Jianqiang Li

Abstract: We investigate the age of information (AoI) of a relay-assisted cooperative communication system, where a source node sends status update packets to the destination node as timely as possible with the aid of a relay node. For time-slotted systems without relaying, prior works have shown that the source should generate and send a new packet to the destination every time slot to minimize the average… ▽ More We investigate the age of information (AoI) of a relay-assisted cooperative communication system, where a source node sends status update packets to the destination node as timely as possible with the aid of a relay node. For time-slotted systems without relaying, prior works have shown that the source should generate and send a new packet to the destination every time slot to minimize the average AoI, regardless of whether the destination has successfully decoded the packet in the previous slot. However, when a dedicated relay is involved, whether the relay can improve the AoI performance requires an in-depth study. In particular, the packet generation and transmission strategy of the source should be carefully designed to cooperate with the relay. Depending on whether the source and the relay are allowed to transmit simultaneously, two relay-assisted schemes are investigated: time division multiple access (TDMA) and non-orthogonal multiple access (NOMA) schemes. A key challenge in deriving their theoretical average AoI is that the destination has different probabilities of successfully receiving an update packet in different time slots. We model each scheme using a Markov chain to derive the corresponding closed-form average AoI. Interestingly, our theoretical analysis indicates that the relay-assisted schemes can only outperform the non-relay scheme in average AoI when the signal-to-noise ratio of the source-destination link is below -2dB. Furthermore, comparing the merits of relay-assisted schemes, simulation results show that the TDMA scheme has a lower energy consumption, while the NOMA counterpart typically achieves a lower average AoI. △ Less

Submitted 20 March, 2023; originally announced March 2023.

Minimum $L_\infty$ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem

Authors: Timothy M. Chan

Abstract: We present a (combinatorial) algorithm with running time close to $O(n^d)$ for computing the minimum directed $L_\infty$ Hausdorff distance between two sets of $n$ points under translations in any constant dimension $d$. This substantially improves the best previous time bound near $O(n^{5d/4})$ by Chew, Dor, Efrat, and Kedem from more than twenty years ago. Our solution is obtained by a new gener… ▽ More We present a (combinatorial) algorithm with running time close to $O(n^d)$ for computing the minimum directed $L_\infty$ Hausdorff distance between two sets of $n$ points under translations in any constant dimension $d$. This substantially improves the best previous time bound near $O(n^{5d/4})$ by Chew, Dor, Efrat, and Kedem from more than twenty years ago. Our solution is obtained by a new generalization of Chan's algorithm [FOCS'13] for Klee's measure problem. To complement this algorithmic result, we also prove a nearly matching conditional lower bound close to $Ω(n^d)$ for combinatorial algorithms, under the Combinatorial $k$-Clique Hypothesis. △ Less

Submitted 16 March, 2023; originally announced March 2023.

Comments: To appear in SoCG 2023

Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs

Authors: Timothy M. Chan

Abstract: We consider problems related to finding short cycles, small cliques, small independent sets, and small subgraphs in geometric intersection graphs. We obtain a plethora of new results. For example: * For the intersection graph of $n$ line segments in the plane, we give algorithms to find a 3-cycle in $O(n^{1.408})$ time, a size-3 independent set in $O(n^{1.652})$ time, a 4-clique in near-… ▽ More We consider problems related to finding short cycles, small cliques, small independent sets, and small subgraphs in geometric intersection graphs. We obtain a plethora of new results. For example: * For the intersection graph of $n$ line segments in the plane, we give algorithms to find a 3-cycle in $O(n^{1.408})$ time, a size-3 independent set in $O(n^{1.652})$ time, a 4-clique in near-$O(n^{24/13})$ time, and a $k$-clique (or any $k$-vertex induced subgraph) in $O(n^{0.565k+O(1)})$ time for any constant $k$; we can also compute the girth in near-$O(n^{3/2})$ time. * For the intersection graph of $n$ axis-aligned boxes in a constant dimension $d$, we give algorithms to find a 3-cycle in $O(n^{1.408})$ time for any $d$, a 4-clique (or any 4-vertex induced subgraph) in $O(n^{1.715})$ time for any $d$, a size-4 independent set in near-$O(n^{3/2})$ time for any $d$, a size-5 independent set in near-$O(n^{4/3})$ time for $d=2$, and a $k$-clique (or any $k$-vertex induced subgraph) in $O(n^{0.429k+O(1)})$ time for any $d$ and any constant $k$. * For the intersection graph of $n$ fat objects in any constant dimension $d$, we give an algorithm to find any $k$-vertex (non-induced) subgraph in $O(n\log n)$ time for any constant $k$, generalizing a result by Kaplan, Klost, Mulzer, Roddity, Seiferth, and Sharir (1999) for 3-cycles in 2D disk graphs. A variety of techniques is used, including geometric range searching, biclique covers, "high-low" tricks, graph degeneracy and separators, and shifted quadtrees. We also prove a near-$Ω(n^{4/3})$ conditional lower bound for finding a size-4 independent set for boxes. △ Less

Submitted 10 November, 2022; originally announced November 2022.

Comments: To appear in SODA 2023

Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures

Authors: Timothy M. Chan, Da Wei Zheng

Abstract: We revisit the classic problem of simplex range searching and related problems in computational geometry. We present a collection of new results which improve previous bounds by multiple logarithmic factors that were caused by the use of multi-level data structures. Highlights include the following: $\bullet$ For a set of $n$ points in a constant dimension $d$, we give data structures with… ▽ More We revisit the classic problem of simplex range searching and related problems in computational geometry. We present a collection of new results which improve previous bounds by multiple logarithmic factors that were caused by the use of multi-level data structures. Highlights include the following: $\bullet$ For a set of $n$ points in a constant dimension $d$, we give data structures with $O(n^d)$ (or slightly better) space that can answer simplex range counting queries in optimal $O(\log n)$ time and simplex range reporting queries in optimal $O(\log n + k)$ time, where $k$ denotes the output size. For semigroup range searching, we obtain $O(\log n)$ query time with $O(n^d\mathop{\rm polylog}n)$ space. Previous data structures with similar space bounds by Matoušek from nearly three decades ago had $O(\log^{d+1}n)$ or $O(\log^{d+1}n + k)$ query time. $\bullet$ For a set of $n$ simplices in a constant dimension $d$, we give data structures with $O(n)$ space that can answer stabbing counting queries (counting the number of simplices containing a query point) in $O(n^{1-1/d})$ time, and stabbing reporting queries in $O(n^{1-1/d}+k)$ time. Previous data structures had extra $\log^d n$ factors in space and query time. $\bullet$ For a set of $n$ (possibly intersecting) line segments in 2D, we give a data structure with $O(n)$ space that can answer ray shooting queries in $O(\sqrt{n})$ time. This improves Wang's recent data structure [SoCG'20] with $O(n\log n)$ space and $O(\sqrt{n}\log n)$ query time. △ Less

Submitted 20 October, 2022; v1 submitted 18 October, 2022; originally announced October 2022.

Comments: Updated abstract metadata formatting. Accepted in SODA'23

Low-Power Random Access for Timely Status Update: Packet-based or Connection-based?

Authors: Tse-Tin Chan, Jian Feng, Haoyuan Pan

Abstract: This paper studies low-power random access protocols for timely status update systems with information freshness requirements, measured by age of information (AoI). In an extensive network, a fundamental challenge is scheduling a large number of transmitters to access the wireless channel in a way that achieves low network-wide AoI while consuming minimal power. Conventional packet-based random ac… ▽ More This paper studies low-power random access protocols for timely status update systems with information freshness requirements, measured by age of information (AoI). In an extensive network, a fundamental challenge is scheduling a large number of transmitters to access the wireless channel in a way that achieves low network-wide AoI while consuming minimal power. Conventional packet-based random access protocols involve transmitters contending for the channel by sending their entire data packets. When the packet duration is long, the time wasted due to packet collisions can be significant. In contrast, connection-based random access protocols establish connections with the receiver before transmitting data packets. From an information freshness perspective, there should be conditions that favor one approach over the other. We present a comparative study of the average AoI of packet-based and connection-based random access protocols. Specifically, we consider frame slotted Aloha (FSA) as a representative of packet-based random access and design a request-then-access (RTA) protocol for connection-based random access. Our analyses indicate that the choice between packet-based or connection-based protocols depends mainly on the payload size of update packets and the transmit power budget. In particular, RTA saves power and significantly reduces AoI, especially when the payload size is large. Overall, our investigation offers insights into the practical design of random access protocols for low-power timely status update systems. △ Less

Submitted 13 December, 2023; v1 submitted 8 October, 2022; originally announced October 2022.

Machine Learning-Augmented Optimization of Large Bilevel and Two-stage Stochastic Programs: Application to Cycling Network Design

Authors: Timothy C. Y. Chan, Bo Lin, Shoshanna Saxe

Abstract: Motivated by a cycling infrastructure planning application, we present a machine learning approach to solving bilevel programs with a large number of independent followers, which as a special case includes two-stage stochastic programming. We propose an optimization model that explicitly considers a sampled subset of followers and exploits a machine learning model to estimate the objective values… ▽ More Motivated by a cycling infrastructure planning application, we present a machine learning approach to solving bilevel programs with a large number of independent followers, which as a special case includes two-stage stochastic programming. We propose an optimization model that explicitly considers a sampled subset of followers and exploits a machine learning model to estimate the objective values of unsampled followers. Unlike existing approaches, we embed machine learning model training into the optimization problem, which allows us to employ follower features that cannot be represented using leader decisions. We prove bounds on the optimality gap of the generated leader decision as measured by the original objective that considers the full follower set. We develop follower sampling algorithms to tighten the bounds and a representation learning approach to learn follower features, which are used as inputs to our machine learning model. Through numerical studies, we show that our approach generates leader decisions of higher quality compared to baselines. Finally, we perform a real-world case study in Toronto, Canada, where we solve a cycling network design problem with over one million followers. Compared to the current practice, our approach improves a transportation metric by 19.2% and can lead to a potential cost saving of $18M. △ Less

Submitted 31 March, 2024; v1 submitted 19 September, 2022; originally announced September 2022.

Improving Information Freshness via Backbone-Assisted Cooperative Access Points

Authors: Haoyuan Pan, Yu Zhou, Tse-Tin Chan, Ming Tang, Jianqiang Li, Zhihua Du

Abstract: Information freshness, characterized by age of information (AoI), is important for sensor applications involving timely status updates. In many cases, the wireless signals from one sensor can be received by multiple access points (APs). This paper investigates the average AoI for cooperative APs, in which they can share information through a wired backbone network. We first study a basic backbone-… ▽ More Information freshness, characterized by age of information (AoI), is important for sensor applications involving timely status updates. In many cases, the wireless signals from one sensor can be received by multiple access points (APs). This paper investigates the average AoI for cooperative APs, in which they can share information through a wired backbone network. We first study a basic backbone-assisted COoperative AP (Co-AP) system where APs share only decoded packets. Experimental results on software-defined radios (SDR) indicate that Co-AP significantly improves the average AoI performance over a single-AP system. Next, we investigate an improved Co-AP system, called Soft-Co-AP. In addition to sharing decoded packets, Soft-Co-AP shares and collects soft information of packets that the APs fail to decode for further joint decoding. A critical issue in Soft-Co-AP is determining the number of quantization bits that represent the soft information (each soft bit) shared over the backbone. While more quantization bits per soft bit improves the joint decoding performance, it leads to higher backbone delay. We experimentally study the average AoI of Soft-Co-AP by evaluating the tradeoff between the backbone delay and the number of quantization bits. SDR experiments show that when the number of sensors is large, Soft-Co-AP further reduces the average AoI by 12% compared with Co-AP. Interestingly, good average AoI performance is usually achieved when the number of quantization bits per soft bit is neither too large nor too small. △ Less

Submitted 13 September, 2022; originally announced September 2022.

Semantic Communication-Empowered Physical-layer Network Coding

Authors: Shuai Yang, Haoyuan Pan, Tse-Tin Chan, Zhaorui Wang

Abstract: In a two-way relay channel (TWRC), physical-layer network coding (PNC) doubles the system throughput by turning superimposed signals transmitted simultaneously by different end nodes into useful network-coded information (known as PNC decoding). Prior works indicated that the PNC decoding performance is affected by the relative phase offset between the received signals from different nodes. In par… ▽ More In a two-way relay channel (TWRC), physical-layer network coding (PNC) doubles the system throughput by turning superimposed signals transmitted simultaneously by different end nodes into useful network-coded information (known as PNC decoding). Prior works indicated that the PNC decoding performance is affected by the relative phase offset between the received signals from different nodes. In particular, some "bad" relative phase offsets could lead to huge performance degradation. Previous solutions to mitigate the relative phase offset effect were limited to the conventional bit-oriented communication paradigm, aiming at delivering a given information stream as quickly and reliably as possible. In contrast, this paper puts forth the first semantic communication-empowered PNC-enabled TWRC to address the relative phase offset issue, referred to as SC-PNC. Despite the bad relative phase offsets, SC-PNC directly extracts the semantic meaning of transmitted messages rather than ensuring accurate bit stream transmission. We jointly design deep neural network (DNN)-based transceivers at the end nodes and propose a semantic PNC decoder at the relay. Taking image delivery as an example, experimental results show that the SC-PNC TWRC achieves high and stable reconstruction quality for images under different channel conditions and relative phase offsets, compared with the conventional bit-oriented counterparts. △ Less

Submitted 1 September, 2022; originally announced September 2022.

A Feedforward Unitary Equivariant Neural Network

Authors: Pui-Wai Ma, T. -H. Hubert Chan

Abstract: We devise a new type of feedforward neural network. It is equivariant with respect to the unitary group $U(n)$. The input and output can be vectors in $\mathbb{C}^n$ with arbitrary dimension $n$. No convolution layer is required in our implementation. We avoid errors due to truncated higher order terms in Fourier-like transformation. The implementation of each layer can be done efficiently using s… ▽ More We devise a new type of feedforward neural network. It is equivariant with respect to the unitary group $U(n)$. The input and output can be vectors in $\mathbb{C}^n$ with arbitrary dimension $n$. No convolution layer is required in our implementation. We avoid errors due to truncated higher order terms in Fourier-like transformation. The implementation of each layer can be done efficiently using simple calculations. As a proof of concept, we have given empirical results on the prediction of the dynamics of atomic motion to demonstrate the practicality of our approach. △ Less

Submitted 25 August, 2022; originally announced August 2022.

Joint Study of Above Ground Biomass and Soil Organic Carbon for Total Carbon Estimation using Satellite Imagery in Scotland

Authors: Terrence Chan, Carla Arus Gomez, Anish Kothikar, Pedro Baiz

Abstract: Land Carbon verification has long been a challenge in the carbon credit market. Carbon verification methods currently available are expensive, and may generate low-quality credit. Scalable and accurate remote sensing techniques enable new approaches to monitor changes in Above Ground Biomass (AGB) and Soil Organic Carbon (SOC). The majority of state-of-the-art research employs remote sensing on AG… ▽ More Land Carbon verification has long been a challenge in the carbon credit market. Carbon verification methods currently available are expensive, and may generate low-quality credit. Scalable and accurate remote sensing techniques enable new approaches to monitor changes in Above Ground Biomass (AGB) and Soil Organic Carbon (SOC). The majority of state-of-the-art research employs remote sensing on AGB and SOC separately, although some studies indicate a positive correlation between the two. We intend to combine the two domains in our research to improve state-of-the-art total carbon estimation and to provide insight into the voluntary carbon trading market. We begin by establishing baseline model in our study area in Scotland, using state-of-the-art methodologies in the SOC and AGB domains. The effects of feature engineering techniques such as variance inflation factor and feature selection on machine learning models are then investigated. This is extended by combining predictor variables from the two domains. Finally, we leverage the possible correlation between AGB and SOC to establish a relationship between the two and propose novel models in an attempt outperform the state-of-the-art results. We compared three machine learning techniques, boosted regression tree, random forest, and xgboost. These techniques have been demonstrated to be the most effective in both domains. △ Less

Submitted 8 May, 2022; originally announced May 2022.

Power Bundle Adjustment for Large-Scale 3D Reconstruction

Authors: Simon Weber, Nikolaus Demmel, Tin Chon Chan, Daniel Cremers

Abstract: We introduce Power Bundle Adjustment as an expansion type algorithm for solving large-scale bundle adjustment problems. It is based on the power series expansion of the inverse Schur complement and constitutes a new family of solvers that we call inverse expansion methods. We theoretically justify the use of power series and we prove the convergence of our approach. Using the real-world BAL datase… ▽ More We introduce Power Bundle Adjustment as an expansion type algorithm for solving large-scale bundle adjustment problems. It is based on the power series expansion of the inverse Schur complement and constitutes a new family of solvers that we call inverse expansion methods. We theoretically justify the use of power series and we prove the convergence of our approach. Using the real-world BAL dataset we show that the proposed solver challenges the state-of-the-art iterative methods and significantly accelerates the solution of the normal equation, even for reaching a very high accuracy. This easy-to-implement solver can also complement a recently presented distributed bundle adjustment framework. We demonstrate that employing the proposed Power Bundle Adjustment as a sub-problem solver significantly improves speed and accuracy of the distributed optimization. △ Less

Submitted 17 April, 2023; v1 submitted 27 April, 2022; originally announced April 2022.

Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV

Authors: Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu

Abstract: The $3$SUM hypothesis, the APSP hypothesis and SETH are the three main hypotheses in fine-grained complexity. So far, within the area, the first two hypotheses have mainly been about integer inputs in the Word RAM model of computation. The "Real APSP" and "Real $3$SUM" hypotheses, which assert that the APSP and $3$SUM hypotheses hold for real-valued inputs in a reasonable version of the Real RAM m… ▽ More The $3$SUM hypothesis, the APSP hypothesis and SETH are the three main hypotheses in fine-grained complexity. So far, within the area, the first two hypotheses have mainly been about integer inputs in the Word RAM model of computation. The "Real APSP" and "Real $3$SUM" hypotheses, which assert that the APSP and $3$SUM hypotheses hold for real-valued inputs in a reasonable version of the Real RAM model, are even more believable than their integer counterparts. Under the very believable hypothesis that at least one of the Integer $3$SUM hypothesis, Integer APSP hypothesis or SETH is true, Abboud, Vassilevska W. and Yu [STOC 2015] showed that a problem called Triangle Collection requires $n^{3-o(1)}$ time on an $n$-node graph. Our main result is a nontrivial lower bound for a slight generalization of Triangle Collection, called All-Color-Pairs Triangle Collection, under the even more believable hypothesis that at least one of the Real $3$SUM, the Real APSP, and the OV hypotheses is true. Combined with slight modifications of prior reductions, we obtain polynomial conditional lower bounds for problems such as the (static) ST-Max Flow problem and dynamic Max Flow, now under the new weaker hypothesis. Our main result is built on the following two lines of reductions. * Real APSP and Real $3$SUM hardness for the All-Edges Sparse Triangle problem. Prior reductions only worked from the integer variants of these problems. * Real APSP and OV hardness for a variant of the Boolean Matrix Multiplication problem. Along the way we show that Triangle Collection is equivalent to a simpler restricted version of the problem, simplifying prior work. Our techniques also have other interesting implications, such as a super-linear lower bound of Integer All-Numbers $3$SUM based on the Real $3$SUM hypothesis, and a tight lower bound for a string matching problem based on the OV hypothesis. △ Less

Submitted 13 April, 2022; v1 submitted 15 March, 2022; originally announced March 2022.

Comments: To appear at STOC'22. Abstract shortened to fit arXiv requirements

OpenKBP-Opt: An international and reproducible evaluation of 76 knowledge-based planning pipelines

Authors: Aaron Babier, Rafid Mahmood, Binghao Zhang, Victor G. L. Alves, Ana Maria Barragán-Montero, Joel Beaudry, Carlos E. Cardenas, Yankui Chang, Zijie Chen, Jaehee Chun, Kelly Diaz, Harold David Eraso, Erik Faustmann, Sibaji Gaj, Skylar Gay, Mary Gronberg, Bingqi Guo, Junjun He, Gerd Heilemann, Sanchit Hira, Yuliang Huang, Fuxin Ji, Dashan Jiang, Jean Carlo Jimenez Giraldo, Hoyeon Lee , et al. (34 additional authors not shown)

Abstract: We establish an open framework for developing plan optimization models for knowledge-based planning (KBP) in radiotherapy. Our framework includes reference plans for 100 patients with head-and-neck cancer and high-quality dose predictions from 19 KBP models that were developed by different research groups during the OpenKBP Grand Challenge. The dose predictions were input to four optimization mode… ▽ More We establish an open framework for developing plan optimization models for knowledge-based planning (KBP) in radiotherapy. Our framework includes reference plans for 100 patients with head-and-neck cancer and high-quality dose predictions from 19 KBP models that were developed by different research groups during the OpenKBP Grand Challenge. The dose predictions were input to four optimization models to form 76 unique KBP pipelines that generated 7600 plans. The predictions and plans were compared to the reference plans via: dose score, which is the average mean absolute voxel-by-voxel difference in dose a model achieved; the deviation in dose-volume histogram (DVH) criterion; and the frequency of clinical planning criteria satisfaction. We also performed a theoretical investigation to justify our dose mimicking models. The range in rank order correlation of the dose score between predictions and their KBP pipelines was 0.50 to 0.62, which indicates that the quality of the predictions is generally positively correlated with the quality of the plans. Additionally, compared to the input predictions, the KBP-generated plans performed significantly better (P<0.05; one-sided Wilcoxon test) on 18 of 23 DVH criteria. Similarly, each optimization model generated plans that satisfied a higher percentage of criteria than the reference plans. Lastly, our theoretical investigation demonstrated that the dose mimicking models generated plans that are also optimal for a conventional planning model. This was the largest international effort to date for evaluating the combination of KBP prediction and optimization models. In the interest of reproducibility, our data and code is freely available at https://github.com/ababier/open-kbp-opt. △ Less

Submitted 16 February, 2022; originally announced February 2022.

Comments: 19 pages, 7 tables, 6 figures