OpenRaiser/Intern-Atlas huggingface dataset:
Scaled VIP Algorithms for Joint Dynamic Forwarding and Caching in Named Data Networks
Venue: arXiv cs.IT 2016
Year: 2016

Emerging Information-Centric Networking (ICN) architectures seek to optimally utilize both bandwidth and storage for efficient content distribution over the network. The Virtual Interest Packet (VIP) framework has been proposed to enable joint design of forwarding and caching within the Named Data Networking (NDN) architecture. The virtual plane of the VIP framework captures the measured demand for content objects, but does not reflect interest collapse and suppression in the NDN network. We aim to further improve the performance of the existing VIP algorithms by using a modified virtual plane where VIP counts are appropriately scaled to reflect interest suppression effects. We characterize the stability region of the modified virtual plane with VIP scaling, develop a new distributed forwarding and caching algorithm operating on the scaled VIPs, and demonstrate the throughput optimality of the scaled VIP algorithm in the virtual plane. Numerical experiments demonstrate significantly enhanced performance relative to the existing VIP algorithm, as well as a number of other baseline algorithms.
Generative and Discriminative Voxel Modeling with Convolutional Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

When working with three-dimensional data, choice of representation is key. We explore voxel-based models, and present evidence for the viability of voxellated representations in applications including shape modeling and object classification. Our key contributions are methods for training voxel-based variational autoencoders, a user interface for exploring the latent space learned by the autoencoder, and a deep convolutional neural network architecture for object classification. We address challenges unique to voxel-based representations, and empirically evaluate our models on the ModelNet benchmark, where we demonstrate a 51.5% relative improvement in the state of the art for object classification.
Graph Distances and Controllability of Networks
Venue: arXiv cs.SY 2016
Year: 2016

In this technical note, we study the controllability of diffusively coupled networks from a graph theoretic perspective. We consider leader-follower networks, where the external control inputs are injected to only some of the agents, namely the leaders. Our main result relates the controllability of such systems to the graph distances between the agents. More specifically, we present a graph topological lower bound on the rank of the controllability matrix. This lower bound is tight, and it is applicable to systems with arbitrary network topologies, coupling weights, and number of leaders. An algorithm for computing the lower bound is also provided. Furthermore, as a prominent application, we present how the proposed bound can be utilized to select a minimal set of leaders for achieving controllability, even when the coupling weights are unknown.
Polynomial Representations of Threshold Functions and Algorithmic Applications
Venue: arXiv cs.DS 2016
Year: 2016

We design new polynomials for representing threshold functions in three different regimes: probabilistic polynomials of low degree, which need far less randomness than previous constructions, polynomial threshold functions (PTFs) with "nice" threshold behavior and degree almost as low as the probabilistic polynomials, and a new notion of probabilistic PTFs where we combine the above techniques to achieve even lower degree with similar "nice" threshold behavior. Utilizing these polynomial constructions, we design faster algorithms for a variety of problems: $\bullet$ Offline Hamming Nearest (and Furthest) Neighbors: Given $n$ red and $n$ blue points in $d$-dimensional Hamming space for $d=c\log n$, we can find an (exact) nearest (or furthest) blue neighbor for every red point in randomized time $n^{2-1/O(\sqrt{c}\log^{2/3}c)}$ or deterministic time $n^{2-1/O(c\log^2c)}$. These also lead to faster MAX-SAT algorithms for sparse CNFs. $\bullet$ Offline Approximate Nearest (and Furthest) Neighbors: Given $n$ red and $n$ blue points in $d$-dimensional $\ell_1$ or Euclidean space, we can find a $(1+ε)$-approximate nearest (or furthest) blue neighbor for each red point in randomized time near $dn+n^{2-Ω(ε^{1/3}/\log(1/ε))}$. $\bullet$ SAT Algorithms and Lower Bounds for Circuits With Linear Threshold Functions: We give a satisfiability algorithm for $AC^0[m]\circ LTF\circ LTF$ circuits with a subquadratic number of linear threshold gates on the bottom layer, and a subexponential number of gates on the other layers, that runs in deterministic $2^{n-n^ε}$ time. This also implies new circuit lower bounds for threshold circuits. We also give a randomized $2^{n-n^ε}$-time SAT algorithm for subexponential-size $MAJ\circ AC^0\circ LTF\circ AC^0\circ LTF$ circuits, where the top $MAJ$ gate and middle $LTF$ gates have $O(n^{6/5-δ})$ fan-in.
Topology Abstraction Service for IP VPNs: Core Network Partitioning for Resource Sharing
Venue: arXiv cs.NI 2016
Year: 2016

