OpenRaiser/Intern-Atlas huggingface dataset:
Improved Convergence for $\ell_\infty$ and $\ell_1$ Regression via Iteratively Reweighted Least Squares
Venue: arXiv cs.DS 2019
Year: 2019

The iteratively reweighted least squares method (IRLS) is a popular technique used in practice for solving regression problems. Various versions of this method have been proposed, but their theoretical analyses failed to capture the good practical performance. In this paper we propose a simple and natural version of IRLS for solving $\ell_\infty$ and $\ell_1$ regression, which provably converges to a $(1+ε)$-approximate solution in $O(m^{1/3}\log(1/ε)/ε^{2/3} + \log m/ε^2)$ iterations, where $m$ is the number of rows of the input matrix. Interestingly, this running time is independent of the conditioning of the input, and the dominant term of the running time depends sublinearly in $ε^{-1}$, which is atypical for the optimization of non-smooth functions. This improves upon the more complex algorithms of Chin et al. (ITCS '12), and Christiano et al. (STOC '11) by a factor of at least $1/ε^2$, and yields a truly efficient natural algorithm for the slime mold dynamics (Straszak-Vishnoi, SODA '16, ITCS '16, ITCS '17).
Moment-Based Bound on Peak-to-Average Power Ratio and Reduction with Unitary Matrix
Venue: arXiv cs.IT 2019
Year: 2019

Reducing Peak-to-Average Power Ratio (PAPR) is a significant task in OFDM systems. To evaluate the efficiency of PAPR-reducing methods, the complementary cumulative distribution function (CCDF) of PAPR is often used. In the situation where the central limit theorem can be applied, an approximate form of the CCDF has been obtained. On the other hand, in general situations, the bound of the CCDF has been obtained under some assumptions. In this paper, we derive the bound of the CCDF with no assumption about modulation schemes. Therefore, our bound can be applied with any codewords and that our bound is written with fourth moments of codewords. Further, we propose a method to reduce the bound with unitary matrices. With this method, it is shown that our bound is closely related to the CCDF of PAPR.
Experimental Assessment of Real-time PDCP-RLC V-RAN Split Transmission with 20 Gbit/s PAM4 Optical Access
Venue: arXiv cs.NI 2019
Year: 2019

We experimentally demonstrate real-time, end-to-end transmission of 3GPP's option 2 functional split RAN interface with virtualized central units through up to 20km using a 20Gbit/s PAM4 link and 10GHz bandwidth optics.
Simple Approximations of the SIR Meta Distribution in General Cellular Networks
Venue: arXiv cs.IT 2019
Year: 2019

Compared to the standard success (coverage) probability, the meta distribution of the signal-to-interference ratio (SIR) provides much more fine-grained information about the network performance. We consider general heterogeneous cellular networks (HCNs) with base station tiers modeled by arbitrary stationary and ergodic non-Poisson point processes. The exact analysis of non-Poisson network models is notoriously difficult, even in terms of the standard success probability, let alone the meta distribution. Hence we propose a simple approach to approximate the SIR meta distribution for non-Poisson networks based on the ASAPPP ("approximate SIR analysis based on the Poisson point process") method. We prove that the asymptotic horizontal gap $G_0$ between its standard success probability and that for the Poisson point process exactly characterizes the gap between the $b$th moment of the conditional success probability, as the SIR threshold goes to $0$. The gap $G_0$ allows two simple approximations of the meta distribution for general HCNs: 1) the per-tier approximation by applying the shift $G_0$ to each tier and 2) the effective gain approximation by directly shifting the meta distribution for the homogeneous independent Poisson network. Given the generality of the model considered and the fine-grained nature of the meta distribution, these approximations work surprisingly well.
Complexity of the quorum intersection property of the Federated Byzantine Agreement System
Venue: arXiv cs.DC 2019
Year: 2019

