Showing 1–31 of 31 results for author: Kim, D H

HyperCLOVA X Technical Report

Authors: Kang Min Yoo, Jaegeun Han, Sookyo In, Heewon Jeon, Jisu Jeong, Jaewook Kang, Hyunwook Kim, Kyung-Min Kim, Munhyong Kim, Sungju Kim, Donghyun Kwak, Hanock Kwak, Se Jung Kwon, Bado Lee, Dongsoo Lee, Gichang Lee, Jooho Lee, Baeseong Park, Seongjin Shin, Joonsang Yu, Seolki Baek, Sumin Byeon, Eungsup Cho, Dooseok Choe, Jeesung Han , et al. (371 additional authors not shown)

Abstract: We introduce HyperCLOVA X, a family of large language models (LLMs) tailored to the Korean language and culture, along with competitive capabilities in English, math, and coding. HyperCLOVA X was trained on a balanced mix of Korean, English, and code data, followed by instruction-tuning with high-quality human-annotated datasets while abiding by strict safety guidelines reflecting our commitment t… ▽ More We introduce HyperCLOVA X, a family of large language models (LLMs) tailored to the Korean language and culture, along with competitive capabilities in English, math, and coding. HyperCLOVA X was trained on a balanced mix of Korean, English, and code data, followed by instruction-tuning with high-quality human-annotated datasets while abiding by strict safety guidelines reflecting our commitment to responsible AI. The model is evaluated across various benchmarks, including comprehensive reasoning, knowledge, commonsense, factuality, coding, math, chatting, instruction-following, and harmlessness, in both Korean and English. HyperCLOVA X exhibits strong reasoning capabilities in Korean backed by a deep understanding of the language and cultural nuances. Further analysis of the inherent bilingual nature and its extension to multilingualism highlights the model's cross-lingual proficiency and strong generalization ability to untargeted languages, including machine translation between several language pairs and cross-lingual inference tasks. We believe that HyperCLOVA X can provide helpful guidance for regions or countries in developing their sovereign LLMs. △ Less

Submitted 13 April, 2024; v1 submitted 2 April, 2024; originally announced April 2024.

Comments: 44 pages; updated authors list and fixed author names

Automatic Speech Recognition (ASR) for the Diagnosis of pronunciation of Speech Sound Disorders in Korean children

Authors: Taekyung Ahn, Yeonjung Hong, Younggon Im, Do Hyung Kim, Dayoung Kang, Joo Won Jeong, Jae Won Kim, Min Jung Kim, Ah-ra Cho, Dae-Hyun Jang, Hosung Nam

Abstract: This study presents a model of automatic speech recognition (ASR) designed to diagnose pronunciation issues in children with speech sound disorders (SSDs) to replace manual transcriptions in clinical procedures. Since ASR models trained for general purposes primarily predict input speech into real words, employing a well-known high-performance ASR model for evaluating pronunciation in children wit… ▽ More This study presents a model of automatic speech recognition (ASR) designed to diagnose pronunciation issues in children with speech sound disorders (SSDs) to replace manual transcriptions in clinical procedures. Since ASR models trained for general purposes primarily predict input speech into real words, employing a well-known high-performance ASR model for evaluating pronunciation in children with SSDs is impractical. We fine-tuned the wav2vec 2.0 XLS-R model to recognize speech as pronounced rather than as existing words. The model was fine-tuned with a speech dataset from 137 children with inadequate speech production pronouncing 73 Korean words selected for actual clinical diagnosis. The model's predictions of the pronunciations of the words matched the human annotations with about 90% accuracy. While the model still requires improvement in recognizing unclear pronunciation, this study demonstrates that ASR models can streamline complex pronunciation error diagnostic procedures in clinical fields. △ Less

Submitted 12 March, 2024; originally announced March 2024.

Comments: 12 pages, 2 figures

ACM Class: I.2.7

AINeedsPlanner: A Workbook to Support Effective Collaboration Between AI Experts and Clients

Authors: Dae Hyun Kim, Hyungyu Shin, Shakhnozakhon Yadgarova, Jinho Son, Hariharan Subramonyam, Juho Kim

Abstract: Clients often partner with AI experts to develop AI applications tailored to their needs. In these partnerships, careful planning and clear communication are critical, as inaccurate or incomplete specifications can result in misaligned model characteristics, expensive reworks, and potential friction between collaborators. Unfortunately, given the complexity of requirements ranging from functionali… ▽ More Clients often partner with AI experts to develop AI applications tailored to their needs. In these partnerships, careful planning and clear communication are critical, as inaccurate or incomplete specifications can result in misaligned model characteristics, expensive reworks, and potential friction between collaborators. Unfortunately, given the complexity of requirements ranging from functionality, data, and governance, effective guidelines for collaborative specification of requirements in client-AI expert collaborations are missing. In this work, we introduce AINeedsPlanner, a workbook that AI experts and clients can use to facilitate effective interchange and clear specifications. The workbook is based on (1) an interview of 10 completed AI application project teams, which identifies and characterizes steps in AI application planning and (2) a study with 12 AI experts, which defines a taxonomy of AI experts' information needs and dimensions that affect the information needs. Finally, we demonstrate the workbook's utility with two case studies in real-world settings. △ Less

Submitted 26 May, 2024; v1 submitted 13 February, 2024; originally announced February 2024.

Comments: To appear in DIS 2024

Natural Language Dataset Generation Framework for Visualizations Powered by Large Language Models

Authors: Hyung-Kwon Ko, Hyeon Jeon, Gwanmo Park, Dae Hyun Kim, Nam Wook Kim, Juho Kim, Jinwook Seo

Abstract: We introduce VL2NL, a Large Language Model (LLM) framework that generates rich and diverse NL datasets using only Vega-Lite specifications as input, thereby streamlining the development of Natural Language Interfaces (NLIs) for data visualization. To synthesize relevant chart semantics accurately and enhance syntactic diversity in each NL dataset, we leverage 1) a guided discovery incorporated int… ▽ More We introduce VL2NL, a Large Language Model (LLM) framework that generates rich and diverse NL datasets using only Vega-Lite specifications as input, thereby streamlining the development of Natural Language Interfaces (NLIs) for data visualization. To synthesize relevant chart semantics accurately and enhance syntactic diversity in each NL dataset, we leverage 1) a guided discovery incorporated into prompting so that LLMs can steer themselves to create faithful NL datasets in a self-directed manner; 2) a score-based paraphrasing to augment NL syntax along with four language axes. We also present a new collection of 1,981 real-world Vega-Lite specifications that have increased diversity and complexity than existing chart collections. When tested on our chart collection, VL2NL extracted chart semantics and generated L1/L2 captions with 89.4% and 76.0% accuracy, respectively. It also demonstrated generating and paraphrasing utterances and questions with greater diversity compared to the benchmarks. Last, we discuss how our NL datasets and framework can be utilized in real-world scenarios. The codes and chart collection are available at https://github.com/hyungkwonko/chart-llm. △ Less

