Showing 1–50 of 78 results for author: Chung, K

Cactus: Towards Psychological Counseling Conversations using Cognitive Behavioral Theory

Authors: Suyeon Lee, Sunghwan Kim, Minju Kim, Dongjin Kang, Dongil Yang, Harim Kim, Minseok Kang, Dayi Jung, Min Hee Kim, Seungbeen Lee, Kyoung-Mee Chung, Youngjae Yu, Dongha Lee, Jinyoung Yeo

Abstract: Recently, the demand for psychological counseling has significantly increased as more individuals express concerns about their mental health. This surge has accelerated efforts to improve the accessibility of counseling by using large language models (LLMs) as counselors. To ensure client privacy, training open-source LLMs faces a key challenge: the absence of realistic counseling datasets. To add… ▽ More Recently, the demand for psychological counseling has significantly increased as more individuals express concerns about their mental health. This surge has accelerated efforts to improve the accessibility of counseling by using large language models (LLMs) as counselors. To ensure client privacy, training open-source LLMs faces a key challenge: the absence of realistic counseling datasets. To address this, we introduce Cactus, a multi-turn dialogue dataset that emulates real-life interactions using the goal-oriented and structured approach of Cognitive Behavioral Therapy (CBT). We create a diverse and realistic dataset by designing clients with varied, specific personas, and having counselors systematically apply CBT techniques in their interactions. To assess the quality of our data, we benchmark against established psychological criteria used to evaluate real counseling sessions, ensuring alignment with expert evaluations. Experimental results demonstrate that Camel, a model trained with Cactus, outperforms other models in counseling skills, highlighting its effectiveness and potential as a counseling agent. We make our data, model, and code publicly available. △ Less

Submitted 3 July, 2024; originally announced July 2024.

Comments: Under Review

Does SAM dream of EIG? Characterizing Interactive Segmenter Performance using Expected Information Gain

Authors: Kuan-I Chung, Daniel Moyer

Abstract: We introduce an assessment procedure for interactive segmentation models. Based on concepts from Bayesian Experimental Design, the procedure measures a model's understanding of point prompts and their correspondence with the desired segmentation mask. We show that Oracle Dice index measurements are insensitive or even misleading in measuring this property. We demonstrate the use of the proposed pr… ▽ More We introduce an assessment procedure for interactive segmentation models. Based on concepts from Bayesian Experimental Design, the procedure measures a model's understanding of point prompts and their correspondence with the desired segmentation mask. We show that Oracle Dice index measurements are insensitive or even misleading in measuring this property. We demonstrate the use of the proposed procedure on three interactive segmentation models and subsets of two large image segmentation datasets. △ Less

Submitted 24 April, 2024; originally announced April 2024.

Guided-Mutation Genetic Algorithm for Mobile IoT Network Relay

Authors: Gyupil Kam, Kiseop Chung

Abstract: The Internet of Things (IoT) is a communication scheme which allows various objects to exchange several types of information, enabling functions such as home automation, production management, healthcare, etc. Moreover, energy-harvesting (EH) technology is considered for IoT environment in order to reduce the need for management and enhance maintainability. However, since environments considering… ▽ More The Internet of Things (IoT) is a communication scheme which allows various objects to exchange several types of information, enabling functions such as home automation, production management, healthcare, etc. Moreover, energy-harvesting (EH) technology is considered for IoT environment in order to reduce the need for management and enhance maintainability. However, since environments considering outdoor elements such as pedestrians, vehicles and drones have been on the rise recently, it is important to consider mobility when designing an IoT network management scheme. In order to handle this challenge, prior research has made an attempt to solve this problem via variational autoencoder (VAE) and backward-pass rate evaluation method. In this article, we propose a guided-mutation genetic algorithm (GMGA) to derive a sub-optimal relaying topology for IoT systems considering energy-harvesting. Furthermore, we propose a mobility-aware iterative relaying topology algorithm, which calculates the sub-optimal relaying topology of current time frame using the topology result of the previous one. Simulation results verify that our proposed scheme effectively solves formulated IoT network problems compared to other conventional schemes, and also effectively handles IoT environments in terms of mobility. △ Less

Submitted 2 April, 2024; originally announced April 2024.

Comments: 12 pages, 8 figures;Submitted to IEEE Access on 2 April 2024

Advancing Graph Neural Networks with HL-HGAT: A Hodge-Laplacian and Attention Mechanism Approach for Heterogeneous Graph-Structured Data

Authors: Jinghan Huang, Qiufeng Chen, Yijun Bian, Pengli Zhu, Nanguang Chen, Moo K. Chung, Anqi Qiu

