OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Business Processes - A Framework for Modeling and Execution
Venue: arXiv cs.MA 2014
Year: 2014

Commercially available business process management systems (BPMS) still suffer to support organizations to enact their business processes in an effective and efficient way. Current BPMS, in general, are based on BPMN 2.0 and/or BPEL. It is well known, that these approaches have some restrictions according modeling and immediate transfer of the model into executable code. Recently, a method for modeling and execution of business processes, named subject-oriented business process management (S-BPM), gained attention. This methodology facilitates modeling of any business process using only five symbols and allows direct execution based on such models. Further on, this methodology has a strong theoretical and formal basis realizing distributed systems; any process is defined as a network of independent and distributed agents - i.e. instances of subjects - which coordinate work through the exchange of messages. In this work, we present a framework and a prototype based on off-the-shelf technologies as a possible realization of the S-BPM methodology. We can prove and demonstrate the principal architecture concept; these results should also stimulate a discussion about actual BPMS and its underlying concepts.
A new design criterion for spherically-shaped division algebra-based space-time codes
Venue: arXiv cs.IT 2014
Year: 2014

This work considers normalized inverse determinant sums as a tool for analyzing the performance of division algebra based space-time codes for multiple antenna wireless systems. A general union bound based code design criterion is obtained as a main result. In our previous work, the behavior of inverse determinant sums was analyzed using point counting techniques for Lie groups; it was shown that the asymptotic growth exponents of these sums correctly describe the diversity-multiplexing gain trade-off of the space-time code for some multiplexing gain ranges. This paper focuses on the constant terms of the inverse determinant sums, which capture the coding gain behavior. Pursuing the Lie group approach, a tighter asymptotic bound is derived, allowing to compute the constant terms for several classes of space-time codes appearing in the literature. The resulting design criterion suggests that the performance of division algebra based codes depends on several fundamental algebraic invariants of the underlying algebra.
Exploring Subexponential Parameterized Complexity of Completion Problems
Venue: arXiv cs.DS 2014
Year: 2014

Let ${\cal F}$ be a family of graphs. In the ${\cal F}$-Completion problem, we are given a graph $G$ and an integer $k$ as input, and asked whether at most $k$ edges can be added to $G$ so that the resulting graph does not contain a graph from ${\cal F}$ as an induced subgraph. It appeared recently that special cases of ${\cal F}$-Completion, the problem of completing into a chordal graph known as Minimum Fill-in, corresponding to the case of ${\cal F}=\{C_4,C_5,C_6,\ldots\}$, and the problem of completing into a split graph, i.e., the case of ${\cal F}=\{C_4, 2K_2, C_5\}$, are solvable in parameterized subexponential time $2^{O(\sqrt{k}\log{k})}n^{O(1)}$. The exploration of this phenomenon is the main motivation for our research on ${\cal F}$-Completion. In this paper we prove that completions into several well studied classes of graphs without long induced cycles also admit parameterized subexponential time algorithms by showing that: - The problem Trivially Perfect Completion is solvable in parameterized subexponential time $2^{O(\sqrt{k}\log{k})}n^{O(1)}$, that is ${\cal F}$-Completion for ${\cal F} =\{C_4, P_4\}$, a cycle and a path on four vertices. - The problems known in the literature as Pseudosplit Completion, the case where ${\cal F} = \{2K_2, C_4\}$, and Threshold Completion, where ${\cal F} = \{2K_2, P_4, C_4\}$, are also solvable in time $2^{O(\sqrt{k}\log{k})} n^{O(1)}$. We complement our algorithms for ${\cal F}$-Completion with the following lower bounds: - For ${\cal F} = \{2K_2\}$, ${\cal F} = \{C_4\}$, ${\cal F} = \{P_4\}$, and ${\cal F} = \{2K_2, P_4\}$, ${\cal F}$-Completion cannot be solved in time $2^{o(k)} n^{O(1)}$ unless the Exponential Time Hypothesis (ETH) fails. Our upper and lower bounds provide a complete picture of the subexponential parameterized complexity of ${\cal F}$-Completion problems for ${\cal F}\subseteq\{2K_2, C_4, P_4\}$.
Near-Field Passive RFID Communication: Channel Model and Code Design
Venue: arXiv cs.IT 2014
Year: 2014

