OpenRaiser/Intern-Atlas huggingface dataset:
Two-User Interference Channels with Local Views: On Capacity Regions of TDM-Dominating Policies
Venue: arXiv cs.IT 2012
Year: 2012

We study the capacity regions of two-user interference channels where transmitters base their transmission schemes on local views of the channel state. Under the local view model, each transmitter knows only a subset of the four channel gains, which may be mismatched from the other transmitter. We consider a set of seven local views, and find that for five out of the seven local views, TDM is sufficient to achieve the qualified notion of capacity region for the linear deterministic interference channel which approximates the Gaussian interference channel. For these five local views, the qualified capacity result implies that no policy can achieve a rate point outside the TDM region without inducing a corner case of sub-TDM performance in another channel state. The common trait shared by the two remaining local views - those with the potential to outperform TDM - is transmitter knowledge of the outgoing interference link accompanied by some common knowledge of state, emphasizing their importance in creating opportunities to coordinate usage of more advanced schemes. Our conclusions are extended to bounded gap characterizations of the capacity region for the Gaussian interference channel.
Runtime Guarantees for Regression Problems
Venue: arXiv cs.DS 2012
Year: 2012

We study theoretical runtime guarantees for a class of optimization problems that occur in a wide variety of inference problems. these problems are motivated by the lasso framework and have applications in machine learning and computer vision. Our work shows a close connection between these problems and core questions in algorithmic graph theory. While this connection demonstrates the difficulties of obtaining runtime guarantees, it also suggests an approach of using techniques originally developed for graph algorithms. We then show that most of these problems can be formulated as a grouped least squares problem, and give efficient algorithms for this formulation. Our algorithms rely on routines for solving quadratic minimization problems, which in turn are equivalent to solving linear systems. Finally we present some experimental results on applying our approximation algorithm to image processing problems.
Stability of a Peer-to-Peer Communication System
Venue: arXiv cs.PF 2012
Year: 2012

This paper focuses on the stationary portion of file download in an unstructured peer-to-peer network, which typically follows for many hours after a flash crowd initiation. The model includes the case that peers can have some pieces at the time of arrival. The contribution of the paper is to identify how much help is needed from the seeds, either fixed seeds or peer seeds (which are peers remaining in the system after obtaining a complete collection) to stabilize the system. The dominant cause for instability is the missing piece syndrome, whereby one piece becomes very rare in the network. It is shown that stability can be achieved with only a small amount of help from peer seeds--even with very little help from a fixed seed, peers need dwell as peer seeds on average only long enough to upload one additional piece. The region of stability is insensitive to the piece selection policy. Network coding can substantially increase the region of stability in case a portion of the new peers arrive with randomly coded pieces.
FMM-based vortex method for simulation of isotropic turbulence on GPUs, compared with a spectral method
Venue: arXiv cs.NA 2012
Year: 2012

The Lagrangian vortex method offers an alternative numerical approach for direct numerical simulation of turbulence. The fact that it uses the fast multipole method (FMM)--a hierarchical algorithm for N-body problems with highly scalable parallel implementations--as numerical engine makes it a potentially good candidate for exascale systems. However, there have been few validation studies of Lagrangian vortex simulations and the insufficient comparisons against standard DNS codes has left ample room for skepticism. This paper presents a comparison between a Lagrangian vortex method and a pseudo-spectral method for the simulation of decaying homogeneous isotropic turbulence. This flow field is chosen despite the fact that it is not the most favorable flow problem for particle methods (which shine in wake flows or where vorticity is compact), due to the fact that it is ideal for the quantitative validation of DNS codes. We use a 256^3 grid with Re_lambda=50 and 100 and look at the turbulence statistics, including high-order moments. The focus is on the effect of the various parameters in the vortex method, e.g., order of FMM series expansion, frequency of reinitialization, overlap ratio and time step. The vortex method uses an FMM code (exaFMM) that runs on GPU hardware using CUDA, while the spectral code (hit3d) runs on CPU only. Results indicate that, for this application (and with the current code implementations), the spectral method is an order of magnitude faster than the vortex method when using a single GPU for the FMM and six CPU cores for the FFT.
Families of polytopal digraphs that do not satisfy the shelling property
Venue: arXiv cs.DM 2012
Year: 2012

