OpenRaiser/Intern-Atlas huggingface dataset:
On the Approximation Ratio of Ordered Parsings
Venue: arXiv cs.DS 2019
Year: 2019

Shannon's entropy is a clear lower bound for statistical compression. The situation is not so well understood for dictionary-based compression. A plausible lower bound is $b$, the least number of phrases of a general bidirectional parse of a text, where phrases can be copied from anywhere else in the text. Since computing $b$ is NP-complete, a popular gold standard is $z$, the number of phrases in the Lempel-Ziv parse of the text, which is the optimal one when phrases can be copied only from the left. While $z$ can be computed in linear time with a greedy algorithm, almost nothing has been known for decades about its approximation ratio with respect to $b$. In this paper we prove that $z=O(b\log(n/b))$, where $n$ is the text length. We also show that the bound is tight as a function of $n$, by exhibiting a text family where $z = Ω(b\log n)$. Our upper bound is obtained by building a run-length context-free grammar based on a locally consistent parsing of the text. Our lower bound is obtained by relating $b$ with $r$, the number of equal-letter runs in the Burrows-Wheeler transform of the text. We proceed by observing that Lempel-Ziv is just one particular case of greedy parses, meaning that the optimal value of $z$ is obtained by scanning the text and maximizing the phrase length at each step, and of ordered parses, meaning that there is an increasing order between phrases and their sources. As a new example of ordered greedy parses, we introduce {\em lexicographical} parses, where phrases can only be copied from lexicographically smaller text locations. We prove that the size $v$ of the optimal lexicographical parse is also obtained greedily in $O(n)$ time, that $v=O(b\log(n/b))$, and that there exists a text family where $v = Ω(b\log n)$.
An Empirical Study of Fault Localization Families and Their Combinations
Venue: arXiv cs.SE 2019
Year: 2019

The performance of fault localization techniques is critical to their adoption in practice. This paper reports on an empirical study of a wide range of fault localization techniques on real-world faults. Different from previous studies, this paper (1) considers a wide range of techniques from different families, (2) combines different techniques, and (3) considers the execution time of different techniques. Our results reveal that a combined technique significantly outperforms any individual technique (200% increase in faults localized in Top 1), suggesting that combination may be a desirable way to apply fault localization techniques and that future techniques should also be evaluated in the combined setting. Our implementation is publicly available for evaluating and combining fault localization techniques.
HDM-Net: Monocular Non-Rigid 3D Reconstruction with Learned Deformation Model
Venue: arXiv cs.CV 2019
Year: 2019

Monocular dense 3D reconstruction of deformable objects is a hard ill-posed problem in computer vision. Current techniques either require dense correspondences and rely on motion and deformation cues, or assume a highly accurate reconstruction (referred to as a template) of at least a single frame given in advance and operate in the manner of non-rigid tracking. Accurate computation of dense point tracks often requires multiple frames and might be computationally expensive. Availability of a template is a very strong prior which restricts system operation to a pre-defined environment and scenarios. In this work, we propose a new hybrid approach for monocular non-rigid reconstruction which we call Hybrid Deformation Model Network (HDM-Net). In our approach, deformation model is learned by a deep neural network, with a combination of domain-specific loss functions. We train the network with multiple states of a non-rigidly deforming structure with a known shape at rest. HDM-Net learns different reconstruction cues including texture-dependent surface deformations, shading and contours. We show generalisability of HDM-Net to states not presented in the training dataset, with unseen textures and under new illumination conditions. Experiments with noisy data and a comparison with other methods demonstrate robustness and accuracy of the proposed approach and suggest possible application scenarios of the new technique in interventional diagnostics and augmented reality.
On the Control of Agents Coupled through Shared Unit-demand Resources
Venue: arXiv cs.SY 2019
Year: 2019

