OpenRaiser/Intern-Atlas huggingface dataset:
Maximum Rooted Connected Expansion
Venue: arXiv cs.DS 2018
Year: 2018

Prefetching constitutes a valuable tool toward efficient Web surfing. As a result, estimating the amount of resources that need to be preloaded during a surfer's browsing becomes an important task. In this regard, prefetching can be modeled as a two-player combinatorial game [Fomin et al., Theoretical Computer Science 2014], where a surfer and a marker alternately play on a given graph (representing the Web graph). During its turn, the marker chooses a set of $k$ nodes to mark (prefetch), whereas the surfer, represented as a token resting on graph nodes, moves to a neighboring node (Web resource). The surfer's objective is to reach an unmarked node before all nodes become marked and the marker wins. Intuitively, since the surfer is step-by-step traversing a subset of nodes in the Web graph, a satisfactory prefetching procedure would load in cache all resources lying in the neighborhood of this growing subset. Motivated by the above, we consider the following problem to which we refer to as the Maximum Rooted Connected Expansion (MRCE) problem. Given a graph $G$ and a root node $v_0$, we wish to find a subset of vertices $S$ such that $S$ is connected, $S$ contains $v_0$ and the ratio $|N[S]|/|S|$ is maximized, where $N[S]$ denotes the closed neighborhood of $S$, that is, $N[S]$ contains all nodes in $S$ and all nodes with at least one neighbor in $S$. We prove that the problem is NP-hard even when the input graph $G$ is restricted to be a split graph. On the positive side, we demonstrate a polynomial time approximation scheme for split graphs. Furthermore, we present a $\frac{1}{6}(1-\frac{1}{e})$-approximation algorithm for general graphs based on techniques for the Budgeted Connected Domination problem [Khuller et al., SODA 2014]. Finally, we provide a polynomial-time algorithm for the special case of interval graphs.
Convex LMI optimization for the uncertain power flow analysis
Venue: arXiv cs.SY 2018
Year: 2018

This paper investigates the uncertain power flow analysis in distribution networks within the context of renewable power resources integration such as wind and solar power. The analysis aims to bound the worst-case voltage magnitude in any node of the network for a given uncertain power generation scenario. The major difficulty of this problem is the non-linear aspect of power flow equations. The proposed approach does not require the linearization of these equations and formulates the problem as an optimization problem with polynomial constraints. A new tool to investigate the feasibility of such problems is presented and it is obtained as an extension of the $\mathcal{S}-$procedure, a fundamental result in robustness analysis. A solution to the uncertain power flow analysis problem is proposed using this new tool. The different obtained results of this paper are expressed as LMI optimization problems which guaranties an efficient numerical resolution as it will be demonstrated through an illustrative example.
How Do Static and Dynamic Test Case Prioritization Techniques Perform on Modern Software Systems? An Extensive Study on GitHub Projects
Venue: arXiv cs.SE 2018
Year: 2018

Test Case Prioritization (TCP) is an increasingly important regression testing technique for reordering test cases according to a pre-defined goal, particularly as agile practices gain adoption. To better understand these techniques, we perform the first extensive study aimed at empirically evaluating four static TCP techniques, comparing them with state-of-research dynamic TCP techniques across several quality metrics. This study was performed on 58 real-word Java programs encompassing 714 KLoC and results in several notable observations. First, our results across two effectiveness metrics (the Average Percentage of Faults Detected APFD and the cost cognizant APFDc) illustrate that at test-class granularity, these metrics tend to correlate, but this correlation does not hold at test-method granularity. Second, our analysis shows that static techniques can be surprisingly effective, particularly when measured by APFDc. Third, we found that TCP techniques tend to perform better on larger programs, but that program size does not affect comparative performance measures between techniques. Fourth, software evolution does not significantly impact comparative performance results between TCP techniques. Fifth, neither the number nor type of mutants utilized dramatically impact measures of TCP effectiveness under typical experimental settings. Finally, our similarity analysis illustrates that highly prioritized test cases tend to uncover dissimilar faults.
CFENet: An Accurate and Efficient Single-Shot Object Detector for Autonomous Driving
Venue: arXiv cs.CV 2018
Year: 2018

The ability to detect small objects and the speed of the object detector are very important for the application of autonomous driving, and in this paper, we propose an effective yet efficient one-stage detector, which gained the second place in the Road Object Detection competition of CVPR2018 workshop - Workshop of Autonomous Driving(WAD). The proposed detector inherits the architecture of SSD and introduces a novel Comprehensive Feature Enhancement(CFE) module into it. Experimental results on this competition dataset as well as the MSCOCO dataset demonstrate that the proposed detector (named CFENet) performs much better than the original SSD and the state-of-the-art method RefineDet especially for small objects, while keeping high efficiency close to the original SSD. Specifically, the single scale version of the proposed detector can run at the speed of 21 fps, while the multi-scale version with larger input size achieves the mAP 29.69, ranking second on the leaderboard
A Multi-Modal Chinese Poetry Generation Model
Venue: arXiv cs.CL 2018
Year: 2018