Submitted 21 January, 2024; v1 submitted 18 September, 2023; originally announced September 2023.

Comments: 22 pages, 5 figures

Journal ref: In Proceedings of the CHI Conference on Human Factors in Computing Systems (CHI '24), May 11-16, 2024, Honolulu, HI, USA

SPANet: Frequency-balancing Token Mixer using Spectral Pooling Aggregation Modulation

Authors: Guhnoo Yun, Juhan Yoo, Kijung Kim, Jeongho Lee, Dong Hwan Kim

Abstract: Recent studies show that self-attentions behave like low-pass filters (as opposed to convolutions) and enhancing their high-pass filtering capability improves model performance. Contrary to this idea, we investigate existing convolution-based models with spectral analysis and observe that improving the low-pass filtering in convolution operations also leads to performance improvement. To account f… ▽ More Recent studies show that self-attentions behave like low-pass filters (as opposed to convolutions) and enhancing their high-pass filtering capability improves model performance. Contrary to this idea, we investigate existing convolution-based models with spectral analysis and observe that improving the low-pass filtering in convolution operations also leads to performance improvement. To account for this observation, we hypothesize that utilizing optimal token mixers that capture balanced representations of both high- and low-frequency components can enhance the performance of models. We verify this by decomposing visual features into the frequency domain and combining them in a balanced manner. To handle this, we replace the balancing problem with a mask filtering problem in the frequency domain. Then, we introduce a novel token-mixer named SPAM and leverage it to derive a MetaFormer model termed as SPANet. Experimental results show that the proposed method provides a way to achieve this balance, and the balanced representations of both high- and low-frequency components can improve the performance of models on multiple computer vision tasks. Our code is available at $\href{https://doranlyong.github.io/projects/spanet/}{\text{https://doranlyong.github.io/projects/spanet/}}$. △ Less

Submitted 22 August, 2023; originally announced August 2023.

Comments: Accepted paper at ICCV 2023

AKVSR: Audio Knowledge Empowered Visual Speech Recognition by Compressing Audio Knowledge of a Pretrained Model

Authors: Jeong Hun Yeo, Minsu Kim, Jeongsoo Choi, Dae Hoe Kim, Yong Man Ro

Abstract: Visual Speech Recognition (VSR) is the task of predicting spoken words from silent lip movements. VSR is regarded as a challenging task because of the insufficient information on lip movements. In this paper, we propose an Audio Knowledge empowered Visual Speech Recognition framework (AKVSR) to complement the insufficient speech information of visual modality by using audio modality. Different fro… ▽ More Visual Speech Recognition (VSR) is the task of predicting spoken words from silent lip movements. VSR is regarded as a challenging task because of the insufficient information on lip movements. In this paper, we propose an Audio Knowledge empowered Visual Speech Recognition framework (AKVSR) to complement the insufficient speech information of visual modality by using audio modality. Different from the previous methods, the proposed AKVSR 1) utilizes rich audio knowledge encoded by a large-scale pretrained audio model, 2) saves the linguistic information of audio knowledge in compact audio memory by discarding the non-linguistic information from the audio through quantization, and 3) includes Audio Bridging Module which can find the best-matched audio features from the compact audio memory, which makes our training possible without audio inputs, once after the compact audio memory is composed. We validate the effectiveness of the proposed method through extensive experiments, and achieve new state-of-the-art performances on the widely-used LRS3 dataset. △ Less

Submitted 11 January, 2024; v1 submitted 15 August, 2023; originally announced August 2023.

Comments: Accepted by IEEE Transactions on Multimedia

EmphasisChecker: A Tool for Guiding Chart and Caption Emphasis

Authors: Dae Hyun Kim, Seulgi Choi, Juho Kim, Vidya Setlur, Maneesh Agrawala