This paper discusses a new channel model and code design for the reader-to-tag channel in near-field passive radio frequency identification (RFID) systems using inductive coupling as a power transfer mechanism. If the receiver resynchronizes its internal clock each time a bit is detected, the bit-shift channel used previously in the literature to model the reader-to-tag channel needs to be modified. In particular, we propose a discretized Gaussian shift channel as a new channel model in this scenario. We introduce the concept of quantifiable error avoidance, which is much simpler than error correction. The capacity is computed numerically, and we also design some new simple codes for error avoidance on this channel model based on insights gained from the capacity calculations. Finally, some simulation results are presented to compare the proposed codes to the Manchester code and two previously proposed codes for the bit-shift channel model.
An Algebraic Approach to the Control of Decentralized Systems
Venue: arXiv cs.SY 2014
Year: 2014

Optimal decentralized controller design is notoriously difficult, but recent research has identified large subclasses of such problems that may be convexified and thus are amenable to solution via efficient numerical methods. One recently discovered sufficient condition for convexity is quadratic invariance (QI). Despite the simple algebraic characterization of QI, which relates the plant and controller maps, proving convexity of the set of achievable closed-loop maps requires tools from functional analysis. In this work, we present a new formulation of quadratic invariance that is purely algebraic. While our results are similar in flavor to those from traditional QI theory, they do not follow from that body of work. Furthermore, they are applicable to new types of systems that are difficult to treat using functional analysis. Examples discussed include rational transfer matrices, systems with delays, and multidimensional systems.
Linear kernels for k-tuple and liar's domination in bounded genus graphs
Venue: arXiv cs.CC 2014
Year: 2014

A set $D\subseteq V$ is called a $k$-tuple dominating set of a graph $G=(V,E)$ if $\left| N_G[v] \cap D \right| \geq k$ for all $v \in V$, where $N_G[v]$ denotes the closed neighborhood of $v$. A set $D \subseteq V$ is called a liar's dominating set of a graph $G=(V,E)$ if (i) $\left| N_G[v] \cap D \right| \geq 2$ for all $v\in V$ and (ii) for every pair of distinct vertices $u, v\in V$, $\left| (N_G[u] \cup N_G[v]) \cap D \right| \geq 3$. Given a graph $G$, the decision versions of $k$-Tuple Domination Problem and the Liar's Domination Problem are to check whether there exists a $k$-tuple dominating set and a liar's dominating set of $G$ of a given cardinality, respectively. These two problems are known to be NP-complete \cite{LiaoChang2003, Slater2009}. In this paper, we study the parameterized complexity of these problems. We show that the $k$-Tuple Domination Problem and the Liar's Domination Problem are $\mathsf{W}[2]$-hard for general graphs but they admit linear kernels for graphs with bounded genus.
The sum-capture problem for abelian groups
Venue: arXiv cs.DM 2014
Year: 2014

Let $G$ be a finite abelian group, let $0 < α< 1$, and let $A \subseteq G$ be a random set of size $|G|^α$. We let $$ μ(A) = \max_{B,C:|B|=|C|=|A|}|\{(a,b,c) \in A \times B \times C : a = b + c \}|. $$ The issue is to determine upper bounds on $μ(A)$ that hold with high probability over the random choice of $A$. Mennink and Preneel \cite{BM} conjecture that $μ(A)$ should be close to $|A|$ (up to possible logarithmic factors in $|G|$) for $α\leq 1/2$ and that $μ(A)$ should not much exceed $|A|^{3/2}$ for $α\leq 2/3$. We prove the second half of this conjecture by showing that $$ μ(A) \leq |A|^3/|G| + 4|A|^{3/2}\ln(|G|)^{1/2} $$ with high probability, for all $0 < α< 1$. We note that $3α- 1 \leq (3/2)α$ for $α\leq 2/3$. In previous work, Alon et al$.$ have shown that $μ(A) \leq O(1)|A|^3/|G|$ with high probability for $α\geq 2/3$ while Kiltz, Pietrzak and Szegedy show that $μ(A) \leq |A|^{1 + 2α}$ with high probability for $α\leq 1/4$. Current bounds on $μ(A)$ are essentially sharp for the range $2/3 \leq α\leq 1$. Finding better bounds remains an open problem for the range $0 < α< 2/3$ and especially for the range $1/4 < α< 2/3$ in which the bound of Kiltz et al$.$ doesn't improve on the bound given in this paper (even if that bound applied). Moreover the conjecture of Mennink and Preneel for $α\leq 1/2$ remains open.
Vive la Différence: Paxos vs. Viewstamped Replication vs. Zab
Venue: arXiv cs.DC 2014
Year: 2014