VPN service providers (VSP) and IP-VPN customers have traditionally maintained service demarcation boundaries between their routing and signaling entities. This has resulted in the VPNs viewing the VSP network as an opaque entity and therefore limiting any meaningful interaction between the VSP and the VPNs. A key challenge is to expose each VPN to information about available network resources through an abstraction (TA) [1] which is both accurate and fair. In [2] we proposed three decentralized schemes assuming that all the border nodes performing the abstraction have access to the entire core network topology. This assumption likely leads to over- or under-subscription. In this paper we develop centralized schemes to partition the core network capacities, and assign each partition to a specific VPN for applying the decentralized abstraction schemes presented in [2]. First, we present two schemes based on the maximum concurrent flow and the maximum multicommodity flow (MMCF) formulations. We then propose approaches to address the fairness concerns that arise when MMCF formulation is used. We present results based on extensive simulations on several topologies, and provide a comparative evaluation of the different schemes in terms of abstraction efficiency, fairness to VPNs and call performance characteristics achieved.
A Note on Markov Normalized Magnetic Eigenmaps
Venue: arXiv cs.SI 2016
Year: 2016

We note that building a magnetic Laplacian from the Markov transition matrix, rather than the graph adjacency matrix, yields several benefits for the magnetic eigenmaps algorithm. The two largest benefits are that the embedding becomes more stable as a function of the rotation parameter g, and the principal eigenvector of the magnetic Laplacian now converges to the page rank of the network as a function of diffusion time. We show empirically that this normalization improves the phase and real/imaginary embeddings of the low-frequency eigenvectors of the magnetic Laplacian.
Lecture Notes on Randomized Linear Algebra
Venue: arXiv cs.DS 2016
Year: 2016

These are lecture notes that are based on the lectures from a class I taught on the topic of Randomized Linear Algebra (RLA) at UC Berkeley during the Fall 2013 semester.
A Proposal for the Measurement and Documentation of Research Software Sustainability in Interactive Metadata Repositories
Venue: arXiv cs.SE 2016
Year: 2016

This paper proposes an interactive repository type for research software metadata which measures and documents software sustainability by accumulating metadata, and computing sustainability metrics over them. Such a repository would help to overcome technical barriers to software sustainability by furthering the discovery and identification of sustainable software, thereby also facilitating documentation of research software within the framework of software management plans.
Fast Calculation of the Knowledge Gradient for Optimization of Deterministic Engineering Simulations
Venue: arXiv cs.CE 2016
Year: 2016

A novel efficient method for computing the Knowledge-Gradient policy for Continuous Parameters (KGCP) for deterministic optimization is derived. The differences with Expected Improvement (EI), a popular choice for Bayesian optimization of deterministic engineering simulations, are explored. Both policies and the Upper Confidence Bound (UCB) policy are compared on a number of benchmark functions including a problem from structural dynamics. It is empirically shown that KGCP has similar performance as the EI policy for many problems, but has better convergence properties for complex (multi-modal) optimization problems as it emphasizes more on exploration when the model is confident about the shape of optimal regions. In addition, the relationship between Maximum Likelihood Estimation (MLE) and slice sampling for estimation of the hyperparameters of the underlying models, and the complexity of the problem at hand, is studied.
Data optimizations for constraint automata
Venue: arXiv cs.PL 2016
Year: 2016