A Federated Byzantine Agreement System is defined as a pair $(V, Q)$ comprising a set of nodes $V$ and a quorum function $Q: V \mapsto 2^{2^{V}} \setminus \{\emptyset\}$ specifying for each node a set of subsets of nodes, called quorum slices. A subset of nodes is a quorum if and only if for each of its nodes it also contains at least one of its quorum slices. The Disjoint Quorums Problem answers the question whether a given instance of \acrlong{fbas} contains two quorums that have no nodes in common. We show that this problem is $\mathsf{NP-complete}$. We also study the problem of finding a quorum of minimal size and show it is $\mathsf{NP-hard}$. Further, we consider the problem of checking whether a given subset of nodes contains a quorum for some selected node. We show this problem is $\mathsf{P-complete}$ and describe a method that solves it in linear time with respect to number of nodes and the total size of all quorum slices. Moreover, we analyze the complexity of some of these problems using the parametrized point of view.
LocalNorm: Robust Image Classification through Dynamically Regularized Normalization
Venue: arXiv cs.CV 2019
Year: 2019

While modern convolutional neural networks achieve outstanding accuracy on many image classification tasks, they are, compared to humans, much more sensitive to image degradation. Here, we describe a variant of Batch Normalization, LocalNorm, that regularizes the normalization layer in the spirit of Dropout while dynamically adapting to the local image intensity and contrast at test-time. We show that the resulting deep neural networks are much more resistant to noise-induced image degradation, improving accuracy by up to three times, while achieving the same or slightly better accuracy on non-degraded classical benchmarks. In computational terms, LocalNorm adds negligible training cost and little or no cost at inference time, and can be applied to already-trained networks in a straightforward manner.
A Dependently Typed Library for Static Information-Flow Control in Idris
Venue: arXiv cs.PL 2019
Year: 2019

Safely integrating third-party code in applications while protecting the confidentiality of information is a long-standing problem. Pure functional programming languages, like Haskell, make it possible to enforce lightweight information-flow control through libraries like MAC by Russo. This work presents DepSec, a MAC inspired, dependently typed library for static information-flow control in Idris. We showcase how adding dependent types increases the expressiveness of state-of-the-art static information-flow control libraries and how DepSec matches a special-purpose dependent information-flow type system on a key example. Finally, we show novel and powerful means of specifying statically enforced declassification policies using dependent types.
Relational parsing: a clean, fast parsing strategy for all context-free languages
Venue: arXiv cs.FL 2019
Year: 2019

We present a novel parsing algorithm for all context-free languages, based on computing the relation between configurations and reaching transitions in a recursive transition network. Parsing complexity w.r.t. input length matches the state of the art: it is worst-case cubic, quadratic for unambiguous grammars, and linear for LR-regular ones. What distinguishes our algorithm is its clean mathematical formulation: parsing is expressed as a composition of simple operations on languages and relations, and can therefore be implemented using only immutable data structures. With a proper choice of these structures, a vast majority of operations performed during parsing typical programming languages can be memoized, which allows our proof-of-concept implementation to outperform common generalized parsing algorithms, in some cases by orders of magnitude.
Maximum distance separable codes to order
Venue: arXiv cs.IT 2019
Year: 2019

Maximum distance separable (MDS) are constructed to required specifications. The codes are explicitly given over finite fields with efficient encoding and decoding algorithms. Series of such codes over finite fields with ratio of distance to length approaching $(1-R)$ for given $R, \, 0 < R < 1$ are derived. For given rate $R=\frac{r}{n}$, with $p$ not dividing $n$, series of codes over finite fields of characteristic $p$ are constructed such that the ratio of the distance to the length approaches $(1-R)$. For a given field $GF(q)$ MDS codes of the form $(q-1,r)$ are constructed for any $r$. The codes are encompassing, easy to construct with efficient encoding and decoding algorithms of complexity $\max\{O(n\log n), t^2\}$, where $t$ is the error-correcting capability of the code.
Appendix for: Cut-free Calculi and Relational Semantics for Temporal STIT logics
Venue: arXiv cs.LO 2019
Year: 2019

