OpenRaiser/Intern-Atlas huggingface dataset:
Taverna Mobile: Taverna workflows on Android
Venue: arXiv cs.SE 2015
Year: 2015

Researchers are often on the move, say at conferences or projects meetings, and as workflows are becoming ubiquitous in the scientific process, having access to scientific workflows from a mobile device would be a significant advantage. We therefore have developed Taverna Mobile, an application for Android phones which allows browsing of existing workflows, executing them, and reviewing the results. Taverna Mobile does not aim to reproduce the full experience of building workflows in the Taverna Workbench, rather it focuses on tasks we have deemed relevant to a scientist that is not at her desk. For instance, when visiting a conference she might hear about someone's workflow, which she can quickly locate and mark for later exploration. When in the biology lab, faced with updated scientific data, the scientist can rerun her own workflow with new inputs. While commuting, she can monitor the status of a long-running job.
Improved Parallel Algorithms for Spanners and Hopsets
Venue: arXiv cs.DS 2015
Year: 2015

We use exponential start time clustering to design faster and more work-efficient parallel graph algorithms involving distances. Previous algorithms usually rely on graph decomposition routines with strict restrictions on the diameters of the decomposed pieces. We weaken these bounds in favor of stronger local probabilistic guarantees. This allows more direct analyses of the overall process, giving: * Linear work parallel algorithms that construct spanners with $O(k)$ stretch and size $O(n^{1+1/k})$ in unweighted graphs, and size $O(n^{1+1/k} \log k)$ in weighted graphs. * Hopsets that lead to the first parallel algorithm for approximating shortest paths in undirected graphs with $O(m\;\mathrm{polylog}\;n)$ work.
Performance Analysis of Massive MIMO for Cell-Boundary Users
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider massive multiple-input multiple-output (MIMO) systems for both downlink and uplink scenarios, where three radio units (RUs) connected via one digital unit (DU) support multiple user equipments (UEs) at the cell-boundary through the same radio resource, i.e., the same time-frequency slot. For downlink transmitter options, the study considers zero-forcing (ZF) and maximum ratio transmission (MRT), while for uplink receiver options it considers ZF and maximum ratio combining (MRC). For the sum rate of each of these, we derive simple closed-form formulas. In the simple but practically relevant case where uniform power is allocated to all downlink data streams, we observe that, for the downlink, vector normalization is better for ZF while matrix normalization is better for MRT. For a given antenna and user configuration, we also derive analytically the signal-to-noise-ratio (SNR) level below which MRC should be used instead of ZF. Numerical simulations confirm our analytical results.
Second-Order Asymptotics for the Gaussian MAC with Degraded Message Sets
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies the second-order asymptotics of the Gaussian multiple-access channel with degraded message sets. For a fixed average error probability $\varepsilon \in (0,1)$ and an arbitrary point on the boundary of the capacity region, we characterize the speed of convergence of rate pairs that converge to that boundary point for codes that have asymptotic error probability no larger than $\varepsilon$. As a stepping stone to this local notion of second-order asymptotics, we study a global notion, and establish relationships between the two. We provide a numerical example to illustrate how the angle of approach to a boundary point affects the second-order coding rate. This is the first conclusive characterization of the second-order asymptotics of a network information theory problem in which the capacity region is not a polygon.
Partial Sums Computation In Polar Codes Decoding
Venue: arXiv cs.AR 2015
Year: 2015

Polar codes are the first error-correcting codes to provably achieve the channel capacity but with infinite codelengths. For finite codelengths the existing decoder architectures are limited in working frequency by the partial sums computation unit. We explain in this paper how the partial sums computation can be seen as a matrix multiplication. Then, an efficient hardware implementation of this product is investigated. It has reduced logic resources and interconnections. Formalized architectures, to compute partial sums and to generate the bits of the generator matrix k^n, are presented. The proposed architecture allows removing the multiplexing resources used to assigned to each processing elements the required partial sums.
An Extreme Learning Machine Approach to Predicting Near Chaotic HCCI Combustion Phasing in Real-Time
Venue: arXiv cs.LG 2015
Year: 2015