Constraint automata (CA) constitute a coordination model based on finite automata on infinite words. Originally introduced for modeling of coordinators, an interesting new application of CAs is implementing coordinators (i.e., compiling CAs into executable code). Such an approach guarantees correctness-by-construction and can even yield code that outperforms hand-crafted code. The extent to which these two potential advantages materialize depends on the smartness of CA-compilers and the existence of proofs of their correctness. Every transition in a CA is labeled by a "data constraint" that specifies an atomic data-flow between coordinated processes as a first-order formula. At run-time, compiler-generated code must handle data constraints as efficiently as possible. In this paper, we present, and prove the correctness of two optimization techniques for CA-compilers related to handling of data constraints: a reduction to eliminate redundant variables and a translation from (declarative) data constraints to (imperative) data commands expressed in a small sequential language. Through experiments, we show that these optimization techniques can have a positive impact on performance of generated executable code.
Training Echo State Networks with Regularization through Dimensionality Reduction
Venue: arXiv cs.NE 2016
Year: 2016

In this paper we introduce a new framework to train an Echo State Network to predict real valued time-series. The method consists in projecting the output of the internal layer of the network on a space with lower dimensionality, before training the output layer to learn the target task. Notably, we enforce a regularization constraint that leads to better generalization capabilities. We evaluate the performances of our approach on several benchmark tests, using different techniques to train the readout of the network, achieving superior predictive performance when using the proposed framework. Finally, we provide an insight on the effectiveness of the implemented mechanics through a visualization of the trajectory in the phase space and relying on the methodologies of nonlinear time-series analysis. By applying our method on well known chaotic systems, we provide evidence that the lower dimensional embedding retains the dynamical properties of the underlying system better than the full-dimensional internal states of the network.
Temporally Consistent Motion Segmentation from RGB-D Video
Venue: arXiv cs.CV 2016
Year: 2016

We present a method for temporally consistent motion segmentation from RGB-D videos assuming a piecewise rigid motion model. We formulate global energies over entire RGB-D sequences in terms of the segmentation of each frame into a number of objects, and the rigid motion of each object through the sequence. We develop a novel initialization procedure that clusters feature tracks obtained from the RGB data by leveraging the depth information. We minimize the energy using a coordinate descent approach that includes novel techniques to assemble object motion hypotheses. A main benefit of our approach is that it enables us to fuse consistently labeled object segments from all RGB-D frames of an input sequence into individual 3D object reconstructions.
Study of movement coordination in human ensembles via a novel computer-based set-up
Venue: arXiv cs.HC 2016
Year: 2016

Movement coordination in human ensembles has been studied little in the current literature. In the existing experimental works, situations where all subjects are connected with each other through direct visual and auditory coupling, and social interaction affects their coordination, have been investigated. Here, we study coordination in human ensembles via a novel computer-based set-up that enables individuals to coordinate each other's motion from a distance so as to minimize the influence of social interaction. The proposed platform makes it possible to implement different visual interaction patterns among the players, so that participants take into consideration the motion of a designated subset of the others. This allows the evaluation of the exclusive effects on coordination of the structure of interconnections among the players and their own dynamics. Our set-up enables also the deployment of virtual players to investigate dyadic interaction between a human and a virtual agent, as well as group synchronization in mixed teams of human and virtual agents. We use this novel set-up to study coordination both in dyads and in groups over different structures of interconnections, with and without virtual agents. We find that, in dual interaction, virtual players manage to interact with participants in a human-like fashion, thus confirming findings in previous work. We also observe that, in group interaction, the level of coordination among humans in the absence of direct visual and auditory coupling depends on the structure of interconnections among participants. This confirms, as recently suggested in the literature, that different coordination levels are achieved over diverse visual pairings in the presence and in the absence of social interaction. We present preliminary experimental results on the effect on group coordination of deploying virtual computer agents in the human ensemble.
Adaptive Position-Based Fluids: Improving Performance of Fluid Simulations for Real-Time Applications
Venue: arXiv cs.GR 2016
Year: 2016