This paper is an appendix to the paper "Cut-free Calculi and Relational Semantics for Temporal STIT logics" by Berkel and Lyon, 2019. It provides the completeness proof for the basic STIT logic Ldm (relative to irreflexive, temporal Kripke STIT frames) as well as gives the derivation of the independence of agents axiom for the logic Xstit.
Fake News Detection on Social Media using Geometric Deep Learning
Venue: arXiv cs.SI 2019
Year: 2019

Social media are nowadays one of the main news sources for millions of people around the globe due to their low cost, easy access and rapid dissemination. This however comes at the cost of dubious trustworthiness and significant risk of exposure to 'fake news', intentionally written to mislead the readers. Automatically detecting fake news poses challenges that defy existing content-based analysis approaches. One of the main reasons is that often the interpretation of the news requires the knowledge of political or social context or 'common sense', which current NLP algorithms are still missing. Recent studies have shown that fake and real news spread differently on social media, forming propagation patterns that could be harnessed for the automatic fake news detection. Propagation-based approaches have multiple advantages compared to their content-based counterparts, among which is language independence and better resilience to adversarial attacks. In this paper we show a novel automatic fake news detection model based on geometric deep learning. The underlying core algorithms are a generalization of classical CNNs to graphs, allowing the fusion of heterogeneous data such as content, user profile and activity, social graph, and news propagation. Our model was trained and tested on news stories, verified by professional fact-checking organizations, that were spread on Twitter. Our experiments indicate that social network structure and propagation are important features allowing highly accurate (92.7% ROC AUC) fake news detection. Second, we observe that fake news can be reliably detected at an early stage, after just a few hours of propagation. Third, we test the aging of our model on training and testing data separated in time. Our results point to the promise of propagation-based approaches for fake news detection as an alternative or complementary strategy to content-based approaches.
Bayesian method for evaluation an airline profitability on the base components of Airline Route Planning
Venue: arXiv cs.CY 2019
Year: 2019

Airline route planning takes into account the factors of commercial and customer preferences, safety, and should allow a flexibility given the tremendous uncertainty about market conditions. The mathematical model on the Bayes formula allows optimizing the interaction of the base factors.
A Speculative Study on 6G
Venue: arXiv cs.NI 2019
Year: 2019

While 5G is being tested worldwide and anticipated to be rolled out gradually in 2019, researchers around the world are beginning to turn their attention to what 6G might be in 10+ years time, and there are already initiatives in various countries focusing on the research of possible 6G technologies. This article aims to extend the vision of 5G to more ambitious scenarios in a more distant future and speculates on the visionary technologies that could provide the step changes needed for enabling 6G.
Incremental Cluster Validity Indices for Hard Partitions: Extensions and Comparative Study
Venue: arXiv cs.LG 2019
Year: 2019

Validation is one of the most important aspects of clustering, but most approaches have been batch methods. Recently, interest has grown in providing incremental alternatives. This paper extends the incremental cluster validity index (iCVI) family to include incremental versions of Calinski-Harabasz (iCH), I index and Pakhira-Bandyopadhyay-Maulik (iI and iPBM), Silhouette (iSIL), Negentropy Increment (iNI), Representative Cross Information Potential (irCIP) and Representative Cross Entropy (irH), and Conn_Index (iConn_Index). Additionally, the effect of under- and over-partitioning on the behavior of these six iCVIs, the Partition Separation (PS) index, as well as two other recently developed iCVIs (incremental Xie-Beni (iXB) and incremental Davies-Bouldin (iDB)) was examined through a comparative study. Experimental results using fuzzy adaptive resonance theory (ART)-based clustering methods showed that while evidence of most under-partitioning cases could be inferred from the behaviors of all these iCVIs, over-partitioning was found to be a more challenging scenario indicated only by the iConn_Index. The expansion of incremental validity indices provides significant novel opportunities for assessing and interpreting the results of unsupervised learning.
Democratisation of Usable Machine Learning in Computer Vision
Venue: arXiv cs.CV 2019
Year: 2019