We consider a control problem involving several agents coupled through multiple unit-demand resources. Such resources are indivisible, and each agent's consumption is modeled as a Bernoulli random variable. Controlling the number of such agents in a probabilistic manner, subject to capacity constraints, is ubiquitous in smart cities. For instance, such agents can be humans in a feedback loop---who respond to a price signal, or automated decision-support systems that strive toward system-level goals. In this paper, we consider both single feedback loop corresponding to a single resource and multiple coupled feedback loops corresponding to multiple resources consumed by the same population of agents. For example, when a network of devices allocates resources to deliver several services, these services are coupled through capacity constraints on the resources. We propose a new algorithm with fundamental guarantees of convergence and optimality, as well as present an example illustrating its performance.
Capturing Polynomial Time using Modular Decomposition
Venue: arXiv cs.CC 2019
Year: 2019

The question of whether there is a logic that captures polynomial time is one of the main open problems in descriptive complexity theory and database theory. In 2010 Grohe showed that fixed point logic with counting captures polynomial time on all classes of graphs with excluded minors. We now consider classes of graphs with excluded induced subgraphs. For such graph classes, an effective graph decomposition, called modular decomposition, was introduced by Gallai in 1976. The graphs that are non-decomposable with respect to modular decomposition are called prime. We present a tool, the Modular Decomposition Theorem, that reduces (definable) canonization of a graph class C to (definable) canonization of the class of prime graphs of C that are colored with binary relations on a linearly ordered set. By an application of the Modular Decomposition Theorem, we show that fixed point logic with counting captures polynomial time on the class of permutation graphs. Within the proof of the Modular Decomposition Theorem, we show that the modular decomposition of a graph is definable in symmetric transitive closure logic with counting. We obtain that the modular decomposition tree is computable in logarithmic space. It follows that cograph recognition and cograph canonization is computable in logarithmic space.
Real-time Progressive 3D Semantic Segmentation for Indoor Scene
Venue: arXiv cs.CV 2019
Year: 2019

The widespread adoption of autonomous systems such as drones and assistant robots has created a need for real-time high-quality semantic scene segmentation. In this paper, we propose an efficient yet robust technique for on-the-fly dense reconstruction and semantic segmentation of 3D indoor scenes. To guarantee (near) real-time performance, our method is built atop an efficient super-voxel clustering method and a conditional random field with higher-order constraints from structural and object cues, enabling progressive dense semantic segmentation without any precomputation. We extensively evaluate our method on different indoor scenes including kitchens, offices, and bedrooms in the SceneNN and ScanNet datasets and show that our technique consistently produces state-of-the-art segmentation results in both qualitative and quantitative experiments.
Revisiting Skip-Gram Negative Sampling Model with Rectification
Venue: arXiv cs.CL 2019
Year: 2019

We revisit skip-gram negative sampling (SGNS), one of the most popular neural-network based approaches to learning distributed word representation. We first point out the ambiguity issue undermining the SGNS model, in the sense that the word vectors can be entirely distorted without changing the objective value. To resolve the issue, we investigate the intrinsic structures in solution that a good word embedding model should deliver. Motivated by this, we rectify the SGNS model with quadratic regularization, and show that this simple modification suffices to structure the solution in the desired manner. A theoretical justification is presented, which provides novel insights into quadratic regularization . Preliminary experiments are also conducted on Google's analytical reasoning task to support the modified SGNS model.
Towards Scaling Blockchain Systems via Sharding
Venue: arXiv cs.DC 2019
Year: 2019

Existing blockchain systems scale poorly because of their distributed consensus protocols. Current attempts at improving blockchain scalability are limited to cryptocurrency. Scaling blockchain systems under general workloads (i.e., non-cryptocurrency applications) remains an open question. In this work, we take a principled approach to apply sharding, which is a well-studied and proven technique to scale out databases, to blockchain systems in order to improve their transaction throughput at scale. This is challenging, however, due to the fundamental difference in failure models between databases and blockchain. To achieve our goal, we first enhance the performance of Byzantine consensus protocols, by doing so we improve individual shards' throughput. Next, we design an efficient shard formation protocol that leverages a trusted random beacon to securely assign nodes into shards. We rely on trusted hardware, namely Intel SGX, to achieve high performance for both consensus and shard formation protocol. Third, we design a general distributed transaction protocol that ensures safety and liveness even when transaction coordinators are malicious. Finally, we conduct an extensive evaluation of our design both on a local cluster and on Google Cloud Platform. The results show that our consensus and shard formation protocols outperform state-of-the-art solutions at scale. More importantly, our sharded blockchain reaches a high throughput that can handle Visa-level workloads, and is the largest ever reported in a realistic environment.
Maximal Ferrers Diagram Codes: Constructions and Genericity Considerations
Venue: arXiv cs.IT 2019
Year: 2019