Abstract: Recent work has shown that when both the chart and caption emphasize the same aspects of the data, readers tend to remember the doubly-emphasized features as takeaways; when there is a mismatch, readers rely on the chart to form takeaways and can miss information in the caption text. Through a survey of 280 chart-caption pairs in real-world sources (e.g., news media, poll reports, government repor… ▽ More Recent work has shown that when both the chart and caption emphasize the same aspects of the data, readers tend to remember the doubly-emphasized features as takeaways; when there is a mismatch, readers rely on the chart to form takeaways and can miss information in the caption text. Through a survey of 280 chart-caption pairs in real-world sources (e.g., news media, poll reports, government reports, academic articles, and Tableau Public), we find that captions often do not emphasize the same information in practice, which could limit how effectively readers take away the authors' intended messages. Motivated by the survey findings, we present EmphasisChecker, an interactive tool that highlights visually prominent chart features as well as the features emphasized by the caption text along with any mismatches in the emphasis. The tool implements a time-series prominent feature detector based on the Ramer-Douglas-Peucker algorithm and a text reference extractor that identifies time references and data descriptions in the caption and matches them with chart data. This information enables authors to compare features emphasized by these two modalities, quickly see mismatches, and make necessary revisions. A user study confirms that our tool is both useful and easy to use when authoring charts and captions. △ Less

Submitted 20 January, 2024; v1 submitted 25 July, 2023; originally announced July 2023.

Comments: IEEE VIS 2023

Journal ref: IEEE Transactions on Visualization and Computer Graphics, vol. 30, no. 1, pp. 120-130, 2024

Spatio-Temporal Attack Course-of-Action (COA) Search Learning for Scalable and Time-Varying Networks

Authors: Haemin Lee, Seok Bin Son, Won Joon Yun, Joongheon Kim, Soyi Jung, Dong Hwa Kim

Abstract: One of the key topics in network security research is the autonomous COA (Couse-of-Action) attack search method. Traditional COA attack search methods that passively search for attacks can be difficult, especially as the network gets bigger. To address these issues, new autonomous COA techniques are being developed, and among them, an intelligent spatial algorithm is designed in this paper for eff… ▽ More One of the key topics in network security research is the autonomous COA (Couse-of-Action) attack search method. Traditional COA attack search methods that passively search for attacks can be difficult, especially as the network gets bigger. To address these issues, new autonomous COA techniques are being developed, and among them, an intelligent spatial algorithm is designed in this paper for efficient operations in scalable networks. On top of the spatial search, a Monte-Carlo (MC)- based temporal approach is additionally considered for taking care of time-varying network behaviors. Therefore, we propose a spatio-temporal attack COA search algorithm for scalable and time-varying networks. △ Less

Submitted 2 September, 2022; originally announced September 2022.

Seamless and Energy Efficient Maritime Coverage in Coordinated 6G Space-Air-Sea Non-Terrestrial Networks

Authors: Sheikh Salman Hassan, Do Hyeon Kim, Yan Kyaw Tun, Nguyen H. Tran, Walid Saad, Choong Seon Hong

Abstract: Non-terrestrial networks (NTNs), which integrate space and aerial networks with terrestrial systems, are a key area in the emerging sixth-generation (6G) wireless networks. As part of 6G, NTNs must provide pervasive connectivity to a wide range of devices, including smartphones, vehicles, sensors, robots, and maritime users. However, due to the high mobility and deployment of NTNs, managing the sp… ▽ More Non-terrestrial networks (NTNs), which integrate space and aerial networks with terrestrial systems, are a key area in the emerging sixth-generation (6G) wireless networks. As part of 6G, NTNs must provide pervasive connectivity to a wide range of devices, including smartphones, vehicles, sensors, robots, and maritime users. However, due to the high mobility and deployment of NTNs, managing the space-air-sea (SAS) NTN resources, i.e., energy, power, and channel allocation, is a major challenge. The design of a SAS-NTN for energy-efficient resource allocation is investigated in this study. The goal is to maximize system energy efficiency (EE) by collaboratively optimizing user equipment (UE) association, power control, and unmanned aerial vehicle (UAV) deployment. Given the limited payloads of UAVs, this work focuses on minimizing the total energy cost of UAVs (trajectory and transmission) while meeting EE requirements. A mixed-integer nonlinear programming problem is proposed, followed by the development of an algorithm to decompose, and solve each problem distributedly. The binary (UE association) and continuous (power, deployment) variables are separated using the Bender decomposition (BD), and then the Dinkelbach algorithm (DA) is used to convert fractional programming into an equivalent solvable form in the subproblem. A standard optimization solver is utilized to deal with the complexity of the master problem for binary variables. The alternating direction method of multipliers (ADMM) algorithm is used to solve the subproblem for the continuous variables. Our proposed algorithm provides a suboptimal solution, and simulation results demonstrate that the proposed algorithm achieves better EE than baselines. △ Less

Submitted 21 January, 2022; originally announced January 2022.

Bayesian Optimization over Permutation Spaces

Authors: Aryan Deshwal, Syrine Belakaria, Janardhan Rao Doppa, Dae Hyun Kim

Abstract: Optimizing expensive to evaluate black-box functions over an input space consisting of all permutations of d objects is an important problem with many real-world applications. For example, placement of functional blocks in hardware design to optimize performance via simulations. The overall goal is to minimize the number of function evaluations to find high-performing permutations. The key challen… ▽ More Optimizing expensive to evaluate black-box functions over an input space consisting of all permutations of d objects is an important problem with many real-world applications. For example, placement of functional blocks in hardware design to optimize performance via simulations. The overall goal is to minimize the number of function evaluations to find high-performing permutations. The key challenge in solving this problem using the Bayesian optimization (BO) framework is to trade-off the complexity of statistical model and tractability of acquisition function optimization. In this paper, we propose and evaluate two algorithms for BO over Permutation Spaces (BOPS). First, BOPS-T employs Gaussian process (GP) surrogate model with Kendall kernels and a Tractable acquisition function optimization approach based on Thompson sampling to select the sequence of permutations for evaluation. Second, BOPS-H employs GP surrogate model with Mallow kernels and a Heuristic search approach to optimize expected improvement acquisition function. We theoretically analyze the performance of BOPS-T to show that their regret grows sub-linearly. Our experiments on multiple synthetic and real-world benchmarks show that both BOPS-T and BOPS-H perform better than the state-of-the-art BO algorithm for combinatorial spaces. To drive future research on this important problem, we make new resources and real-world benchmarks available to the community. △ Less

Submitted 2 December, 2021; originally announced December 2021.

Comments: Accepted at AAAI 2022

Towards Defensive Autonomous Driving: Collecting and Probing Driving Demonstrations of Mixed Qualities

Authors: Jeongwoo Oh, Gunmin Lee, Jeongeun Park, Wooseok Oh, Jaeseok Heo, Hojun Chung, Do Hyung Kim, Byungkyu Park, Chang-Gun Lee, Sungjoon Choi, Songhwai Oh

Abstract: Designing or learning an autonomous driving policy is undoubtedly a challenging task as the policy has to maintain its safety in all corner cases. In order to secure safety in autonomous driving, the ability to detect hazardous situations, which can be seen as an out-of-distribution (OOD) detection problem, becomes crucial. However, most conventional datasets only provide expert driving demonstrat… ▽ More Designing or learning an autonomous driving policy is undoubtedly a challenging task as the policy has to maintain its safety in all corner cases. In order to secure safety in autonomous driving, the ability to detect hazardous situations, which can be seen as an out-of-distribution (OOD) detection problem, becomes crucial. However, most conventional datasets only provide expert driving demonstrations, although some non-expert or uncommon driving behavior data are needed to implement a safety guaranteed autonomous driving platform. To this end, we present a novel dataset called the R3 Driving Dataset, composed of driving data with different qualities. The dataset categorizes abnormal driving behaviors into eight categories and 369 different detailed situations. The situations include dangerous lane changes and near-collision situations. To further enlighten how these abnormal driving behaviors can be detected, we utilize different uncertainty estimation and anomaly detection methods to the proposed dataset. From the results of the proposed experiment, it can be inferred that by using both uncertainty estimation and anomaly detection, most of the abnormal cases in the proposed dataset can be discriminated. The dataset of this paper can be downloaded from https://rllab-snu.github.io/projects/R3-Driving-Dataset/doc.html. △ Less

Submitted 18 September, 2021; v1 submitted 16 September, 2021; originally announced September 2021.

Comments: 6 pages, 6 figures, 3 tables

Ruin Theory for User Association and Energy Optimization in Multi-access Edge Computing

Authors: Do Hyeon Kim, Aunas Manzoor, Madyan Alsenwi, Yan Kyaw Tun, Walid Saad, Choong Seon Hong

Abstract: In this correspondence, a novel framework is proposed for analyzing data offloading in a multi-access edge computing system. Specifically, a two-phase algorithm, is proposed, including two key phases: 1) user association phase and 2) task offloading phase. In the first phase, a ruin theory-based approach is developed to obtain the users association considering the users' transmission reliability a… ▽ More In this correspondence, a novel framework is proposed for analyzing data offloading in a multi-access edge computing system. Specifically, a two-phase algorithm, is proposed, including two key phases: 1) user association phase and 2) task offloading phase. In the first phase, a ruin theory-based approach is developed to obtain the users association considering the users' transmission reliability and resource utilization efficiency. Meanwhile, in the second phase, an optimization-based algorithm is used to optimize the data offloading process. In particular, ruin theory is used to manage the user association phase, and a ruin probability-based preference profile is considered to control the priority of proposing users. Here, ruin probability is derived by the surplus buffer space of each edge node at each time slot. Giving the association results, an optimization problem is formulated to optimize the amount of offloaded data aiming at minimizing the energy consumption of users. Simulation results show that the developed solutions guarantee system reliability, association efficiency under a tolerable value of surplus buffer size, and minimize the total energy consumption of all users. △ Less