A polytopal digraph $G(P)$ is an orientation of the skeleton of a convex polytope $P$. The possible non-degenerate pivot operations of the simplex method in solving a linear program over $P$ can be represented as a special polytopal digraph known as an LP digraph. Presently there is no general characterization of which polytopal digraphs are LP digraphs, although four necessary properties are known: acyclicity, unique sink orientation(USO), the Holt-Klee property and the shelling property. The shelling property was introduced by Avis and Moriyama (2009), where two examples are given in $d=4$ dimensions of polytopal digraphs satisfying the first three properties but not the shelling property. The smaller of these examples has $n=7$ vertices. Avis, Miyata and Moriyama(2009) constructed for each $d \ge 4$ and $n \ge d+2$, a $d$-polytope $P$ with $n$ vertices which has a polytopal digraph which is an acyclic USO that satisfies the Holt-Klee property, but does not satisfy the shelling property. The construction was based on a minimal such example, which has $d=4$ and $n=6$. In this paper we explore the shelling condition further. First we give an apparently stronger definition of the shelling property, which we then prove is equivalent to the original definition. Using this stronger condition we are able to give a more general construction of such families. In particular, we show that given any 4-dimensional polytope $P$ with $n_0$ vertices whose unique sink is simple, we can extend $P$ for any $d \ge 4$ and $n \ge n_0 + d-4$ to a $d$-polytope with these properties that has $n$ vertices. Finally we investigate the strength of the shelling condition for $d$-crosspolytopes, for which Develin (2004) has given a complete characterization of LP orientations.
Faster Energy Efficient Dadda Based Baugh-Wooley Multipliers
Venue: arXiv cs.AR 2012
Year: 2012

In this work faster Baugh-Wooley multiplication has been achieved by using a combination of two design techniques: partition of the partial products into two parts for independent parallel column compression and acceleration of the final addition using a hybrid adder proposed in this work. Based on the proposed techniques 8, 16, 32 and 64-bit Dadda based Baugh-Wooley multipliers has been developed and compared with the regular Baugh-Wooley multiplier. The performance of the proposed multiplier is analyzed by evaluating the delay, area and power, with 180 nm process technologies on interconnect and layout using industry standard design and layout tools. The result analysis shows that the 64-bit proposed multiplier is as much as 26.9% faster than the regular Baugh-Wooley multiplier and requires only 2.21% more power. Also the power-delay product of the proposed design is significantly lower than that of the regular Baugh-Wooley multiplier.
Period-halving Bifurcation of a Neuronal Recurrence Equation
Venue: arXiv cs.NE 2012
Year: 2012

We study the sequences generated by neuronal recurrence equations of the form $x(n) = {\bf 1}[\sum_{j=1}^{h} a_{j} x(n-j)- θ]$. From a neuronal recurrence equation of memory size $h$ which describes a cycle of length $ρ(m) \times lcm(p_0, p_1,..., p_{-1+ρ(m)})$, we construct a set of $ρ(m)$ neuronal recurrence equations whose dynamics describe respectively the transient of length $O(ρ(m) \times lcm(p_0, ..., p_{d}))$ and the cycle of length $O(ρ(m) \times lcm(p_{d+1}, ..., p_{-1+ρ(m)}))$ if $0 \leq d \leq -2+ρ(m)$ and 1 if $d=ρ(m)-1$. This result shows the exponential time of the convergence of neuronal recurrence equation to fixed points and the existence of the period-halving bifurcation.
Complexity of Ising Polynomials
Venue: arXiv cs.CC 2012
Year: 2012