Recent studies in sequence-to-sequence learning demonstrate that RNN encoder-decoder structure can successfully generate Chinese poetry. However, existing methods can only generate poetry with a given first line or user's intent theme. In this paper, we proposed a three-stage multi-modal Chinese poetry generation approach. Given a picture, the first line, the title and the other lines of the poem are successively generated in three stages. According to the characteristics of Chinese poems, we propose a hierarchy-attention seq2seq model which can effectively capture character, phrase, and sentence information between contexts and improve the symmetry delivered in poems. In addition, the Latent Dirichlet allocation (LDA) model is utilized for title generation and improve the relevance of the whole poem and the title. Compared with strong baseline, the experimental results demonstrate the effectiveness of our approach, using machine evaluations as well as human judgments.
Beyond Worst-Case Analysis
Venue: arXiv cs.DS 2018
Year: 2018

In the worst-case analysis of algorithms, the overall performance of an algorithm is summarized by its worst performance on any input. This approach has countless success stories, but there are also important computational problems --- like linear programming, clustering, online caching, and neural network training --- where the worst-case analysis framework does not provide any helpful advice on how to solve the problem. This article covers a number of modeling methods for going beyond worst-case analysis and articulating which inputs are the most relevant.
Linear Tree Constraints
Venue: arXiv cs.LO 2018
Year: 2018

Linear tree constraints were introduced by Hofmann and Rodriguez in the context of amortized resource analysis for object oriented programs. More precisely, they gave a reduction from inference of resource types to constraint solving. Thus, once we have found an algorithm to solve the constraints generated from a program, we can read off the resource consumption from their solutions. These constraints have the form of pointwise linear inequalities between infinite trees labeled with nonnegative rational numbers. We are interested in the question if a system of such constraints is simultaneously satisfiable. Bauer and Hofmann have recently identified a fragment of the tree constraint problem (UTC) that is still sufficient for program analysis and they proved that the list case of UTC is decidable, whereas the case with trees of degree at least two remained open. In this paper, we solve this problem. We give a decision procedure that covers the entire range of constraints needed for resource analysis.
Unveiling the semantic structure of text documents using paragraph-aware Topic Models
Venue: arXiv cs.CL 2018
Year: 2018

Classic Topic Models are built under the Bag Of Words assumption, in which word position is ignored for simplicity. Besides, symmetric priors are typically used in most applications. In order to easily learn topics with different properties among the same corpus, we propose a new line of work in which the paragraph structure is exploited. Our proposal is based on the following assumption: in many text document corpora there are formal constraints shared across all the collection, e.g. sections. When this assumption is satisfied, some paragraphs may be related to general concepts shared by all documents in the corpus, while others would contain the genuine description of documents. Assuming each paragraph can be semantically more general, specific, or hybrid, we look for ways to measure this, transferring this distinction to topics and being able to learn what we call specific and general topics. Experiments show that this is a proper methodology to highlight certain paragraphs in structured documents at the same time we learn interesting and more diverse topics.
System Design in the Era of IoT --- Meeting the Autonomy Challenge
Venue: arXiv cs.SY 2018
Year: 2018

The advent of IoT is a great opportunity to reinvigorate Computing by focusing on autonomous system design. This certainly raises technology questions but, more importantly, it requires building new foundation that will systematically integrate the innovative results needed to face increasing environment and mission complexity. A key idea is to compensate the lack of human intervention by adaptive control. This is instrumental for system resilience: it allows both coping with uncertainty and managing mixed criticality services. Our proposal for knowledge-based design seeks a compromise: preserving rigorousness despite the fact that essential properties cannot be guaranteed at design time. It makes knowledge generation and application a primary concern and aims to fully and seamlessly incorporate the adaptive control paradigm in system architecture.
The Communication Cost of Information Spreading in Dynamic Networks
Venue: arXiv cs.DC 2018
Year: 2018