Paxos, Viewstamped Replication, and Zab are replication protocols that ensure high-availability in asynchronous environments with crash failures. Various claims have been made about similarities and differences between these protocols. But how does one determine whether two protocols are the same, and if not, how significant the differences are? We propose to address these questions using refinement mappings, where protocols are expressed as succinct specifications that are progressively refined to executable implementations. Doing so enables a principled understanding of the correctness of the different design decisions that went into implementing the various protocols. Additionally, it allowed us to identify key differences that have a significant impact on performance.
Online Bin Covering: Expectations vs. Guarantees
Venue: arXiv cs.DS 2014
Year: 2014

Bin covering is a dual version of classic bin packing. Thus, the goal is to cover as many bins as possible, where covering a bin means packing items of total size at least one in the bin. For online bin covering, competitive analysis fails to distinguish between most algorithms of interest; all "reasonable" algorithms have a competitive ratio of 1/2. Thus, in order to get a better understanding of the combinatorial difficulties in solving this problem, we turn to other performance measures, namely relative worst order, random order, and max/max analysis, as well as analyzing input with restricted or uniformly distributed item sizes. In this way, our study also supplements the ongoing systematic studies of the relative strengths of various performance measures. Two classic algorithms for online bin packing that have natural dual versions are Harmonic and Next-Fit. Even though the algorithms are quite different in nature, the dual versions are not separated by competitive analysis. We make the case that when guarantees are needed, even under restricted input sequences, dual Harmonic is preferable. In addition, we establish quite robust theoretical results showing that if items come from a uniform distribution or even if just the ordering of items is uniformly random, then dual Next-Fit is the right choice.
High Throughput Data Center Topology Design
Venue: arXiv cs.NI 2014
Year: 2014

With high throughput networks acquiring a crucial role in supporting data-intensive applications, a variety of data center network topologies have been proposed to achieve high capacity at low cost. While this literature explores a large number of design points, even in the limited case of a network of identical switches, no proposal has been able to claim any notion of optimality. The case of heterogeneous networks, incorporating multiple line-speeds and port-counts as data centers grow over time, introduces even greater complexity. In this paper, we present the first non-trivial upper-bound on network throughput under uniform traffic patterns for any topology with identical switches. We then show that random graphs achieve throughput surprisingly close to this bound, within a few percent at the scale of a few thousand servers. Apart from demonstrating that homogeneous topology design may be reaching its limits, this result also motivates our use of random graphs as building blocks to explore the design of heterogeneous networks. Given a heterogeneous pool of network switches, through experiments and analysis, we explore how the distribution of servers across switches and the interconnection of switches affect network throughput. We apply these insights to a real-world heterogeneous data center topology, VL2, demonstrating as much as 43% higher throughput with the same equipment.
Pilot Beam Pattern Design for Channel Estimation in Massive MIMO Systems
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, the problem of pilot beam pattern design for channel estimation in massive multiple-input multiple-output systems with a large number of transmit antennas at the base station is considered, and a new algorithm for pilot beam pattern design for optimal channel estimation is proposed under the assumption that the channel is a stationary Gauss-Markov random process. The proposed algorithm designs the pilot beam pattern sequentially by exploiting the properties of Kalman filtering and the associated prediction error covariance matrices and also the channel statistics such as spatial and temporal channel correlation. The resulting design generates a sequentially-optimal sequence of pilot beam patterns with low complexity for a given set of system parameters. Numerical results show the effectiveness of the proposed algorithm.
Asynchronous Gossip for Averaging and Spectral Ranking
Venue: arXiv cs.DC 2014
Year: 2014