Submitted 21 April, 2023; v1 submitted 2 July, 2021; originally announced July 2021.

Comments: Accepted Article By IEEE Transactions on Vehicular Technology, DOI: https://doi.org/10.1109/TVT.2023.3269427 (In Press)

Towards Understanding How Readers Integrate Charts and Captions: A Case Study with Line Charts

Authors: Dae Hyun Kim, Vidya Setlur, Maneesh Agrawala

Abstract: Charts often contain visually prominent features that draw attention to aspects of the data and include text captions that emphasize aspects of the data. Through a crowdsourced study, we explore how readers gather takeaways when considering charts and captions together. We first ask participants to mark visually prominent regions in a set of line charts. We then generate text captions based on the… ▽ More Charts often contain visually prominent features that draw attention to aspects of the data and include text captions that emphasize aspects of the data. Through a crowdsourced study, we explore how readers gather takeaways when considering charts and captions together. We first ask participants to mark visually prominent regions in a set of line charts. We then generate text captions based on the prominent features and ask participants to report their takeaways after observing chart-caption pairs. We find that when both the chart and caption describe a high-prominence feature, readers treat the doubly emphasized high-prominence feature as the takeaway; when the caption describes a low-prominence chart feature, readers rely on the chart and report a higher-prominence feature as the takeaway. We also find that external information that provides context, helps further convey the caption's message to the reader. We use these findings to provide guidelines for authoring effective chart-caption pairs. △ Less

Submitted 20 January, 2021; originally announced January 2021.

Comments: To appear at CHI 2021

HeM3D: Heterogeneous Manycore Architecture Based on Monolithic 3D Vertical Integration

Authors: Aqeeb Iqbal Arka, Biresh Kumar Joardar, Ryan Gary Kim, Dae Hyun Kim, Janardhan Rao Doppa, Partha Pratim Pande

Abstract: Heterogeneous manycore architectures are the key to efficiently execute compute- and data-intensive applications. Through silicon via (TSV)-based 3D manycore system is a promising solution in this direction as it enables integration of disparate computing cores on a single system. However, the achievable performance of conventional through-silicon-via (TSV)-based 3D systems is ultimately bottlenec… ▽ More Heterogeneous manycore architectures are the key to efficiently execute compute- and data-intensive applications. Through silicon via (TSV)-based 3D manycore system is a promising solution in this direction as it enables integration of disparate computing cores on a single system. However, the achievable performance of conventional through-silicon-via (TSV)-based 3D systems is ultimately bottlenecked by the horizontal wires (wires in each planar die). Moreover, current TSV 3D architectures suffer from thermal limitations. Hence, TSV-based architectures do not realize the full potential of 3D integration. Monolithic 3D (M3D) integration, a breakthrough technology to achieve - More Moore and More Than Moore - and opens up the possibility of designing cores and associated network routers using multiple layers by utilizing monolithic inter-tier vias (MIVs) and hence, reducing the effective wire length. Compared to TSV-based 3D ICs, M3D offers the true benefits of vertical dimension for system integration: the size of a MIV used in M3D is over 100x smaller than a TSV. In this work, we demonstrate how M3D-enabled vertical core and uncore elements offer significant performance and thermal improvements in manycore heterogeneous architectures compared to its TSV-based counterpart. To overcome the difficult optimization challenges due to the large design space and complex interactions among the heterogeneous components (CPU, GPU, Last Level Cache, etc.) in an M3D-based manycore chip, we leverage novel design-space exploration algorithms to trade-off different objectives. The proposed M3D-enabled heterogeneous architecture, called HeM3D, outperforms its state-of-the-art TSV-equivalent counterpart by up to 18.3% in execution time while being up to 19 degrees Celcius cooler. △ Less

Submitted 7 December, 2020; v1 submitted 30 November, 2020; originally announced December 2020.

Comments: This work has been accepted in ACM Transactions on Design Automation of Electronic Systems

ACM Class: C.2

Drive Safe: Cognitive-Behavioral Mining for Intelligent Transportation Cyber-Physical System

Authors: Md. Shirajum Munir, Sarder Fakhrul Abedin, Ki Tae Kim, Do Hyeon Kim, Md. Golam Rabiul Alam, Choong Seon Hong

Abstract: This paper presents a cognitive behavioral-based driver mood repairment platform in intelligent transportation cyber-physical systems (IT-CPS) for road safety. In particular, we propose a driving safety platform for distracted drivers, namely \emph{drive safe}, in IT-CPS. The proposed platform recognizes the distracting activities of the drivers as well as their emotions for mood repair. Further,… ▽ More This paper presents a cognitive behavioral-based driver mood repairment platform in intelligent transportation cyber-physical systems (IT-CPS) for road safety. In particular, we propose a driving safety platform for distracted drivers, namely \emph{drive safe}, in IT-CPS. The proposed platform recognizes the distracting activities of the drivers as well as their emotions for mood repair. Further, we develop a prototype of the proposed drive safe platform to establish proof-of-concept (PoC) for the road safety in IT-CPS. In the developed driving safety platform, we employ five AI and statistical-based models to infer a vehicle driver's cognitive-behavioral mining to ensure safe driving during the drive. Especially, capsule network (CN), maximum likelihood (ML), convolutional neural network (CNN), Apriori algorithm, and Bayesian network (BN) are deployed for driver activity recognition, environmental feature extraction, mood recognition, sequential pattern mining, and content recommendation for affective mood repairment of the driver, respectively. Besides, we develop a communication module to interact with the systems in IT-CPS asynchronously. Thus, the developed drive safe PoC can guide the vehicle drivers when they are distracted from driving due to the cognitive-behavioral factors. Finally, we have performed a qualitative evaluation to measure the usability and effectiveness of the developed drive safe platform. We observe that the P-value is 0.0041 (i.e., < 0.05) in the ANOVA test. Moreover, the confidence interval analysis also shows significant gains in prevalence value which is around 0.93 for a 95% confidence level. The aforementioned statistical results indicate high reliability in terms of driver's safety and mental state. △ Less

Submitted 23 August, 2020; originally announced August 2020.

Comments: Submitted to IEEE Transactions on Intelligent Transportation Systems, Special Issue on Technologies for risk mitigation and support of impaired drivers

CycleMorph: Cycle Consistent Unsupervised Deformable Image Registration