This paper investigates the message complexity of distributed information spreading (a.k.a gossip or token dissemination) in adversarial dynamic networks, where the goal is to spread $k$ tokens of information to every node on an $n$-node network. We consider the amortized (average) message complexity of spreading a token, assuming that the number of tokens is large. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying, and forwarding them. We consider two types of adversaries that arbitrarily rewire the network while keeping it connected: the adaptive adversary that is aware of the status of all the nodes and the algorithm (including the current random choices), and the oblivious adversary that is oblivious to the random choices made by the algorithm. The central question that motivates our work is whether one can achieve subquadratic amortized message complexity for information spreading. We present two sets of results depending on how nodes send messages to their neighbors: (1) Local broadcast: We show a tight lower bound of $Ω(n^2)$ on the number of amortized local broadcasts, which is matched by the naive flooding algorithm, (2) Unicast: We study the message complexity as a function of the number of dynamic changes in the network. To facilitate this, we introduce a natural complexity measure for analyzing dynamic networks called adversary-competitive message complexity where the adversary pays a unit cost for every topological change. Under this model, it is shown that if $k$ is sufficiently large, we can obtain an optimal amortized message complexity of $O(n)$. We also present a randomized algorithm that achieves subquadratic amortized message complexity when the number of tokens is not large under an oblivious adversary.
Verification of Shared-Reading Synchronisers
Venue: arXiv cs.SE 2018
Year: 2018

Synchronisation classes are an important building block for shared memory concurrent programs. Thus to reason about such programs, it is important to be able to verify the implementation of these synchronisation classes, considering atomic operations as the synchronisation primitives on which the implementations are built. For synchronisation classes controlling exclusive access to a shared resource, such as locks, a technique has been proposed to reason about their behaviour. This paper proposes a technique to verify implementations of both exclusive access and shared-reading synchronisers. We use permission-based Separation Logic to describe the behaviour of the main atomic operations, and the basis for our technique is formed by a specification for class AtomicInteger, which is commonly used to implement synchronisation classes in java.util.concurrent. To demonstrate the applicability of our approach, we mechanically verify the implementation of various synchronisation classes like Semaphore, CountDownLatch and Lock.
New extension constructions of optimal frequency hopping sequence sets
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, a general framework of constructing optimal frequency hopping sequence (FHS) sets is presented based on the designated direct product. Under the framework, we obtain infinitely many new optimal FHS sets by combining a family of sequences that are newly constructed in this paper with some known optimal FHS sets. Our constructions of optimal FHS sets are also based on extension method. However, our constructions remove the constraint requiring that the extension factor is co-prime with the length of original FHSs and get new parameters. In literature, most of the extension constructions suffer from this constraint. As a result, our constructions allow a great flexibility of choosing parameters of FHS sets for a given frequency-hopping spread spectrum system.
Kolmogorov $n$-widths for linear dynamical systems
Venue: arXiv cs.SY 2018
Year: 2018

Kolmogorov $n$-widths and Hankel singular values are two commonly used concepts in model reduction. Here we show that for the special case of linear time-invariant dynamical (LTI) systems, these two concepts are directly connected. More specifically, the greedy search applied to the Hankel operator of an LTI system resembles the minimizing subspace for the Kolmogorov n-width and the Kolmogorov $n$-width of an LTI system equals its $(n+1)st$ Hankel singular value once the subspaces are appropriately defined. We also establish a lower bound for the Kolmorogov $n$-width for parametric LTI systems and illustrate that the method of active subspaces can be viewed as the dual concept to the minimizing subspace for the Kolmogorov $n$-width.
Tangent-Space Regularization for Neural-Network Models of Dynamical Systems
Venue: arXiv cs.LG 2018
Year: 2018

This work introduces the concept of tangent space regularization for neural-network models of dynamical systems. The tangent space to the dynamics function of many physical systems of interest in control applications exhibits useful properties, e.g., smoothness, motivating regularization of the model Jacobian along system trajectories using assumptions on the tangent space of the dynamics. Without assumptions, large amounts of training data are required for a neural network to learn the full non-linear dynamics without overfitting. We compare different network architectures on one-step prediction and simulation performance and investigate the propensity of different architectures to learn models with correct input-output Jacobian. Furthermore, the influence of $L_2$ weight regularization on the learned Jacobian eigenvalue spectrum, and hence system stability, is investigated.
Complexity Results for Preference Aggregation over (m)CP-nets: Pareto and Majority Voting
Venue: arXiv cs.AI 2018
Year: 2018

