OpenRaiser/Intern-Atlas huggingface dataset:
Doing Right by Not Doing Wrong in Human-Robot Collaboration
Venue: arXiv cs.RO 2022
Year: 2022

As robotic systems become more and more capable of assisting humans in their everyday lives, we must consider the opportunities for these artificial agents to make their human collaborators feel unsafe or to treat them unfairly. Robots can exhibit antisocial behavior causing physical harm to people or reproduce unfair behavior replicating and even amplifying historical and societal biases which are detrimental to humans they interact with. In this paper, we discuss these issues considering sociable robotic manipulation and fair robotic decision making. We propose a novel approach to learning fair and sociable behavior, not by reproducing positive behavior, but rather by avoiding negative behavior. In this study, we highlight the importance of incorporating sociability in robot manipulation, as well as the need to consider fairness in human-robot interactions.
A survey of top-down approaches for human pose estimation
Venue: arXiv cs.CV 2022
Year: 2022

Human pose estimation in two-dimensional images videos has been a hot topic in the computer vision problem recently due to its vast benefits and potential applications for improving human life, such as behaviors recognition, motion capture and augmented reality, training robots, and movement tracking. Many state-of-the-art methods implemented with Deep Learning have addressed several challenges and brought tremendous remarkable results in the field of human pose estimation. Approaches are classified into two kinds: the two-step framework (top-down approach) and the part-based framework (bottom-up approach). While the two-step framework first incorporates a person detector and then estimates the pose within each box independently, detecting all body parts in the image and associating parts belonging to distinct persons is conducted in the part-based framework. This paper aims to provide newcomers with an extensive review of deep learning methods-based 2D images for recognizing the pose of people, which only focuses on top-down approaches since 2016. The discussion through this paper presents significant detectors and estimators depending on mathematical background, the challenges and limitations, benchmark datasets, evaluation metrics, and comparison between methods.
Leveraging the Power of Graph Algorithms: Efficient Algorithms for Computer-Aided Verification
Venue: arXiv cs.LO 2022
Year: 2022

