OpenRaiser/Intern-Atlas huggingface dataset:
Flexible composition and execution of high performance, high fidelity multiscale biomedical simulations
Venue: arXiv cs.DC 2013
Year: 2013

Multiscale simulations are essential in the biomedical domain to accurately model human physiology. We present a modular approach for designing, constructing and executing multiscale simulations on a wide range of resources, from desktops to petascale supercomputers, including combinations of these. Our work features two multiscale applications, in-stent restenosis and cerebrovascular bloodflow, which combine multiple existing single-scale applications to create a multiscale simulation. These applications can be efficiently coupled, deployed and executed on computers up to the largest (peta) scale, incurring a coupling overhead of 1 to 10% of the total execution time.
Simpler and Faster Lempel Ziv Factorization
Venue: arXiv cs.DS 2013
Year: 2013

We present a new, simple, and efficient approach for computing the Lempel-Ziv (LZ77) factorization of a string in linear time, based on suffix arrays. Computational experiments on various data sets show that our approach constantly outperforms the currently fastest algorithm LZ OG (Ohlebusch and Gog 2011), and can be up to 2 to 3 times faster in the processing after obtaining the suffix array, while requiring the same or a little more space.
Partitioning of Distributed MIMO Systems based on Overhead Considerations
Venue: arXiv cs.NI 2013
Year: 2013

Distributed-Multiple Input Multiple Output (DMIMO) networks is a promising enabler to address the challenges of high traffic demand in future wireless networks. A limiting factor that is directly related to the performance of these systems is the overhead signaling required for distributing data and control information among the network elements. In this paper, the concept of orthogonal partitioning is extended to D-MIMO networks employing joint multi-user beamforming, aiming to maximize the effective sum-rate, i.e., the actual transmitted information data. Furthermore, in order to comply with practical requirements, the overhead subframe size is considered to be constrained. In this context, a novel formulation of constrained orthogonal partitioning is introduced as an elegant Knapsack optimization problem, which allows the derivation of quick and accurate solutions. Several numerical results give insight into the capabilities of D-MIMO networks and the actual sum-rate scaling under overhead constraints.
Objective Improvement in Information-Geometric Optimization
Venue: arXiv cs.LG 2013
Year: 2013

Information-Geometric Optimization (IGO) is a unified framework of stochastic algorithms for optimization problems. Given a family of probability distributions, IGO turns the original optimization problem into a new maximization problem on the parameter space of the probability distributions. IGO updates the parameter of the probability distribution along the natural gradient, taken with respect to the Fisher metric on the parameter manifold, aiming at maximizing an adaptive transform of the objective function. IGO recovers several known algorithms as particular instances: for the family of Bernoulli distributions IGO recovers PBIL, for the family of Gaussian distributions the pure rank-mu CMA-ES update is recovered, and for exponential families in expectation parametrization the cross-entropy/ML method is recovered. This article provides a theoretical justification for the IGO framework, by proving that any step size not greater than 1 guarantees monotone improvement over the course of optimization, in terms of q-quantile values of the objective function f. The range of admissible step sizes is independent of f and its domain. We extend the result to cover the case of different step sizes for blocks of the parameters in the IGO algorithm. Moreover, we prove that expected fitness improves over time when fitness-proportional selection is applied, in which case the RPP algorithm is recovered.
Modeling, Analysis and Design for Carrier Aggregation in Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2013
Year: 2013