Authors: Boah Kim, Dong Hwan Kim, Seong Ho Park, Jieun Kim, June-Goo Lee, Jong Chul Ye

Abstract: Image registration is a fundamental task in medical image analysis. Recently, deep learning based image registration methods have been extensively investigated due to their excellent performance despite the ultra-fast computational time. However, the existing deep learning methods still have limitation in the preservation of original topology during the deformation with registration vector fields.… ▽ More Image registration is a fundamental task in medical image analysis. Recently, deep learning based image registration methods have been extensively investigated due to their excellent performance despite the ultra-fast computational time. However, the existing deep learning methods still have limitation in the preservation of original topology during the deformation with registration vector fields. To address this issues, here we present a cycle-consistent deformable image registration. The cycle consistency enhances image registration performance by providing an implicit regularization to preserve topology during the deformation. The proposed method is so flexible that can be applied for both 2D and 3D registration problems for various applications, and can be easily extended to multi-scale implementation to deal with the memory issues in large volume registration. Experimental results on various datasets from medical and non-medical applications demonstrate that the proposed method provides effective and accurate registration on diverse image pairs within a few seconds. Qualitative and quantitative evaluations on deformation fields also verify the effectiveness of the cycle consistency of the proposed method. △ Less

Submitted 13 August, 2020; originally announced August 2020.

1-Point RANSAC-Based Method for Ground Object Pose Estimation

Authors: Jeong-Kyun Lee, Young-Ki Baik, Hankyu Cho, Kang Kim, Duck Hoon Kim

Abstract: Solving Perspective-n-Point (PnP) problems is a traditional way of estimating object poses. Given outlier-contaminated data, a pose of an object is calculated with PnP algorithms of n = {3, 4} in the RANSAC-based scheme. However, the computational complexity considerably increases along with n and the high complexity imposes a severe strain on devices which should estimate multiple object poses in… ▽ More Solving Perspective-n-Point (PnP) problems is a traditional way of estimating object poses. Given outlier-contaminated data, a pose of an object is calculated with PnP algorithms of n = {3, 4} in the RANSAC-based scheme. However, the computational complexity considerably increases along with n and the high complexity imposes a severe strain on devices which should estimate multiple object poses in real time. In this paper, we propose an efficient method based on 1-point RANSAC for estimating a pose of an object on the ground. In the proposed method, a pose is calculated with 1-DoF parameterization by using a ground object assumption and a 2D object bounding box as an additional observation, thereby achieving the fastest performance among the RANSAC-based methods. In addition, since the method suffers from the errors of the additional information, we propose a hierarchical robust estimation method for polishing a rough pose estimate and discovering more inliers in a coarse-to-fine manner. The experiments in synthetic and real-world datasets demonstrate the superiority of the proposed method. △ Less

Submitted 10 June, 2021; v1 submitted 9 August, 2020; originally announced August 2020.

Comments: Accepted in the workshop on Autonomous Driving: Perception, Prediction and Planning in conjunction with CVPR 2021

Controlling the Outbreak of COVID-19: A Noncooperative Game Perspective

Authors: Anupam Kumar Bairagi, Mehedi Masud, Do Hyeon Kim, Md. Shirajum Munir, Abdullah Al Nahid, Sarder Fakhrul Abedin, Kazi Masudul Alam, Sujit Biswas, Sultan S Alshamrani, Zhu Han, Choong Seon Hong

Abstract: COVID-19 is a global epidemic. Till now, there is no remedy for this epidemic. However, isolation and social distancing are seemed to be effective preventive measures to control this pandemic. Therefore, in this paper, an optimization problem is formulated that accommodates both isolation and social distancing features of the individuals. To promote social distancing, we solve the formulated probl… ▽ More COVID-19 is a global epidemic. Till now, there is no remedy for this epidemic. However, isolation and social distancing are seemed to be effective preventive measures to control this pandemic. Therefore, in this paper, an optimization problem is formulated that accommodates both isolation and social distancing features of the individuals. To promote social distancing, we solve the formulated problem by applying a noncooperative game that can provide an incentive for maintaining social distancing to prevent the spread of COVID-19. Furthermore, the sustainability of the lockdown policy is interpreted with the help of our proposed game-theoretic incentive model for maintaining social distancing where there exists a Nash equilibrium. Finally, we perform an extensive numerical analysis that shows the effectiveness of the proposed approach in terms of achieving the desired social-distancing to prevent the outbreak of the COVID-19 in a noncooperative environment. Numerical results show that the individual incentive increases more than 85% with an increasing percentage of home isolation from 25% to 100% for all considered scenarios. The numerical results also demonstrate that in a particular percentage of home isolation, the individual incentive decreases with an increasing number of individuals. △ Less

Submitted 26 November, 2020; v1 submitted 27 July, 2020; originally announced July 2020.

Comments: Accepted article by IEEE Access. DOI: 10.1109/ACCESS.2020.3040821

Deep Convolutional GANs for Car Image Generation

Authors: Dong Hui Kim

Abstract: In this paper, we investigate the application of deep convolutional GANs on car image generation. We improve upon the commonly used DCGAN architecture by implementing Wasserstein loss to decrease mode collapse and introducing dropout at the end of the discrimiantor to introduce stochasticity. Furthermore, we introduce convolutional layers at the end of the generator to improve expressiveness and s… ▽ More In this paper, we investigate the application of deep convolutional GANs on car image generation. We improve upon the commonly used DCGAN architecture by implementing Wasserstein loss to decrease mode collapse and introducing dropout at the end of the discrimiantor to introduce stochasticity. Furthermore, we introduce convolutional layers at the end of the generator to improve expressiveness and smooth noise. All of these improvements upon the DCGAN architecture comprise our proposal of the novel BoolGAN architecture, which is able to decrease the FID from 195.922 (baseline) to 165.966. △ Less

Submitted 24 June, 2020; originally announced June 2020.

Comments: 6 pages, 8 figures

End-to-End Lane Marker Detection via Row-wise Classification

Authors: Seungwoo Yoo, Heeseok Lee, Heesoo Myeong, Sungrack Yun, Hyoungwoo Park, Janghoon Cho, Duck Hoon Kim