Combinatorial preference aggregation has many applications in AI. Given the exponential nature of these preferences, compact representations are needed and ($m$)CP-nets are among the most studied ones. Sequential and global voting are two ways to aggregate preferences over CP-nets. In the former, preferences are aggregated feature-by-feature. Hence, when preferences have specific feature dependencies, sequential voting may exhibit voting paradoxes, i.e., it might select sub-optimal outcomes. To avoid paradoxes in sequential voting, one has often assumed the $\mathcal{O}$-legality restriction, which imposes a shared topological order among all the CP-nets. On the contrary, in global voting, CP-nets are considered as a whole during preference aggregation. For this reason, global voting is immune from paradoxes, and there is no need to impose restrictions over the CP-nets' topological structure. Sequential voting over $\mathcal{O}$-legal CP-nets has extensively been investigated. On the other hand, global voting over non-$\mathcal{O}$-legal CP-nets has not carefully been analyzed, despite it was stated in the literature that a theoretical comparison between global and sequential voting was promising and a precise complexity analysis for global voting has been asked for multiple times. In quite few works, very partial results on the complexity of global voting over CP-nets have been given. We start to fill this gap by carrying out a thorough complexity analysis of Pareto and majority global voting over not necessarily $\mathcal{O}$-legal acyclic binary polynomially connected (m)CP-nets. We settle these problems in the polynomial hierarchy, and some of them in PTIME or LOGSPACE, whereas EXPTIME was the previously known upper bound for most of them. We show various tight lower bounds and matching upper bounds for problems that up to date did not have any explicit non-obvious lower bound.
Deictic Image Maps: An Abstraction For Learning Pose Invariant Manipulation Policies
Venue: arXiv cs.RO 2018
Year: 2018

In applications of deep reinforcement learning to robotics, it is often the case that we want to learn pose invariant policies: policies that are invariant to changes in the position and orientation of objects in the world. For example, consider a peg-in-hole insertion task. If the agent learns to insert a peg into one hole, we would like that policy to generalize to holes presented in different poses. Unfortunately, this is a challenge using conventional methods. This paper proposes a novel state and action abstraction that is invariant to pose shifts called \textit{deictic image maps} that can be used with deep reinforcement learning. We provide broad conditions under which optimal abstract policies are optimal for the underlying system. Finally, we show that the method can help solve challenging robotic manipulation problems.
Adaptive Blending Units: Trainable Activation Functions for Deep Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

The most widely used activation functions in current deep feed-forward neural networks are rectified linear units (ReLU), and many alternatives have been successfully applied, as well. However, none of the alternatives have managed to consistently outperform the rest and there is no unified theory connecting properties of the task and network with properties of activation functions for most efficient training. A possible solution is to have the network learn its preferred activation functions. In this work, we introduce Adaptive Blending Units (ABUs), a trainable linear combination of a set of activation functions. Since ABUs learn the shape, as well as the overall scaling of the activation function, we also analyze the effects of adaptive scaling in common activation functions. We experimentally demonstrate advantages of both adaptive scaling and ABUs over common activation functions across a set of systematically varied network specifications. We further show that adaptive scaling works by mitigating covariate shifts during training, and that the observed advantages in performance of ABUs likewise rely largely on the activation function's ability to adapt over the course of training.
Towards a Logic for Reasoning About LF Specifications
Venue: arXiv cs.LO 2018
Year: 2018

We describe the development of a logic for reasoning about specifications in the Edinburgh Logical Framework (LF). In this logic, typing judgments in LF serve as atomic formulas, and quantification is permitted over contexts and terms that might appear in them. Further, contexts, which constitute type assignments to uniquely named variables that are modeled using the technical device of nominal constants, can be characterized via an inductive description of their structure. We present a semantics for such formulas and then consider the task of proving them. Towards this end, we restrict the collection of formulas we consider so as to ensure that they have normal forms upon which proof rules may be based. We then specifically discuss a proof rule that provides the basis for case analysis over LF typing judgments; this rule is the most complex and innovative one in the collection. We illustrate the proof system through an example. Finally, we discuss ongoing work and we relate our project to existing systems that have a similar goal.
Hierarchical Coded Computation
Venue: arXiv cs.IT 2018
Year: 2018

Coded computation is a method to mitigate "stragglers" in distributed computing systems through the use of error correction coding that has lately received significant attention. First used in vector-matrix multiplication, the range of application was later extended to include matrix-matrix multiplication, heterogeneous networks, convolution, and approximate computing. A drawback to previous results is they completely ignore work completed by stragglers. While stragglers are slower compute nodes, in many settings the amount of work completed by stragglers can be non-negligible. Thus, in this work, we propose a hierarchical coded computation method that exploits the work completed by all compute nodes. We partition each node's computation into layers of sub-computations such that each layer can be treated as (distinct) erasure channel. We then design different erasure codes for each layer so that all layers have the same failure exponent. We propose design guidelines to optimize parameters of such codes. Numerical results show the proposed scheme has an improvement of a factor of 1.5 in the expected finishing time compared to previous work.