OpenRaiser/Intern-Atlas huggingface dataset:
Register Games
Venue: arXiv cs.FL 2020
Year: 2020

The complexity of parity games is a long standing open problem that saw a major breakthrough in 2017 when two quasi-polynomial algorithms were published. This article presents a third, independent approach to solving parity games in quasi-polynomial time, based on the notion of register game, a parameterised variant of a parity game. The analysis of register games leads to a quasi-polynomial algorithm for parity games, a polynomial algorithm for restricted classes of parity games and a novel measure of complexity, the register index, which aims to capture the combined complexity of the priority assignement and the underlying game graph. We further present a translation of alternating parity word automata into alternating weak automata with only a quasi-polynomial increase in size, based on register games; this improves on the previous exponential translation. We also use register games to investigate the parity index hierarchy: while for words the index hierarchy of alternating parity automata collapses to the weak level, and for trees it is strict, for structures between trees and words, it collapses logarithmically, in the sense that any parity tree automaton of size n is equivalent, on these particular classes of structures, to an automaton with a number of priorities logarithmic in n.
Constrained Thompson Sampling for Wireless Link Optimization
Venue: arXiv cs.LG 2020
Year: 2020

Wireless communication systems operate in complex time-varying environments. Therefore, selecting the optimal configuration parameters in these systems is a challenging problem. For wireless links, \emph{rate selection} is used to select the optimal data transmission rate that maximizes the link throughput subject to an application-defined latency constraint. We model rate selection as a stochastic multi-armed bandit (MAB) problem, where a finite set of transmission rates are modeled as independent bandit arms. For this setup, we propose Con-TS, a novel constrained version of the Thompson sampling algorithm, where the latency requirement is modeled by a high-probability linear constraint. We show that for Con-TS, the expected number of constraint violations over T transmission intervals is upper bounded by O(\sqrt{KT}), where K is the number of available rates. Further, the expected loss in cumulative throughput compared to the optimal rate selection scheme (i.e., the egret is also upper bounded by O(\sqrt{KT \log K}). Through numerical simulations, we demonstrate that Con-TS significantly outperforms state-of-the-art bandit schemes for rate selection.
On the convex geometry of blind deconvolution and matrix completion
Venue: arXiv cs.IT 2020
Year: 2020

Low-rank matrix recovery from structured measurements has been a topic of intense study in the last decade and many important problems like matrix completion and blind deconvolution have been formulated in this framework. An important benchmark method to solve these problems is to minimize the nuclear norm, a convex proxy for the rank. A common approach to establish recovery guarantees for this convex program relies on the construction of a so-called approximate dual certificate. However, this approach provides only limited insight in various respects. Most prominently, the noise bounds exhibit seemingly suboptimal dimension factors. In this paper we take a novel, more geometric viewpoint to analyze both the matrix completion and the blind deconvolution scenario. We find that for both these applications the dimension factors in the noise bounds are not an artifact of the proof, but the problems are intrinsically badly conditioned. We show, however, that bad conditioning only arises for very small noise levels: Under mild assumptions that include many realistic noise levels we derive near-optimal error estimates for blind deconvolution under adversarial noise.
Uplink Non-Orthogonal Multiple Access over Mixed RF-FSO Systems
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we consider a relay-assisted uplink non-orthogonal multiple access (NOMA) system. In this system, two radio frequency (RF) users are grouped for simultaneous transmissions, over each resource block, to an intermediate relay. The relay then forwards the amplified version of the users' aggregated signals, in the presence of multiuser interference, to a relatively far destination. In order to cope with the users' ever-increasing desire for higher data rates, a high-throughput free-space optics (FSO) link is employed as the relay-destination backhaul link. It is assumed that the FSO backhaul link is subject to Gamma-Gamma turbulence with pointing error. Also, a Rayleigh fading model is considered for the user-relay access links. Under these assumptions, we derive closed-form expressions for the outage probability and tractable forms, involving only one-dimensional integrals, for the ergodic capacity. Moreover, the outage probability and ergodic capacity analysis are extended to the conventional RF-backhauled systems in the presence of multiuser interference to both relay and destination nodes, and Rician fading for the relay-destination RF link. Our results reveal the superiority of FSO backhauling for high-throughput and high-reliability NOMA systems compared to RF backhauling. This work can be considered as a general analysis of dual-hop uplink NOMA systems as well as the first attempt to incorporate power-domain NOMA in mixed RF-FSO systems.
2LS: Heap Analysis and Memory Safety (Competition Contribution)
Venue: arXiv cs.SE 2020
Year: 2020

2LS is a framework for analysis of sequential C programs that can verify and refute program assertions and termination. The 2LS framework is built upon the CPROVER infrastructure and implements template-based synthesis techniques, e.g. to find invariants and ranking functions, and incremental loop unwinding techniques to find counterexamples and k-induction proofs. The main improvements in this year's version are the ability of 2LS to analyse programs requiring combined reasoning about shape and content of dynamic data structures, and an instrumentation for memory safety properties.
Pushing the Boundaries of Asymptotic Optimality in Integrated Task and Motion Planning
Venue: arXiv cs.RO 2020
Year: 2020

Integrated task and motion planning problems describe a multi-modal state space, which is often abstracted as a set of smooth manifolds that are connected via sets of transitions states. One approach to solving such problems is to sample reachable states in each of the manifolds, while simultaneously sampling transition states. Prior work has shown that in order to achieve asymptotically optimal (AO) solutions for such piecewise-smooth task planning problems, it is sufficient to double the connection radius required for AO sampling-based motion planning. This was shown under the assumption that the transition sets themselves are smooth. The current work builds upon this result and demonstrates that it is sufficient to use the same connection radius as for standard AO motion planning. Furthermore, the current work studies the case that the transition sets are non-smooth boundary points of the valid state space, which is frequently the case in practice, such as when a gripper grasps an object. This paper generalizes the notion of clearance that is typically assumed in motion and task planning to include such individual, potentially non-smooth transition states. It is shown that asymptotic optimality is retained under this generalized regime.
Distributed Optimal Voltage Control with Asynchronous and Delayed Communication
Venue: arXiv cs.SY 2020
Year: 2020

The increased penetration of volatile renewable energy into distribution networks necessities more efficient distributed voltage control. In this paper, we design distributed feedback control algorithms where each bus can inject \emph{both active and reactive} power into the grid to regulate the voltages. The control law on each bus is only based on local voltage measurements and communication to its physical neighbors. Moreover, the buses can perform their updates \emph{asynchronously} without receiving information from their neighbors for periods of time. The algorithm enforces \emph{hard upper and lower limits} on the active and reactive powers at every iteration. We prove that the algorithm converges to the optimal feasible voltage profile, assuming linear power flows. This provable convergence is maintained under bounded communication delays and asynchronous communications. We further numerically test the performance of the algorithm using the full \emph{nonlinear AC power flow} model. Our simulations show the effectiveness of our algorithm on realistic networks with both static and fluctuating loads, even in the presence of communication delays.
Joint Perception and Control as Inference with an Object-based Implementation
Venue: arXiv cs.LG 2020
Year: 2020

Existing model-based reinforcement learning methods often study perception modeling and decision making separately. We introduce joint Perception and Control as Inference (PCI), a general framework to combine perception and control for partially observable environments through Bayesian inference. Based on the fact that object-level inductive biases are critical in human perceptual learning and reasoning, we propose Object-based Perception Control (OPC), an instantiation of PCI which manages to facilitate control using automatic discovered object-based representations. We develop an unsupervised end-to-end solution and analyze the convergence of the perception model update. Experiments in a high-dimensional pixel environment demonstrate the learning effectiveness of our object-based perception control approach. Specifically, we show that OPC achieves good perceptual grouping quality and outperforms several strong baselines in accumulated rewards.
Towards Better Human Robot Collaboration with Robust Plan Recognition and Trajectory Prediction
Venue: arXiv cs.RO 2020
Year: 2020

Human robot collaboration (HRC) is becoming increasingly important as the paradigm of manufacturing is shifting from mass production to mass customization. The introduction of HRC can significantly improve the flexibility and intelligence of automation. However, due to the stochastic and time-varying nature of human collaborators, it is challenging for the robot to efficiently and accurately identify the plan of human and respond in a safe manner. To address this challenge, we propose an integrated human robot collaboration framework in this paper which includes both plan recognition and trajectory prediction. Such a framework enables the robots to perceive, predict and adapt their actions to the human's plan and intelligently avoid collisions with the human based on the predicted human trajectory. Moreover, by explicitly leveraging the hierarchical relationship between the plan and trajectories, more robust plan recognition performance can be achieved. Experiments are conducted on an industrial robot to verify the proposed framework, which shows that our proposed framework can not only assure safe HRC, but also improve the time efficiency of the HRC team, and the plan recognition module is not sensitive to noises.
Generalized Fast-Convolution-based Filtered-OFDM: Techniques and Application to 5G New Radio
Venue: arXiv cs.IT 2020
Year: 2020

This paper proposes a generalized model and methods for fast-convolution (FC)-based waveform generation and processing with specific applications to fifth generation new radio (5G-NR). Following the progress of 5G-NR standardization in 3rd generation partnership project (3GPP), the main focus is on subband-filtered cyclic prefix (CP) orthogonal frequency-division multiplexing (OFDM) processing with specific emphasis on spectrally well localized transmitter processing. Subband filtering is able to suppress the interference leakage between adjacent subbands, thus supporting different numerologies for so-called bandwidth parts as well as asynchronous multiple access. The proposed generalized FC scheme effectively combines overlapped block processing with time- and frequency-domain windowing to provide highly selective subband filtering with very low intrinsic interference level. Jointly optimized multi-window designs with different allocation sizes and design parameters are compared in terms of interference levels and implementation complexity. The proposed methods are shown to clearly outperform the existing state-of-the-art windowing and filtering-based methods.
Mix and match networks: cross-modal alignment for zero-pair image-to-image translation
Venue: arXiv cs.CV 2020
Year: 2020

This paper addresses the problem of inferring unseen cross-modal image-to-image translations between multiple modalities. We assume that only some of the pairwise translations have been seen (i.e. trained) and infer the remaining unseen translations (where training pairs are not available). We propose mix and match networks, an approach where multiple encoders and decoders are aligned in such a way that the desired translation can be obtained by simply cascading the source encoder and the target decoder, even when they have not interacted during the training stage (i.e. unseen). The main challenge lies in the alignment of the latent representations at the bottlenecks of encoder-decoder pairs. We propose an architecture with several tools to encourage alignment, including autoencoders and robust side information and latent consistency losses. We show the benefits of our approach in terms of effectiveness and scalability compared with other pairwise image-to-image translation approaches. We also propose zero-pair cross-modal image translation, a challenging setting where the objective is inferring semantic segmentation from depth (and vice-versa) without explicit segmentation-depth pairs, and only from two (disjoint) segmentation-RGB and depth-RGB training sets. We observe that a certain part of the shared information between unseen modalities might not be reachable, so we further propose a variant that leverages pseudo-pairs which allows us to exploit this shared information between the unseen modalities.
Artificial intelligence in cyber physical systems
Venue: arXiv cs.CY 2020
Year: 2020

This article conducts a literature review of current and future challenges in the use of artificial intelligence (AI) in cyber physical systems. The literature review is focused on identifying a conceptual framework for increasing resilience with AI through automation supporting both, a technical and human level. The methodology applied resembled a literature review and taxonomic analysis of complex internet of things (IoT) interconnected and coupled cyber physical systems. There is an increased attention on propositions on models, infrastructures and frameworks of IoT in both academic and technical papers. These reports and publications frequently represent a juxtaposition of other related systems and technologies (e.g. Industrial Internet of Things, Cyber Physical Systems, Industry 4.0 etc.). We review academic and industry papers published between 2010 and 2020. The results determine a new hierarchical cascading conceptual framework for analysing the evolution of AI decision-making in cyber physical systems. We argue that such evolution is inevitable and autonomous because of the increased integration of connected devices (IoT) in cyber physical systems. To support this argument, taxonomic methodology is adapted and applied for transparency and justifications of concepts selection decisions through building summary maps that are applied for designing the hierarchical cascading conceptual framework.
Future developments in standardisation of cyber risk in the Internet of Things (IoT)
Venue: arXiv cs.CY 2020
Year: 2020

In this research article, we explore the use of a design process for adapting existing cyber risk assessment standards to allow the calculation of economic impact from IoT cyber risk. The paper presents a new model that includes a design process with new risk assessment vectors, specific for IoT cyber risk. To design new risk assessment vectors for IoT, the study applied a range of methodologies, including literature review, empirical study and comparative study, followed by theoretical analysis and grounded theory. An epistemological framework emerges from applying the constructivist grounded theory methodology to draw on knowledge from existing cyber risk frameworks, models and methodologies. This framework presents the current gaps in cyber risk standards and policies, and defines the design principles of future cyber risk impact assessment. The core contribution of the article therefore, being the presentation of a new model for impact assessment of IoT cyber risk.
On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five
Venue: arXiv cs.DM 2020
Year: 2020

A hole in a graph is an induced cycle of length at least $4$, and an antihole is the complement of an induced cycle of length at least $4$. A hole or antihole is long if its length is at least $5$. For an integer $k$, the $k$-prism is the graph consisting of two cliques of size $k$ joined by a matching. The complexity of Maximum (Weight) Independent Set (MWIS) in long-hole-free graphs remains an important open problem. In this paper we give a polynomial time algorithm to solve MWIS in long-hole-free graphs with no $k$-prism (for any fixed integer $k$), and a subexponential algorithm for MWIS in long-hole-free graphs in general. As a special case this gives a polynomial time algorithm to find a maximum weight clique in perfect graphs with no long antihole, and no hole of length $6$. The algorithms use the framework of minimal chordal completions and potential maximal cliques.
Distributed Detection with Empirically Observed Statistics
Venue: arXiv cs.IT 2020
Year: 2020

Consider a distributed detection problem in which the underlying distributions of the observations are unknown; instead of these distributions, noisy versions of empirically observed statistics are available to the fusion center. These empirically observed statistics, together with source (test) sequences, are transmitted through different channels to the fusion center. The fusion center decides which distribution the source sequence is sampled from based on these data. For the binary case, we derive the optimal type-II error exponent given that the type-I error decays exponentially fast. The type-II error exponent is maximized over the proportions of channels for both source and training sequences. We conclude that as the ratio of the lengths of training to test sequences $α$ tends to infinity, using only one channel is optimal. By calculating the derived exponents numerically, we conjecture that the same is true when $α$ is finite. We relate our results to the classical distributed detection problem studied by Tsitsiklis, in which the underlying distributions are known. Finally, our results are extended to the case of $m$-ary distributed detection with a rejection option.
Can User-Centered Reinforcement Learning Allow a Robot to Attract Passersby without Causing Discomfort?
Venue: arXiv cs.AI 2020
Year: 2020

The aim of our study was to develop a method by which a social robot can greet passersby and get their attention without causing them to suffer discomfort.A number of customer services have recently come to be provided by social robots rather than people, including, serving as receptionists, guides, and exhibitors. Robot exhibitors, for example, can explain products being promoted by the robot owners. However, a sudden greeting by a robot can startle passersby and cause discomfort to passersby.Social robots should thus adapt their mannerisms to the situation they face regarding passersby.We developed a method for meeting this requirement on the basis of the results of related work. Our proposed method, user-centered reinforcement learning, enables robots to greet passersby and get their attention without causing them to suffer discomfort (p<0.01) .The results of an experiment in the field, an office entrance, demonstrated that our method meets this requirement.
Large-Scale Beamforming for Massive MIMO via Randomized Sketching
Venue: arXiv cs.IT 2020
Year: 2020

Massive MIMO system yields significant improvements in spectral and energy efficiency for future wireless communication systems. The regularized zero-forcing (RZF) beamforming is able to provide good performance with the capability of achieving numerical stability and robustness to the channel uncertainty. However, in massive MIMO systems, the matrix inversion operation in RZF beamforming becomes computationally expensive. To address this computational issue, we shall propose a novel randomized sketching based RZF beamforming approach with low computational complexity. This is achieved by solving a linear system via randomized sketching based on the preconditioned Richard iteration, which guarantees high quality approximations to the optimal solution. We theoretically prove that the sequence of approximations obtained iteratively converges to the exact RZF beamforming matrix linearly fast as the number of iterations increases. Also, it turns out that the system sum-rate for such sequence of approximations converges to the exact one at a linear convergence rate. Our simulation results verify our theoretical findings.
Maximum Cut Parameterized by Crossing Number
Venue: arXiv cs.DS 2020
Year: 2020

Given an edge-weighted graph $G$ on $n$ nodes, the NP-hard Max-Cut problem asks for a node bipartition such that the sum of edge weights joining the different partitions is maximized. We propose a fixed-parameter tractable algorithm parameterized by the number $k$ of crossings in a given drawing of $G$. Our algorithm achieves a running time of $O(2^k \cdot p(n + k))$, where $p$ is the polynomial running time for planar Max-Cut. The only previously known similar algorithm [8] is restricted to 1-planar graphs (i.e., at most one crossing per edge) and its dependency on $k$ is of order $3^k$ . A direct consequence of our result is that Max-Cut is fixed-parameter tractable w.r.t. the crossing number, even without a given drawing. Moreover, the results naturally carry over to the minor crossing number.
Arbitrage with Power Factor Correction using Energy Storage
Venue: arXiv cs.SY 2020
Year: 2020

The importance of reactive power compensation for power factor (PF) correction will significantly increase with the large-scale integration of distributed generation interfaced via inverters producing only active power. In this work, we focus on co-optimizing energy storage for performing energy arbitrage as well as local power factor correction. The joint optimization problem is non-convex, but can be solved efficiently using a McCormick relaxation along with penalty-based schemes. Using numerical simulations on real data and realistic storage profiles, we show that energy storage can correct PF locally without reducing arbitrage profit. It is observed that active and reactive power control is largely decoupled in nature for performing arbitrage and PF correction (PFC). Furthermore, we consider a real-time implementation of the problem with uncertain load, renewable and pricing profiles. We develop a model predictive control based storage control policy using auto-regressive forecast for the uncertainty. We observe that PFC is primarily governed by the size of the converter and therefore, look-ahead in time in the online setting does not affect PFC noticeably. However, arbitrage profit are more sensitive to uncertainty for batteries with faster ramp rates compared to slow ramping batteries.