OpenRaiser/Intern-Atlas huggingface dataset:
Three-Phase Dynamic Simulation of Power Systems Using Combined Transmission and Distribution System Models
Venue: arXiv cs.SY 2016
Year: 2016

This paper presents a new method for studying electromechanical transients in power systems using three phase, combined transmission and distribution models (hybrid models). The methodology models individual phases of an electric network and associated unbalance in load and generation. Therefore, the impacts of load unbalance, single phase distributed generation and line impedance unbalance on electromechanical transients can be studied without using electromagnetic transient simulation (EMTP) programs. The implementation of this methodology in software is called the Three Phase Dynamics Analyzer (TPDA). Case studies included in the paper demonstrate the accuracy of TPDA and its ability to simulate electromechanical transients in hybrid models. TPDA has the potential for providing electric utilities and power system planners with more accurate assessment of system stability than traditional dynamic simulation software that assume balanced network topology.
Simulation Algorithms with Exponential Integration for Time-Domain Analysis of Large-Scale Power Delivery Networks
Venue: arXiv cs.CE 2016
Year: 2016

We design an algorithmic framework using matrix exponentials for time-domain simulation of power delivery network (PDN). Our framework can reuse factorized matrices to simulate the large-scale linear PDN system with variable stepsizes. In contrast, current conventional PDN simulation solvers have to use fixed step-size approach in order to reuse factorized matrices generated by the expensive matrix decomposition. Based on the proposed exponential integration framework, we design a PDN solver R-MATEX with the flexible time-stepping capability. The key operation of matrix exponential and vector product (MEVP) is computed by the rational Krylov subspace method. To further improve the runtime, we also propose a distributed computing framework DR-MATEX. DR-MATEX reduces Krylov subspace generations caused by frequent breakpoints from a large number of current sources during simulation. By virtue of the superposition property of linear system and scaling invariance property of Krylov subspace, DR-MATEX can divide the whole simulation task into subtasks based on the alignments of breakpoints among those sources. The subtasks are processed in parallel at different computing nodes without any communication during the computation of transient simulation. The final result is obtained by summing up the partial results among all the computing nodes after they finish the assigned subtasks. Therefore, our computation model belongs to the category known as Embarrassingly Parallel model. Experimental results show R-MATEX and DR-MATEX can achieve up to around 14.4X and 98.0X runtime speedups over traditional trapezoidal integration based solver with fixed timestep approach.
Sequential Dimensionality Reduction for Extracting Localized Features
Venue: arXiv cs.CV 2016
Year: 2016

Linear dimensionality reduction techniques are powerful tools for image analysis as they allow the identification of important features in a data set. In particular, nonnegative matrix factorization (NMF) has become very popular as it is able to extract sparse, localized and easily interpretable features by imposing an additive combination of nonnegative basis elements. Nonnegative matrix underapproximation (NMU) is a closely related technique that has the advantage to identify features sequentially. In this paper, we propose a variant of NMU that is particularly well suited for image analysis as it incorporates the spatial information, that is, it takes into account the fact that neighboring pixels are more likely to be contained in the same features, and favors the extraction of localized features by looking for sparse basis elements. We show that our new approach competes favorably with comparable state-of-the-art techniques on synthetic, facial and hyperspectral image data sets.
A survey on Information Visualization in light of Vision and Cognitive sciences
Venue: arXiv cs.GR 2016
Year: 2016

Information Visualization techniques are built on a context with many factors related to both vision and cognition, making it difficult to draw a clear picture of how data visually turns into comprehension. In the intent of promoting a better picture, here, we survey concepts on vision, cognition, and Information Visualization organized in a theorization named Visual Expression Process. Our theorization organizes the basis of visualization techniques with a reduced level of complexity; still, it is complete enough to foster discussions related to design and analytical tasks. Our work introduces the following contributions: (1) a Theoretical compilation of vision, cognition, and Information Visualization; (2) Discussions supported by vast literature; and (3) Reflections on visual-cognitive aspects concerning use and design. We expect our contributions will provide further clarification about how users and designers think about InfoVis, leveraging the potential of systems and techniques.
Duality Preserving Gray Maps for Codes over Rings
Venue: arXiv cs.IT 2016
Year: 2016