Abstract: In autonomous driving, detecting reliable and accurate lane marker positions is a crucial yet challenging task. The conventional approaches for the lane marker detection problem perform a pixel-level dense prediction task followed by sophisticated post-processing that is inevitable since lane markers are typically represented by a collection of line segments without thickness. In this paper, we pr… ▽ More In autonomous driving, detecting reliable and accurate lane marker positions is a crucial yet challenging task. The conventional approaches for the lane marker detection problem perform a pixel-level dense prediction task followed by sophisticated post-processing that is inevitable since lane markers are typically represented by a collection of line segments without thickness. In this paper, we propose a method performing direct lane marker vertex prediction in an end-to-end manner, i.e., without any post-processing step that is required in the pixel-level dense prediction task. Specifically, we translate the lane marker detection problem into a row-wise classification task, which takes advantage of the innate shape of lane markers but, surprisingly, has not been explored well. In order to compactly extract sufficient information about lane markers which spread from the left to the right in an image, we devise a novel layer, which is utilized to successively compress horizontal components so enables an end-to-end lane marker detection system where the final lane marker positions are simply obtained via argmax operations in testing time. Experimental results demonstrate the effectiveness of the proposed method, which is on par or outperforms the state-of-the-art methods on two popular lane marker detection benchmarks, i.e., TuSimple and CULane. △ Less

Submitted 6 May, 2020; originally announced May 2020.

Metric-based Regularization and Temporal Ensemble for Multi-task Learning using Heterogeneous Unsupervised Tasks

Authors: Dae Ha Kim, Seung Hyun Lee, Byung Cheol Song

Abstract: One of the ways to improve the performance of a target task is to learn the transfer of abundant knowledge of a pre-trained network. However, learning of the pre-trained network requires high computation capability and large-scale labeled dataset. To mitigate the burden of large-scale labeling, learning in un/self-supervised manner can be a solution. In addition, using unsupervised multi-task lear… ▽ More One of the ways to improve the performance of a target task is to learn the transfer of abundant knowledge of a pre-trained network. However, learning of the pre-trained network requires high computation capability and large-scale labeled dataset. To mitigate the burden of large-scale labeling, learning in un/self-supervised manner can be a solution. In addition, using unsupervised multi-task learning, a generalized feature representation can be learned. However, unsupervised multi-task learning can be biased to a specific task. To overcome this problem, we propose the metric-based regularization term and temporal task ensemble (TTE) for multi-task learning. Since these two techniques prevent the entire network from learning in a state deviated to a specific task, it is possible to learn a generalized feature representation that appropriately reflects the characteristics of each task without biasing. Experimental results for three target tasks such as classification, object detection and embedding clustering prove that the TTE-based multi-task framework is more effective than the state-of-the-art (SOTA) method in improving the performance of a target task. △ Less

Submitted 28 August, 2019; originally announced August 2019.

Comments: 11 pages. To Appear in the IEEE International Conference on Computer Vision Workshops (ICCVW) 2019

Planning for target retrieval using a robotic manipulator in cluttered and occluded environments

Authors: Changjoo Nam, Jinhwi Lee, Younggil Cho, Jeongho Lee, Dong Hwan Kim, ChangHwan Kim