This paper investigates the construction of rank-metric codes with specified Ferrers diagram shapes. These codes play a role in the multilevel construction for subspace codes. A conjecture from 2009 provides an upper bound for the dimension of a rank-metric code with given specified Ferrers diagram shape and rank distance. While the conjecture in its generality is wide open, several cases have been established in the literature. This paper contributes further cases of Ferrers diagrams and ranks for which the conjecture holds true. In addition, the proportion of maximal Ferrers diagram codes within the space of all rank-metric codes with the same shape and dimension is investigated. Special attention is being paid to MRD codes. It is shown that for growing field size the limiting proportion depends highly on the Ferrers diagram. For instance, for $[m\times 2]$-MRD codes with rank~$2$ this limiting proportion is close to $1/e$.
Development and Validation of the Japanese Moral Foundations Dictionary
Venue: arXiv cs.CY 2019
Year: 2019

The Moral Foundations Dictionary (MFD) is a useful tool for applying the conceptual framework developed in Moral Foundations Theory and quantifying the moral meanings implicated in the linguistic information people convey. However, the applicability of the MFD is limited because it is available only in English. Translated versions of the MFD are therefore needed to study morality across various cultures, including non-Western cultures. The contribution of this paper is two-fold. We developed the first Japanese version of the MFD (referred to as the J-MFD) by introducing a semi-automated method---this serves as a reference when translating the MFD into other languages. We next tested the validity of the J-MFD by analyzing open-ended written texts about the situations that Japanese participants thought followed and violated the five moral foundations. We found that the J-MFD correctly categorized the Japanese participants' descriptions into the corresponding moral foundations, and that the Moral Foundations Questionnaire (MFQ) scores were correlated with the frequency of situations, of total words, and of J-MFD words in the participants' descriptions for the Harm and Fairness foundations. The J-MFD can be used to study morality unique to the Japanese and cultural differences in moral behavior.
Survey of Communication Protocols for Internet-of-Things and Related Challenges of Fog and Cloud Computing Integration
Venue: arXiv cs.NI 2019
Year: 2019

The fast increment in the number of IoT (Internet of Things) devices is accelerating the research on new solutions to make cloud services scalable. In this context, the novel concept of fog computing as well as the combined fog-to-cloud computing paradigm is becoming essential to decentralize the cloud, while bringing the services closer to the end-system. This paper surveys on the application layer communication protocols to fulfil the IoT communication requirements, and their potential for implementation in fog- and cloud-based IoT systems. To this end, the paper first presents a comparative analysis of the main characteristics of IoT communication protocols, including request-reply and publish-subscribe protocols. After that, the paper surveys the protocols that are widely adopted and implemented in each segment of the system (IoT, fog, cloud), and thus opens up the discussion on their interoperability and wider system integration. Finally, the paper reviews the main performance issues, including latency, energy consumption and network throughput. The survey is expected to be useful to system architects and protocol designers when choosing the communication protocols in an integrated IoT-to-fog-to-cloud system architecture.
Mobility-Aware Coded Storage and Delivery
Venue: arXiv cs.IT 2019
Year: 2019