Given a finite ring $A$ which is a free left module over a subring $R$ of $A$, two types of $R$-bases, pseudo-self-dual bases (similar to trace orthogonal bases) and symmetric bases, are defined which in turn are used to define duality preserving maps from codes over $A$ to codes over $R$. Both types of bases are generalizations of similar concepts for fields. Many illustrative examples are given to shed light on the advantages to such mappings as well as their abundance.
A characterization of b-chromatic and partial Grundy numbers by induced subgraphs
Venue: arXiv cs.DM 2016
Year: 2016

Gy{á}rf{á}s et al. and Zaker have proven that the Grundy number of a graph $G$ satisfies $Γ(G)\ge t$ if and only if $G$ contains an induced subgraph called a $t$-atom.The family of $t$-atoms has bounded order and contains a finite number of graphs.In this article, we introduce equivalents of $t$-atoms for b-coloring and partial Grundy coloring.This concept is used to prove that determining if $φ(G)\ge t$ and $\partialΓ(G)\ge t$ (under conditions for the b-coloring), for a graph $G$, is in XP with parameter $t$.We illustrate the utility of the concept of $t$-atoms by giving results on b-critical vertices and edges, on b-perfect graphs and on graphs of girth at least $7$.
Amplification and DRDoS Attack Defense -- A Survey and New Perspectives
Venue: arXiv cs.NI 2016
Year: 2016

The severity of amplification attacks has grown in recent years. Since 2013 there have been at least two attacks which involved over 300Gbps of attack traffic. This paper offers an analysis of these and many other amplification attacks. We compare a wide selection of different proposals for detecting and preventing amplification attacks, as well as proposals for tracing the attackers. Since source IP spoofing plays an important part in almost all of the attacks mentioned, a survey on the state of the art in spoofing defenses is also presented. This work acts as an introduction into amplification attacks and source IP address spoofing. By combining previous works into a single comprehensive bibliography, and with our concise discussion, we hope to prevent redundant work and encourage others to find practical solutions for defending against future amplification attacks.
Personalizing Universal Recurrent Neural Network Language Model with User Characteristic Features by Social Network Crowdsouring
Venue: arXiv cs.CL 2016
Year: 2016

With the popularity of mobile devices, personalized speech recognizer becomes more realizable today and highly attractive. Each mobile device is primarily used by a single user, so it's possible to have a personalized recognizer well matching to the characteristics of individual user. Although acoustic model personalization has been investigated for decades, much less work have been reported on personalizing language model, probably because of the difficulties in collecting enough personalized corpora. Previous work used the corpora collected from social networks to solve the problem, but constructing a personalized model for each user is troublesome. In this paper, we propose a universal recurrent neural network language model with user characteristic features, so all users share the same model, except each with different user characteristic features. These user characteristic features can be obtained by crowdsouring over social networks, which include huge quantity of texts posted by users with known friend relationships, who may share some subject topics and wording patterns. The preliminary experiments on Facebook corpus showed that this proposed approach not only drastically reduced the model perplexity, but offered very good improvement in recognition accuracy in n-best rescoring tests. This approach also mitigated the data sparseness problem for personalized language models.
Defending against malicious peripherals with Cinch
Venue: arXiv cs.OS 2016
Year: 2016