We consider two variants of the classical gossip algorithm. The first variant is a version of asynchronous stochastic approximation. We highlight a fundamental difficulty associated with the classical asynchronous gossip scheme, viz., that it may not converge to a desired average, and suggest an alternative scheme based on reinforcement learning that has guaranteed convergence to the desired average. We then discuss a potential application to a wireless network setting with simultaneous link activation constraints. The second variant is a gossip algorithm for distributed computation of the Perron-Frobenius eigenvector of a nonnegative matrix. While the first variant draws upon a reinforcement learning algorithm for an average cost controlled Markov decision problem, the second variant draws upon a reinforcement learning algorithm for risk-sensitive control. We then discuss potential applications of the second variant to ranking schemes, reputation networks, and principal component analysis.
Energy Efficient Telemonitoring of Physiological Signals via Compressed Sensing: A Fast Algorithm and Power Consumption Evaluation
Venue: arXiv cs.IT 2014
Year: 2014

Wireless telemonitoring of physiological signals is an important topic in eHealth. In order to reduce on-chip energy consumption and extend sensor life, recorded signals are usually compressed before transmission. In this paper, we adopt compressed sensing (CS) as a low-power compression framework, and propose a fast block sparse Bayesian learning (BSBL) algorithm to reconstruct original signals. Experiments on real-world fetal ECG signals and epilepsy EEG signals showed that the proposed algorithm has good balance between speed and data reconstruction fidelity when compared to state-of-the-art CS algorithms. Further, we implemented the CS-based compression procedure and a low-power compression procedure based on a wavelet transform in Filed Programmable Gate Array (FPGA), showing that the CS-based compression can largely save energy and other on-chip computing resources.
The SAT-UNSAT transition in the adversarial SAT problem
Venue: arXiv cs.CC 2014
Year: 2014

Adversarial SAT (AdSAT) is a generalization of the satisfiability (SAT) problem in which two players try to make a boolean formula true (resp. false) by controlling their respective sets of variables. AdSAT belongs to a higher complexity class in the polynomial hierarchy than SAT and therefore the nature of the critical region and the transition are not easily paralleled to those of SAT and worth of independent study. AdSAT also provides an upper bound for the transition threshold of the quantum satisfiability problem (QSAT). We present a complete algorithm for AdSAT, show that 2-AdSAT is in $\mathbf{P}$, and then study two stochastic algorithms (simulated annealing and its improved variant) and compare their performances in detail for 3-AdSAT. Varying the density of clauses $α$ we find a sharp SAT-UNSAT transition at a critical value whose upper bound is $α_c \lesssim 1.5$, thus providing a much stricter upper bound for the QSAT transition than those previously found.
The Firefighter Problem: A Structural Analysis
Venue: arXiv cs.DM 2014
Year: 2014

We consider the complexity of the firefighter problem where b>=1 firefighters are available at each time step. This problem is proved NP-complete even on trees of degree at most three and budget one (Finbow et al.,2007) and on trees of bounded degree b+3 for any fixed budget b>=2 (Bazgan et al.,2012). In this paper, we provide further insight into the complexity landscape of the problem by showing that the pathwidth and the maximum degree of the input graph govern its complexity. More precisely, we first prove that the problem is NP-complete even on trees of pathwidth at most three for any fixed budget b>=1. We then show that the problem turns out to be fixed parameter-tractable with respect to the combined parameter "pathwidth" and "maximum degree" of the input graph.
MDR Codes: A New Class of RAID-6 Codes with Optimal Rebuilding and Encoding
Venue: arXiv cs.IT 2014
Year: 2014

As storage systems grow in size, device failures happen more frequently than ever before. Given the commodity nature of hard drives employed, a storage system needs to tolerate a certain number of disk failures while maintaining data integrity, and to recover lost data with minimal interference to normal disk I/O operations. RAID-6, which can tolerate up to two disk failures with the minimum redundancy, is becoming widespread. However, traditional RAID-6 codes suffer from high disk I/O overhead during recovery. In this paper, we propose a new family of RAID-6 codes, the Minimum Disk I/O Repairable (MDR) codes, which achieve the optimal disk I/O overhead for single failure recoveries. Moreover, we show that MDR codes can be encoded with the minimum number of bit-wise XOR operations. Simulation results show that MDR codes help to save about half of disk read operations than traditional RAID-6 codes, and thus can reduce the recovery time by up to 40%.
A Lyapunov Optimization Approach to Repeated Stochastic Games
Venue: arXiv cs.GT 2014
Year: 2014