This paper deals with the partition function of the Ising model from statistical mechanics, which is used to study phase transitions in physical systems. A special case of interest is that of the Ising model with constant energies and external field. One may consider such an Ising system as a simple graph together with vertex and edge weights. When these weights are considered indeterminates, the partition function for the constant case is a trivariate polynomial Z(G;x,y,z). This polynomial was studied with respect to its approximability by L. A. Goldberg, M. Jerrum and M. Paterson in 2003. Z(G;x,y,z) generalizes a bivariate polynomial Z(G;t,y), which was studied by D. Andrén and K. Markström in 2009. We consider the complexity of Z(G;t,y) and Z(G;x,y,z) in comparison to that of the Tutte polynomial, which is well-known to be closely related to the Potts model in the absence of an external field. We show that Z(G;\x,\y,\z) is #P-hard to evaluate at all points in $mathbb{Q}^3$, except those in an exception set of low dimension, even when restricted to simple graphs which are bipartite and planar. A counting version of the Exponential Time Hypothesis, #ETH, was introduced by H. Dell, T. Husfeldt and M. Wahlén in 2010 in order to study the complexity of the Tutte polynomial. In analogy to their results, we give a dichotomy theorem stating that evaluations of Z(G;t,y) either take exponential time in the number of vertices of $G$ to compute, or can be done in polynomial time. Finally, we give an algorithm for computing Z(G;x,y,z) in polynomial time on graphs of bounded clique-width, which is not known in the case of the Tutte polynomial.
Parameterized Complexity of Satisfying Almost All Linear Equations over $\mathbb{F}_2$
Venue: arXiv cs.CC 2012
Year: 2012

The problem MaxLin2 can be stated as follows. We are given a system $S$ of $m$ equations in variables $x_1,...,x_n$, where each equation is $\sum_{i \in I_j}x_i = b_j$ is assigned a positive integral weight $w_j$ and $x_i,b_j \in \mathbb{F}_2$, $I_j \subseteq \{1,2,...,n\}$ for $j=1,...,m$. We are required to find an assignment of values to the variables in order to maximize the total weight of the satisfied equations. Let $W$ be the total weight of all equations in $S$. We consider the following parameterized version of MaxLin2: decide whether there is an assignment satisfying equations of total weight at least $W-k$, where $k$ is a nonnegative parameter. We prove that this parameterized problem is W[1]-hard even if each equation of $S$ has exactly three variables and every variable appears in exactly three equations and, moreover, each weight $w_j$ equals 1 and no two equations have the same left-hand side. We show the tightness of this result by proving that if each equation has at most two variables then the parameterized problem is fixed-parameter tractable. We also prove that if no variable appears in more than two equations then we can maximize the total weight of satisfied equations in polynomial time.
Pointwise Relations between Information and Estimation in Gaussian Noise
Venue: arXiv cs.IT 2012
Year: 2012

Many of the classical and recent relations between information and estimation in the presence of Gaussian noise can be viewed as identities between expectations of random quantities. These include the I-MMSE relationship of Guo et al.; the relative entropy and mismatched estimation relationship of Verdú; the relationship between causal estimation and mutual information of Duncan, and its extension to the presence of feedback by Kadota et al.; the relationship between causal and non-casual estimation of Guo et al., and its mismatched version of Weissman. We dispense with the expectations and explore the nature of the pointwise relations between the respective random quantities. The pointwise relations that we find are as succinctly stated as - and give considerable insight into - the original expectation identities. As an illustration of our results, consider Duncan's 1970 discovery that the mutual information is equal to the causal MMSE in the AWGN channel, which can equivalently be expressed saying that the difference between the input-output information density and half the causal estimation error is a zero mean random variable (regardless of the distribution of the channel input). We characterize this random variable explicitly, rather than merely its expectation. Classical estimation and information theoretic quantities emerge with new and surprising roles. For example, the variance of this random variable turns out to be given by the causal MMSE (which, in turn, is equal to the mutual information by Duncan's result).
On a Bounded Budget Network Creation Game
Venue: arXiv cs.GT 2012
Year: 2012