Malicious peripherals designed to attack their host computers are a growing problem. Inexpensive and powerful peripherals that attach to plug-and-play buses have made such attacks easy to mount. Making matters worse, commodity operating systems lack coherent defenses, and users are often unaware of the scope of the problem. We present Cinch, a pragmatic response to this threat. Cinch uses virtualization to attach peripheral devices to a logically separate, untrusted machine, and includes an interposition layer between the untrusted machine and the protected one. This layer regulates interaction with devices according to user-configured policies. Cinch integrates with existing OSes, enforces policies that thwart real-world attacks, and has low overhead.
Polynomial-time Algorithm for Isomorphism of Graphs with Clique-width at most Three
Venue: arXiv cs.CC 2016
Year: 2016

The clique-width is a measure of complexity of decomposing graphs into certain tree-like structures. The class of graphs with bounded clique-width contains bounded tree-width graphs. We give a polynomial time graph isomorphism algorithm for graphs with clique-width at most three. Our work is independent of the work by Grohe et al. \cite{grohe2015isomorphism} showing that the isomorphism problem for graphs of bounded clique-width is polynomial time.
Index problems for game automata
Venue: arXiv cs.FL 2016
Year: 2016

For a given regular language of infinite trees, one can ask about the minimal number of priorities needed to recognize this language with a non-deterministic, alternating, or weak alternating parity automaton. These questions are known as, respectively, the non-deterministic, alternating, and weak Rabin-Mostowski index problems. Whether they can be answered effectively is a long-standing open problem, solved so far only for languages recognizable by deterministic automata (the alternating variant trivializes). We investigate a wider class of regular languages, recognizable by so-called game automata, which can be seen as the closure of deterministic ones under complementation and composition. Game automata are known to recognize languages arbitrarily high in the alternating Rabin-Mostowski index hierarchy; that is, the alternating index problem does not trivialize any more. Our main contribution is that all three index problems are decidable for languages recognizable by game automata. Additionally, we show that it is decidable whether a given regular language can be recognized by a game automaton.
Forgery-Resistant Touch-based Authentication on Mobile Devices
Venue: arXiv cs.CR 2016
Year: 2016

Mobile devices store a diverse set of private user data and have gradually become a hub to control users' other personal Internet-of-Things devices. Access control on mobile devices is therefore highly important. The widely accepted solution is to protect access by asking for a password. However, password authentication is tedious, e.g., a user needs to input a password every time she wants to use the device. Moreover, existing biometrics such as face, fingerprint, and touch behaviors are vulnerable to forgery attacks. We propose a new touch-based biometric authentication system that is passive and secure against forgery attacks. In our touch-based authentication, a user's touch behaviors are a function of some random "secret". The user can subconsciously know the secret while touching the device's screen. However, an attacker cannot know the secret at the time of attack, which makes it challenging to perform forgery attacks even if the attacker has already obtained the user's touch behaviors. We evaluate our touch-based authentication system by collecting data from 25 subjects. Results are promising: the random secrets do not influence user experience and, for targeted forgery attacks, our system achieves 0.18 smaller Equal Error Rates (EERs) than previous touch-based authentication.
On the Feasibility of Wireless Energy Transfer Using Massive Antenna Arrays
Venue: arXiv cs.IT 2016
Year: 2016

We illustrate potential benefits of using massive antenna arrays for wireless energy transfer (WET). Specifically, we analyze probability of outage in WET over fading channels when a base station (BS) with multiple antennas beamforms energy to a wireless sensor node (WSN). Our analytical results show that by using massive antenna arrays, the range of WET can be increased for a given target outage probability. We prove that by using multiple-antenna arrays at the BS, a lower downlink energy is required to get the same outage performance, resulting into savings of radiated energy. We show that for energy levels used in WET, the outage performance with least-squares or minimum mean-square error channel estimates is same as that obtained based on perfect channel estimates. We observe that a strong line-of-sight component between the BS and WSN lowers outage probability. Furthermore, by deploying more antennas at the BS, a larger energy can be transferred reliably to the WSN at a given target outage performance for the sensor to be able to perform its main tasks. In our numerical examples, the RF power received at the input of the sensor is assumed to be on the order of a mW, such that the rectenna operates at an efficiency in the order of 50 %.
Approximate Message Passing Algorithm with Universal Denoising and Gaussian Mixture Learning
Venue: arXiv cs.IT 2016
Year: 2016