Content caching at small-cell base stations (SBSs) is a promising method to mitigate the excessive backhaul load and delay, particularly for on-demand video streaming applications. A cache-enabled heterogeneous cellular network architecture is considered in this paper, where mobile users connect to multiple SBSs during a video downloading session, and the SBSs request files, or fragments of files, from the macro-cell base station (MBS) according to the user requests they receive. A novel coded storage and delivery scheme is introduced to reduce the load on the backhaul link from the MBS to the SBSs. The achievable backhaul delivery rate as well as the number of sub-files required to achieve this rate are studied for the proposed coded delivery scheme, and it is shown that the proposed scheme provides significant reduction in the number of sub-files required, making it more viable for practical applications.
A Subquadratic Approximation Scheme for Partition
Venue: arXiv cs.DS 2019
Year: 2019

The subject of this paper is the time complexity of approximating Knapsack, Subset Sum, Partition, and some other related problems. The main result is an $\widetilde{O}(n+1/\varepsilon^{5/3})$ time randomized FPTAS for Partition, which is derived from a certain relaxed form of a randomized FPTAS for Subset Sum. To the best of our knowledge, this is the first NP-hard problem that has been shown to admit a subquadratic time approximation scheme, i.e., one with time complexity of $O((n+1/\varepsilon)^{2-δ})$ for some $δ>0$. To put these developments in context, note that a quadratic FPTAS for \partition has been known for 40 years. Our main contribution lies in designing a mechanism that reduces an instance of Subset Sum to several simpler instances, each with some special structure, and keeps track of interactions between them. This allows us to combine techniques from approximation algorithms, pseudo-polynomial algorithms, and additive combinatorics. We also prove several related results. Notably, we improve approximation schemes for 3SUM, (min,+)-convolution, and Tree Sparsity. Finally, we argue why breaking the quadratic barrier for approximate Knapsack is unlikely by giving an $Ω((n+1/\varepsilon)^{2-o(1)})$ conditional lower bound.
From Regular Expression Matching to Parsing
Venue: arXiv cs.DS 2019
Year: 2019

Given a regular expression $R$ and a string $Q$, the regular expression parsing problem is to determine if $Q$ matches $R$ and if so, determine how it matches, e.g., by a mapping of the characters of $Q$ to the characters in $R$. Regular expression parsing makes finding matches of a regular expression even more useful by allowing us to directly extract subpatterns of the match, e.g., for extracting IP-addresses from internet traffic analysis or extracting subparts of genomes from genetic data bases. We present a new general techniques for efficiently converting a large class of algorithms that determine if a string $Q$ matches regular expression $R$ into algorithms that can construct a corresponding mapping. As a consequence, we obtain the first efficient linear space solutions for regular expression parsing.
HyperDense-Net: A hyper-densely connected CNN for multi-modal image segmentation
Venue: arXiv cs.CV 2019
Year: 2019

Recently, dense connections have attracted substantial attention in computer vision because they facilitate gradient flow and implicit deep supervision during training. Particularly, DenseNet, which connects each layer to every other layer in a feed-forward fashion, has shown impressive performances in natural image classification tasks. We propose HyperDenseNet, a 3D fully convolutional neural network that extends the definition of dense connectivity to multi-modal segmentation problems. Each imaging modality has a path, and dense connections occur not only between the pairs of layers within the same path, but also between those across different paths. This contrasts with the existing multi-modal CNN approaches, in which modeling several modalities relies entirely on a single joint layer (or level of abstraction) for fusion, typically either at the input or at the output of the network. Therefore, the proposed network has total freedom to learn more complex combinations between the modalities, within and in-between all the levels of abstraction, which increases significantly the learning representation. We report extensive evaluations over two different and highly competitive multi-modal brain tissue segmentation challenges, iSEG 2017 and MRBrainS 2013, with the former focusing on 6-month infant data and the latter on adult images. HyperDenseNet yielded significant improvements over many state-of-the-art segmentation networks, ranking at the top on both benchmarks. We further provide a comprehensive experimental analysis of features re-use, which confirms the importance of hyper-dense connections in multi-modal representation learning. Our code is publicly available at https://www.github.com/josedolz/HyperDenseNet.
User Scheduling for Millimeter Wave Hybrid Beamforming Systems with Low-Resolution ADCs
Venue: arXiv cs.IT 2019
Year: 2019