Fuel efficient Homogeneous Charge Compression Ignition (HCCI) engine combustion timing predictions must contend with non-linear chemistry, non-linear physics, period doubling bifurcation(s), turbulent mixing, model parameters that can drift day-to-day, and air-fuel mixture state information that cannot typically be resolved on a cycle-to-cycle basis, especially during transients. In previous work, an abstract cycle-to-cycle mapping function coupled with $ε$-Support Vector Regression was shown to predict experimentally observed cycle-to-cycle combustion timing over a wide range of engine conditions, despite some of the aforementioned difficulties. The main limitation of the previous approach was that a partially acausual randomly sampled training dataset was used to train proof of concept offline predictions. The objective of this paper is to address this limitation by proposing a new online adaptive Extreme Learning Machine (ELM) extension named Weighted Ring-ELM. This extension enables fully causal combustion timing predictions at randomly chosen engine set points, and is shown to achieve results that are as good as or better than the previous offline method. The broader objective of this approach is to enable a new class of real-time model predictive control strategies for high variability HCCI and, ultimately, to bring HCCI's low engine-out NOx and reduced CO2 emissions to production engines.
Message Authentication Code over a Wiretap Channel
Venue: arXiv cs.IT 2015
Year: 2015

Message Authentication Code (MAC) is a keyed function $f_K$ such that when Alice, who shares the secret $K$ with Bob, sends $f_K(M)$ to the latter, Bob will be assured of the integrity and authenticity of $M$. Traditionally, it is assumed that the channel is noiseless. However, Maurer showed that in this case an attacker can succeed with probability $2^{-\frac{H(K)}{\ell+1}}$ after authenticating $\ell$ messages. In this paper, we consider the setting where the channel is noisy. Specifically, Alice and Bob are connected by a discrete memoryless channel (DMC) $W_1$ and a noiseless but insecure channel. In addition, an attacker Oscar is connected with Alice through DMC $W_2$ and with Bob through a noiseless channel. In this setting, we study the framework that sends $M$ over the noiseless channel and the traditional MAC $f_K(M)$ over channel $(W_1, W_2)$. We regard the noisy channel as an expensive resource and define the authentication rate $ρ_{auth}$ as the ratio of message length to the number $n$ of channel $W_1$ uses. The security of this framework depends on the channel coding scheme for $f_K(M)$. A natural coding scheme is to use the secrecy capacity achieving code of Csiszár and Körner. Intuitively, this is also the optimal strategy. However, we propose a coding scheme that achieves a higher $ρ_{auth}.$ Our crucial point for this is that in the secrecy capacity setting, Bob needs to recover $f_K(M)$ while in our coding scheme this is not necessary. How to detect the attack without recovering $f_K(M)$ is the main contribution of this work. We achieve this through random coding techniques.
Linear tree codes and the problem of explicit constructions
Venue: arXiv cs.IT 2015
Year: 2015

We reduce the problem of constructing asymptotically good tree codes to the construction of triangular totally nonsingular matrices over fields with polynomially many elements. We show a connection of this problem to Birkhoff interpolation in finite fields.
Extended Formulations for Online Linear Bandit Optimization
Venue: arXiv cs.LG 2015
Year: 2015