Abstract: This paper presents planning algorithms for a robotic manipulator with a fixed base in order to grasp a target object in cluttered environments. We consider a configuration of objects in a confined space with a high density so no collision-free path to the target exists. The robot must relocate some objects to retrieve the target while avoiding collisions. For fast completion of the retrieval task… ▽ More This paper presents planning algorithms for a robotic manipulator with a fixed base in order to grasp a target object in cluttered environments. We consider a configuration of objects in a confined space with a high density so no collision-free path to the target exists. The robot must relocate some objects to retrieve the target while avoiding collisions. For fast completion of the retrieval task, the robot needs to compute a plan optimizing an appropriate objective value directly related to the execution time of the relocation plan. We propose planning algorithms that aim to minimize the number of objects to be relocated. Our objective value is appropriate for the object retrieval task because grasping and releasing objects often dominate the total running time. In addition to the algorithm working in fully known and static environments, we propose algorithms that can deal with uncertain and dynamic situations incurred by occluded views. The proposed algorithms are shown to be complete and run in polynomial time. Our methods reduce the total running time significantly compared to a baseline method (e.g., 25.1% of reduction in a known static environment with 10 objects △ Less

Submitted 8 July, 2019; originally announced July 2019.

Comments: 8 pages, 14 figures

Unsupervised Deformable Image Registration Using Cycle-Consistent CNN

Authors: Boah Kim, Jieun Kim, June-Goo Lee, Dong Hwan Kim, Seong Ho Park, Jong Chul Ye

Abstract: Medical image registration is one of the key processing steps for biomedical image analysis such as cancer diagnosis. Recently, deep learning based supervised and unsupervised image registration methods have been extensively studied due to its excellent performance in spite of ultra-fast computational time compared to the classical approaches. In this paper, we present a novel unsupervised medical… ▽ More Medical image registration is one of the key processing steps for biomedical image analysis such as cancer diagnosis. Recently, deep learning based supervised and unsupervised image registration methods have been extensively studied due to its excellent performance in spite of ultra-fast computational time compared to the classical approaches. In this paper, we present a novel unsupervised medical image registration method that trains deep neural network for deformable registration of 3D volumes using a cycle-consistency. Thanks to the cycle consistency, the proposed deep neural networks can take diverse pair of image data with severe deformation for accurate registration. Experimental results using multiphase liver CT images demonstrate that our method provides very precise 3D image registration within a few seconds, resulting in more accurate cancer size estimation. △ Less

Submitted 2 July, 2019; originally announced July 2019.

Comments: accepted for MICCAI 2019

Inter-Tier Process Variation-Aware Monolithic 3D NoC Architectures

Authors: Shouvik Musavvir, Anwesha Chatterjee, Ryan Gary Kim, Dae Hyun Kim, Partha Pratim Pande

Abstract: Monolithic 3D (M3D) technology enables high density integration, performance, and energy-efficiency by sequentially stacking tiers on top of each other. M3D-based network-on-chip (NoC) architectures can exploit these benefits by adopting tier partitioning for intra-router stages. However, conventional fabrication methods are infeasible for M3D-enabled designs due to temperature related issues. Thi… ▽ More Monolithic 3D (M3D) technology enables high density integration, performance, and energy-efficiency by sequentially stacking tiers on top of each other. M3D-based network-on-chip (NoC) architectures can exploit these benefits by adopting tier partitioning for intra-router stages. However, conventional fabrication methods are infeasible for M3D-enabled designs due to temperature related issues. This has necessitated lower temperature and temperature-resilient techniques for M3D fabrication, leading to inferior performance of transistors in the top tier and interconnects in the bottom tier. The resulting inter-tier process variation leads to performance degradation of M3D-enabled NoCs. In this work, we demonstrate that without considering inter-tier process variation, an M3D-enabled NoC architecture overestimates the energy-delay-product (EDP) on average by 50.8% for a set of SPLASH-2 and PARSEC benchmarks. As a countermeasure, we adopt a process variation aware design approach. The proposed design and optimization method distribute the intra-router stages and inter-router links among the tiers to mitigate the adverse effects of process variation. Experimental results show that the NoC architecture under consideration improves the EDP by 27.4% on average across all benchmarks compared to the process-oblivious design. △ Less

Submitted 10 June, 2019; originally announced June 2019.

Comments: Submitted to IEEE TVLSI (Under Review)

Finding Solutions to Generative Adversarial Privacy

Authors: Dae Hyun Kim, Taeyoung Kong, Seungbin Jeong

Abstract: We present heuristics for solving the maximin problem induced by the generative adversarial privacy setting for linear and convolutional neural network (CNN) adversaries. In the linear adversary setting, we present a greedy algorithm for approximating the optimal solution for the privatizer, which performs better as the number of instances increases. We also provide an analysis of the algorithm to… ▽ More We present heuristics for solving the maximin problem induced by the generative adversarial privacy setting for linear and convolutional neural network (CNN) adversaries. In the linear adversary setting, we present a greedy algorithm for approximating the optimal solution for the privatizer, which performs better as the number of instances increases. We also provide an analysis of the algorithm to show that it not only removes the features most correlated with the private label first, but also preserves the prediction accuracy of public labels that are sufficiently independent of the features that are relevant to the private label. In the CNN adversary setting, we present a method of hiding selected information from the adversary while preserving the others through alternately optimizing the goals of the privatizer and the adversary using neural network backpropagation. We experimentally show that our method succeeds on a fixed adversary. △ Less

Submitted 4 October, 2018; originally announced October 2018.

Self-supervised Knowledge Distillation Using Singular Value Decomposition

Authors: Seung Hyun Lee, Dae Ha Kim, Byung Cheol Song

Abstract: To solve deep neural network (DNN)'s huge training dataset and its high computation issue, so-called teacher-student (T-S) DNN which transfers the knowledge of T-DNN to S-DNN has been proposed. However, the existing T-S-DNN has limited range of use, and the knowledge of T-DNN is insufficiently transferred to S-DNN. To improve the quality of the transferred knowledge from T-DNN, we propose a new kn… ▽ More To solve deep neural network (DNN)'s huge training dataset and its high computation issue, so-called teacher-student (T-S) DNN which transfers the knowledge of T-DNN to S-DNN has been proposed. However, the existing T-S-DNN has limited range of use, and the knowledge of T-DNN is insufficiently transferred to S-DNN. To improve the quality of the transferred knowledge from T-DNN, we propose a new knowledge distillation using singular value decomposition (SVD). In addition, we define a knowledge transfer as a self-supervised task and suggest a way to continuously receive information from T-DNN. Simulation results show that a S-DNN with a computational cost of 1/5 of the T-DNN can be up to 1.1\% better than the T-DNN in terms of classification accuracy. Also assuming the same computational cost, our S-DNN outperforms the S-DNN driven by the state-of-the-art distillation with a performance advantage of 1.79\%. code is available on https://github.com/sseung0703/SSKD\_SVD. △ Less

Submitted 18 July, 2018; originally announced July 2018.

Comments: accepted to ECCV 2018

Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary

Authors: Julia Chuzhoy, David H. K. Kim, Rachit Nimavat

Abstract: We study the classical Node-Disjoint Paths (NDP) problem: given an undirected $n$-vertex graph G, together with a set {(s_1,t_1),...,(s_k,t_k)} of pairs of its vertices, called source-destination, or demand pairs, find a maximum-cardinality set of mutually node-disjoint paths that connect the demand pairs. The best current approximation for the problem is achieved by a simple greedy $O(\sqrt{n})$-… ▽ More We study the classical Node-Disjoint Paths (NDP) problem: given an undirected $n$-vertex graph G, together with a set {(s_1,t_1),...,(s_k,t_k)} of pairs of its vertices, called source-destination, or demand pairs, find a maximum-cardinality set of mutually node-disjoint paths that connect the demand pairs. The best current approximation for the problem is achieved by a simple greedy $O(\sqrt{n})$-approximation algorithm. A special case of the problem called NDP-Grid, where the underlying graph is a grid, has been studied extensively. The best current approximation algorithm for NDP-Grid achieves an $\tilde{O}(n^{1/4})$-approximation factor. On the negative side, a recent result by the authors shows that NDP is hard to approximate to within factor $2^{Ω(\sqrt{\log n})}$, even if the underlying graph is a sub-graph of a grid, and all source vertices lie on the grid boundary. In a follow-up work, the authors further show that NDP-Grid is hard to approximate to within factor $Ω(2^{\log^{1-ε}n})$ for any constant $ε$ under standard complexity assumptions, and to within factor $n^{Ω(1/(\log\log n)^2)}$ under randomized ETH. In this paper we study NDP-Grid, where all source vertices {s_1,...,s_k} appear on the grid boundary. Our main result is an efficient randomized $2^{O(\sqrt{\log n} \cdot \log\log n)}$-approximation algorithm for this problem. We generalize this result to instances where the source vertices lie within a prescribed distance from the grid boundary. Much of the work on approximation algorithms for NDP relies on the multicommodity flow relaxation of the problem, which is known to have an $Ω(\sqrt n)$ integrality gap, even in grid graphs. Our work departs from this paradigm, and uses a (completely different) linear program only to select the pairs to be routed, while the routing itself is computed by other methods. △ Less

Submitted 24 May, 2018; originally announced May 2018.

Comments: To appear in the proceedings of ICALP 2018

ACM Class: F.2.2

Almost Polynomial Hardness of Node-Disjoint Paths in Grids

Authors: Julia Chuzhoy, David H. K. Kim, Rachit Nimavat

Abstract: In the classical Node-Disjoint Paths (NDP) problem, we are given an $n$-vertex graph $G=(V,E)$, and a collection $M=\{(s_1,t_1),\ldots,(s_k,t_k)\}$ of pairs of its vertices, called source-destination, or demand pairs. The goal is to route as many of the demand pairs as possible, where to route a pair we need to select a path connecting it, so that all selected paths are disjoint in their vertices.… ▽ More In the classical Node-Disjoint Paths (NDP) problem, we are given an $n$-vertex graph $G=(V,E)$, and a collection $M=\{(s_1,t_1),\ldots,(s_k,t_k)\}$ of pairs of its vertices, called source-destination, or demand pairs. The goal is to route as many of the demand pairs as possible, where to route a pair we need to select a path connecting it, so that all selected paths are disjoint in their vertices. The best current algorithm for NDP achieves an $O(\sqrt{n})$-approximation, while, until recently, the best negative result was a factor $Ω(\log^{1/2-ε}n)$-hardness of approximation, for any constant $ε$, unless $NP \subseteq ZPTIME(n^{poly \log n})$. In a recent work, the authors have shown an improved $2^{Ω(\sqrt{\log n})}$-hardness of approximation for NDP, unless $NP\subseteq DTIME(n^{O(\log n)})$, even if the underlying graph is a subgraph of a grid graph, and all source vertices lie on the boundary of the grid. Unfortunately, this result does not extend to grid graphs. The approximability of the NDP problem on grid graphs has remained a tantalizing open question, with the best current upper bound of $\tilde{O}(n^{1/4})$, and the best current lower bound of APX-hardness. In this paper we come close to resolving the approximability of NDP in general, and NDP in grids in particular. Our main result is that NDP is $2^{Ω(\log^{1-ε} n)}$-hard to approximate for any constant $ε$, assuming that $NP\not\subseteq RTIME(n^{poly\log n})$, and that it is $n^{Ω(1/(\log \log n)^2)}$-hard to approximate, assuming that for some constant $δ>0$, $NP \not \subseteq RTIME(2^{n^δ})$. These results hold even for grid graphs and wall graphs, and extend to the closely related Edge-Disjoint Paths problem, even in wall graphs. △ Less

Submitted 6 November, 2017; originally announced November 2017.

New Hardness Results for Routing on Disjoint Paths

Authors: Julia Chuzhoy, David H. K. Kim, Rachit Nimavat

Abstract: In the classical Node-Disjoint Paths (NDP) problem, the input consists of an undirected $n$-vertex graph $G$, and a collection $\mathcal{M}=\{(s_1,t_1),\ldots,(s_k,t_k)\}$ of pairs of its vertices, called source-destination, or demand, pairs. The goal is to route the largest possible number of the demand pairs via node-disjoint paths. The best current approximation for the problem is achieved by a… ▽ More In the classical Node-Disjoint Paths (NDP) problem, the input consists of an undirected $n$-vertex graph $G$, and a collection $\mathcal{M}=\{(s_1,t_1),\ldots,(s_k,t_k)\}$ of pairs of its vertices, called source-destination, or demand, pairs. The goal is to route the largest possible number of the demand pairs via node-disjoint paths. The best current approximation for the problem is achieved by a simple greedy algorithm, whose approximation factor is $O(\sqrt n)$, while the best current negative result is an $Ω(\log^{1/2-δ}n)$-hardness of approximation for any constant $δ$, under standard complexity assumptions. Even seemingly simple special cases of the problem are still poorly understood: when the input graph is a grid, the best current algorithm achieves an $\tilde O(n^{1/4})$-approximation, and when it is a general planar graph, the best current approximation ratio of an efficient algorithm is $\tilde O(n^{9/19})$. The best currently known lower bound on the approximability of both these versions of the problem is APX-hardness. In this paper we prove that NDP is $2^{Ω(\sqrt{\log n})}$-hard to approximate, unless all problems in NP have algorithms with running time $n^{O(\log n)}$. Our result holds even when the underlying graph is a planar graph with maximum vertex degree $3$, and all source vertices lie on the boundary of a single face (but the destination vertices may lie anywhere in the graph). We extend this result to the closely related Edge-Disjoint Paths problem, showing the same hardness of approximation ratio even for sub-cubic planar graphs with all sources lying on the boundary of a single face. △ Less

Submitted 16 November, 2016; originally announced November 2016.

Improved Approximation for Node-Disjoint Paths in Planar Graphs

Authors: Julia Chuzhoy, David H. K. Kim, Shi Li

Abstract: We study the classical Node-Disjoint Paths (NDP) problem: given an $n$-vertex graph $G$ and a collection $M=\{(s_1,t_1),\ldots,(s_k,t_k)\}$ of pairs of vertices of $G$ called demand pairs, find a maximum-cardinality set of node-disjoint paths connecting the demand pairs. NDP is one of the most basic routing problems, that has been studied extensively. Despite this, there are still wide gaps in our… ▽ More We study the classical Node-Disjoint Paths (NDP) problem: given an $n$-vertex graph $G$ and a collection $M=\{(s_1,t_1),\ldots,(s_k,t_k)\}$ of pairs of vertices of $G$ called demand pairs, find a maximum-cardinality set of node-disjoint paths connecting the demand pairs. NDP is one of the most basic routing problems, that has been studied extensively. Despite this, there are still wide gaps in our understanding of its approximability: the best currently known upper bound of $O(\sqrt n)$ on its approximation ratio is achieved via a simple greedy algorithm, while the best current negative result shows that the problem does not have a better than $Ω(\log^{1/2-δ}n)$-approximation for any constant $δ$, under standard complexity assumptions. Even for planar graphs no better approximation algorithms are known, and to the best of our knowledge, the best negative bound is APX-hardness. Perhaps the biggest obstacle to obtaining better approximation algorithms for NDP is that most currently known approximation algorithms for this type of problems rely on the standard multicommodity flow relaxation, whose integrality gap is $Ω(\sqrt n)$ for NDP, even in planar graphs. In this paper, we break the barrier of $O(\sqrt n)$ on the approximability of the NDP problem in planar graphs and obtain an $\tilde O(n^{9/19})$-approximation. We introduce a new linear programming relaxation of the problem, and a number of new techniques, that we hope will be helpful in designing more powerful algorithms for this and related problems. △ Less

Submitted 17 March, 2016; originally announced March 2016.

A characterization of eventually periodicity

Authors: Teturo Kamae, Dong Han Kim

Abstract: In this article, we show that the Kamae-Xue complexity function for an infinite sequence classifies eventual periodicity completely. We prove that an infinite binary word $x_1x_2 \cdots $ is eventually periodic if and only if $Σ(x_1x_2\cdots x_n)/n^3$ has a positive limit, where $Σ(x_1x_2\cdots x_n)$ is the sum of the squares of all the numbers of appearance of finite words in… ▽ More In this article, we show that the Kamae-Xue complexity function for an infinite sequence classifies eventual periodicity completely. We prove that an infinite binary word $x_1x_2 \cdots $ is eventually periodic if and only if $Σ(x_1x_2\cdots x_n)/n^3$ has a positive limit, where $Σ(x_1x_2\cdots x_n)$ is the sum of the squares of all the numbers of appearance of finite words in $x_1 x_2 \cdots x_n$, which was introduced by Kamae-Xue as a criterion of randomness in the sense that $x_1x_2\cdots x_n$ is more random if $Σ(x_1x_2\cdots x_n)$ is smaller. In fact, it is known that the lower limit of $Σ(x_1x_2\cdots x_n) /n^2 $ is at least 3/2 for any sequence $x_1x_2 \cdots$, while the limit exists as 3/2 almost surely for the $(1/2,1/2)$ product measure. For the other extreme, the upper limit of $Σ(x_1x_2\cdots x_n)/n^3$ is bounded by 1/3. There are sequences which are not eventually periodic but the lower limit of $Σ(x_1x_2\cdots x_n)/n^3$ is positive, while the limit does not exist. △ Less

Submitted 16 April, 2014; originally announced April 2014.

Comments: 11 pages

MSC Class: 68R15