OpenRaiser/Intern-Atlas huggingface dataset:
On Inequalities Relating the Characteristic Function and Fisher Information
Venue: arXiv cs.IT 2010
Year: 2010

A relationship between the Fisher information and the characteristic function is established with the help of two inequalities. A necessary and sufficient condition for equality is found. These results are used to determine the asymptotic efficiency of a distributed estimation algorithm that uses constant modulus transmissions over Gaussian multiple access channels. The loss in efficiency of the distributed estimation scheme relative to the centralized approach is quantified for different sensing noise distributions. It is shown that the distributed estimator does not incur an efficiency loss if and only if the sensing noise distribution is Gaussian.
A Constant-Factor Approximation for Wireless Capacity Maximization with Power Control in the SINR Model
Venue: arXiv cs.NI 2010
Year: 2010

In modern wireless networks, devices are able to set the power for each transmission carried out. Experimental but also theoretical results indicate that such power control can improve the network capacity significantly. We study this problem in the physical interference model using SINR constraints. In the SINR capacity maximization problem, we are given n pairs of senders and receivers, located in a metric space (usually a so-called fading metric). The algorithm shall select a subset of these pairs and choose a power level for each of them with the objective of maximizing the number of simultaneous communications. This is, the selected pairs have to satisfy the SINR constraints with respect to the chosen powers. We present the first algorithm achieving a constant-factor approximation in fading metrics. The best previous results depend on further network parameters such as the ratio of the maximum and the minimum distance between a sender and its receiver. Expressed only in terms of n, they are (trivial) Omega(n) approximations. Our algorithm still achieves an O(log n) approximation if we only assume to have a general metric space rather than a fading metric. Furthermore, by using standard techniques the algorithm can also be used in single-hop and multi-hop scheduling scenarios. Here, we also get polylog(n) approximations.
Submodular Maximization by Simulated Annealing
Venue: arXiv cs.DS 2010
Year: 2010