Many industries are now investing heavily in data science and automation to replace manual tasks and/or to help with decision making, especially in the realm of leveraging computer vision to automate many monitoring, inspection, and surveillance tasks. This has resulted in the emergence of the 'data scientist' who is conversant in statistical thinking, machine learning (ML), computer vision, and computer programming. However, as ML becomes more accessible to the general public and more aspects of ML become automated, applications leveraging computer vision are increasingly being created by non-experts with less opportunity for regulatory oversight. This points to the overall need for more educated responsibility for these lay-users of usable ML tools in order to mitigate potentially unethical ramifications. In this paper, we undertake a SWOT analysis to study the strengths, weaknesses, opportunities, and threats of building usable ML tools for mass adoption for important areas leveraging ML such as computer vision. The paper proposes a set of data science literacy criteria for educating and supporting lay-users in the responsible development and deployment of ML applications.
A Markov Process Approach to Ensemble Control of Smart Buildings
Venue: arXiv cs.SY 2019
Year: 2019

This paper describes a step-by-step procedure that converts a physical model of a building into a Markov Process that characterizes energy consumption of this and other similar buildings. Relative to existing thermo-physics-based building models, the proposed procedure reduces model complexity and depends on fewer parameters, while also maintaining accuracy and feasibility sufficient for system-level analyses. Furthermore, the proposed Markov Process approach makes it possible to leverage real-time data streams available from intelligent data acquisition systems, which are readily available in smart buildings, and merge it with physics-based and statistical models. Construction of the Markov Process naturally leads to a Markov Decision Process formulation, which describes optimal probabilistic control of a collection of similar buildings. The approach is illustrated using validated building data from Belgium.
Euclidean TSP, Motorcycle Graphs, and Other New Applications of Nearest-Neighbor Chains
Venue: arXiv cs.CG 2019
Year: 2019

We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We apply it to a diverse class of geometric problems: we construct the greedy multi-fragment tour for Euclidean TSP in $O(n\log n)$ time in any fixed dimension and for Steiner TSP in planar graphs in $O(n\sqrt{n}\log n)$ time; we compute motorcycle graphs (which are a central part in straight skeleton algorithms) in $O(n^{4/3+\varepsilon})$ time for any $\varepsilon>0$; we introduce a narcissistic variant of the $k$-attribute stable matching model, and solve it in $O(n^{2-4/(k(1+\varepsilon)+2)})$ time; we give a linear-time $2$-approximation for a 1D geometric set cover problem with applications to radio station placement.
Implementing Homomorphic Encryption Based Secure Feedback Control for Physical Systems
Venue: arXiv cs.CR 2019
Year: 2019

This paper is about an encryption based approach to the secure implementation of feedback controllers for physical systems. Specifically, Paillier's homomorphic encryption is used to digitally implement a class of linear dynamic controllers, which includes the commonplace static gain and PID type feedback control laws as special cases. The developed implementation is amenable to Field Programmable Gate Array (FPGA) realization. Experimental results, including timing analysis and resource usage characteristics for different encryption key lengths, are presented for the realization of an inverted pendulum controller; as this is an unstable plant, the control is necessarily fast.
Explaining a black-box using Deep Variational Information Bottleneck Approach
Venue: arXiv cs.LG 2019
Year: 2019

Interpretable machine learning has gained much attention recently. Briefness and comprehensiveness are necessary in order to provide a large amount of information concisely when explaining a black-box decision system. However, existing interpretable machine learning methods fail to consider briefness and comprehensiveness simultaneously, leading to redundant explanations. We propose the variational information bottleneck for interpretation, VIBI, a system-agnostic interpretable method that provides a brief but comprehensive explanation. VIBI adopts an information theoretic principle, information bottleneck principle, as a criterion for finding such explanations. For each instance, VIBI selects key features that are maximally compressed about an input (briefness), and informative about a decision made by a black-box system on that input (comprehensive). We evaluate VIBI on three datasets and compare with state-of-the-art interpretable machine learning methods in terms of both interpretability and fidelity evaluated by human and quantitative metrics
Using Conditional Generative Adversarial Networks to Generate Ground-Level Views From Overhead Imagery
Venue: arXiv cs.CV 2019
Year: 2019