Carrier aggregation (CA) and small cells are two distinct features of next-generation cellular networks. Cellular networks with small cells take on a very heterogeneous characteristic, and are often referred to as HetNets. In this paper, we introduce a load-aware model for CA-enabled \textit{multi}-band HetNets. Under this model, the impact of biasing can be more appropriately characterized; for example, it is observed that with large enough biasing, the spectral efficiency of small cells may increase while its counterpart in a fully-loaded model always decreases. Further, our analysis reveals that the peak data rate does not depend on the base station density and transmit powers; this strongly motivates other approaches e.g. CA to increase the peak data rate. Last but not least, different band deployment configurations are studied and compared. We find that with large enough small cell density, spatial reuse with small cells outperforms adding more spectrum for increasing user rate. More generally, universal cochannel deployment typically yields the largest rate; and thus a capacity loss exists in orthogonal deployment. This performance gap can be reduced by appropriately tuning the HetNet coverage distribution (e.g. by optimizing biasing factors).
Online Energy Generation Scheduling for Microgrids with Intermittent Energy Sources and Co-Generation
Venue: arXiv cs.OH 2013
Year: 2013

Microgrids represent an emerging paradigm of future electric power systems that can utilize both distributed and centralized generations. Two recent trends in microgrids are the integration of local renewable energy sources (such as wind farms) and the use of co-generation (i.e., to supply both electricity and heat). However, these trends also bring unprecedented challenges to the design of intelligent control strategies for microgrids. Traditional generation scheduling paradigms rely on perfect prediction of future electricity supply and demand. They are no longer applicable to microgrids with unpredictable renewable energy supply and with co-generation (that needs to consider both electricity and heat demand). In this paper, we study online algorithms for the microgrid generation scheduling problem with intermittent renewable energy sources and co-generation, with the goal of maximizing the cost-savings with local generation. Based on the insights from the structure of the offline optimal solution, we propose a class of competitive online algorithms, called CHASE (Competitive Heuristic Algorithm for Scheduling Energy-generation), that track the offline optimal in an online fashion. Under typical settings, we show that CHASE achieves the best competitive ratio among all deterministic online algorithms, and the ratio is no larger than a small constant 3.
A Cross-layer Perspective on Energy Harvesting Aided Green Communications over Fading Channels
Venue: arXiv cs.IT 2013
Year: 2013

We consider the power allocation of the physical layer and the buffer delay of the upper application layer in energy harvesting green networks. The total power required for reliable transmission includes the transmission power and the circuit power. The harvested power (which is stored in a battery) and the grid power constitute the power resource. The uncertainty of data generated from the upper layer, the intermittence of the harvested energy, and the variation of the fading channel are taken into account and described as independent Markov processes. In each transmission, the transmitter decides the transmission rate as well as the allocated power from the battery, and the rest of the required power will be supplied by the power grid. The objective is to find an allocation sequence of transmission rate and battery power to minimize the long-term average buffer delay under the average grid power constraint. A stochastic optimization problem is formulated accordingly to find such transmission rate and battery power sequence. Furthermore, the optimization problem is reformulated as a constrained MDP problem whose policy is a two-dimensional vector with the transmission rate and the power allocation of the battery as its elements. We prove that the optimal policy of the constrained MDP can be obtained by solving the unconstrained MDP. Then we focus on the analysis of the unconstrained average-cost MDP. The structural properties of the average optimal policy are derived. Moreover, we discuss the relations between elements of the two-dimensional policy. Next, based on the theoretical analysis, the algorithm to find the constrained optimal policy is presented for the finite state space scenario. In addition, heuristic policies with low-complexity are given for the general state space. Finally, simulations are performed under these policies to demonstrate the effectiveness.
Approximate pattern matching with k-mismatches in packed text
Venue: arXiv cs.DS 2013
Year: 2013