We consider the problem of maximizing a nonnegative (possibly non-monotone) submodular set function with or without constraints. Feige et al. [FOCS'07] showed a 2/5-approximation for the unconstrained problem and also proved that no approximation better than 1/2 is possible in the value oracle model. Constant-factor approximation was also given for submodular maximization subject to a matroid independence constraint (a factor of 0.309 Vondrak [FOCS'09]) and for submodular maximization subject to a matroid base constraint, provided that the fractional base packing number is at least 2 (a 1/4-approximation, Vondrak [FOCS'09]). In this paper, we propose a new algorithm for submodular maximization which is based on the idea of {\em simulated annealing}. We prove that this algorithm achieves improved approximation for two problems: a 0.41-approximation for unconstrained submodular maximization, and a 0.325-approximation for submodular maximization subject to a matroid independence constraint. On the hardness side, we show that in the value oracle model it is impossible to achieve a 0.478-approximation for submodular maximization subject to a matroid independence constraint, or a 0.394-approximation subject to a matroid base constraint in matroids with two disjoint bases. Even for the special case of cardinality constraint, we prove it is impossible to achieve a 0.491-approximation. (Previously it was conceivable that a 1/2-approximation exists for these problems.) It is still an open question whether a 1/2-approximation is possible for unconstrained submodular maximization.
A tool stack for implementing Behaviour-Driven Development in Python Language
Venue: arXiv cs.SE 2010
Year: 2010

This paper presents a tool stack for the implementation, specification and test of software following the practices of Behavior Driven Development (BDD) in Python language. The usage of this stack highlights the specification and validation of the software's expected behavior, reducing the error rate and improving documentation. Therefore, it is possible to produce code with much less defects at both functional and unit levels, in addition to better serving to stakeholders' expectations.
Shannon Meets Nash on the Interference Channel
Venue: arXiv cs.IT 2010
Year: 2010

The interference channel is the simplest communication scenario where multiple autonomous users compete for shared resources. We combine game theory and information theory to define a notion of a Nash equilibrium region of the interference channel. The notion is game theoretic: it captures the selfish behavior of each user as they compete. The notion is also information theoretic: it allows each user to use arbitrary communication strategies as it optimizes its own performance. We give an exact characterization of the Nash equilibrium region of the two-user linear deterministic interference channel and an approximate characterization of the Nash equilibrium region of the two-user Gaussian interference channel to within 1 bit/s/Hz..
Discrete denoising of heterogenous two-dimensional data
Venue: arXiv cs.IT 2010
Year: 2010

We consider discrete denoising of two-dimensional data with characteristics that may be varying abruptly between regions. Using a quadtree decomposition technique and space-filling curves, we extend the recently developed S-DUDE (Shifting Discrete Universal DEnoiser), which was tailored to one-dimensional data, to the two-dimensional case. Our scheme competes with a genie that has access, in addition to the noisy data, also to the underlying noiseless data, and can employ $m$ different two-dimensional sliding window denoisers along $m$ distinct regions obtained by a quadtree decomposition with $m$ leaves, in a way that minimizes the overall loss. We show that, regardless of what the underlying noiseless data may be, the two-dimensional S-DUDE performs essentially as well as this genie, provided that the number of distinct regions satisfies $m=o(n)$, where $n$ is the total size of the data. The resulting algorithm complexity is still linear in both $n$ and $m$, as in the one-dimensional case. Our experimental results show that the two-dimensional S-DUDE can be effective when the characteristics of the underlying clean image vary across different regions in the data.
On the Capacity of a Class of Cognitive Z-interference Channels
Venue: arXiv cs.IT 2010
Year: 2010

We study a special class of the cognitive radio channel in which the receiver of the cognitive pair does not suffer interference from the primary user. Previously developed general encoding schemes for this channel are complex as they attempt to cope with arbitrary channel conditions, which leads to rate regions that are difficult to evaluate. The focus of our work is to derive simple rate regions that are easily computable, thereby providing more insights into achievable rates and good coding strategies under different channel conditions. We first present several explicit achievable regions for the general discrete memoryless case. We also present an improved outer bound on the capacity region for the case of high interference. We then extend these regions to Gaussian channels. With a simple outer bound we establish a new capacity region in the high-interference regime. Lastly, we provide numerical comparisons between the derived achievable rate regions and the outer bounds.
Acyclic Edge Coloring of Triangle Free Planar Graphs
Venue: arXiv cs.DM 2010
Year: 2010

An $acyclic$ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The \emph{acyclic chromatic index} of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by $a'(G)$. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that $a'(G)\le Δ+2$, where $Δ=Δ(G)$ denotes the maximum degree of the graph. If every induced subgraph $H$ of $G$ satisfies the condition $\vert E(H) \vert \le 2\vert V(H) \vert -1$, we say that the graph $G$ satisfies $Property\ A$. In this paper, we prove that if $G$ satisfies $Property\ A$, then $a'(G)\le Δ+ 3$. Triangle free planar graphs satisfy $Property\ A$. We infer that $a'(G)\le Δ+ 3$, if $G$ is a triangle free planar graph. Another class of graph which satisfies $Property\ A$ is 2-fold graphs (union of two forests).
Is Content Publishing in BitTorrent Altruistic or Profit-Driven
Venue: arXiv cs.NI 2010
Year: 2010

BitTorrent is the most popular P2P content delivery application where individual users share various type of content with tens of thousands of other users. The growing popularity of BitTorrent is primarily due to the availability of valuable content without any cost for the consumers. However, apart from required resources, publishing (sharing) valuable (and often copyrighted) content has serious legal implications for user who publish the material (or publishers). This raises a question that whether (at least major) content publishers behave in an altruistic fashion or have other incentives such as financial. In this study, we identify the content publishers of more than 55k torrents in 2 major BitTorrent portals and examine their behavior. We demonstrate that a small fraction of publishers are responsible for 66% of published content and 75% of the downloads. Our investigations reveal that these major publishers respond to two different profiles. On one hand, antipiracy agencies and malicious publishers publish a large amount of fake files to protect copyrighted content and spread malware respectively. On the other hand, content publishing in BitTorrent is largely driven by companies with financial incentive. Therefore, if these companies lose their interest or are unable to publish content, BitTorrent traffic/portals may disappear or at least their associated traffic will significantly reduce.
Neural Network Based Reconstruction of a 3D Object from a 2D Wireframe
Venue: arXiv cs.CV 2010
Year: 2010

We propose a new approach for constructing a 3D representation from a 2D wireframe drawing. A drawing is simply a parallel projection of a 3D object onto a 2D surface; humans are able to recreate mental 3D models from 2D representations very easily, yet the process is very difficult to emulate computationally. We hypothesize that our ability to perform this construction relies on the angles in the 2D scene, among other geometric properties. Being able to reproduce this reconstruction process automatically would allow for efficient and robust 3D sketch interfaces. Our research focuses on the relationship between 2D geometry observable in the sketch and 3D geometry derived from a potential 3D construction. We present a fully automated system that constructs 3D representations from 2D wireframes using a neural network in conjunction with a genetic search algorithm.
Extension of Stanley's Theorem for Partitions
Venue: arXiv cs.DM 2010
Year: 2010

In this paper we present an extension of Stanley's theorem related to partitions of positive integers. Stanley's theorem states a relation between "the sum of the numbers of distinct members in the partitions of a positive integer $n$" and "the total number of 1's that occur in the partitions of $n$". Our generalization states a similar relation between "the sum of the numbers of distinct members in the partitions of $n$" and the total number of 2's or 3's or any general $k$ that occur in the partitions of $n$ and the subsequent integers. We also apply this result to obtain an array of interesting corollaries, including alternate proofs and analogues of some of the very well-known results in the theory of partitions. We extend Ramanujan's results on congruence behavior of the 'number of partition' function $p(n)$ to get analogous results for the 'number of occurrences of an element $k$ in partitions of $n$'. Moreover, we present an alternate proof of Ramanujan's results in this paper.
On k-Convex Polygons
Venue: arXiv cs.CG 2010
Year: 2010

We introduce a notion of $k$-convexity and explore polygons in the plane that have this property. Polygons which are \mbox{$k$-convex} can be triangulated with fast yet simple algorithms. However, recognizing them in general is a 3SUM-hard problem. We give a characterization of \mbox{$2$-convex} polygons, a particularly interesting class, and show how to recognize them in \mbox{$O(n \log n)$} time. A description of their shape is given as well, which leads to Erdős-Szekeres type results regarding subconfigurations of their vertex sets. Finally, we introduce the concept of generalized geometric permutations, and show that their number can be exponential in the number of \mbox{$2$-convex} objects considered.
(n,K)-user Interference Channels: Degrees of Freedom
Venue: arXiv cs.IT 2010
Year: 2010

We analyze the gains of opportunistic communication in multiuser interference channels. Consider a fully connected $n$-user Gaussian interference channel. At each time instance only $K\leq n$ transmitters are allowed to be communicating with their respective receivers and the remaining $(n-K)$ transmitter-receiver pairs remain inactive. For finite $n$, if the transmitters can acquire channel state information (CSI) and if all channel gains are bounded away from zero and infinity, the seminal results on interference alignment establish that for any $K$ {\em arbitrary} active pairs the total number of spatial degrees of freedom per orthogonal time and frequency domain is $\frac{K}{2}$. Also it is noteworthy that without transmit-side CSI the interference channel becomes interference-limited and the degrees of freedom is 0. In {\em dense} networks ($n\rightarrow\infty$), however, as the size of the network increase, it becomes less likely to sustain the bounding conditions on the channel gains. By exploiting this fact, we show that when $n$ obeys certain scaling laws, by {\em opportunistically} and {\em dynamically} selecting the $K$ active pairs at each time instance, the number of degrees of freedom can exceed $\frac{K}{2}$ and in fact can be made arbitrarily close to $K$. More specifically when all transmitters and receivers are equipped with one antenna, then the network size scaling as $n\inω(\snr^{d(K-1)})$ is a {\em sufficient} condition for achieving $d\in[0,K]$ degrees of freedom. Moreover, achieving these degrees of freedom does not necessitate the transmitters to acquire channel state information. Hence, invoking opportunistic communication in the context of interference channels leads to achieving higher degrees of freedom that are not achievable otherwise.
Development of three dimensional constitutive theories based on lower dimensional experimental data
Venue: arXiv cs.NA 2010
Year: 2010

Most three dimensional constitutive relations that have been developed to describe the behavior of bodies are correlated against one dimensional and two dimensional experiments. What is usually lost sight of is the fact that infinity of such three dimensional models may be able to explain these experiments that are lower dimensional. Recently, the notion of maximization of the rate of entropy production has been used to obtain constitutive relations based on the choice of the stored energy and rate of entropy production, etc. In this paper we show different choices for the manner in which the body stores energy and dissipates energy and satisfies the requirement of maximization of the rate of entropy production that leads to many three dimensional models. All of these models, in one dimension, reduce to the model proposed by Burgers to describe the viscoelastic behavior of bodies.
Expressiveness and Closure Properties for Quantitative Languages
Venue: arXiv cs.LO 2010
Year: 2010

Weighted automata are nondeterministic automata with numerical weights on transitions. They can define quantitative languages~$L$ that assign to each word~$w$ a real number~$L(w)$. In the case of infinite words, the value of a run is naturally computed as the maximum, limsup, liminf, limit-average, or discounted-sum of the transition weights. The value of a word $w$ is the supremum of the values of the runs over $w$. We study expressiveness and closure questions about these quantitative languages. We first show that the set of words with value greater than a threshold can be non-$ω$-regular for deterministic limit-average and discounted-sum automata, while this set is always $ω$-regular when the threshold is isolated (i.e., some neighborhood around the threshold contains no word). In the latter case, we prove that the $ω$-regular language is robust against small perturbations of the transition weights. We next consider automata with transition weights Weighted automata are nondeterministic automata with numerical weights ontransitions. They can define quantitative languages~$L$ that assign to eachword~$w$ a real number~$L(w)$. In the case of infinite words, the value of arun is naturally computed as the maximum, limsup, liminf, limit-average, ordiscounted-sum of the transition weights. The value of a word $w$ is thesupremum of the values of the runs over $w$. We study expressiveness andclosure questions about these quantitative languages. We first show that the set of words with value greater than a threshold canbe non-$ω$-regular for deterministic limit-average and discounted-sumautomata, while this set is always $ω$-regular when the threshold isisolated (i.e., some neighborhood around the threshold contains no word). Inthe latter case, we prove that the $ω$-regular language is robust againstsmall perturbations of the transition weights. We next consider automata with transition weights $0$ or $1$ and show thatthey are as expressive as general weighted automata in the limit-average case,but not in the discounted-sum case. Third, for quantitative languages $L_1$ and~$L_2$, we consider the operations$\max(L_1,L_2)$, $\min(L_1,L_2)$, and $1-L_1$, which generalize the booleanoperations on languages, as well as the sum $L_1 + L_2$. We establish theclosure properties of all classes of quantitative languages with respect tothese four operations.$ or $ and show that they are as expressive as general weighted automata in the limit-average case, but not in the discounted-sum case. Third, for quantitative languages $L_1$ and~$L_2$, we consider the operations $\max(L_1,L_2)$, $\min(L_1,L_2)$, and -L_1$, which generalize the boolean operations on languages, as well as the sum $L_1 + L_2$. We establish the closure properties of all classes of quantitative languages with respect to these four operations.
Precise, Scalable and Online Request Tracing for Multi-tier Services of Black Boxes
Venue: arXiv cs.DC 2010
Year: 2010

As more and more multi-tier services are developed from commercial off-the-shelf components or heterogeneous middleware without source code available, both developers and administrators need a request tracing tool to (1) exactly know how a user request of interest travels through services of black boxes; (2) obtain macro-level user request behavior information of services without the necessity of inundating within massive logs. Previous research efforts either accept imprecision of probabilistic correlation methods or present precise but unscalable tracing approaches that have to collect and analyze large amount of logs; Besides, previous precise request tracing approaches of black boxes fail to propose macro-level abstractions that enables debugging performance-in-the-large, and hence users have to manually interpret massive logs. This paper introduces a precise, scalable and online request tracing tool, named PreciseTracer, for multi-tier services of black boxes. Our contributions are four-fold: first, we propose a precise request tracing algorithm for multi-tier services of black boxes, which only uses application-independent knowledge; second, we respectively present micro-level and macro-level abstractions: component activity graphs and dominated causal path patterns to represent causal paths of each individual request and repeatedly executed causal paths that account for significant fractions; third, we present two mechanisms: tracing on demand and sampling to significantly increase system scalability; fourth, we design and implement an online request tracing tool. PreciseTracer's fast response, low overhead and scalability make it a promising tracing tool for large-scale production systems.
The multiobjective multidimensional knapsack problem: a survey and a new approach
Venue: arXiv cs.DM 2010
Year: 2010

The knapsack problem (KP) and its multidimensional version (MKP) are basic problems in combinatorial optimization. In this paper we consider their multiobjective extension (MOKP and MOMKP), for which the aim is to obtain or to approximate the set of efficient solutions. In a first step, we classify and describe briefly the existing works, that are essentially based on the use of metaheuristics. In a second step, we propose the adaptation of the two-phase Pareto local search (2PPLS) to the resolution of the MOMKP. With this aim, we use a very-large scale neighborhood (VLSN) in the second phase of the method, that is the Pareto local search. We compare our results to state-of-the-art results and we show that we obtain results never reached before by heuristics, for the biobjective instances. Finally we consider the extension to three-objective instances.
Dynamic monopolies with randomized starting configuration
Venue: arXiv cs.DM 2010
Year: 2010

Properties of systems with majority voting rules have been exhaustingly studied. In this work we focus on the randomized case - where the system is initialized by randomized initial set of seeds. Our main aim is to give an asymptotic estimate for sampling probability, such that the initial set of seeds is (is not) a dynamic monopoly almost surely. After presenting some trivial examples, we present exhaustive results for toroidal mesh and random 4-regular graph under simple majority scenario.
Breaking Symmetries
Venue: arXiv cs.LO 2010
Year: 2010

A well-known result by Palamidessi tells us that πmix (the π-calculus with mixed choice) is more expressive than πsep (its subset with only separate choice). The proof of this result argues with their different expressive power concerning leader election in symmetric networks. Later on, Gorla of- fered an arguably simpler proof that, instead of leader election in symmetric networks, employed the reducibility of "incestual" processes (mixed choices that include both enabled senders and receivers for the same channel) when running two copies in parallel. In both proofs, the role of breaking (ini- tial) symmetries is more or less apparent. In this paper, we shed more light on this role by re-proving the above result-based on a proper formalization of what it means to break symmetries-without referring to another layer of the distinguishing problem domain of leader election. Both Palamidessi and Gorla rephrased their results by stating that there is no uniform and reason- able encoding from πmix into πsep . We indicate how the respective proofs can be adapted and exhibit the consequences of varying notions of uniformity and reasonableness. In each case, the ability to break initial symmetries turns out to be essential.