This paper develops a deep-learning framework to synthesize a ground-level view of a location given an overhead image. We propose a novel conditional generative adversarial network (cGAN) in which the trained generator generates realistic looking and representative ground-level images using overhead imagery as auxiliary information. The generator is an encoder-decoder network which allows us to compare low- and high-level features as well as their concatenation for encoding the overhead imagery. We also demonstrate how our framework can be used to perform land cover classification by modifying the trained cGAN to extract features from overhead imagery. This is interesting because, although we are using this modified cGAN as a feature extractor for overhead imagery, it incorporates knowledge of how locations look from the ground.
Multi-Antenna Covert Communications in Random Wireless Networks
Venue: arXiv cs.IT 2019
Year: 2019

This paper studies multi-antenna-aided covert communications coexisting with randomly located wardens and interferers, considering both centralized and distributed antenna systems (CAS/DAS). The throughput performance of the covert communication is analyzed and optimized under a stochastic geometry framework, where the joint impact of the small-scale channel fading and the large-scale path loss is examined. To be specific, two probabilistic metrics, namely, the covert outage probability and the connectivity probability, are adopted to characterize the covertness and reliability of the transmission, respectively, and analytically tractable expressions for the two metrics are derived. The worst-case covert communication scenario is then investigated, {where the wardens invariably can maximize the covert outage probability by adjusting the detection thresholds for their detectors}. Afterwards, the optimal transmit power and transmission rate are jointly designed to maximize the covert throughput subject to a covertness constraint. Interestingly, it is found that the maximal covert throughput for both the CAS and DAS is invariant to the density of interferers and the interfering power, regardless of the number of transmit antennas. Numerical results demonstrate that the CAS outperforms the DAS in terms of the covert throughput for the random network of interest, and the throughput gap between the two systems increases dramatically when the number of transmit antennas becomes larger.
Cybercrime Investigators are Users Too! Understanding the Socio-Technical Challenges Faced by Law Enforcement
Venue: arXiv cs.HC 2019
Year: 2019

Cybercrime investigators face numerous challenges when policing online crimes. Firstly, the methods and processes they use when dealing with traditional crimes do not necessarily apply in the cyber-world. Additionally, cyber criminals are usually technologically-aware and constantly adapting and developing new tools that allow them to stay ahead of law enforcement investigations. In order to provide adequate support for cybercrime investigators, there needs to be a better understanding of the challenges they face at both technical and socio-technical levels. In this paper, we investigate this problem through an analysis of current practices and workflows of investigators. We use interviews with experts from government and private sectors who investigate cybercrimes as our main data gathering process. From an analysis of the collected data, we identify several outstanding challenges faced by investigators. These pertain to practical, technical, and social issues such as systems availability, usability, and in computer-supported collaborative work. Importantly, we use our findings to highlight research areas where user-centric workflows and tools are desirable. We also define a set of recommendations that can aid in providing a better foundation for future research in the field and allow more effective combating of cybercrimes.
Zest: REST over ZeroMQ
Venue: arXiv cs.DC 2019
Year: 2019

In this paper, we introduce Zest (REST over ZeroMQ), a middleware technology in support of an Internet of Things (IoT). Our work is influenced by the Constrained Application Protocol (CoAP) but emphasises systems that can support fine-grained access control to both resources and audit information, and can provide features such as asynchronous communication patterns between nodes. We achieve this by using a hybrid approach that combines a RESTful architecture with a variant of a publisher/subscriber topology that has enhanced routing support. The primary motivation for Zest is to provide inter-component communications in the Databox, but it is applicable in other contexts where tight control needs to be maintained over permitted communication patterns.