On-line linear optimization on combinatorial action sets (d-dimensional actions) with bandit feedback, is known to have complexity in the order of the dimension of the problem. The exponential weighted strategy achieves the best known regret bound that is of the order of $d^{2}\sqrt{n}$ (where $d$ is the dimension of the problem, $n$ is the time horizon). However, such strategies are provably suboptimal or computationally inefficient. The complexity is attributed to the combinatorial structure of the action set and the dearth of efficient exploration strategies of the set. Mirror descent with entropic regularization function comes close to solving this problem by enforcing a meticulous projection of weights with an inherent boundary condition. Entropic regularization in mirror descent is the only known way of achieving a logarithmic dependence on the dimension. Here, we argue otherwise and recover the original intuition of exponential weighting by borrowing a technique from discrete optimization and approximation algorithms called `extended formulation'. Such formulations appeal to the underlying geometry of the set with a guaranteed logarithmic dependence on the dimension underpinned by an information theoretic entropic analysis.
On conformal divergences and their population minimizers
Venue: arXiv cs.IT 2015
Year: 2015

Total Bregman divergences are a recent tweak of ordinary Bregman divergences originally motivated by applications that required invariance by rotations. They have displayed superior results compared to ordinary Bregman divergences on several clustering, computer vision, medical imaging and machine learning tasks. These preliminary results raise two important problems : First, report a complete characterization of the left and right population minimizers for this class of total Bregman divergences. Second, characterize a principled superset of total and ordinary Bregman divergences with good clustering properties, from which one could tailor the choice of a divergence to a particular application. In this paper, we provide and study one such superset with interesting geometric features, that we call conformal divergences, and focus on their left and right population minimizers. Our results are obtained in a recently coined $(u, v)$-geometric structure that is a generalization of the dually flat affine connections in information geometry. We characterize both analytically and geometrically the population minimizers. We prove that conformal divergences (resp. total Bregman divergences) are essentially exhaustive for their left (resp. right) population minimizers. We further report new results and extend previous results on the robustness to outliers of the left and right population minimizers, and discuss the role of the $(u, v)$-geometric structure in clustering. Additional results are also given.
Analysis of Load Balancing in Large Heterogeneous Processor Sharing Systems
Venue: arXiv cs.DC 2015
Year: 2015

We analyze randomized dynamic load balancing schemes for multi-server processor sharing systems when the number of servers in the system is large and the servers have heterogeneous service rates. In particular, we focus on the classical power-of-two load balancing scheme and a variant of it in which a newly arrived job is assigned to the server having the least instantaneous Lagrange shadow cost among two randomly chosen servers. The instantaneous Lagrange shadow cost at a server is given by the ratio of the number of unfinished jobs at the server to the capacity of the server. Two different approaches of analysis are presented for each scheme. For exponential job length distribution, the analysis is done using the mean field approach and for more general job length distributions the analysis is carried out assuming an asymptotic independence property. Analytical expressions to compute mean sojourn time of jobs are found for both schemes. Asymptotic insensitivity of the schemes to the type of job length distribution is established. Numerical results are presented to validate the theoretical results and to show that, unlike the homogeneous scenario, the power-of-two type schemes considered in this paper may not always result in better behaviour in terms of the mean sojourn time of jobs.
Compact families of Jordan curves and convex hulls in three dimensions
Venue: arXiv cs.CG 2015
Year: 2015

We prove that for certain families of semi-algebraic convex bodies in 3 dimensions, the convex hull of $n$ disjoint bodies has $O(nλ_s(n))$ features, where $s$ is a constant depending on the family: $λ_s(n)$ is the maximum length of order-$s$ Davenport-Schinzel sequences with $n$ letters. The argument is based on an apparently new idea of `compact families' of convex bodies or discs, and of `crossing content' of disc intersections.
Online Algorithms with Advice for Bin Packing and Scheduling Problems
Venue: arXiv cs.DS 2015
Year: 2015

We consider the setting of online computation with advice, and study the bin packing problem and a number of scheduling problems. We show that it is possible, for any of these problems, to arbitrarily approach a competitive ratio of $1$ with only a constant number of bits of advice per request. For the bin packing problem, we give an online algorithm with advice that is $(1+\varepsilon)$-competitive and uses $O\left(\frac{1}{\varepsilon}\log \frac{1}{\varepsilon} \right)$ bits of advice per request. For scheduling on $m$ identical machines, with the objective function of any of makespan, machine covering and the minimization of the $\ell_p$ norm, $p >1$, we give similar results. We give online algorithms with advice which are $(1+\varepsilon)$-competitive ($(1/(1-\varepsilon))$-competitive for machine covering) and also use $O\left(\frac{1}{\varepsilon}\log \frac{1}{\varepsilon} \right)$ bits of advice per request. We complement our results by giving a lower bound showing that for any online algorithm with advice to be optimal, for any of the above scheduling problems, a non-constant number (namely, at least $\left(1 - \frac{2m}{n}\right)\log m$, where $n$ is the number of jobs and $m$ is the number of machines) of bits of advice per request is needed.
On Strong Centerpoints
Venue: arXiv cs.CG 2015
Year: 2015