Given strings $P$ of length $m$ and $T$ of length $n$ over an alphabet of size $σ$, the string matching with $k$-mismatches problem is to find the positions of all the substrings in $T$ that are at Hamming distance at most $k$ from $P$. If $T$ can be read only one character at the time the best known bounds are $O(n\sqrt{k\log k})$ and $O(n + n\sqrt{k/w}\log k)$ in the word-RAM model with word length $w$. In the RAM models (including $AC^0$ and word-RAM) it is possible to read up to $\floor{w / \log σ}$ characters in constant time if the characters of $T$ are encoded using $\ceil{\log σ}$ bits. The only solution for $k$-mismatches in packed text works in $O((n \logσ/\log n)\ceil{m \log (k + \log n / \logσ) / w} + n^{\varepsilon})$ time, for any $\varepsilon > 0$. We present an algorithm that runs in time $O(\frac{n}{\floor{w/(m\logσ)}} (1 + \log \min(k,σ) \log m / \logσ))$ in the $AC^0$ model if $m=O(w / \logσ)$ and $T$ is given packed. We also describe a simpler variant that runs in time $O(\frac{n}{\floor{w/(m\logσ)}}\log \min(m, \log w / \logσ))$ in the word-RAM model. The algorithms improve the existing bound for $w = Ω(\log^{1+ε}n)$, for any $ε> 0$. Based on the introduced technique, we present algorithms for several other approximate matching problems.
A survey of uncertainty principles and some signal processing applications
Venue: arXiv cs.IT 2013
Year: 2013

The goal of this paper is to review the main trends in the domain of uncertainty principles and localization, emphasize their mutual connections and investigate practical consequences. The discussion is strongly oriented towards, and motivated by signal processing problems, from which significant advances have been made recently. Relations with sparse approximation and coding problems are emphasized.
Social Network Games
Venue: arXiv cs.GT 2013
Year: 2013

One of the natural objectives of the field of the social networks is to predict agents' behaviour. To better understand the spread of various products through a social network arXiv:1105.2434 introduced a threshold model, in which the nodes influenced by their neighbours can adopt one out of several alternatives. To analyze the consequences of such product adoption we associate here with each such social network a natural strategic game between the agents. In these games the payoff of each player weakly increases when more players choose his strategy, which is exactly opposite to the congestion games. The possibility of not choosing any product results in two special types of (pure) Nash equilibria. We show that such games may have no Nash equilibrium and that determining an existence of a Nash equilibrium, also of a special type, is NP-complete. This implies the same result for a more general class of games, namely polymatrix games. The situation changes when the underlying graph of the social network is a DAG, a simple cycle, or, more generally, has no source nodes. For these three classes we determine the complexity of an existence of (a special type of) Nash equilibria. We also clarify for these categories of games the status and the complexity of the finite best response property (FBRP) and the finite improvement property (FIP). Further, we introduce a new property of the uniform FIP which is satisfied when the underlying graph is a simple cycle, but determining it is co-NP-hard in the general case and also when the underlying graph has no source nodes. The latter complexity results also hold for the property of being a weakly acyclic game. A preliminary version of this paper appeared as [19].
Online Stochastic Optimization with Multiple Objectives
Venue: arXiv cs.LG 2013
Year: 2013

In this paper we propose a general framework to characterize and solve the stochastic optimization problems with multiple objectives underlying many real world learning applications. We first propose a projection based algorithm which attains an $O(T^{-1/3})$ convergence rate. Then, by leveraging on the theory of Lagrangian in constrained optimization, we devise a novel primal-dual stochastic approximation algorithm which attains the optimal convergence rate of $O(T^{-1/2})$ for general Lipschitz continuous objectives.
Duality between subgradient and conditional gradient methods
Venue: arXiv cs.LG 2013
Year: 2013

Given a convex optimization problem and its dual, there are many possible first-order algorithms. In this paper, we show the equivalence between mirror descent algorithms and algorithms generalizing the conditional gradient method. This is done through convex duality, and implies notably that for certain problems, such as for supervised machine learning problems with non-smooth losses or problems regularized by non-smooth regularizers, the primal subgradient method and the dual conditional gradient method are formally equivalent. The dual interpretation leads to a form of line search for mirror descent, as well as guarantees of convergence for primal-dual certificates.
Exploring heterogeneity of unreliable machines for p2p backup
Venue: arXiv cs.DC 2013
Year: 2013