Abstract: Graph neural networks (GNNs) have proven effective in capturing relationships among nodes in a graph. This study introduces a novel perspective by considering a graph as a simplicial complex, encompassing nodes, edges, triangles, and $k$-simplices, enabling the definition of graph-structured data on any $k$-simplices. Our contribution is the Hodge-Laplacian heterogeneous graph attention network (H… ▽ More Graph neural networks (GNNs) have proven effective in capturing relationships among nodes in a graph. This study introduces a novel perspective by considering a graph as a simplicial complex, encompassing nodes, edges, triangles, and $k$-simplices, enabling the definition of graph-structured data on any $k$-simplices. Our contribution is the Hodge-Laplacian heterogeneous graph attention network (HL-HGAT), designed to learn heterogeneous signal representations across $k$-simplices. The HL-HGAT incorporates three key components: HL convolutional filters (HL-filters), simplicial projection (SP), and simplicial attention pooling (SAP) operators, applied to $k$-simplices. HL-filters leverage the unique topology of $k$-simplices encoded by the Hodge-Laplacian (HL) operator, operating within the spectral domain of the $k$-th HL operator. To address computation challenges, we introduce a polynomial approximation for HL-filters, exhibiting spatial localization properties. Additionally, we propose a pooling operator to coarsen $k$-simplices, combining features through simplicial attention mechanisms of self-attention and cross-attention via transformers and SP operators, capturing topological interconnections across multiple dimensions of simplices. The HL-HGAT is comprehensively evaluated across diverse graph applications, including NP-hard problems, graph multi-label and classification challenges, and graph regression tasks in logistics, computer vision, biology, chemistry, and neuroscience. The results demonstrate the model's efficacy and versatility in handling a wide range of graph-based scenarios. △ Less

Submitted 22 April, 2024; v1 submitted 11 March, 2024; originally announced March 2024.

On Central Primitives for Quantum Cryptography with Classical Communication

Authors: Kai-Min Chung, Eli Goldin, Matthew Gray

Abstract: Recent work has introduced the "Quantum-Computation Classical-Communication" (QCCC) (Chung et. al.) setting for cryptography. There has been some evidence that One Way Puzzles (OWPuzz) are the natural central cryptographic primitive for this setting (Khurana and Tomer). For a primitive to be considered central it should have several characteristics. It should be well behaved (which for this paper… ▽ More Recent work has introduced the "Quantum-Computation Classical-Communication" (QCCC) (Chung et. al.) setting for cryptography. There has been some evidence that One Way Puzzles (OWPuzz) are the natural central cryptographic primitive for this setting (Khurana and Tomer). For a primitive to be considered central it should have several characteristics. It should be well behaved (which for this paper we will think of as having amplification, combiners, and universal constructions); it should be implied by a wide variety of other primitives; and it should be equivalent to some class of useful primitives. We present combiners, correctness and security amplification, and a universal construction for OWPuzz. Our proof of security amplification uses a new and cleaner version construction of EFI from OWPuzz (in comparison to the result of Khurana and Tomer) that generalizes to weak OWPuzz and is the most technically involved section of the paper. It was previously known that OWPuzz are implied by other primitives of interest including commitments, symmetric key encryption, one way state generators (OWSG), and therefore pseudorandom states (PRS). However we are able to rule out OWPuzz's equivalence to many of these primitives by showing a black box separation between general OWPuzz and a restricted class of OWPuzz (those with efficient verification, which we call EV-OWPuzz). We then show that EV-OWPuzz are also implied by most of these primitives, which separates them from OWPuzz as well. This separation also separates extending PRS from highly compressing PRS answering an open question of Ananth et. al. △ Less

Submitted 28 June, 2024; v1 submitted 27 February, 2024; originally announced February 2024.

Comments: Accepted to CRYPTO 2024

COCOA: CBT-based Conversational Counseling Agent using Memory Specialized in Cognitive Distortions and Dynamic Prompt

Authors: Suyeon Lee, Jieun Kang, Harim Kim, Kyoung-Mee Chung, Dongha Lee, Jinyoung Yeo

Abstract: The demand for conversational agents that provide mental health care is consistently increasing. In this work, we develop a psychological counseling agent, referred to as CoCoA, that applies Cognitive Behavioral Therapy (CBT) techniques to identify and address cognitive distortions inherent in the client's statements. Specifically, we construct a memory system to efficiently manage information nec… ▽ More The demand for conversational agents that provide mental health care is consistently increasing. In this work, we develop a psychological counseling agent, referred to as CoCoA, that applies Cognitive Behavioral Therapy (CBT) techniques to identify and address cognitive distortions inherent in the client's statements. Specifically, we construct a memory system to efficiently manage information necessary for counseling while extracting high-level insights about the client from their utterances. Additionally, to ensure that the counseling agent generates appropriate responses, we introduce dynamic prompting to flexibly apply CBT techniques and facilitate the appropriate retrieval of information. We conducted dialogues between CoCoA and characters from Character.ai, creating a dataset for evaluation. Then, we asked GPT to evaluate the constructed counseling dataset, and our model demonstrated a statistically significant difference from other models. △ Less

Submitted 27 February, 2024; originally announced February 2024.

Comments: 4 pages, 2 figures

Goal-Reaching Trajectory Design Near Danger with Piecewise Affine Reach-avoid Computation

Authors: Long Kiu Chung, Wonsuhk Jung, Chuizheng Kong, Shreyas Kousik

Abstract: Autonomous mobile robots must maintain safety, but should not sacrifice performance, leading to the classical reach-avoid problem: find a trajectory that is guaranteed to reach a goal and avoid obstacles. This paper addresses the near danger case, also known as a narrow gap, where the agent starts near the goal, but must navigate through tight obstacles that block its path. The proposed method bui… ▽ More Autonomous mobile robots must maintain safety, but should not sacrifice performance, leading to the classical reach-avoid problem: find a trajectory that is guaranteed to reach a goal and avoid obstacles. This paper addresses the near danger case, also known as a narrow gap, where the agent starts near the goal, but must navigate through tight obstacles that block its path. The proposed method builds off the common approach of using a simplified planning model to generate plans, which are then tracked using a high-fidelity tracking model and controller. Existing approaches use reachability analysis to overapproximate the error between these models and ensure safety, but doing so introduces numerical approximation error conservativeness that prevents goal-reaching. The present work instead proposes a Piecewise Affine Reach-avoid Computation (PARC) method to tightly approximate the reachable set of the planning model. PARC significantly reduces conservativeness through a careful choice of the planning model and set representation, along with an effective approach to handling time-varying tracking errors. The utility of this method is demonstrated through extensive numerical experiments in which PARC outperforms state-of-the-art reach avoid methods in near-danger goal reaching. Furthermore, in a simulated demonstration, PARC enables the generation of provably-safe extreme vehicle dynamics drift parking maneuvers. A preliminary hardware demo on a TurtleBot3 also validates the method. △ Less

Submitted 28 May, 2024; v1 submitted 23 February, 2024; originally announced February 2024.

Comments: The first two authors contributed equally to the work. This work has been submitted for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

Bayes3D: fast learning and inference in structured generative models of 3D objects and scenes

Authors: Nishad Gothoskar, Matin Ghavami, Eric Li, Aidan Curtis, Michael Noseworthy, Karen Chung, Brian Patton, William T. Freeman, Joshua B. Tenenbaum, Mirko Klukas, Vikash K. Mansinghka

Abstract: Robots cannot yet match humans' ability to rapidly learn the shapes of novel 3D objects and recognize them robustly despite clutter and occlusion. We present Bayes3D, an uncertainty-aware perception system for structured 3D scenes, that reports accurate posterior uncertainty over 3D object shape, pose, and scene composition in the presence of clutter and occlusion. Bayes3D delivers these capabilit… ▽ More Robots cannot yet match humans' ability to rapidly learn the shapes of novel 3D objects and recognize them robustly despite clutter and occlusion. We present Bayes3D, an uncertainty-aware perception system for structured 3D scenes, that reports accurate posterior uncertainty over 3D object shape, pose, and scene composition in the presence of clutter and occlusion. Bayes3D delivers these capabilities via a novel hierarchical Bayesian model for 3D scenes and a GPU-accelerated coarse-to-fine sequential Monte Carlo algorithm. Quantitative experiments show that Bayes3D can learn 3D models of novel objects from just a handful of views, recognizing them more robustly and with orders of magnitude less training data than neural baselines, and tracking 3D objects faster than real time on a single GPU. We also demonstrate that Bayes3D learns complex 3D object models and accurately infers 3D scene composition when used on a Panda robot in a tabletop scenario. △ Less

Submitted 14 December, 2023; originally announced December 2023.

A Novel Lockable Spring-loaded Prismatic Spine to Support Agile Quadrupedal Locomotion

Authors: Keran Ye, Kenneth Chung, Konstantinos Karydis

Abstract: This paper introduces a way to systematically investigate the effect of compliant prismatic spines in quadrupedal robot locomotion. We develop a novel spring-loaded lockable spine module, together with a new Spinal Compliance-Integrated Quadruped (SCIQ) platform for both empirical and numerical research. Individual spine tests reveal beneficial spinal characteristics like a degressive spring, and… ▽ More This paper introduces a way to systematically investigate the effect of compliant prismatic spines in quadrupedal robot locomotion. We develop a novel spring-loaded lockable spine module, together with a new Spinal Compliance-Integrated Quadruped (SCIQ) platform for both empirical and numerical research. Individual spine tests reveal beneficial spinal characteristics like a degressive spring, and validate the efficacy of a proposed compact locking/unlocking mechanism for the spine. Benchmark vertical jumping and landing tests with our robot show comparable jumping performance between the rigid and compliant spines. An observed advantage of the compliant spine module is that it can alleviate more challenging landing conditions by absorbing impact energy and dissipating the remainder via feet slipping through much in cat-like stretching fashion. △ Less

Submitted 1 August, 2023; originally announced August 2023.

Comments: To appear in 2023 IEEE IROS

On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation

Authors: Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, Yu-Ching Shen

Abstract: Hamiltonian simulation is one of the most important problems in the field of quantum computing. There have been extended efforts on designing algorithms for faster simulation, and the evolution time $T$ for the simulation turns out to largely affect algorithm runtime. While there are some specific types of Hamiltonians that can be fast-forwarded, i.e., simulated within time $o(T)$, for large enoug… ▽ More Hamiltonian simulation is one of the most important problems in the field of quantum computing. There have been extended efforts on designing algorithms for faster simulation, and the evolution time $T$ for the simulation turns out to largely affect algorithm runtime. While there are some specific types of Hamiltonians that can be fast-forwarded, i.e., simulated within time $o(T)$, for large enough classes of Hamiltonians (e.g., all local/sparse Hamiltonians), existing simulation algorithms require running time at least linear in the evolution time $T$. On the other hand, while there exist lower bounds of $Ω(T)$ circuit size for some large classes of Hamiltonian, these lower bounds do not rule out the possibilities of Hamiltonian simulation with large but "low-depth" circuits by running things in parallel. Therefore, it is intriguing whether we can achieve fast Hamiltonian simulation with the power of parallelism. In this work, we give a negative result for the above open problem, showing that sparse Hamiltonians and (geometrically) local Hamiltonians cannot be parallelly fast-forwarded. In the oracle model, we prove that there are time-independent sparse Hamiltonians that cannot be simulated via an oracle circuit of depth $o(T)$. In the plain model, relying on the random oracle heuristic, we show that there exist time-independent local Hamiltonians and time-dependent geometrically local Hamiltonians that cannot be simulated via an oracle circuit of depth $o(T/n^c)$, where the Hamiltonians act on $n$-qubits, and $c$ is a constant. △ Less

Submitted 21 May, 2023; originally announced May 2023.

Comments: 44 pages, 7 figures

Beyond Toxic: Toxicity Detection Datasets are Not Enough for Brand Safety

Authors: Elizaveta Korotkova, Isaac Kwan Yin Chung

Abstract: The rapid growth in user generated content on social media has resulted in a significant rise in demand for automated content moderation. Various methods and frameworks have been proposed for the tasks of hate speech detection and toxic comment classification. In this work, we combine common datasets to extend these tasks to brand safety. Brand safety aims to protect commercial branding by identif… ▽ More The rapid growth in user generated content on social media has resulted in a significant rise in demand for automated content moderation. Various methods and frameworks have been proposed for the tasks of hate speech detection and toxic comment classification. In this work, we combine common datasets to extend these tasks to brand safety. Brand safety aims to protect commercial branding by identifying contexts where advertisements should not appear and covers not only toxicity, but also other potentially harmful content. As these datasets contain different label sets, we approach the overall problem as a binary classification task. We demonstrate the need for building brand safety specific datasets via the application of common toxicity detection datasets to a subset of brand safety and empirically analyze the effects of weighted sampling strategies in text classification. △ Less

Submitted 27 March, 2023; originally announced March 2023.

Heterogeneous Graph Convolutional Neural Network via Hodge-Laplacian for Brain Functional Data

Authors: Jinghan Huang, Moo K. Chung, Anqi Qiu

Abstract: This study proposes a novel heterogeneous graph convolutional neural network (HGCNN) to handle complex brain fMRI data at regional and across-region levels. We introduce a generic formulation of spectral filters on heterogeneous graphs by introducing the $k-th$ Hodge-Laplacian (HL) operator. In particular, we propose Laguerre polynomial approximations of HL spectral filters and prove that their sp… ▽ More This study proposes a novel heterogeneous graph convolutional neural network (HGCNN) to handle complex brain fMRI data at regional and across-region levels. We introduce a generic formulation of spectral filters on heterogeneous graphs by introducing the $k-th$ Hodge-Laplacian (HL) operator. In particular, we propose Laguerre polynomial approximations of HL spectral filters and prove that their spatial localization on graphs is related to the polynomial order. Furthermore, based on the bijection property of boundary operators on simplex graphs, we introduce a generic topological graph pooling (TGPool) method that can be used at any dimensional simplices. This study designs HL-node, HL-edge, and HL-HGCNN neural networks to learn signal representation at a graph node, edge levels, and both, respectively. Our experiments employ fMRI from the Adolescent Brain Cognitive Development (ABCD; n=7693) to predict general intelligence. Our results demonstrate the advantage of the HL-edge network over the HL-node network when functional brain connectivity is considered as features. The HL-HGCNN outperforms the state-of-the-art graph neural networks (GNNs) approaches, such as GAT, BrainGNN, dGCN, BrainNetCNN, and Hypergraph NN. The functional connectivity features learned from the HL-HGCNN are meaningful in interpreting neural circuits related to general intelligence. △ Less

Submitted 18 February, 2023; originally announced February 2023.

Journal ref: IPMI 2023

Machine Learning for Relaying Topology: Optimization of IoT Network with Energy Harvesting

Authors: Kiseop Chung, Jin-Taek Lim

Abstract: In this paper, we examine the internet of things system which is dedicated for smart cities, smart factory, and connected cars, etc. To support such systems in wide area with low power consumption, energy harvesting technology without wired charging infrastructure is one of the important issues for longevity of networks. In consideration of the fact that the position and amount of energy charged f… ▽ More In this paper, we examine the internet of things system which is dedicated for smart cities, smart factory, and connected cars, etc. To support such systems in wide area with low power consumption, energy harvesting technology without wired charging infrastructure is one of the important issues for longevity of networks. In consideration of the fact that the position and amount of energy charged for each device might be unbalanced according to the distribution of nodes and energy sources, the problem of maximizing the minimum throughput among all nodes becomes a NP-hard challenging issue. To overcome this complexity, we propose a machine learning based relaying topology algorithm with a novel backward-pass rate assessment method to present proper learning direction and an iterative balancing time slot allocation algorithm which can utilize the node with sufficient energy as the relay. To validate the proposed scheme, we conducted simulations on the system model we established, thus confirm that the proposed scheme is stable and superior to conventional schemes. △ Less

Submitted 27 April, 2023; v1 submitted 20 January, 2023; originally announced January 2023.

Comments: 12 pages, 11 figures; this work has been accepted for publication in IEEE Access. Accepted 24 April 2023

An Automata-based Framework for Verification and Bug Hunting in Quantum Circuits (Technical Report)

Authors: Yu-Fang Chen, Kai-Min Chung, Ondřej Lengál, Jyun-Ao Lin, Wei-Lun Tsai, Di-De Yen

Abstract: We introduce a new paradigm for analysing and finding bugs in quantum circuits. In our approach, the problem is given by a triple $\{P\}\,C\,\{Q\}$ and the question is whether, given a set $P$ of quantum states on the input of a circuit $C$, the set of quantum states on the output is equal to (or included in) a set $Q$. While this is not suitable to specify, e.g., functional correctness of a quant… ▽ More We introduce a new paradigm for analysing and finding bugs in quantum circuits. In our approach, the problem is given by a triple $\{P\}\,C\,\{Q\}$ and the question is whether, given a set $P$ of quantum states on the input of a circuit $C$, the set of quantum states on the output is equal to (or included in) a set $Q$. While this is not suitable to specify, e.g., functional correctness of a quantum circuit, it is sufficient to detect many bugs in quantum circuits. We propose a technique based on tree automata to compactly represent sets of quantum states and develop transformers to implement the semantics of quantum gates over this representation. Our technique computes with an algebraic representation of quantum states, avoiding the inaccuracy of working with floating-point numbers. We implemented the proposed approach in a prototype tool and evaluated its performance against various benchmarks from the literature. The evaluation shows that our approach is quite scalable, e.g., we managed to verify a large circuit with 40 qubits and 141,527 gates, or catch bugs injected into a circuit with 320 qubits and 1,758 gates, where all tools we compared with failed. In addition, our work establishes a connection between quantum program verification and automata, opening new possibilities to exploit the richness of automata theory and automata-based verification in the world of quantum computing. △ Less

Submitted 23 November, 2023; v1 submitted 18 January, 2023; originally announced January 2023.

Comments: This is a technical report for the paper with the same name that appeared at PLDI'23

Best-of-Both-Worlds Multiparty Quantum Computation with Publicly Verifiable Identifiable Abort

Authors: Kai-Min Chung, Mi-Ying Huang, Er-Cheng Tang, Jiapeng Zhang

Abstract: Alon et al. (CRYPTO 2021) introduced a multiparty quantum computation protocol that is secure with identifiable abort (MPQC-SWIA). However, their protocol allows only inside MPQC parties to know the identity of malicious players. This becomes problematic when two groups of people disagree and need a third party, like a jury, to verify who the malicious party is. This issue takes on heightened sign… ▽ More Alon et al. (CRYPTO 2021) introduced a multiparty quantum computation protocol that is secure with identifiable abort (MPQC-SWIA). However, their protocol allows only inside MPQC parties to know the identity of malicious players. This becomes problematic when two groups of people disagree and need a third party, like a jury, to verify who the malicious party is. This issue takes on heightened significance in the quantum setting, given that quantum states may exist in only a single copy. Thus, we emphasize the necessity of a protocol with publicly verifiable identifiable abort (PVIA), enabling outside observers with only classical computational power to agree on the identity of the malicious party in case of an abort. However, achieving MPQC with PVIA poses significant challenges due to the no-cloning theorem, and previous works proposed by Mahadev (STOC 2018) and Chung et al. (Eurocrypt 2022) for classical verification of quantum computation fall short. In this paper, we obtain the first MPQC-PVIA protocol assuming post-quantum oblivious transfer and a classical broadcast channel. The core component of our construction is a new authentication primitive called auditable quantum authentication (AQA) that identifies the malicious sender with overwhelming probability. Additionally, we provide the first MPQC protocol with best-of-both-worlds (BoBW) security, which guarantees output delivery with an honest majority and remains secure with abort even if the majority is dishonest. Our best-of-both-worlds MPQC protocol also satisfies PVIA upon abort. △ Less

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

Multi-Frequency-Aware Patch Adversarial Learning for Neural Point Cloud Rendering

Authors: Jay Karhade, Haiyue Zhu, Ka-Shing Chung, Rajesh Tripathy, Wei Lin, Marcelo H. Ang Jr

Abstract: We present a neural point cloud rendering pipeline through a novel multi-frequency-aware patch adversarial learning framework. The proposed approach aims to improve the rendering realness by minimizing the spectrum discrepancy between real and synthesized images, especially on the high-frequency localized sharpness information which causes image blur visually. Specifically, a patch multi-discrimin… ▽ More We present a neural point cloud rendering pipeline through a novel multi-frequency-aware patch adversarial learning framework. The proposed approach aims to improve the rendering realness by minimizing the spectrum discrepancy between real and synthesized images, especially on the high-frequency localized sharpness information which causes image blur visually. Specifically, a patch multi-discriminator scheme is proposed for the adversarial learning, which combines both spectral domain (Fourier Transform and Discrete Wavelet Transform) discriminators as well as the spatial (RGB) domain discriminator to force the generator to capture global and local spectral distributions of the real images. The proposed multi-discriminator scheme not only helps to improve rendering realness, but also enhance the convergence speed and stability of adversarial learning. Moreover, we introduce a noise-resistant voxelisation approach by utilizing both the appearance distance and spatial distance to exclude the spatial outlier points caused by depth noise. Our entire architecture is fully differentiable and can be learned in an end-to-end fashion. Extensive experiments show that our method produces state-of-the-art results for neural point cloud rendering by a significant margin. Our source code will be made public at a later date. △ Less

Submitted 7 October, 2022; originally announced October 2022.

Comments: 8 pages, 4 figures

Learning Topological Interactions for Multi-Class Medical Image Segmentation

Authors: Saumya Gupta, Xiaoling Hu, James Kaan, Michael Jin, Mutshipay Mpoy, Katherine Chung, Gagandeep Singh, Mary Saltz, Tahsin Kurc, Joel Saltz, Apostolos Tassiopoulos, Prateek Prasanna, Chao Chen

Abstract: Deep learning methods have achieved impressive performance for multi-class medical image segmentation. However, they are limited in their ability to encode topological interactions among different classes (e.g., containment and exclusion). These constraints naturally arise in biomedical images and can be crucial in improving segmentation quality. In this paper, we introduce a novel topological int… ▽ More Deep learning methods have achieved impressive performance for multi-class medical image segmentation. However, they are limited in their ability to encode topological interactions among different classes (e.g., containment and exclusion). These constraints naturally arise in biomedical images and can be crucial in improving segmentation quality. In this paper, we introduce a novel topological interaction module to encode the topological interactions into a deep neural network. The implementation is completely convolution-based and thus can be very efficient. This empowers us to incorporate the constraints into end-to-end training and enrich the feature representation of neural networks. The efficacy of the proposed method is validated on different types of interactions. We also demonstrate the generalizability of the method on both proprietary and public challenge datasets, in both 2D and 3D settings, as well as across different modalities such as CT and Ultrasound. Code is available at: https://github.com/TopoXLab/TopoInteraction △ Less

Submitted 20 July, 2022; originally announced July 2022.

Comments: Accepted to ECCV 2022 (Oral); 32 pages, 19 figures

Online TSP with Predictions

Authors: Hsiao-Yu Hu, Hao-Ting Wei, Meng-Hsi Li, Kai-Min Chung, Chung-Shou Liao

Abstract: We initiate the study of online routing problems with predictions, inspired by recent exciting results in the area of learning-augmented algorithms. A learning-augmented online algorithm which incorporates predictions in a black-box manner to outperform existing algorithms if the predictions are accurate while otherwise maintaining theoretical guarantees even when the predictions are extremely err… ▽ More We initiate the study of online routing problems with predictions, inspired by recent exciting results in the area of learning-augmented algorithms. A learning-augmented online algorithm which incorporates predictions in a black-box manner to outperform existing algorithms if the predictions are accurate while otherwise maintaining theoretical guarantees even when the predictions are extremely erroneous is a popular framework for overcoming pessimistic worst-case competitive analysis. In this study, we particularly begin investigating the classical online traveling salesman problem (OLTSP), where future requests are augmented with predictions. Unlike the prediction models in other previous studies, each actual request in the OLTSP, associated with its arrival time and position, may not coincide with the predicted ones, which, as imagined, leads to a troublesome situation. Our main result is to study different prediction models and design algorithms to improve the best-known results in the different settings. Moreover, we generalize the proposed results to the online dial-a-ride problem. △ Less

Submitted 30 June, 2022; originally announced June 2022.

Scaling Cross-Domain Content-Based Image Retrieval for E-commerce Snap and Search Application

Authors: Isaac Kwan Yin Chung, Minh Tran, Eran Nussinovitch

Abstract: In this industry talk at ECIR 2022, we illustrate how we approach the main challenges from large scale cross-domain content-based image retrieval using a cascade method and a combination of our visual search and classification capabilities. Specifically, we present a system that is able to handle the scale of the data for e-commerce usage and the cross-domain nature of the query and gallery image… ▽ More In this industry talk at ECIR 2022, we illustrate how we approach the main challenges from large scale cross-domain content-based image retrieval using a cascade method and a combination of our visual search and classification capabilities. Specifically, we present a system that is able to handle the scale of the data for e-commerce usage and the cross-domain nature of the query and gallery image pools. We showcase the approach applied in real-world e-commerce snap and search use case and its impact on ranking and latency performance. △ Less

Submitted 13 April, 2022; originally announced April 2022.

Comments: ECIR 2022 Industry Day

Persistent Homological State-Space Estimation of Functional Human Brain Networks at Rest

Authors: Moo K. Chung, Shih-Gu Huang, Ian C. Carroll, Vince D. Calhoun, H. Hill Goldsmith

Abstract: We introduce an innovative, data-driven topological data analysis (TDA) technique for estimating the state spaces of dynamically changing functional human brain networks at rest. Our method utilizes the Wasserstein distance to measure topological differences, enabling the clustering of brain networks into distinct topological states. This technique outperforms the commonly used k-means clustering… ▽ More We introduce an innovative, data-driven topological data analysis (TDA) technique for estimating the state spaces of dynamically changing functional human brain networks at rest. Our method utilizes the Wasserstein distance to measure topological differences, enabling the clustering of brain networks into distinct topological states. This technique outperforms the commonly used k-means clustering in identifying brain network state spaces by effectively incorporating the temporal dynamics of the data without the need for explicit model specification. We further investigate the genetic underpinnings of these topological features using a twin study design, examining the heritability of such state changes. Our findings suggest that the topology of brain networks, particularly in their dynamic state changes, may hold significant hidden genetic information. MATLAB code for the method is available at https://github.com/laplcebeltrami/PH-STAT. △ Less

Submitted 16 April, 2024; v1 submitted 31 December, 2021; originally announced January 2022.

Comments: To be published in PLOS Computational Biology

Masked Deep Q-Recommender for Effective Question Scheduling

Authors: Keunhyung Chung, Daehan Kim, Sangheon Lee, Guik Jung

Abstract: Providing appropriate questions according to a student's knowledge level is imperative in personalized learning. However, It requires a lot of manual effort for teachers to understand students' knowledge status and provide optimal questions accordingly. To address this problem, we introduce a question scheduling model that can effectively boost student knowledge level using Reinforcement Learning… ▽ More Providing appropriate questions according to a student's knowledge level is imperative in personalized learning. However, It requires a lot of manual effort for teachers to understand students' knowledge status and provide optimal questions accordingly. To address this problem, we introduce a question scheduling model that can effectively boost student knowledge level using Reinforcement Learning (RL). Our proposed method first evaluates students' concept-level knowledge using knowledge tracing (KT) model. Given predicted student knowledge, RL-based recommender predicts the benefits of each question. With curriculum range restriction and duplicate penalty, the recommender selects questions sequentially until it reaches the predefined number of questions. In an experimental setting using a student simulator, which gives 20 questions per day for two weeks, questions recommended by the proposed method increased average student knowledge level by 21.3%, superior to an expert-designed schedule baseline with a 10% increase in student knowledge levels. △ Less

Submitted 19 December, 2021; originally announced December 2021.

Comments: 10 pages, 5 figures

A Note on the Post-Quantum Security of (Ring) Signatures

Authors: Rohit Chatterjee, Kai-Min Chung, Xiao Liang, Giulio Malavolta

Abstract: This work revisits the security of classical signatures and ring signatures in a quantum world. For (ordinary) signatures, we focus on the arguably preferable security notion of blind-unforgeability recently proposed by Alagic et al. (Eurocrypt'20). We present two short signature schemes achieving this notion: one is in the quantum random oracle model, assuming quantum hardness of SIS; and the oth… ▽ More This work revisits the security of classical signatures and ring signatures in a quantum world. For (ordinary) signatures, we focus on the arguably preferable security notion of blind-unforgeability recently proposed by Alagic et al. (Eurocrypt'20). We present two short signature schemes achieving this notion: one is in the quantum random oracle model, assuming quantum hardness of SIS; and the other is in the plain model, assuming quantum hardness of LWE with super-polynomial modulus. Prior to this work, the only known blind-unforgeable schemes are Lamport's one-time signature and the Winternitz one-time signature, and both of them are in the quantum random oracle model. For ring signatures, the recent work by Chatterjee et al. (Crypto'21) proposes a definition trying to capture adversaries with quantum access to the signer. However, it is unclear if their definition, when restricted to the classical world, is as strong as the standard security notion for ring signatures. They also present a construction that only partially achieves (even) this seeming weak definition, in the sense that the adversary can only conduct superposition attacks over the messages, but not the rings. We propose a new definition that does not suffer from the above issue. Our definition is an analog to the blind-unforgeability in the ring signature setting. Moreover, assuming the quantum hardness of LWE, we construct a compiler converting any blind-unforgeable (ordinary) signatures to a ring signature satisfying our definition. △ Less

Submitted 11 December, 2021; originally announced December 2021.

Post-Quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round

Authors: Nai-Hui Chia, Kai-Min Chung, Xiao Liang, Takashi Yamakawa

Abstract: From the minimal assumption of post-quantum semi-honest oblivious transfers, we build the first $ε$-simulatable two-party computation (2PC) against quantum polynomial-time (QPT) adversaries that is both constant-round and black-box (for both the construction and security reduction). A recent work by Chia, Chung, Liu, and Yamakawa (FOCS'21) shows that post-quantum 2PC with standard simulation-based… ▽ More From the minimal assumption of post-quantum semi-honest oblivious transfers, we build the first $ε$-simulatable two-party computation (2PC) against quantum polynomial-time (QPT) adversaries that is both constant-round and black-box (for both the construction and security reduction). A recent work by Chia, Chung, Liu, and Yamakawa (FOCS'21) shows that post-quantum 2PC with standard simulation-based security is impossible in constant rounds, unless either $\mathbf{NP} \subseteq \mathbf{BQP}$ or relying on non-black-box simulation. The $ε$-simulatability we target is a relaxation of the standard simulation-based security that allows for an arbitrarily small noticeable simulation error $ε$. Moreover, when quantum communication is allowed, we can further weaken the assumption to post-quantum secure one-way functions (PQ-OWFs), while maintaining the constant-round and black-box property. Our techniques also yield the following set of constant-round and black-box two-party protocols secure against QPT adversaries, only assuming black-box access to PQ-OWFs: - extractable commitments for which the extractor is also an $ε$-simulator; - $ε$-zero-knowledge commit-and-prove whose commit stage is extractable with $ε$-simulation; - $ε$-simulatable coin-flipping; - $ε$-zero-knowledge arguments of knowledge for $\mathbf{NP}$ for which the knowledge extractor is also an $ε$-simulator; - $ε$-zero-knowledge arguments for $\mathbf{QMA}$. At the heart of the above results is a black-box extraction lemma showing how to efficiently extract secrets from QPT adversaries while disturbing their quantum state in a controllable manner, i.e., achieving $ε$-simulatability of the post-extraction state of the adversary. △ Less

Submitted 4 November, 2023; v1 submitted 16 November, 2021; originally announced November 2021.

Isogeny-based Group Signatures and Accountable Ring Signatures in QROM

Authors: Kai-Min Chung, Yao-Ching Hsieh, Mi-Ying Huang, Yu-Hsuan Huang, Tanja Lange, Bo-Yin Yang

Abstract: We provide the first isogeny-based group signature (GS) and accountable ring signature (ARS) that are provably secure in the quantum random oracle model (QROM). We do so by building an intermediate primitive called openable sigma protocol and show that every such protocol gives rise to a secure ARS and GS. Additionally, the QROM security is guaranteed if the perfect unique-response property is sat… ▽ More We provide the first isogeny-based group signature (GS) and accountable ring signature (ARS) that are provably secure in the quantum random oracle model (QROM). We do so by building an intermediate primitive called openable sigma protocol and show that every such protocol gives rise to a secure ARS and GS. Additionally, the QROM security is guaranteed if the perfect unique-response property is satisfied. Our design, with the underlying protocol satisfying this essential unique-response property, is sophisticatedly crafted for QROM security. From there, with clever twists to available proving techniques, we obtain the first isogeny-based ARS and GS that are proven QROM-secure. Concurrently, an efficient construction was proposed by Beullens et al. (Eurocrypt 2022), but is only proven secure in the classical random oracle model (ROM). Our proposal seeks stronger QROM security, although it is less efficient due to the signature size quadratically scaling with the ring/group size. △ Less

Submitted 2 November, 2022; v1 submitted 10 October, 2021; originally announced October 2021.

Prior Omission of Dissimilar Source Domain(s) for Cost-Effective Few-Shot Learning

Authors: Zezhong Wang, Hongru Wang, Kwan Wai Chung, Jia Zhu, Gabriel Pui Cheong Fung, Kam-Fai Wong

Abstract: Few-shot slot tagging is an emerging research topic in the field of Natural Language Understanding (NLU). With sufficient annotated data from source domains, the key challenge is how to train and adapt the model to another target domain which only has few labels. Conventional few-shot approaches use all the data from the source domains without considering inter-domain relations and implicitly assu… ▽ More Few-shot slot tagging is an emerging research topic in the field of Natural Language Understanding (NLU). With sufficient annotated data from source domains, the key challenge is how to train and adapt the model to another target domain which only has few labels. Conventional few-shot approaches use all the data from the source domains without considering inter-domain relations and implicitly assume each sample in the domain contributes equally. However, our experiments show that the data distribution bias among different domains will significantly affect the adaption performance. Moreover, transferring knowledge from dissimilar domains will even introduce some extra noises so that affect the performance of models. To tackle this problem, we propose an effective similarity-based method to select data from the source domains. In addition, we propose a Shared-Private Network (SP-Net) for the few-shot slot tagging task. The words from the same class would have some shared features. We extract those shared features from the limited annotated data on the target domain and merge them together as the label embedding to help us predict other unlabelled data on the target domain. The experiment shows that our method outperforms the state-of-the-art approaches with fewer source data. The result also proves that some training data from dissimilar sources are redundant and even negative for the adaption. △ Less

Submitted 11 September, 2021; originally announced September 2021.

Constrained Feedforward Neural Network Training via Reachability Analysis

Authors: Long Kiu Chung, Adam Dai, Derek Knowles, Shreyas Kousik, Grace X. Gao

Abstract: Neural networks have recently become popular for a wide variety of uses, but have seen limited application in safety-critical domains such as robotics near and around humans. This is because it remains an open challenge to train a neural network to obey safety constraints. Most existing safety-related methods only seek to verify that already-trained networks obey constraints, requiring alternating… ▽ More Neural networks have recently become popular for a wide variety of uses, but have seen limited application in safety-critical domains such as robotics near and around humans. This is because it remains an open challenge to train a neural network to obey safety constraints. Most existing safety-related methods only seek to verify that already-trained networks obey constraints, requiring alternating training and verification. Instead, this work proposes a constrained method to simultaneously train and verify a feedforward neural network with rectified linear unit (ReLU) nonlinearities. Constraints are enforced by computing the network's output-space reachable set and ensuring that it does not intersect with unsafe sets; training is achieved by formulating a novel collision-check loss function between the reachable set and unsafe portions of the output space. The reachable and unsafe sets are represented by constrained zonotopes, a convex polytope representation that enables differentiable collision checking. The proposed method is demonstrated successfully on a network with one nonlinearity layer and approximately 50 parameters. △ Less

Submitted 16 July, 2021; originally announced July 2021.

Comments: 5 pages, 4 figures

Automated Agriculture Commodity Price Prediction System with Machine Learning Techniques

Authors: Zhiyuan Chen, Howe Seng Goh, Kai Ling Sin, Kelly Lim, Nicole Ka Hei Chung, Xin Yu Liew

Abstract: The intention of this research is to study and design an automated agriculture commodity price prediction system with novel machine learning techniques. Due to the increasing large amounts historical data of agricultural commodity prices and the need of performing accurate prediction of price fluctuations, the solution has largely shifted from statistical methods to machine learning area. However,… ▽ More The intention of this research is to study and design an automated agriculture commodity price prediction system with novel machine learning techniques. Due to the increasing large amounts historical data of agricultural commodity prices and the need of performing accurate prediction of price fluctuations, the solution has largely shifted from statistical methods to machine learning area. However, the selection of proper set from historical data for forecasting still has limited consideration. On the other hand, when implementing machine learning techniques, finding a suitable model with optimal parameters for global solution, nonlinearity and avoiding curse of dimensionality are still biggest challenges, therefore machine learning strategies study are needed. In this research, we propose a web-based automated system to predict agriculture commodity price. In the two series experiments, five popular machine learning algorithms, ARIMA, SVR, Prophet, XGBoost and LSTM have been compared with large historical datasets in Malaysia and the most optimal algorithm, LSTM model with an average of 0.304 mean-square error has been selected as the prediction engine of the proposed system. △ Less

Submitted 23 June, 2021; originally announced June 2021.

Comments: This paper has been submitted to Advances in Science, Technology and Engineering Systems Journal

Beyond 5G URLLC Evolution: New Service Modes and Practical Considerations

Authors: Hirley Alves, Gweon Do Jo, JaeSheung Shin, Choongil Yeh, Nurul Huda Mahmood, Carlos Lima, Chanho Yoon, Nandana Rahatheva, Ok-Sun Park, Seokki Kim, Eunah Kim, Ville Niemelä, Hyeon Woo Lee, Ari Pouttu, Hyun Kyu Chung, Matti Latva-aho

Abstract: Ultra-reliable low latency communications (URLLC) arose to serve industrial IoT (IIoT) use cases within the 5G. Currently, it has inherent limitations to support future services. Based on state-of-the-art research and practical deployment experience, in this article, we introduce and advocate for three variants: broadband, scalable and extreme URLLC. We discuss use cases and key performance indica… ▽ More Ultra-reliable low latency communications (URLLC) arose to serve industrial IoT (IIoT) use cases within the 5G. Currently, it has inherent limitations to support future services. Based on state-of-the-art research and practical deployment experience, in this article, we introduce and advocate for three variants: broadband, scalable and extreme URLLC. We discuss use cases and key performance indicators and identify technology enablers for the new service modes. We bring practical considerations from the IIoT testbed and provide an outlook toward some new research directions. △ Less

Submitted 16 June, 2022; v1 submitted 7 June, 2021; originally announced June 2021.

Comments: The manuscript is undergoing extensive review

Lattice Paths for Persistent Diagrams

Authors: Moo K. Chung, Hernando Ombao

Abstract: Persistent homology has undergone significant development in recent years. However, one outstanding challenge is to build a coherent statistical inference procedure on persistent diagrams. In this paper, we first present a new lattice path representation for persistent diagrams. We then develop a new exact statistical inference procedure for lattice paths via combinatorial enumerations. The lattic… ▽ More Persistent homology has undergone significant development in recent years. However, one outstanding challenge is to build a coherent statistical inference procedure on persistent diagrams. In this paper, we first present a new lattice path representation for persistent diagrams. We then develop a new exact statistical inference procedure for lattice paths via combinatorial enumerations. The lattice path method is applied to the topological characterization of the protein structures of the COVID-19 virus. We demonstrate that there are topological changes during the conformational change of spike proteins. △ Less

Submitted 30 July, 2021; v1 submitted 1 May, 2021; originally announced May 2021.

On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds

Authors: Nai-Hui Chia, Kai-Min Chung, Qipeng Liu, Takashi Yamakawa

Abstract: We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for $\mathbf{NP}$. As a main result, we show that there is no constant-round post-quantum black-box zero-knowledge argument for $\mathbf{NP}$ unless $\mathbf{NP}\subseteq \mathbf{BQP}$. As constant-round black-box zero-knowledge arguments for $\mathbf{NP}$ exist in the classical setting, our main result… ▽ More We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for $\mathbf{NP}$. As a main result, we show that there is no constant-round post-quantum black-box zero-knowledge argument for $\mathbf{NP}$ unless $\mathbf{NP}\subseteq \mathbf{BQP}$. As constant-round black-box zero-knowledge arguments for $\mathbf{NP}$ exist in the classical setting, our main result points out a fundamental difference between post-quantum and classical zero-knowledge protocols. Combining previous results, we conclude that unless $\mathbf{NP}\subseteq \mathbf{BQP}$, constant-round post-quantum zero-knowledge protocols for $\mathbf{NP}$ exist if and only if we use non-black-box techniques or relax certain security requirements such as relaxing standard zero-knowledge to $ε$-zero-knowledge. Additionally, we also prove that three-round and public-coin constant-round post-quantum black-box $ε$-zero-knowledge arguments for $\mathbf{NP}$ do not exist unless $\mathbf{NP}\subseteq \mathbf{BQP}$. △ Less

Submitted 14 June, 2021; v1 submitted 20 March, 2021; originally announced March 2021.

Comments: 46 pages

Reviews: Topological Distances and Losses for Brain Networks

Authors: Moo K. Chung, Alexander Smith, Gary Shiu

Abstract: Almost all statistical and machine learning methods in analyzing brain networks rely on distances and loss functions, which are mostly Euclidean or matrix norms. The Euclidean or matrix distances may fail to capture underlying subtle topological differences in brain networks. Further, Euclidean distances are sensitive to outliers. A few extreme edge weights may severely affect the distance. Thus i… ▽ More Almost all statistical and machine learning methods in analyzing brain networks rely on distances and loss functions, which are mostly Euclidean or matrix norms. The Euclidean or matrix distances may fail to capture underlying subtle topological differences in brain networks. Further, Euclidean distances are sensitive to outliers. A few extreme edge weights may severely affect the distance. Thus it is necessary to use distances and loss functions that recognize topology of data. In this review paper, we survey various topological distance and loss functions from topological data analysis (TDA) and persistent homology that can be used in brain network analysis more effectively. Although there are many recent brain imaging studies that are based on TDA methods, possibly due to the lack of method awareness, TDA has not taken as the mainstream tool in brain imaging field yet. The main purpose of this paper is provide the relevant technical survey of these powerful tools that are immediately applicable to brain network data. △ Less

Submitted 17 February, 2021; originally announced February 2021.

Bayesian Neural Ordinary Differential Equations

Authors: Raj Dandekar, Karen Chung, Vaibhav Dixit, Mohamed Tarek, Aslan Garcia-Valadez, Krishna Vishal Vemula, Chris Rackauckas

Abstract: Recently, Neural Ordinary Differential Equations has emerged as a powerful framework for modeling physical simulations without explicitly defining the ODEs governing the system, but instead learning them via machine learning. However, the question: "Can Bayesian learning frameworks be integrated with Neural ODE's to robustly quantify the uncertainty in the weights of a Neural ODE?" remains unanswe… ▽ More Recently, Neural Ordinary Differential Equations has emerged as a powerful framework for modeling physical simulations without explicitly defining the ODEs governing the system, but instead learning them via machine learning. However, the question: "Can Bayesian learning frameworks be integrated with Neural ODE's to robustly quantify the uncertainty in the weights of a Neural ODE?" remains unanswered. In an effort to address this question, we primarily evaluate the following categories of inference methods: (a) The No-U-Turn MCMC sampler (NUTS), (b) Stochastic Gradient Hamiltonian Monte Carlo (SGHMC) and (c) Stochastic Langevin Gradient Descent (SGLD). We demonstrate the successful integration of Neural ODEs with the above Bayesian inference frameworks on classical physical systems, as well as on standard machine learning datasets like MNIST, using GPU acceleration. On the MNIST dataset, we achieve a posterior sample accuracy of 98.5% on the test ensemble of 10,000 images. Subsequently, for the first time, we demonstrate the successful integration of variational inference with normalizing flows and Neural ODEs, leading to a powerful Bayesian Neural ODE object. Finally, considering a predator-prey model and an epidemiological system, we demonstrate the probabilistic identification of model specification in partially-described dynamical systems using universal ordinary differential equations. Together, this gives a scientific machine learning tool for probabilistic estimation of epistemic uncertainties. △ Less

Submitted 6 February, 2022; v1 submitted 13 December, 2020; originally announced December 2020.

Comments: 16 pages, 10 figures, 3 tables; added new inference methods, substantially improved MNIST accuracy, revised author affiliations

Constant-round Blind Classical Verification of Quantum Sampling

Authors: Kai-Min Chung, Yi Lee, Han-Hsuan Lin, Xiaodi Wu

Abstract: In a recent breakthrough, Mahadev constructed a classical verification of quantum computation (CVQC) protocol for a classical client to delegate decision problems in BQP to an untrusted quantum prover under computational assumptions. In this work, we explore further the feasibility of CVQC with the more general sampling problems in BQP and with the desirable blindness property. We contribute affir… ▽ More In a recent breakthrough, Mahadev constructed a classical verification of quantum computation (CVQC) protocol for a classical client to delegate decision problems in BQP to an untrusted quantum prover under computational assumptions. In this work, we explore further the feasibility of CVQC with the more general sampling problems in BQP and with the desirable blindness property. We contribute affirmative solutions to both as follows. (1) Motivated by the sampling nature of many quantum applications (e.g., quantum algorithms for machine learning and quantum supremacy tasks), we initiate the study of CVQC for quantum sampling problems (denoted by SampBQP). More precisely, in a CVQC protocol for a SampBQP problem, the prover and the verifier are given an input $x\in \{0,1\}^n$ and a quantum circuit $C$, and the goal of the classical client is to learn a sample from the output $z \leftarrow C(x)$ up to a small error, from its interaction with an untrusted prover. We demonstrate its feasibility by constructing a four-message CVQC protocol for SampBQP based on the quantum Learning With Error assumption. (2) The blindness of CVQC protocols refers to a property of the protocol where the prover learns nothing, and hence is blind, about the client's input. It is a highly desirable property that has been intensively studied for the delegation of quantum computation. We provide a simple yet powerful generic compiler that transforms any CVQC protocol to a blind one while preserving its completeness and soundness errors as well as the number of rounds. Applying our compiler to (a parallel repetition of) Mahadev's CVQC protocol for BQP and our CVQC protocol for SampBQP yields the first constant-round blind CVQC protocol for BQP and SampBQP respectively, with negligible and inverse polynomial soundness errors respectively, and negligible completeness errors. △ Less

Submitted 24 October, 2021; v1 submitted 8 December, 2020; originally announced December 2020.

Comments: improved presentation. main results remain the same

Topological Learning for Brain Networks

Authors: Tananun Songdechakraiwut, Moo K. Chung

Abstract: This paper proposes a novel topological learning framework that integrates networks of different sizes and topology through persistent homology. Such challenging task is made possible through the introduction of a computationally efficient topological loss. The use of the proposed loss bypasses the intrinsic computational bottleneck associated with matching networks. We validate the method in exte… ▽ More This paper proposes a novel topological learning framework that integrates networks of different sizes and topology through persistent homology. Such challenging task is made possible through the introduction of a computationally efficient topological loss. The use of the proposed loss bypasses the intrinsic computational bottleneck associated with matching networks. We validate the method in extensive statistical simulations to assess its effectiveness when discriminating networks with different topology. The method is further demonstrated in a twin brain imaging study where we determine if brain networks are genetically heritable. The challenge here is due to the difficulty of overlaying the topologically different functional brain networks obtained from resting-state functional MRI onto the template structural brain network obtained through diffusion MRI. △ Less

Submitted 26 January, 2023; v1 submitted 25 November, 2020; originally announced December 2020.

Comments: 31 pages, 14 figures, 4 tables, code at https://github.com/topolearn

Journal ref: Ann. Appl. Stat. 17(1): 403-433 (March 2023)

A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds

Authors: Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa

Abstract: In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with erro… ▽ More In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called $ε$-zero-knowledge. Concretely, we construct the following protocols: - We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box $ε$-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of $ε$-zero-knowledge property against quantum adversaries requires novel ideas. - We construct a constant round interactive argument for NP that satisfies computational soundness and black-box $ε$-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense. △ Less

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

Comments: Fixed a minor technical issue (see Footnote 17 in page 21) and improved the proof of Claim 4.5. (10/30/2023)

Journal ref: CRYPTO 2021

Revisiting convolutional neural network on graphs with polynomial approximations of Laplace-Beltrami spectral filtering

Authors: Shih-Gu Huang, Moo K. Chung, Anqi Qiu, Alzheimer's Disease Neuroimaging Initiative

Abstract: This paper revisits spectral graph convolutional neural networks (graph-CNNs) given in Defferrard (2016) and develops the Laplace-Beltrami CNN (LB-CNN) by replacing the graph Laplacian with the LB operator. We then define spectral filters via the LB operator on a graph. We explore the feasibility of Chebyshev, Laguerre, and Hermite polynomials to approximate LB-based spectral filters and define an… ▽ More This paper revisits spectral graph convolutional neural networks (graph-CNNs) given in Defferrard (2016) and develops the Laplace-Beltrami CNN (LB-CNN) by replacing the graph Laplacian with the LB operator. We then define spectral filters via the LB operator on a graph. We explore the feasibility of Chebyshev, Laguerre, and Hermite polynomials to approximate LB-based spectral filters and define an update of the LB operator for pooling in the LBCNN. We employ the brain image data from Alzheimer's Disease Neuroimaging Initiative (ADNI) and demonstrate the use of the proposed LB-CNN. Based on the cortical thickness of the ADNI dataset, we showed that the LB-CNN didn't improve classification accuracy compared to the spectral graph-CNN. The three polynomials had a similar computational cost and showed comparable classification accuracy in the LB-CNN or spectral graph-CNN. Our findings suggest that even though the shapes of the three polynomials are different, deep learning architecture allows us to learn spectral filters such that the classification performance is not dependent on the type of the polynomials or the operators (graph Laplacian and LB operator). △ Less

Submitted 25 October, 2020; originally announced October 2020.

On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work

Authors: Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, Tai-Ning Liao

Abstract: We revisit the so-called compressed oracle technique, introduced by Zhandry for analyzing quantum algorithms in the quantum random oracle model (QROM). To start off with, we offer a concise exposition of the technique, which easily extends to the parallel-query QROM, where in each query-round the considered algorithm may make several queries to the QROM in parallel. This variant of the QROM allows… ▽ More We revisit the so-called compressed oracle technique, introduced by Zhandry for analyzing quantum algorithms in the quantum random oracle model (QROM). To start off with, we offer a concise exposition of the technique, which easily extends to the parallel-query QROM, where in each query-round the considered algorithm may make several queries to the QROM in parallel. This variant of the QROM allows for a more fine-grained query-complexity analysis. Our main technical contribution is a framework that simplifies the use of (the parallel-query generalization of) the compressed oracle technique for proving query complexity results. With our framework in place, whenever applicable, it is possible to prove quantum query complexity lower bounds by means of purely classical reasoning. More than that, for typical examples the crucial classical observations that give rise to the classical bounds are sufficient to conclude the corresponding quantum bounds. We demonstrate this on a few examples, recovering known results (like the optimality of parallel Grover), but also obtaining new results (like the optimality of parallel BHT collision search). Our main target is the hardness of finding a $q$-chain with fewer than $q$ parallel queries, i.e., a sequence $x_0, x_1,\ldots, x_q$ with $x_i = H(x_{i-1})$ for all $1 \leq i \leq q$. The above problem of finding a hash chain is of fundamental importance in the context of proofs of sequential work. Indeed, as a concrete cryptographic application of our techniques, we prove that the "Simple Proofs of Sequential Work" proposed by Cohen and Pietrzak remains secure against quantum attacks. Such an analysis is not simply a matter of plugging in our new bound; the entire protocol needs to be analyzed in the light of a quantum attack. Thanks to our framework, this can now be done with purely classical reasoning. △ Less

Submitted 9 July, 2021; v1 submitted 22 October, 2020; originally announced October 2020.

Fast Mesh Data Augmentation via Chebyshev Polynomial of Spectral filtering

Authors: Shih-Gu Huang, Moo K. Chung, Anqi Qiu, Alzheimer's Disease Neuroimaging Initiative

Abstract: Deep neural networks have recently been recognized as one of the powerful learning techniques in computer vision and medical image analysis. Trained deep neural networks need to be generalizable to new data that was not seen before. In practice, there is often insufficient training data available and augmentation is used to expand the dataset. Even though graph convolutional neural network (graph-… ▽ More Deep neural networks have recently been recognized as one of the powerful learning techniques in computer vision and medical image analysis. Trained deep neural networks need to be generalizable to new data that was not seen before. In practice, there is often insufficient training data available and augmentation is used to expand the dataset. Even though graph convolutional neural network (graph-CNN) has been widely used in deep learning, there is a lack of augmentation methods to generate data on graphs or surfaces. This study proposes two unbiased augmentation methods, Laplace-Beltrami eigenfunction Data Augmentation (LB-eigDA) and Chebyshev polynomial Data Augmentation (C-pDA), to generate new data on surfaces, whose mean is the same as that of real data. LB-eigDA augments data via the resampling of the LB coefficients. In parallel with LB-eigDA, we introduce a fast augmentation approach, C-pDA, that employs a polynomial approximation of LB spectral filters on surfaces. We design LB spectral bandpass filters by Chebyshev polynomial approximation and resample signals filtered via these filters to generate new data on surfaces. We first validate LB-eigDA and C-pDA via simulated data and demonstrate their use for improving classification accuracy. We then employ the brain images of Alzheimer's Disease Neuroimaging Initiative (ADNI) and extract cortical thickness that is represented on the cortical surface to illustrate the use of the two augmentation methods. We demonstrate that augmented cortical thickness has a similar pattern to real data. Second, we show that C-pDA is much faster than LB-eigDA. Last, we show that C-pDA can improve the AD classification accuracy of graph-CNN. △ Less

Submitted 6 October, 2020; originally announced October 2020.

Novel and Effective CNN-Based Binarization for Historically Degraded As-built Drawing Maps

Authors: Kuo-Liang Chung, De-Wei Hsieh

Abstract: Binarizing historically degraded as-built drawing (HDAD) maps is a new challenging job, especially in terms of removing the three artifacts, namely noise, the yellowing areas, and the folded lines, while preserving the foreground components well. In this paper, we first propose a semi-automatic labeling method to create the HDAD-pair dataset of which each HDAD-pair consists of one HDAD map and its… ▽ More Binarizing historically degraded as-built drawing (HDAD) maps is a new challenging job, especially in terms of removing the three artifacts, namely noise, the yellowing areas, and the folded lines, while preserving the foreground components well. In this paper, we first propose a semi-automatic labeling method to create the HDAD-pair dataset of which each HDAD-pair consists of one HDAD map and its binarized HDAD map. Based on the created training HDAD-pair dataset, we propose a convolutional neural network-based (CNN-based) binarization method to produce high-quality binarized HDAD maps. Based on the testing HDAD maps, the thorough experimental data demonstrated that in terms of the accuracy, PSNR (peak-signal-to-noise-ratio), and the perceptual effect of the binarized HDAD maps, our method substantially outperforms the nine existing binarization methods. In addition, with similar accuracy, the experimental results demonstrated the significant execution-time reduction merit of our method relative to the retrained version of the state-of-the-art CNN-based binarization methods. △ Less

Submitted 11 September, 2020; originally announced September 2020.

Introduction to logistic regression

Authors: Moo K. Chung

Abstract: For random field theory based multiple comparison corrections In brain imaging, it is often necessary to compute the distribution of the supremum of a random field. Unfortunately, computing the distribution of the supremum of the random field is not easy and requires satisfying many distributional assumptions that may not be true in real data. Thus, there is a need to come up with a different fram… ▽ More For random field theory based multiple comparison corrections In brain imaging, it is often necessary to compute the distribution of the supremum of a random field. Unfortunately, computing the distribution of the supremum of the random field is not easy and requires satisfying many distributional assumptions that may not be true in real data. Thus, there is a need to come up with a different framework that does not use the traditional statistical hypothesis testing paradigm that requires to compute p-values. With this as a motivation, we can use a different approach called the logistic regression that does not require computing the p-value and still be able to localize the regions of brain network differences. Unlike other discriminant and classification techniques that tried to classify preselected feature vectors, the method here does not require any preselected feature vectors and performs the classification at each edge level. △ Less

Submitted 28 October, 2020; v1 submitted 28 August, 2020; originally announced August 2020.

On the Hardness of Massively Parallel Computation

Authors: Kai-Min Chung, Kuan-Yi Ho, Xiaorui Sun

Abstract: We investigate whether there are inherent limits of parallelization in the (randomized) massively parallel computation (MPC) model by comparing it with the (sequential) RAM model. As our main result, we show the existence of hard functions that are essentially not parallelizable in the MPC model. Based on the widely-used random oracle methodology in cryptography with a cryptographic hash function… ▽ More We investigate whether there are inherent limits of parallelization in the (randomized) massively parallel computation (MPC) model by comparing it with the (sequential) RAM model. As our main result, we show the existence of hard functions that are essentially not parallelizable in the MPC model. Based on the widely-used random oracle methodology in cryptography with a cryptographic hash function $h:\{0,1\}^n \rightarrow \{0,1\}^n$ computable in time $t_h$, we show that there exists a function that can be computed in time $O(T\cdot t_h)$ and space $S$ by a RAM algorithm, but any MPC algorithm with local memory size $s < S/c$ for some $c>1$ requires at least $\tildeΩ(T)$ rounds to compute the function, even in the average case, for a wide range of parameters $n \leq S \leq T \leq 2^{n^{1/4}}$. Our result is almost optimal in the sense that by taking $T$ to be much larger than $t_h$, \textit{e.g.}, $T$ to be sub-exponential in $t_h$, to compute the function, the round complexity of any MPC algorithm with small local memory size is asymptotically the same (up to a polylogarithmic factor) as the time complexity of the RAM algorithm. Our result is obtained by adapting the so-called compression argument from the data structure lower bounds and cryptography literature to the context of massively parallel computation. △ Less

Submitted 14 August, 2020; originally announced August 2020.

Gaussian kernel smoothing

Authors: Moo K. Chung

Abstract: Image acquisition and segmentation are likely to introduce noise. Further image processing such as image registration and parameterization can introduce additional noise. It is thus imperative to reduce noise measurements and boost signal. In order to increase the signal-to-noise ratio (SNR) and smoothness of data required for the subsequent random field theory based statistical inference, some ty… ▽ More Image acquisition and segmentation are likely to introduce noise. Further image processing such as image registration and parameterization can introduce additional noise. It is thus imperative to reduce noise measurements and boost signal. In order to increase the signal-to-noise ratio (SNR) and smoothness of data required for the subsequent random field theory based statistical inference, some type of smoothing is necessary. Among many image smoothing methods, Gaussian kernel smoothing has emerged as a de facto smoothing technique among brain imaging researchers due to its simplicity in numerical implementation. Gaussian kernel smoothing also increases statistical sensitivity and statistical power as well as Gausianness. Gaussian kernel smoothing can be viewed as weighted averaging of voxel values. Then from the central limit theorem, the weighted average should be more Gaussian. △ Less

Submitted 29 November, 2021; v1 submitted 18 July, 2020; originally announced July 2020.

A Confidence-Calibrated MOBA Game Winner Predictor

Authors: Dong-Hee Kim, Changwoo Lee, Ki-Seok Chung

Abstract: In this paper, we propose a confidence-calibration method for predicting the winner of a famous multiplayer online battle arena (MOBA) game, League of Legends. In MOBA games, the dataset may contain a large amount of input-dependent noise; not all of such noise is observable. Hence, it is desirable to attempt a confidence-calibrated prediction. Unfortunately, most existing confidence calibration m… ▽ More In this paper, we propose a confidence-calibration method for predicting the winner of a famous multiplayer online battle arena (MOBA) game, League of Legends. In MOBA games, the dataset may contain a large amount of input-dependent noise; not all of such noise is observable. Hence, it is desirable to attempt a confidence-calibrated prediction. Unfortunately, most existing confidence calibration methods are pertaining to image and document classification tasks where consideration on uncertainty is not crucial. In this paper, we propose a novel calibration method that takes data uncertainty into consideration. The proposed method achieves an outstanding expected calibration error (ECE) (0.57%) mainly owing to data uncertainty consideration, compared to a conventional temperature scaling method of which ECE value is 1.11%. △ Less

Submitted 28 June, 2020; originally announced June 2020.

Comments: Submitted to IEEE Conference on Games(CoG) 2020

Tight Quantum Time-Space Tradeoffs for Function Inversion

Authors: Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian

Abstract: In function inversion, we are given a function $f: [N] \mapsto [N]$, and want to prepare some advice of size $S$, such that we can efficiently invert any image in time $T$. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower bounds. Investigation of this problem in the quantum setting was initiated by Nayebi, Aarons… ▽ More In function inversion, we are given a function $f: [N] \mapsto [N]$, and want to prepare some advice of size $S$, such that we can efficiently invert any image in time $T$. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower bounds. Investigation of this problem in the quantum setting was initiated by Nayebi, Aaronson, Belovs, and Trevisan (2015), who proved a lower bound of $ST^2 = \tildeΩ(N)$ for random permutations against classical advice, leaving open an intriguing possibility that Grover's search can be sped up to time $\tilde O(\sqrt{N/S})$. Recent works by Hhan, Xagawa, and Yamakawa (2019), and Chung, Liao, and Qian (2019) extended the argument for random functions and quantum advice, but the lower bound remains $ST^2 = \tildeΩ(N)$. In this work, we prove that even with quantum advice, $ST + T^2 = \tildeΩ(N)$ is required for an algorithm to invert random functions. This demonstrates that Grover's search is optimal for $S = \tilde O(\sqrt{N})$, ruling out any substantial speed-up for Grover's search even with quantum advice. Further improvements to our bounds would imply new classical circuit lower bounds, as shown by Corrigan-Gibbs and Kogan (2019). To prove this result, we develop a general framework for establishing quantum time-space lower bounds. We further demonstrate the power of our framework by proving quantum time-space lower bounds for Yao's box problem and salted cryptography. △ Less

Submitted 22 November, 2020; v1 submitted 10 June, 2020; originally announced June 2020.

Comments: Minor updates from FOCS review comments

Novel Adaptive Binary Search Strategy-First Hybrid Pyramid- and Clustering-Based CNN Filter Pruning Method without Parameters Setting

Authors: Kuo-Liang Chung, Yu-Lun Chang, Bo-Wei Tsai

Abstract: Pruning redundant filters in CNN models has received growing attention. In this paper, we propose an adaptive binary search-first hybrid pyramid- and clustering-based (ABSHPC-based) method for pruning filters automatically. In our method, for each convolutional layer, initially a hybrid pyramid data structure is constructed to store the hierarchical information of each filter. Given a tolerant acc… ▽ More Pruning redundant filters in CNN models has received growing attention. In this paper, we propose an adaptive binary search-first hybrid pyramid- and clustering-based (ABSHPC-based) method for pruning filters automatically. In our method, for each convolutional layer, initially a hybrid pyramid data structure is constructed to store the hierarchical information of each filter. Given a tolerant accuracy loss, without parameters setting, we begin from the last convolutional layer to the first layer; for each considered layer with less or equal pruning rate relative to its previous layer, our ABSHPC-based process is applied to optimally partition all filters to clusters, where each cluster is thus represented by the filter with the median root mean of the hybrid pyramid, leading to maximal removal of redundant filters. Based on the practical dataset and the CNN models, with higher accuracy, the thorough experimental results demonstrated the significant parameters and floating-point operations reduction merits of the proposed filter pruning method relative to the state-of-the-art methods. △ Less

Submitted 30 April, 2021; v1 submitted 8 June, 2020; originally announced June 2020.

Self-Supervised Feature Extraction for 3D Axon Segmentation

Authors: Tzofi Klinghoffer, Peter Morales, Young-Gyun Park, Nicholas Evans, Kwanghun Chung, Laura J. Brattain

Abstract: Existing learning-based methods to automatically trace axons in 3D brain imagery often rely on manually annotated segmentation labels. Labeling is a labor-intensive process and is not scalable to whole-brain analysis, which is needed for improved understanding of brain function. We propose a self-supervised auxiliary task that utilizes the tube-like structure of axons to build a feature extractor… ▽ More Existing learning-based methods to automatically trace axons in 3D brain imagery often rely on manually annotated segmentation labels. Labeling is a labor-intensive process and is not scalable to whole-brain analysis, which is needed for improved understanding of brain function. We propose a self-supervised auxiliary task that utilizes the tube-like structure of axons to build a feature extractor from unlabeled data. The proposed auxiliary task constrains a 3D convolutional neural network (CNN) to predict the order of permuted slices in an input 3D volume. By solving this task, the 3D CNN is able to learn features without ground-truth labels that are useful for downstream segmentation with the 3D U-Net model. To the best of our knowledge, our model is the first to perform automated segmentation of axons imaged at subcellular resolution with the SHIELD technique. We demonstrate improved segmentation performance over the 3D U-Net model on both the SHIELD PVGPe dataset and the BigNeuron Project, single neuron Janelia dataset. △ Less

Submitted 20 April, 2020; originally announced April 2020.

Comments: Accepted to CVPR Computer Vision for Microscopy Image Analysis Workshop 2020. 7 pages. 3 Figures

Classical Verification of Quantum Computations with Efficient Verifier

Authors: Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa

Abstract: In this paper, we extend the protocol of classical verification of quantum computations (CVQC) recently proposed by Mahadev to make the verification efficient. Our result is obtained in the following three steps: $\bullet$ We show that parallel repetition of Mahadev's protocol has negligible soundness error. This gives the first constant round CVQC protocol with negligible soundness error. In th… ▽ More In this paper, we extend the protocol of classical verification of quantum computations (CVQC) recently proposed by Mahadev to make the verification efficient. Our result is obtained in the following three steps: $\bullet$ We show that parallel repetition of Mahadev's protocol has negligible soundness error. This gives the first constant round CVQC protocol with negligible soundness error. In this part, we only assume the quantum hardness of the learning with error (LWE) problem similar to the Mahadev's work. $\bullet$ We construct a two-round CVQC protocol in the quantum random oracle model (QROM) where a cryptographic hash function is idealized to be a random function. This is obtained by applying the Fiat-Shamir transform to the parallel repetition version of the Mahadev's protocol. $\bullet$ We construct a two-round CVQC protocol with the efficient verifier in the CRS+QRO model where both prover and verifier can access to a (classical) common reference string generated by a trusted third party in addition to quantum access to QRO. Specifically, the verifier can verify a $QTIME(T)$ computation in time $poly(n,log T)$ where $n$ is the security parameter. For proving soundness, we assume that a standard model instantiation of our two-round protocol with a concrete hash function (say, SHA-3) is sound and the existence of post-quantum indistinguishability obfuscation and post-quantum fully homomorphic encryption in addition to the quantum hardness of the LWE problem. △ Less

Submitted 12 March, 2020; v1 submitted 2 December, 2019; originally announced December 2019.

Lower Bounds for Function Inversion with Quantum Advice

Authors: Kai-Min Chung, Tai-Ning Liao, Luowen Qian

Abstract: Function inversion is the problem that given a random function $f: [M] \to [N]$, we want to find pre-image of any image $f^{-1}(y)$ in time $T$. In this work, we revisit this problem under the preprocessing model where we can compute some auxiliary information or advice of size $S$ that only depends on $f$ but not on $y$. It is a well-studied problem in the classical settings, however, it is not c… ▽ More Function inversion is the problem that given a random function $f: [M] \to [N]$, we want to find pre-image of any image $f^{-1}(y)$ in time $T$. In this work, we revisit this problem under the preprocessing model where we can compute some auxiliary information or advice of size $S$ that only depends on $f$ but not on $y$. It is a well-studied problem in the classical settings, however, it is not clear how quantum algorithms can solve this task any better besides invoking Grover's algorithm, which does not leverage the power of preprocessing. Nayebi et al. proved a lower bound $ST^2 \ge \tildeΩ(N)$ for quantum algorithms inverting permutations, however, they only consider algorithms with classical advice. Hhan et al. subsequently extended this lower bound to fully quantum algorithms for inverting permutations. In this work, we give the same asymptotic lower bound to fully quantum algorithms for inverting functions for fully quantum algorithms under the regime where $M = O(N)$. In order to prove these bounds, we generalize the notion of quantum random access code, originally introduced by Ambainis et al., to the setting where we are given a list of (not necessarily independent) random variables, and we wish to compress them into a variable-length encoding such that we can retrieve a random element just using the encoding with high probability. As our main technical contribution, we give a nearly tight lower bound (for a wide parameter range) for this generalized notion of quantum random access codes, which may be of independent interest. △ Less

Submitted 8 April, 2020; v1 submitted 20 November, 2019; originally announced November 2019.

Comments: ITC full version

Fast Polynomial Approximation of Heat Kernel Convolution on Manifolds and Its Application to Brain Sulcal and Gyral Graph Pattern Analysis

Authors: Shih-Gu Huang, Ilwoo Lyu, Anqi Qiu, Moo K. Chung

Abstract: Heat diffusion has been widely used in brain imaging for surface fairing, mesh regularization and cortical data smoothing. Motivated by diffusion wavelets and convolutional neural networks on graphs, we present a new fast and accurate numerical scheme to solve heat diffusion on surface meshes. This is achieved by approximating the heat kernel convolution using high degree orthogonal polynomials in… ▽ More Heat diffusion has been widely used in brain imaging for surface fairing, mesh regularization and cortical data smoothing. Motivated by diffusion wavelets and convolutional neural networks on graphs, we present a new fast and accurate numerical scheme to solve heat diffusion on surface meshes. This is achieved by approximating the heat kernel convolution using high degree orthogonal polynomials in the spectral domain. We also derive the closed-form expression of the spectral decomposition of the Laplace-Beltrami operator and use it to solve heat diffusion on a manifold for the first time. The proposed fast polynomial approximation scheme avoids solving for the eigenfunctions of the Laplace-Beltrami operator, which is computationally costly for large mesh size, and the numerical instability associated with the finite element method based diffusion solvers. The proposed method is applied in localizing the male and female differences in cortical sulcal and gyral graph patterns obtained from MRI in an innovative way. The MATLAB code is available at http://www.stat.wisc.edu/~mchung/chebyshev. △ Less

Submitted 17 January, 2020; v1 submitted 6 November, 2019; originally announced November 2019.

Comments: Accepted for publication

Journal ref: IEEE Transactions on Medical Imaging, 2020

Dual-domain Cascade of U-nets for Multi-channel Magnetic Resonance Image Reconstruction

Authors: Roberto Souza, Mariana Bento, Nikita Nogovitsyn, Kevin J. Chung, R. Marc Lebel, Richard Frayne

Abstract: The U-net is a deep-learning network model that has been used to solve a number of inverse problems. In this work, the concatenation of two-element U-nets, termed the W-net, operating in k-space (K) and image (I) domains, were evaluated for multi-channel magnetic resonance (MR) image reconstruction. The two element network combinations were evaluated for the four possible image-k-space domain conf… ▽ More The U-net is a deep-learning network model that has been used to solve a number of inverse problems. In this work, the concatenation of two-element U-nets, termed the W-net, operating in k-space (K) and image (I) domains, were evaluated for multi-channel magnetic resonance (MR) image reconstruction. The two element network combinations were evaluated for the four possible image-k-space domain configurations: a) W-net II, b) W-net KK, c) W-net IK, and d) W-net KI were evaluated. Selected promising four element networks (WW-nets) were also examined. Two configurations of each network were compared: 1) Each coil channel processed independently, and 2) all channels processed simultaneously. One hundred and eleven volumetric, T1-weighted, 12-channel coil k-space datasets were used in the experiments. Normalized root mean squared error, peak signal to noise ratio, visual information fidelity and visual inspection were used to assess the reconstructed images against the fully sampled reference images. Our results indicated that networks that operate solely in the image domain are better suited when processing individual channels of multi-channel data independently. Dual domain methods are more advantageous when simultaneously reconstructing all channels of multi-channel data. Also, the appropriate cascade of U-nets compared favorably (p < 0.01) to the previously published, state-of-the-art Deep Cascade model in in three out of four experiments. △ Less

Submitted 4 November, 2019; originally announced November 2019.