We consider a network creation game in which each player (vertex) has a fixed budget to establish links to other players. In our model, each link has unit price and each agent tries to minimize its cost, which is either its local diameter or its total distance to other players in the (undirected) underlying graph of the created network. Two versions of the game are studied: in the MAX version, the cost incurred to a vertex is the maximum distance between the vertex and other vertices, and in the SUM version, the cost incurred to a vertex is the sum of distances between the vertex and other vertices. We prove that in both versions pure Nash equilibria exist, but the problem of finding the best response of a vertex is NP-hard. We take the social cost of the created network to be its diameter, and next we study the maximum possible diameter of an equilibrium graph with n vertices in various cases. When the sum of players' budgets is n-1, the equilibrium graphs are always trees, and we prove that their maximum diameter is Theta(n) and Theta(log n) in MAX and SUM versions, respectively. When each vertex has unit budget (i.e. can establish link to just one vertex), the diameter of any equilibrium graph in either version is Theta(1). We give examples of equilibrium graphs in the MAX version, such that all vertices have positive budgets and yet the diameter is Omega(sqrt(log n)). This interesting (and perhaps counter-intuitive) result shows that increasing the budgets may increase the diameter of equilibrium graphs and hence deteriorate the network structure. Then we prove that every equilibrium graph in the SUM version has diameter 2^O(sqrt(log n)). Finally, we show that if the budget of each player is at least k, then every equilibrium graph in the SUM version is k-connected or has diameter smaller than 4.
Regular Functions, Cost Register Automata, and Generalized Min-Cost Problems
Venue: arXiv cs.FL 2012
Year: 2012

Motivated by the successful application of the theory of regular languages to formal verification of finite-state systems, there is a renewed interest in developing a theory of analyzable functions from strings to numerical values that can provide a foundation for analyzing {\em quantitative} properties of finite-state systems. In this paper, we propose a deterministic model for associating costs with strings that is parameterized by operations of interest (such as addition, scaling, and $\min$), a notion of {\em regularity} that provides a yardstick to measure expressiveness, and study decision problems and theoretical properties of resulting classes of cost functions. Our definition of regularity relies on the theory of string-to-tree transducers, and allows associating costs with events that are conditional upon regular properties of future events. Our model of {\em cost register automata} allows computation of regular functions using multiple "write-only" registers whose values can be combined using the allowed set of operations. We show that classical shortest-path algorithms as well as algorithms designed for computing {\em discounted costs}, can be adopted for solving the min-cost problems for the more general classes of functions specified in our model. Cost register automata with $\min$ and increment give a deterministic model that is equivalent to {\em weighted automata}, an extensively studied nondeterministic model, and this connection results in new insights and new open problems.
Quantum/Relativistic Computation of Security and Efficiency of Electrical Power System for a Day-Ahead
Venue: arXiv cs.OH 2012
Year: 2012

An algorithm for Electric Power System (EPS) quantum/relativistic security and efficiency computation for a day-ahead via perturbative renormalization of the EPS, finding the computation flowcharts, verification and validation is built in this paper.
Sparse Differential Resultant for Laurent Differential Polynomials
Venue: arXiv cs.SC 2012
Year: 2012

In this paper, we first introduce the concept of Laurent differentially essential systems and give a criterion for Laurent differentially essential systems in terms of their supports. Then the sparse differential resultant for a Laurent differentially essential system is defined and its basic properties are proved. In particular, order and degree bounds for the sparse differential resultant are given. Based on these bounds, an algorithm to compute the sparse differential resultant is proposed, which is single exponential in terms of the number of indeterminates, the Jacobi number of the system, and the size of the system.
The Capacity Region of the Restricted Two-Way Relay Channel with Any Deterministic Uplink
Venue: arXiv cs.IT 2012
Year: 2012

This paper considers the two-way relay channel (TWRC) where two users communicate via a relay. For the restricted TWRC where the uplink from the users to the relay is any deterministic function and the downlink from the relay to the users is any arbitrary channel, the capacity region is obtained. The TWRC considered is restricted in the sense that each user can only transmit a function of its message.
Moderate-Deviations of Lossy Source Coding for Discrete and Gaussian Sources
Venue: arXiv cs.IT 2012
Year: 2012

We study the moderate-deviations (MD) setting for lossy source coding of stationary memoryless sources. More specifically, we derive fundamental compression limits of source codes whose rates are $R(D) \pm ε_n$, where $R(D)$ is the rate-distortion function and $ε_n$ is a sequence that dominates $\sqrt{1/n}$. This MD setting is complementary to the large-deviations and central limit settings and was studied by Altug and Wagner for the channel coding setting. We show, for finite alphabet and Gaussian sources, that as in the central limit-type results, the so-called dispersion for lossy source coding plays a fundamental role in the MD setting for the lossy source coding problem.
Improving broadcast channel rate using hierarchical modulation
Venue: arXiv cs.NI 2012
Year: 2012