We study compressed sensing (CS) signal reconstruction problems where an input signal is measured via matrix multiplication under additive white Gaussian noise. Our signals are assumed to be stationary and ergodic, but the input statistics are unknown; the goal is to provide reconstruction algorithms that are universal to the input statistics. We present a novel algorithmic framework that combines: (i) the approximate message passing (AMP) CS reconstruction framework, which solves the matrix channel recovery problem by iterative scalar channel denoising; (ii) a universal denoising scheme based on context quantization, which partitions the stationary ergodic signal denoising into independent and identically distributed (i.i.d.) subsequence denoising; and (iii) a density estimation approach that approximates the probability distribution of an i.i.d. sequence by fitting a Gaussian mixture (GM) model. In addition to the algorithmic framework, we provide three contributions: (i) numerical results showing that state evolution holds for non-separable Bayesian sliding-window denoisers; (ii) an i.i.d. denoiser based on a modified GM learning algorithm; and (iii) a universal denoiser that does not need information about the range where the input takes values from or require the input signal to be bounded. We provide two implementations of our universal CS recovery algorithm with one being faster and the other being more accurate. The two implementations compare favorably with existing universal reconstruction algorithms in terms of both reconstruction quality and runtime.
On the Groupoid Model of Computational Paths
Venue: arXiv cs.LO 2016
Year: 2016