P2P architecture is a viable option for enterprise backup. In contrast to dedicated backup servers, nowadays a standard solution, making backups directly on organization's workstations should be cheaper (as existing hardware is used), more efficient (as there is no single bottleneck server) and more reliable (as the machines are geographically dispersed). We present the architecture of a p2p backup system that uses pairwise replication contracts between a data owner and a replicator. In contrast to standard p2p storage systems using directly a DHT, the contracts allow our system to optimize replicas' placement depending on a specific optimization strategy, and so to take advantage of the heterogeneity of the machines and the network. Such optimization is particularly appealing in the context of backup: replicas can be geographically dispersed, the load sent over the network can be minimized, or the optimization goal can be to minimize the backup/restore time. However, managing the contracts, keeping them consistent and adjusting them in response to dynamically changing environment is challenging. We built a scientific prototype and ran the experiments on 150 workstations in the university's computer laboratories and, separately, on 50 PlanetLab nodes. We found out that the main factor affecting the quality of the system is the availability of the machines. Yet, our main conclusion is that it is possible to build an efficient and reliable backup system on highly unreliable machines (our computers had just 13% average availability).
Manipulating Google Scholar Citations and Google Scholar Metrics: simple, easy and tempting
Venue: arXiv cs.DL 2013
Year: 2013

The launch of Google Scholar Citations and Google Scholar Metrics may provoke a revolution in the research evaluation field as it places within every researchers reach tools that allow bibliometric measuring. In order to alert the research community over how easily one can manipulate the data and bibliometric indicators offered by Google s products we present an experiment in which we manipulate the Google Citations profiles of a research group through the creation of false documents that cite their documents, and consequently, the journals in which they have published modifying their H index. For this purpose we created six documents authored by a faked author and we uploaded them to a researcher s personal website under the University of Granadas domain. The result of the experiment meant an increase of 774 citations in 129 papers (six citations per paper) increasing the authors and journals H index. We analyse the malicious effect this type of practices can cause to Google Scholar Citations and Google Scholar Metrics. Finally, we conclude with several deliberations over the effects these malpractices may have and the lack of control tools these tools offer
Two Algorithms for Finding $k$ Shortest Paths of a Weighted Pushdown Automaton
Venue: arXiv cs.CL 2013
Year: 2013