The goal of the thesis is to leverage fast graph algorithms and modern algorithmic techniques for problems in model checking and synthesis on graphs, MDPs, and game graphs. The results include symbolic algorithms, a well-known class of algorithms in model checking that trades limited access to the input model for an efficient representation. In particular, we present the following results: Algorithms for game graphs with mean-payoff Büchi objectives and mean-payoff coBüchi objectives which match one of the best running time bounds for mean-payoff objectives. A near-linear time randomized algorithm for Streett objectives in graphs and MDPs. A sub-cubic time algorithm for bounded Büchi objectives in graphs and a cubic time algorithm for game graphs. Conditional lower bounds for queries of reachability objectives in game graphs and MDPs. Linear and near-linear time algorithms for sequential reachability objectives in graphs and MDPs respectively. The first quasi-polynomial time symbolic algorithm for parity objectives in game graphs. We break a long-standing running time bound for MEC decomposition from the '90s by providing a sub-quadratic time symbolic algorithm.
(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna
Venue: arXiv cs.GT 2022
Year: 2022

We study the problem of finding fair and efficient allocations of a set of indivisible items to a set of agents, where each item may be a good (positively valued) for some agents and a bad (negatively valued) for others, i.e., a mixed manna. As fairness notions, we consider arguably the strongest possible relaxations of envy-freeness and proportionality, namely envy-free up to any item (EFX and EFX$_0$), and proportional up to the maximin good or any bad (PropMX and PropMX$_0$). Our efficiency notion is Pareto-optimality (PO). We study two types of instances: (i) Separable, where the item set can be partitioned into goods and bads, and (ii) Restricted mixed goods (RMG), where for each item $j$, every agent has either a non-positive value for $j$, or values $j$ at the same $v_j>0$. We obtain polynomial-time algorithms for the following: (i) Separable instances: PropMX$_0$ allocation. (ii) RMG instances: Let pure bads be the set of items that everyone values negatively. - PropMX allocation for general pure bads. - EFX+PropMX allocation for identically-ordered pure bads. - EFX+PropMX+PO allocation for identical pure bads. Finally, if the RMG instances are further restricted to binary mixed goods where all the $v_j$'s are the same, we strengthen the results to guarantee EFX$_0$ and PropMX$_0$ respectively.
Featherweight Assisted Vulnerability Discovery
Venue: arXiv cs.CR 2022
Year: 2022

Predicting vulnerable source code helps to focus attention on those parts of the code that need to be examined with more scrutiny. Recent work proposed the use of function names as semantic cues that can be learned by a deep neural network (DNN) to aid in the hunt for vulnerability of functions. Combining identifier splitting, which splits each function name into its constituent words, with a novel frequency-based algorithm, we explore the extent to which the words that make up a function's name can predict potentially vulnerable functions. In contrast to *lightweight* predictions by a DNN that considers only function names, avoiding the use of a DNN provides *featherweight* predictions. The underlying idea is that function names that contain certain "dangerous" words are more likely to accompany vulnerable functions. Of course, this assumes that the frequency-based algorithm can be properly tuned to focus on truly dangerous words. Because it is more transparent than a DNN, the frequency-based algorithm enables us to investigate the inner workings of the DNN. If successful, this investigation into what the DNN does and does not learn will help us train more effective future models. We empirically evaluate our approach on a heterogeneous dataset containing over 73000 functions labeled vulnerable, and over 950000 functions labeled benign. Our analysis shows that words alone account for a significant portion of the DNN's classification ability. We also find that words are of greatest value in the datasets with a more homogeneous vocabulary. Thus, when working within the scope of a given project, where the vocabulary is unavoidably homogeneous, our approach provides a cheaper, potentially complementary, technique to aid in the hunt for source-code vulnerabilities. Finally, this approach has the advantage that it is viable with orders of magnitude less training data.
Joint Pilot Optimization, Target Detection and Channel Estimation for Integrated Sensing and Communication Systems
Venue: arXiv cs.IT 2022
Year: 2022

Radar sensing will be integrated into the 6G communication system to support various applications. In this integrated sensing and communication system, a radar target may also be a communication channel scatterer. In this case, the radar and communication channels exhibit certain joint burst sparsity. We propose a two-stage joint pilot optimization, target detection and channel estimation scheme to exploit such joint burst sparsity and pilot beamforming gain to enhance detection/estimation performance. In Stage 1, the base station (BS) sends downlink pilots (DP) for initial target search, and the user sends uplink pilots (UP) for channel estimation. Then the BS performs joint target detection and channel estimation based on the reflected DP and received UP signals. In Stage 2, the BS exploits the prior information obtained in Stage 1 to optimize the DP signal to achieve beamforming gain and further refine the performance. A Turbo Sparse Bayesian inference algorithm is proposed for joint target detection and channel estimation in both stages. The pilot optimization problem in Stage 2 is a semi-definite programming with rank-1 constraints. By replacing the rank-1 constraint with a tight and smooth approximation, we propose an efficient pilot optimization algorithm based on the majorization-minimization method. Simulations verify the advantages of the proposed scheme.
FEAT: Face Editing with Attention
Venue: arXiv cs.CV 2022
Year: 2022

Employing the latent space of pretrained generators has recently been shown to be an effective means for GAN-based face manipulation. The success of this approach heavily relies on the innate disentanglement of the latent space axes of the generator. However, face manipulation often intends to affect local regions only, while common generators do not tend to have the necessary spatial disentanglement. In this paper, we build on the StyleGAN generator, and present a method that explicitly encourages face manipulation to focus on the intended regions by incorporating learned attention maps. During the generation of the edited image, the attention map serves as a mask that guides a blending between the original features and the modified ones. The guidance for the latent space edits is achieved by employing CLIP, which has recently been shown to be effective for text-driven edits. We perform extensive experiments and show that our method can perform disentangled and controllable face manipulations based on text descriptions by attending to the relevant regions only. Both qualitative and quantitative experimental results demonstrate the superiority of our method for facial region editing over alternative methods.
Optimal Correlators and Waveforms for Mismatched Detection
Venue: arXiv cs.IT 2022
Year: 2022

We consider the classical Neymann-Pearson hypothesis testing problem of signal detection, where under the null hypothesis ($\calH_0$), the received signal is white Gaussian noise, and under the alternative hypothesis ($\calH_1$), the received signal includes also an additional non-Gaussian random signal, which in turn can be viewed as a deterministic waveform plus zero-mean, non-Gaussian noise. However, instead of the classical likelihood ratio test detector, which might be difficult to implement, in general, we impose a (mismatched) correlation detector, which is relatively easy to implement, and we characterize the optimal correlator weights in the sense of the best trade-off between the false-alarm error exponent and the missed-detection error exponent. Those optimal correlator weights depend (non-linearly, in general) on the underlying deterministic waveform under $\calH_1$. We then assume that the deterministic waveform may also be free to be optimized (subject to a power constraint), jointly with the correlator, and show that both the optimal waveform and the optimal correlator weights may take on values in a small finite set of typically no more than two to four levels, depending on the distribution of the non-Gaussian noise component. Finally, we outline an extension of the scope to a wider class of detectors that are based on linear combinations of the correlation and the energy of the received signal.
The Exponential-Time Complexity of the complex weighted #CSP
Venue: arXiv cs.CC 2022
Year: 2022

In this paper, I consider a fine-grained dichotomy of Boolean counting constraint satisfaction problem (#CSP), under the exponential time hypothesis of counting version (#ETH). Suppose $\mathscr{F}$ is a finite set of algebraic complex-valued functions defined on Boolean domain. When $\mathscr{F}$ is a subset of either two special function sets, I prove that #CSP($\mathscr{F}$) is polynomial-time solvable, otherwise it can not be computed in sub-exponential time unless #ETH fails. I also improve the result by proving the same dichotomy holds for #CSP with bounded degree (every variable appears at most constant constraints), even for #R$_3$-CSP. An important preparation before proving the result is to argue that pinning (two special unary functions $[1,0]$ and $[0,1]$ are used to reduce arity) can also keep the sub-exponential lower bound of a Boolean #CSP problem. I discuss this issue by utilizing some common methods in proving #P-hardness of counting problems. The proof illustrates the internal correlation among these commonly used methods.
Proving Information Inequalities and Identities with Symbolic Computation
Venue: arXiv cs.IT 2022
Year: 2022

Proving linear inequalities and identities of Shannon's information measures, possibly with linear constraints on the information measures, is an important problem in information theory. For this purpose, ITIP and other variant algorithms have been developed and implemented, which are all based on solving a linear program (LP). In particular, an identity $f = 0$ is verified by solving two LPs, one for $f \ge 0$ and one for $f \le 0$. In this paper, we develop a set of algorithms that can be implemented by symbolic computation. Based on these algorithms, procedures for verifying linear information inequalities and identities are devised. Compared with LP-based algorithms, our procedures can produce analytical proofs that are both human-verifiable and free of numerical errors. Our procedures are also more efficient computationally. For constrained inequalities, by taking advantage of the algebraic structure of the problem, the size of the LP that needs to be solved can be significantly reduced. For identities, instead of solving two LPs, the identity can be verified directly with very little computation.
Alpha Blending with No Division Operations
Venue: arXiv cs.GR 2022
Year: 2022

Highly accurate alpha blending can be performed entirely with integer operations, and no divisions. To reduce the number of integer multiplications, multiple color components can be blended in parallel in the same 32-bit or 64-bit register. This tutorial explains how to avoid division operations when alpha blending with 32-bit RGBA pixels. An RGBA pixel contains four 8-bit components (red, green, blue, and alpha) whose values range from 0 to 255. Alpha blending requires multiplication of the color components by an alpha value, after which (for greatest accuracy) each of these products is divided by 255 and then rounded to the nearest integer. This tutorial presents an approximate alpha-blending formula that replaces the division operation with an integer shift and add -- and also enables the number of multiplications to be reduced. When the same blending calculation is carried out to high precision using double-precision floating-point division operations, the results are found to exactly match those produced by this approximation. C++ code examples are included.
Applications of Machine Learning in Healthcare and Internet of Things (IOT): A Comprehensive Review
Venue: arXiv cs.LG 2022
Year: 2022

In recent years, smart healthcare IoT devices have become ubiquitous, but they work in isolated networks due to their policy. Having these devices connected in a network enables us to perform medical distributed data analysis. However, the presence of diverse IoT devices in terms of technology, structure, and network policy, makes it a challenging issue while applying traditional centralized learning algorithms on decentralized data collected from the IoT devices. In this study, we present an extensive review of the state-of-the-art machine learning applications particularly in healthcare, challenging issues in IoT, and corresponding promising solutions. Finally, we highlight some open-ended issues of IoT in healthcare that leaves further research studies and investigation for scientists.
A Compressed Sensing Based Least Squares Approach to Semi-supervised Local Cluster Extraction
Venue: arXiv cs.LG 2022
Year: 2022

A least squares semi-supervised local clustering algorithm based on the idea of compressed sensing is proposed to extract clusters from a graph with known adjacency matrix. The algorithm is based on a two-stage approach similar to the one in \cite{LaiMckenzie2020}. However, under a weaker assumption and with less computational complexity than the one in \cite{LaiMckenzie2020}, the algorithm is shown to be able to find a desired cluster with high probability. The ``one cluster at a time" feature of our method distinguishes it from other global clustering methods. Several numerical experiments are conducted on the synthetic data such as stochastic block model and real data such as MNIST, political blogs network, AT\&T and YaleB human faces data sets to demonstrate the effectiveness and efficiency of our algorithm.
3TO: THz-Enabled Throughput and Trajectory Optimization of UAVs in 6G Networks by Proximal Policy Optimization Deep Reinforcement Learning
Venue: arXiv cs.NI 2022
Year: 2022

Next-generation networks need to meet ubiquitous and high data-rate demand. Therefore, this paper considers the throughput and trajectory optimization of terahertz (THz)-enabled unmanned aerial vehicles (UAVs) in the sixth-generation (6G) communication networks. In the considered scenario, multiple UAVs must provide on-demand terabits per second (TB/s) services to an urban area along with existing terrestrial networks. However, THz-empowered UAVs pose some new constraints, e.g., dynamic THz-channel conditions for ground users (GUs) association and UAV trajectory optimization to fulfill GU's throughput demands. Thus, a framework is proposed to address these challenges, where a joint UAVs-GUs association, transmit power, and the trajectory optimization problem is studied. The formulated problem is mixed-integer non-linear programming (MINLP), which is NP-hard to solve. Consequently, an iterative algorithm is proposed to solve three sub-problems iteratively, i.e., UAVs-GUs association, transmit power, and trajectory optimization. Simulation results demonstrate that the proposed algorithm increased the throughput by up to 10%, 68.9%, and 69.1% respectively compared to baseline algorithms.
On the Stability of Super-Resolution and a Beurling-Selberg Type Extremal Problem
Venue: arXiv cs.IT 2022
Year: 2022

Super-resolution estimation is the problem of recovering a stream of spikes (point sources) from the noisy observation of a few numbers of its first trigonometric moments. The performance of super-resolution is recognized to be intimately related to the separation between the spikes to recover. A novel notion of stability of the Fisher information matrix (FIM) of the super-resolution problem is introduced when the minimal eigenvalue of the FIM is not asymptotically vanishing. The regime where the minimal separation is inversely proportional to the number of acquired moments is considered. It is shown that there is a separation threshold above which the eigenvalues of the FIM can be bounded by a quantity that does not depend on the number of moments. The proof relies on characterizing the connection between the stability of the FIM and a generalization of the Beurling-Selberg box approximation problem.
One to Rule them All? A First Look at DNS over QUIC
Venue: arXiv cs.NI 2022
Year: 2022

The DNS is one of the most crucial parts of the Internet. Since the original DNS specifications defined UDP and TCP as the underlying transport protocols, DNS queries are inherently unencrypted, making them vulnerable to eavesdropping and on-path manipulations. Consequently, concerns about DNS privacy have gained attention in recent years, which resulted in the introduction of the encrypted protocols DNS over TLS (DoT) and DNS over HTTPS (DoH). Although these protocols address the key issues of adding privacy to the DNS, they are inherently restrained by their underlying transport protocols, which are at strife with, e.g., IP fragmentation or multi-RTT handshakes - challenges which are addressed by QUIC. As such, the recent addition of DNS over QUIC (DoQ) promises to improve upon the established DNS protocols. However, no studies focusing on DoQ, its adoption, or its response times exist to this date - a gap we close with our study. Our active measurements show a slowly but steadily increasing adoption of DoQ and reveal a high week-over-week fluctuation, which reflects the ongoing development process: As DoQ is still in standardization, implementations and services undergo rapid changes. Analyzing the response times of DoQ, we find that roughly 40% of measurements show considerably higher handshake times than expected, which traces back to the enforcement of the traffic amplification limit despite successful validation of the client's address. However, DoQ already outperforms DoT as well as DoH, which makes it the best choice for encrypted DNS to date.
Network Calculus with Flow Prolongation -- A Feedforward FIFO Analysis enabled by ML
Venue: arXiv cs.NI 2022
Year: 2022

The derivation of upper bounds on data flows' worst-case traversal times is an important task in many application areas. For accurate bounds, model simplifications should be avoided even in large networks. Network Calculus (NC) provides a modeling framework and different analyses for delay bounding. We investigate the analysis of feedforward networks where all queues implement First-In First-Out (FIFO) service. Correctly considering the effect of data flows onto each other under FIFO is already a challenging task. Yet, the fastest available NC FIFO analysis suffers from limitations resulting in unnecessarily loose bounds. A feature called Flow Prolongation (FP) has been shown to improve delay bound accuracy significantly. Unfortunately, FP needs to be executed within the NC FIFO analysis very often and each time it creates an exponentially growing set of alternative networks with prolongations. FP therefore does not scale and has been out of reach for the exhaustive analysis of large networks. We introduce DeepFP, an approach to make FP scale by predicting prolongations using machine learning. In our evaluation, we show that DeepFP can improve results in FIFO networks considerably. Compared to the standard NC FIFO analysis, DeepFP reduces delay bounds by 12.1% on average at negligible additional computational cost.
B2EA: An Evolutionary Algorithm Assisted by Two Bayesian Optimization Modules for Neural Architecture Search
Venue: arXiv cs.NE 2022
Year: 2022

The early pioneering Neural Architecture Search (NAS) works were multi-trial methods applicable to any general search space. The subsequent works took advantage of the early findings and developed weight-sharing methods that assume a structured search space typically with pre-fixed hyperparameters. Despite the amazing computational efficiency of the weight-sharing NAS algorithms, it is becoming apparent that multi-trial NAS algorithms are also needed for identifying very high-performance architectures, especially when exploring a general search space. In this work, we carefully review the latest multi-trial NAS algorithms and identify the key strategies including Evolutionary Algorithm (EA), Bayesian Optimization (BO), diversification, input and output transformations, and lower fidelity estimation. To accommodate the key strategies into a single framework, we develop B2EA that is a surrogate assisted EA with two BO surrogate models and a mutation step in between. To show that B2EA is robust and efficient, we evaluate three performance metrics over 14 benchmarks with general and cell-based search spaces. Comparisons with state-of-the-art multi-trial algorithms reveal that B2EA is robust and efficient over the 14 benchmarks for three difficulty levels of target performance. The B2EA code is publicly available at \url{https://github.com/snu-adsl/BBEA}.