This paper considers a time-varying game with $N$ players. Every time slot, players observe their own random events and then take a control action. The events and control actions affect the individual utilities earned by each player. The goal is to maximize a concave function of time average utilities subject to equilibrium constraints. Specifically, participating players are provided access to a common source of randomness from which they can optimally correlate their decisions. The equilibrium constraints incentivize participation by ensuring that players cannot earn more utility if they choose not to participate. This form of equilibrium is similar to the notions of Nash equilibrium and correlated equilibrium, but is simpler to attain. A Lyapunov method is developed that solves the problem in an online \emph{max-weight} fashion by selecting actions based on a set of time-varying weights. The algorithm does not require knowledge of the event probabilities and has polynomial convergence time. A similar method can be used to compute a standard correlated equilibrium, albeit with increased complexity.
An Empirical-Bayes Approach to Recovering Linearly Constrained Non-Negative Sparse Signals
Venue: arXiv cs.IT 2014
Year: 2014

We propose two novel approaches to the recovery of an (approximately) sparse signal from noisy linear measurements in the case that the signal is a priori known to be non-negative and obey given linear equality constraints, such as simplex signals. This problem arises in, e.g., hyperspectral imaging, portfolio optimization, density estimation, and certain cases of compressive imaging. Our first approach solves a linearly constrained non-negative version of LASSO using the max-sum version of the generalized approximate message passing (GAMP) algorithm, where we consider both quadratic and absolute loss, and where we propose a novel approach to tuning the LASSO regularization parameter via the expectation maximization (EM) algorithm. Our second approach is based on the sum-product version of the GAMP algorithm, where we propose the use of a Bernoulli non-negative Gaussian-mixture signal prior and a Laplacian likelihood, and propose an EM-based approach to learning the underlying statistical parameters. In both approaches, the linear equality constraints are enforced by augmenting GAMP's generalized-linear observation model with noiseless pseudo-measurements. Extensive numerical experiments demonstrate the state-of-the-art performance of our proposed approaches.
Evaluation of DNF Formulas
Venue: arXiv cs.CC 2014
Year: 2014

Stochastic Boolean Function Evaluation (SBFE) is the problem of determining the value of a given Boolean function $f$ on an unknown input $x$, when each bit of $x_i$ of $x$ can only be determined by paying a given associated cost $c_i$. Further, $x$ is drawn from a given product distribution: for each $x_i$, $Prob[x_i=1] = p_i$, and the bits are independent. The goal is to minimize the expected cost of evaluation. Stochastic Boolean Function Evaluation (SBFE) is the problem of determining the value of a given Boolean function $f$ on an unknown input $x$, when each bit of $x_i$ of $x$ can only be determined by paying a given associated cost $c_i$. Further, $x$ is drawn from a given product distribution: for each $x_i$, $Prob[x_i=1] = p_i$, and the bits are independent. The goal is to minimize the expected cost of evaluation. In this paper, we study the complexity of the SBFE problem for classes of DNF formulas. We consider both exact and approximate versions of the problem for subclasses of DNF, for arbitrary costs and product distributions, and for unit costs and/or the uniform distribution.
A novel sparsity and clustering regularization
Venue: arXiv cs.LG 2014
Year: 2014

We propose a novel SPARsity and Clustering (SPARC) regularizer, which is a modified version of the previous octagonal shrinkage and clustering algorithm for regression (OSCAR), where, the proposed regularizer consists of a $K$-sparse constraint and a pair-wise $\ell_{\infty}$ norm restricted on the $K$ largest components in magnitude. The proposed regularizer is able to separably enforce $K$-sparsity and encourage the non-zeros to be equal in magnitude. Moreover, it can accurately group the features without shrinking their magnitude. In fact, SPARC is closely related to OSCAR, so that the proximity operator of the former can be efficiently computed based on that of the latter, allowing using proximal splitting algorithms to solve problems with SPARC regularization. Experiments on synthetic data and with benchmark breast cancer data show that SPARC is a competitive group-sparsity inducing regularizer for regression and classification.