Let $P$ be a set of $n$ points in $\mathbb{R}^d$ and $\mathcal{F}$ be a family of geometric objects. We call a point $x \in P$ a strong centerpoint of $P$ w.r.t $\mathcal{F}$ if $x$ is contained in all $F \in \mathcal{F}$ that contains more than $cn$ points from $P$, where $c$ is a fixed constant. A strong centerpoint does not exist even when $\mathcal{F}$ is the family of halfspaces in the plane. We prove the existence of strong centerpoints with exact constants for convex polytopes defined by a fixed set of orientations. We also prove the existence of strong centerpoints for abstract set systems with bounded intersection.
Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
Venue: arXiv cs.IT 2015
Year: 2015

We study the behavior of Approximate Message-Passing, a solver for linear sparse estimation problems such as compressed sensing, when the i.i.d matrices -for which it has been specifically designed- are replaced by structured operators, such as Fourier and Hadamard ones. We show empirically that after proper randomization, the structure of the operators does not significantly affect the performances of the solver. Furthermore, for some specially designed spatially coupled operators, this allows a computationally fast and memory efficient reconstruction in compressed sensing up to the information-theoretical limit. We also show how this approach can be applied to sparse superposition codes, allowing the Approximate Message-Passing decoder to perform at large rates for moderate block length.
Improved integrality gap upper bounds for TSP with distances one and two
Venue: arXiv cs.DS 2015
Year: 2015

We study the structure of solutions to linear programming formulations for the traveling salesperson problem (TSP). We perform a detailed analysis of the support of the subtour elimination linear programming relaxation, which leads to algorithms that find 2-matchings with few components in polynomial time. The number of components directly leads to integrality gap upper bounds for the TSP with distances one and two, for both undirected and directed graphs. Our main results concern the subtour elimination relaxation with one additional cutting plane inequality: - For undirected instances we obtain an integrality gap upper bound of 5/4 without any further restrictions, of 7/6 if the optimal LP solution is half-integral. - For instances of order n where the fractional LP value has a cost of n, we obtain a tight integrality gap upper bound of 10/9 if there is an optimal solution with subcubic support graph. The latter property that the graph is subcubic is implied if the solution is a basic solution in the fractional 2-matching polytope. - For directed instances we obtain an integrality gap upper bound of 3/2, and of 4/3 if given an optimal 1/2-integral solution. In the case of undirected graphs, we can avoid to add the cutting plane inequality if we accept slightly increased values. For the tight result, the cutting plane is not required. Additionally, we show that relying on the structure of the support is not an artefact of our algorithm, but is necessary under standard complexity-theoretic assumptions: we show that finding improved solutions via local search is W[1]-hard for k-edge change neighborhoods even for the TSP with distances one and two, which strengthens a result of Dániel Marx.
Indecomposable coverings with homothetic polygons
Venue: arXiv cs.CG 2015
Year: 2015

We prove that for any convex polygon $S$ with at least four sides, or a concave one with no parallel sides, and any $m>0$, there is an $m$-fold covering of the plane with homothetic copies of $S$ that cannot be decomposed into two coverings.
Avoiding Confusion between Predictors and Inhibitors in Value Function Approximation
Venue: arXiv cs.AI 2015
Year: 2015

In reinforcement learning, the goal is to seek rewards and avoid punishments. A simple scalar captures the value of a state or of taking an action, where expected future rewards increase and punishments decrease this quantity. Naturally an agent should learn to predict this quantity to take beneficial actions, and many value function approximators exist for this purpose. In the present work, however, we show how value function approximators can cause confusion between predictors of an outcome of one valence (e.g., a signal of reward) and the inhibitor of the opposite valence (e.g., a signal canceling expectation of punishment). We show this to be a problem for both linear and non-linear value function approximators, especially when the amount of data (or experience) is limited. We propose and evaluate a simple resolution: to instead predict reward and punishment values separately, and rectify and add them to get the value needed for decision making. We evaluate several function approximators in this slightly different value function approximation architecture and show that this approach is able to circumvent the confusion and thereby achieve lower value-prediction errors.
Path Finding II : An Õ(m sqrt(n)) Algorithm for the Minimum Cost Flow Problem
Venue: arXiv cs.DS 2015
Year: 2015