The main objective of this work is to study mathematical properties of computational paths. Originally proposed by de Queiroz \& Gabbay (1994) as `sequences or rewrites', computational paths are taken to be terms of the identity type of Martin Löf's Intensional Type Theory, since these paths can be seen as the grounds on which the propositional equality between two computational objects stand. From this perspective, this work aims to show that one of the properties of the identity type is present on computational paths. We are referring to the fact that that the identity type induces a groupoid structure, as proposed by Hofmann \& Streicher (1994). Using categorical semantics, we show that computational paths induce a groupoid structure. We also show that computational paths are capable of inducing higher categorical structures.
Deep SimNets
Venue: arXiv cs.NE 2016
Year: 2016

We present a deep layered architecture that generalizes convolutional neural networks (ConvNets). The architecture, called SimNets, is driven by two operators: (i) a similarity function that generalizes inner-product, and (ii) a log-mean-exp function called MEX that generalizes maximum and average. The two operators applied in succession give rise to a standard neuron but in "feature space". The feature spaces realized by SimNets depend on the choice of the similarity operator. The simplest setting, which corresponds to a convolution, realizes the feature space of the Exponential kernel, while other settings realize feature spaces of more powerful kernels (Generalized Gaussian, which includes as special cases RBF and Laplacian), or even dynamically learned feature spaces (Generalized Multiple Kernel Learning). As a result, the SimNet contains a higher abstraction level compared to a traditional ConvNet. We argue that enhanced expressiveness is important when the networks are small due to run-time constraints (such as those imposed by mobile applications). Empirical evaluation validates the superior expressiveness of SimNets, showing a significant gain in accuracy over ConvNets when computational resources at run-time are limited. We also show that in large-scale settings, where computational complexity is less of a concern, the additional capacity of SimNets can be controlled with proper regularization, yielding accuracies comparable to state of the art ConvNets.
Remarks on the Most Informative Function Conjecture at fixed mean
Venue: arXiv cs.IT 2016
Year: 2016

In 2013, Courtade and Kumar posed the following problem: Let $\boldsymbol{x} \sim \{\pm 1\}^n$ be uniformly random, and form $\boldsymbol{y} \sim \{\pm 1\}^n$ by negating each bit of $\boldsymbol{x}$ independently with probability $α$. Is it true that the mutual information $I(f(\boldsymbol{x}) \mathbin{;} \boldsymbol{y})$ is maximized among $f:\{\pm 1\}^n \to \{\pm 1\}$ by $f(x) = x_1$? We do not resolve this problem. Instead, we make a couple of observations about the fixed-mean version of the conjecture. We show that Courtade and Kumar's stronger Lex Conjecture fails for small noise rates. We also prove a continuous version of the conjecture on the sphere and show that it implies the previously-known analogue for Gaussian space.
Strong Successive Refinability and Rate-Distortion-Complexity Tradeoff
Venue: arXiv cs.IT 2016
Year: 2016

We investigate the second order asymptotics (source dispersion) of the successive refinement problem. Similarly to the classical definition of a successively refinable source, we say that a source is strongly successively refinable if successive refinement coding can achieve the second order optimum rate (including the dispersion terms) at both decoders. We establish a sufficient condition for strong successive refinability. We show that any discrete source under Hamming distortion and the Gaussian source under quadratic distortion are strongly successively refinable. We also demonstrate how successive refinement ideas can be used in point-to-point lossy compression problems in order to reduce complexity. We give two examples, the binary-Hamming and Gaussian-quadratic cases, in which a layered code construction results in a low complexity scheme that attains optimal performance. For example, when the number of layers grows with the block length $n$, we show how to design an $O(n^{\log(n)})$ algorithm that asymptotically achieves the rate-distortion bound.
Combinatorial topology of the standard chromatic subdivision and Weak Symmetry Breaking for 6 processes
Venue: arXiv cs.DC 2016
Year: 2016

In this paper we study a family of discrete configuration spaces, the so-called protocol complexes, which are of utmost importance in theoretical distributed computing. Specifically, we consider questions of the existance of compliant binary labelings on the vertices of iterated standard chromatic subdivisions of an n-simplex. The existance of such labelings is equivalent to the existance of distributed protocols solving Weak Symmetry Breaking task in the standard computational model. As a part of our formal model, we introduce function sb(n), defined for natural numbers n, called the symmetry breaking function. From the geometric point of view sb(n) denotes the minimal number of iterations of the standard chromatic subdivision of an (n-1)-simplex, which is needed for the compliant binary labeling to exist. From the point of distributed computing, the function sb(n) measures the minimal number of rounds in a protocol solving the Weak Symmetry Breaking task. In addition to the development of combinatorial topology, which is applicable in a broader context, our main contribution is the proof of new bounds for the function sb(n). Accordingly, the bulk of the paper is taken up by in-depth analysis of the structure of adjacency graph on the set of n-simplices in iterated standard chromatic subdivision of an n-simplex. On the algorithmic side, we provide the first distributed protocol solving Weak Symmetry Breaking task in the layered immediate snapshot computational model for some number of processes. It is well known, that the smallest number of processes for which Weak Symmetry Breaking task is solvable is 6. Based on our analysis, we are able to find a very fast explicit protocol, solving the Weak Symmetry Breaking for 6 processes using only 3 rounds. Furthermore, we show that no protocol can solve Weak Symmetry Breaking in fewer than 2 rounds.
Approximation Algorithm for the Binary-Preference Capacitated Selfish Replication Game and a Tight Bound on its Price of Anarchy
Venue: arXiv cs.GT 2016
Year: 2016

We consider the capacitated selfish replication (CSR) game with binary preferences, over general undirected networks. We first show that such games have an associated ordinary potential function, and hence always admit a pure-strategy Nash equilibrium (NE). Further, when the minimum degree of the network and the number of resources are of the same order, there exists an exact polynomial time algorithm which can find a NE. Following this, we study the price of anarchy of such games, and show that it is bounded above by 3; we further provide some instances for which the price of anarchy is at least 2. We develop a quasi-polynomial algorithm O(n^2D^{ln n}), where n is the number of players and D is the diameter of the network, which can find, in a distributed manner, an allocation profile that is within a constant factor of the optimal allocation, and hence of any pure-strategy NE of the game. Proof of this result uses a novel potential function.