We investigate uplink user scheduling for millimeter wave (mmWave) hybrid analog/digital beamforming systems with low-resolution analog-to-digital converters (ADCs). Deriving new scheduling criteria for the mmWave systems, we show that the channel structure in the beamspace, in addition to the channel magnitude and orthogonality, plays a key role in maximizing the achievable rates of scheduled users due to quantization error. The criteria show that to maximize the achievable rate for a given channel gain, the channels of the scheduled users need to have (1) as many propagation paths as possible with unique angle-of-arrivals (AoAs) and (2) even power distribution in the beamspace. Leveraging the derived criteria, we propose an efficient scheduling algorithm for mmWave zero-forcing receivers with low-resolution ADCs. We further propose a chordal distance-based scheduling algorithm that exploits only the AoA knowledge and analyze the performance by deriving ergodic rates in closed form. Based on the derived rates, we show that the beamspace channel leakage resulting from phase offsets between AoAs and quantized angles of analog combiners can lead to sum rate gain by reducing quantization error compared to the channel without leakage. Simulation results validate the sum rate performance of the proposed algorithms and derived ergodic rates expressions.
Dynamic Set Cover: Improved Algorithms & Lower Bounds
Venue: arXiv cs.DS 2019
Year: 2019

We give new upper and lower bounds for the {\em dynamic} set cover problem. First, we give a $(1+ε) f$-approximation for fully dynamic set cover in $O(f^2\log n /ε^5)$ (amortized) update time, for any $ε> 0$, where $f$ is the maximum number of sets that an element belongs to. In the decremental setting, the update time can be improved to $O(f^2/ε^5)$, while still obtaining an $(1+ε) f$-approximation. These are the first algorithms that obtain an approximation factor linear in $f$ for dynamic set cover, thereby almost matching the best bounds known in the offline setting and improving upon the previous best approximation of $O(f^2)$ in the dynamic setting. To complement our upper bounds, we also show that a linear dependence of the update time on $f$ is necessary unless we can tolerate much worse approximation factors. Using the recent distributed PCP-framework, we show that any dynamic set cover algorithm that has an amortized update time of $O(f^{1-ε})$ must have an approximation factor that is $Ω(n^δ)$ for some constant $δ>0$ under the Strong Exponential Time Hypothesis.
Ubiquitous Cell-Free Massive MIMO Communications
Venue: arXiv cs.IT 2019
Year: 2019

Since the first cellular networks were trialled in the 1970s, we have witnessed an incredible wireless revolution. From 1G to 4G, the massive traffic growth has been managed by a combination of wider bandwidths, refined radio interfaces, and network densification, namely increasing the number of antennas per site. Due its cost-efficiency, the latter has contributed the most. Massive MIMO (multiple-input multiple-output) is a key 5G technology that uses massive antenna arrays to provide a very high beamforming gain and spatially multiplexing of users, and hence, increases the spectral and energy efficiency. It constitutes a centralized solution to densify a network, and its performance is limited by the inter-cell interference inherent in its cell-centric design. Conversely, ubiquitous cell-free Massive MIMO refers to a distributed Massive MIMO system implementing coherent user-centric transmission to overcome the inter-cell interference limitation in cellular networks and provide additional macro-diversity. These features, combined with the system scalability inherent in the Massive MIMO design, distinguishes ubiquitous cell-free Massive MIMO from prior coordinated distributed wireless systems. In this article, we investigate the enormous potential of this promising technology while addressing practical deployment issues to deal with the increased back/front-hauling overhead deriving from the signal co-processing.
Computing quasiconformal folds
Venue: arXiv cs.CG 2019
Year: 2019

We propose a novel way of computing surface folding maps via solving a linear PDE. This framework is a generalization to the existing quasiconformal methods and allows manipulation of the geometry of folding. Moreover, the crucial quantity that characterizes the geometry occurs as the coefficient of the equation, namely the Beltrami coefficient. This allows us to solve an inverse problem of parametrizing the folded surface given only partial data but with known folding topology. Various interesting applications such as fold sculpting on 3D models and self-occlusion reasoning are demonstrated to show the effectiveness of our method.