In this paper we present an $\tilde{O}(m\sqrt{n}\log^{O(1)}U)$ time algorithm for solving the maximum flow problem on directed graphs with $m$ edges, $n$ vertices, and capacity ratio $U$. This improves upon the previous fastest running time of $O(m\min\left(n^{2/3},m^{1/2}\right)\log\left(n^{2}/m\right)\log U)$ achieved over 15 years ago by Goldberg and Rao. In the special case of solving dense directed unit capacity graphs our algorithm improves upon the previous fastest running times of of $O(\min\{m^{3/2},mn^{^{2/3}}\})$ achieved by Even and Tarjan and Karzanov over 35 years ago and of $\tilde{O}(m^{10/7})$ achieved recently by Mądry. We achieve these results through the development and application of a new general interior point method that we believe is of independent interest. The number of iterations required by this algorithm is better than that predicted by analyzing the best self-concordant barrier of the feasible region. By applying this method to the linear programming formulations of maximum flow, minimum cost flow, and lossy generalized minimum cost flow and applying analysis by Daitch and Spielman we achieve running time of $\tilde{O}(m\sqrt{n}\log^{O(1)}(U/ε))$ for these problems as well. Furthermore, our algorithm is parallelizable and using a recent nearly linear time work polylogarithmic depth Laplacian system solver of Spielman and Peng we achieve a $\tilde{O}(\sqrt{n}\log^{O(1)}(U/ε))$ depth algorithm and $\tilde{O}(m\sqrt{n}\log^{O(1)}(U/ε))$ work algorithm for solving these problems.
Nash Equilibrium Computation in Subnetwork Zero-Sum Games with Switching Communications
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we investigate a distributed Nash equilibrium computation problem for a time-varying multi-agent network consisting of two subnetworks, where the two subnetworks share the same objective function. We first propose a subgradient-based distributed algorithm with heterogeneous stepsizes to compute a Nash equilibrium of a zero-sum game. We then prove that the proposed algorithm can achieve a Nash equilibrium under uniformly jointly strongly connected (UJSC) weight-balanced digraphs with homogenous stepsizes. Moreover, we demonstrate that for weighted-unbalanced graphs a Nash equilibrium may not be achieved with homogenous stepsizes unless certain conditions on the objective function hold. We show that there always exist heterogeneous stepsizes for the proposed algorithm to guarantee that a Nash equilibrium can be achieved for UJSC digraphs. Finally, in two standard weight-unbalanced cases, we verify the convergence to a Nash equilibrium by adaptively updating the stepsizes along with the arc weights in the proposed algorithm.
Distributed Game Theoretic Optimization and Management of Multichannel ALOHA Networks
Venue: arXiv cs.NI 2015
Year: 2015

The problem of distributed rate maximization in multi-channel ALOHA networks is considered. First, we study the problem of constrained distributed rate maximization, where user rates are subject to total transmission probability constraints. We propose a best-response algorithm, where each user updates its strategy to increase its rate according to the channel state information and the current channel utilization. We prove the convergence of the algorithm to a Nash equilibrium in both homogeneous and heterogeneous networks using the theory of potential games. The performance of the best-response dynamic is analyzed and compared to a simple transmission scheme, where users transmit over the channel with the highest collision-free utility. Then, we consider the case where users are not restricted by transmission probability constraints. Distributed rate maximization under uncertainty is considered to achieve both efficiency and fairness among users. We propose a distributed scheme where users adjust their transmission probability to maximize their rates according to the current network state, while maintaining the desired load on the channels. We show that our approach plays an important role in achieving the Nash bargaining solution among users. Sequential and parallel algorithms are proposed to achieve the target solution in a distributed manner. The efficiencies of the algorithms are demonstrated through both theoretical and simulation results.