The Position Based Fluids (PBF) method is a state-of-the-art approach for fluid simulations in the context of real-time applications like games. It uses an iterative solver concept that tries to maintain a constant fluid density (incompressibility) to realize incompressible fluids like water. However, larger fluid volumes that consist of several hundred thousand particles (e.g. for the simulation of oceans) require many iterations and a lot of simulation power. We present a lightweight and easy-to-integrate extension to PBF that adaptively adjusts the number of solver iterations on a fine-grained basis. Using a novel adaptive-simulation approach, we are able to achieve significant improvements in performance on our evaluation scenarios while maintaining high-quality results in terms of visualization quality, which makes it a perfect choice for game developers. Furthermore, our method does not weaken the advantages of prior work and seamlessly integrates into other position-based methods for physically-based simulations.
An Efficient Character-Level Neural Machine Translation
Venue: arXiv cs.CL 2016
Year: 2016

Neural machine translation aims at building a single large neural network that can be trained to maximize translation performance. The encoder-decoder architecture with an attention mechanism achieves a translation performance comparable to the existing state-of-the-art phrase-based systems on the task of English-to-French translation. However, the use of large vocabulary becomes the bottleneck in both training and improving the performance. In this paper, we propose an efficient architecture to train a deep character-level neural machine translation by introducing a decimator and an interpolator. The decimator is used to sample the source sequence before encoding while the interpolator is used to resample after decoding. Such a deep model has two major advantages. It avoids the large vocabulary issue radically; at the same time, it is much faster and more memory-efficient in training than conventional character-based models. More interestingly, our model is able to translate the misspelled word like human beings.
Bounded Turing Reductions and Data Processing Inequalities for Sequences
Venue: arXiv cs.CC 2016
Year: 2016

A data processing inequality states that the quantity of shared information between two entities (e.g. signals, strings) cannot be significantly increased when one of the entities is processed by certain kinds of transformations. In this paper, we prove several data processing inequalities for sequences, where the transformations are bounded Turing functionals and the shared information is measured by the lower and upper mutual dimensions between sequences. We show that, for all sequences $X,Y,$ and $Z$, if $Z$ is computable Lipschitz reducible to $X$, then \[ mdim(Z:Y) \leq mdim(X:Y) \text{ and } Mdim(Z:Y) \leq Mdim(X:Y). \] We also show how to derive different data processing inequalities by making adjustments to the computable bounds of the use of a Turing functional. The yield of a Turing functional $Φ^S$ with access to at most $n$ bits of the oracle $S$ is the smallest input $m \in \mathbb{N}$ such that $Φ^{S \upharpoonright n}(m)\uparrow$. We show how to derive reverse data processing inequalities (i.e., data processing inequalities where the transformation may significantly increase the shared information between two entities) for sequences by applying computable bounds to the yield of a Turing functional.
Compact and Fast Sensitivity Oracles for Single-Source Distances
Venue: arXiv cs.DS 2016
Year: 2016

Let $s$ denote a distinguished source vertex of a non-negatively real weighted and undirected graph $G$ with $n$ vertices and $m$ edges. In this paper we present two efficient \emph{single-source approximate-distance sensitivity oracles}, namely \emph{compact} data structures which are able to \emph{quickly} report an approximate (by a multiplicative stretch factor) distance from $s$ to any node of $G$ following the failure of any edge in $G$. More precisely, we first present a sensitivity oracle of size $O(n)$ which is able to report 2-approximate distances from the source in $O(1)$ time. Then, we further develop our construction by building, for any $0<ε<1$, another sensitivity oracle having size $O\left(n\cdot \frac{1}ε \log \frac{1}ε\right)$, and which is able to report a $(1+ε)$-approximate distance from $s$ to any vertex of $G$ in $O\left(\log n\cdot \frac{1}ε \log \frac{1}ε\right)$ time. Thus, this latter oracle is essentially optimal as far as size and stretch are concerned, and it only asks for a logarithmic query time. Finally, our results are complemented with a space lower bound for the related class of single-source \emph{additively-stretched} sensitivity oracles, which is helpful to realize the hardness of designing compact oracles of this type.
Self-Assembly of Shapes at Constant Scale using Repulsive Forces
Venue: arXiv cs.CG 2016
Year: 2016