We investigate the design of a broadcast system where the aim is to maximise the throughput. This task is usually challenging due to the channel variability. Modern satellite communications systems such as DVB-SH and DVB-S2 mainly rely on time sharing strategy to optimize throughput. They consider hierarchical modulation but only for unequal error protection or backward compatibility purposes. We propose in this article to combine time sharing and hierarchical modulation together and show how this scheme can improve the performance in terms of available rate. We present the gain on a simple channel modeling the broadcasting area of a satellite. Our work is applied to the DVB-SH standard, which considers hierarchical modulation as an optional feature.
On the Practicality of Atomic MWMR Register Implementations
Venue: arXiv cs.DC 2012
Year: 2012

Multiple-writer/multiple-reader (MWMR) atomic register implementations provide precise consistency guarantees, in the asynchronous, crash-prone, message passing environment. Fast MWMR atomic register implementations were first introduced in Englert et al. 2009. Fastness is measured in terms of the number of single round read and write operations that does not sacrifice correctness. In Georgiou et al. 2011 was shown, however, that decreasing the communication cost is not enough in these implementations. In particular, considering that the performance is measured in terms of the latency of read and write operations due to both (a) communication delays and (b)local computation, they introduced two new algorithms that traded communication for reducing computation. As computation is still part of the algorithms, someone may wonder: What is the trade-off between communication and local computation in real-time systems? In this work we conduct an experimental performance evaluation of four MWMR atomic register implementations: SFW from Englert et al. 2009, APRX-SFW and CWFR from Georgiou at al. 2011, and the generalization of the traditional algorithm of Attiya et al. 1996 in the MWMR environment, which we call SIMPLE. We implement and evaluate the algorithms on NS2, a single-processor simulator, and on PlanetLab, a planetary-scale real-time network platform. Our comparison provides an empirical answer to the above question and demonstrates the practicality of atomic MWMR register implementations.
Eigenvector Synchronization, Graph Rigidity and the Molecule Problem
Venue: arXiv cs.CE 2012
Year: 2012

The graph realization problem has received a great deal of attention in recent years, due to its importance in applications such as wireless sensor networks and structural biology. In this paper, we extend on previous work and propose the 3D-ASAP algorithm, for the graph realization problem in $\mathbb{R}^3$, given a sparse and noisy set of distance measurements. 3D-ASAP is a divide and conquer, non-incremental and non-iterative algorithm, which integrates local distance information into a global structure determination. Our approach starts with identifying, for every node, a subgraph of its 1-hop neighborhood graph, which can be accurately embedded in its own coordinate system. In the noise-free case, the computed coordinates of the sensors in each patch must agree with their global positioning up to some unknown rigid motion, that is, up to translation, rotation and possibly reflection. In other words, to every patch there corresponds an element of the Euclidean group Euc(3) of rigid transformations in $\mathbb{R}^3$, and the goal is to estimate the group elements that will properly align all the patches in a globally consistent way. Furthermore, 3D-ASAP successfully incorporates information specific to the molecule problem in structural biology, in particular information on known substructures and their orientation. In addition, we also propose 3D-SP-ASAP, a faster version of 3D-ASAP, which uses a spectral partitioning algorithm as a preprocessing step for dividing the initial graph into smaller subgraphs. Our extensive numerical simulations show that 3D-ASAP and 3D-SP-ASAP are very robust to high levels of noise in the measured distances and to sparse connectivity in the measurement graph, and compare favorably to similar state-of-the art localization algorithms.
An additivity theorem for plain Kolmogorov complexity
Venue: arXiv cs.CC 2012
Year: 2012

We prove the formula C(a,b) = K(a|C(a,b)) + C(b|a,C(a,b)) + O(1) that expresses the plain complexity of a pair in terms of prefix and plain conditional complexities of its components.