We introduce efficient algorithms for finding the $k$ shortest paths of a weighted pushdown automaton (WPDA), a compact representation of a weighted set of strings with potential applications in parsing and machine translation. Both of our algorithms are derived from the same weighted deductive logic description of the execution of a WPDA using different search strategies. Experimental results show our Algorithm 2 adds very little overhead vs. the single shortest path algorithm, even with a large $k$.
A fair comparison of many max-tree computation algorithms (Extended version of the paper submitted to ISMM 2013
Venue: arXiv cs.CV 2013
Year: 2013

With the development of connected filters for the last decade, many algorithms have been proposed to compute the max-tree. Max-tree allows to compute the most advanced connected operators in a simple way. However, no fair comparison of algorithms has been proposed yet and the choice of an algorithm over an other depends on many parameters. Since the need of fast algorithms is obvious for production code, we present an in depth comparison of five algorithms and some variations of them in a unique framework. Finally, a decision tree will be proposed to help user in choosing the right algorithm with respect to their data.
Power Consumption Analysis of a Modern Smartphone
Venue: arXiv cs.PF 2013
Year: 2013

This paper presents observations about power consumption of a latest smartphone. Modern smartphones are powerful devices with different choices of data connections and other functional modes. This paper provides analysis of power utilization for these different operation modes. Also, we present power consumption by vital operating system (OS) components.
Constant-Competitive Prior-Free Auction with Ordered Bidders
Venue: arXiv cs.GT 2013
Year: 2013

A central problem in Microeconomics is to design auctions with good revenue properties. In this setting, the bidders' valuations for the items are private knowledge, but they are drawn from publicly known prior distributions. The goal is to find a truthful auction (no bidder can gain in utility by misreporting her valuation) that maximizes the expected revenue. Naturally, the optimal-auction is sensitive to the prior distributions. An intriguing question is to design a truthful auction that is oblivious to these priors, and yet manages to get a constant factor of the optimal revenue. Such auctions are called prior-free. Goldberg et al. presented a constant-approximate prior-free auction when there are identical copies of an item available in unlimited supply, bidders are unit-demand, and their valuations are drawn from i.i.d. distributions. The recent work of Leonardi et al. [STOC 2012] generalized this problem to non i.i.d. bidders, assuming that the auctioneer knows the ordering of their reserve prices. Leonardi et al. proposed a prior-free auction that achieves a $O(\log^* n)$ approximation. We improve upon this result, by giving the first prior-free auction with constant approximation guarantee.
On the Design of Artificial-Noise-Aided Secure Multi-Antenna Transmission in Slow Fading Channels
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we investigate the design of artificial-noise-aided secure multi-antenna transmission in slow fading channels. The primary design concerns include the transmit power allocation and the rate parameters of the wiretap code. We consider two scenarios with different complexity levels: i) the design parameters are chosen to be fixed for all transmissions, ii) they are adaptively adjusted based on the instantaneous channel feedback from the intended receiver. In both scenarios, we provide explicit design solutions for achieving the maximal throughput subject to a secrecy constraint, given by a maximum allowable secrecy outage probability. We then derive accurate approximations for the maximal throughput in both scenarios in the high signal-to-noise ratio region, and give new insights into the additional power cost for achieving a higher security level, whilst maintaining a specified target throughput. In the end, the throughput gain of adaptive transmission over non-adaptive transmission is also quantified and analyzed.
On Capacity Region of Wiretap Networks
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we consider the problem of secure network coding where an adversary has access to an unknown subset of links chosen from a known collection of links subsets. We study the capacity region of such networks, commonly called "wiretap networks", subject to weak and strong secrecy constraints, and consider both zero-error and asymptotically zero-error communication. We prove that in general discrete memoryless networks modeled by discrete memoryless channels, the capacity region subject to strong secrecy requirement and the capacity region subject to weak secrecy requirement are equal. In particular, this result shows that requiring strong secrecy in a wiretap network with asymptotically zero probability of error does not shrink the capacity region compared to the case of weak secrecy requirement. We also derive inner and outer bounds on the network coding capacity region of wiretap networks subject to weak secrecy constraint, for both zero probability of error and asymptotically zero probability of error, in terms of the entropic region.
Sliding Windows with Limited Storage
Venue: arXiv cs.CC 2013
Year: 2013

We consider time-space tradeoffs for exactly computing frequency moments and order statistics over sliding windows. Given an input of length 2n-1, the task is to output the function of each window of length n, giving n outputs in total. Computations over sliding windows are related to direct sum problems except that inputs to instances almost completely overlap. We show an average case and randomized time-space tradeoff lower bound of TS in Omega(n^2) for multi-way branching programs, and hence standard RAM and word-RAM models, to compute the number of distinct elements, F_0, in sliding windows over alphabet [n]. The same lower bound holds for computing the low-order bit of F_0 and computing any frequency moment F_k for k not equal to 1. We complement this lower bound with a TS in \tilde O(n^2) deterministic RAM algorithm for exactly computing F_k in sliding windows. We show time-space separations between the complexity of sliding-window element distinctness and that of sliding-window $F_0\bmod 2$ computation. In particular for alphabet [n] there is a very simple errorless sliding-window algorithm for element distinctness that runs in O(n) time on average and uses O(log{n}) space. We show that any algorithm for a single element distinctness instance can be extended to an algorithm for the sliding-window version of element distinctness with at most a polylogarithmic increase in the time-space product. Finally, we show that the sliding-window computation of order statistics such as the maximum and minimum can be computed with only a logarithmic increase in time, but that a TS in Omega(n^2) lower bound holds for sliding-window computation of order statistics such as the median, a nearly linear increase in time when space is small.