The algorithmic self-assembly of shapes has been considered in several models of self-assembly. For the problem of \emph{shape construction}, we consider an extended version of the Two-Handed Tile Assembly Model (2HAM), which contains positive (attractive) and negative (repulsive) interactions. As a result, portions of an assembly can become unstable and detach. In this model, we utilize fuel-efficient computation to perform Turing machine simulations for the construction of the shape. In this paper, we show how an arbitrary shape can be constructed using an asymptotically optimal number of distinct tile types (based on the shape's Kolmogorov complexity). We achieve this at $O(1)$ scale factor in this straightforward model, whereas all previous results with sublinear scale factors utilize powerful self-assembly models containing features such as staging, tile deletion, chemical reaction networks, and tile activation/deactivation. Furthermore, the computation and construction in our result only creates constant-size garbage assemblies as a byproduct of assembling the shape.
Lecture Notes on Spectral Graph Methods
Venue: arXiv cs.DS 2016
Year: 2016

These are lecture notes that are based on the lectures from a class I taught on the topic of Spectral Graph Methods at UC Berkeley during the Spring 2015 semester.
Approximating the Chromatic Polynomial
Venue: arXiv cs.DM 2016
Year: 2016

Chromatic polynomials are important objects in graph theory and statistical physics, but as a result of computational difficulties, their study is limited to graphs that are small, highly structured, or very sparse. We have devised and implemented two algorithms that approximate the coefficients of the chromatic polynomial $P(G,x)$, where $P(G,k)$ is the number of proper $k$-colorings of a graph $G$ for $k\in\mathbb{N}$. Our algorithm is based on a method of Knuth that estimates the order of a search tree. We compare our results to the true chromatic polynomial in several known cases, and compare our error with previous approximation algorithms.
Opaque Response Generation Enabling Automatic Creation of Virtual Services for Service Virtualisation
Venue: arXiv cs.SE 2016
Year: 2016

Service virtualisation is a method to create virtual service models that can mimic interaction behaviors between a system under test and the target system. With service virtualisation, the development team can get access to the production-like conditions whenever and however many times they need, enabling frequent and comprehensive testing. Previous techniques for service virtualisation have relied on explicitly modelling the target services by a service expert and require detailed knowledge of message protocol and structure. However, neither of these are necessarily available. In this thesis, we introduce our novel opaque response generation approach. This approach enables services to be virtualised automatically without any expert knowledge or documentation of system protocol and interaction behaviours. Given a collection of interactions exchanged between a system under test and a target real service, our approach can 1) organise the same type of interactions into the same cluster and derive a cluster prototype for each cluster; 2) search a given incoming request for its the most similar request in the interaction library; 3) learn knowledge from the incoming request and the recorded interaction; and 4) generate a response. A framework and proof-of-concept implementation of our opaque response generation approach is described. Experimental results show our opaque response generation approach is able to automatically generate accurate responses in real time with an accuracy rate over 99% on average.
Reinforcement Learning algorithms for regret minimization in structured Markov Decision Processes
Venue: arXiv cs.LG 2016
Year: 2016

A recent goal in the Reinforcement Learning (RL) framework is to choose a sequence of actions or a policy to maximize the reward collected or minimize the regret incurred in a finite time horizon. For several RL problems in operation research and optimal control, the optimal policy of the underlying Markov Decision Process (MDP) is characterized by a known structure. The current state of the art algorithms do not utilize this known structure of the optimal policy while minimizing regret. In this work, we develop new RL algorithms that exploit the structure of the optimal policy to minimize regret. Numerical experiments on MDPs with structured optimal policies show that our algorithms have better performance, are easy to implement, have a smaller run-time and require less number of random number generations.