OpenRaiser/Intern-Atlas huggingface dataset:
Transmission of non-linear binary input functions over a CDMA System
Venue: arXiv cs.IT 2012
Year: 2012

We study the problem of transmission of binary input non-linear functions over a network of mobiles based on CDMA. Motivation for this study comes from the application of using cheap measurement devices installed on personal cell-phones to monitor environmental parameters such as air pollution, temperature and noise level. Our model resembles the MAC model of Nazer and Gastpar except that the encoders are restricted to be CDMA encoders. Unlike the work of Nazer and Gastpar whose main attention is transmission of linear functions, we deal with non-linear functions with binary inputs. A main contribution of this paper is a lower bound on the computational capacity for this problem. While in the traditional CDMA system the signature matrix of the CDMA system preferably has independent rows, in our setup the signature matrix of the CDMA system is viewed as the parity check matrix of a linear code, reflecting our treatment of the interference.
Optimal antithickenings of claw-free trigraphs
Venue: arXiv cs.DM 2012
Year: 2012

Chudnovsky and Seymour's structure theorem for claw-free graphs has led to a multitude of recent results that exploit two structural operations: {\em compositions of strips} and {\em thickenings}. In this paper we consider the latter, proving that every claw-free graph has a unique optimal {\em antithickening}, where our definition of {\em optimal} is chosen carefully to respect the structural foundation of the graph. Furthermore, we give an algorithm to find the optimal antithickening in $O(m^2)$ time. For the sake of both completeness and ease of proof, we prove stronger results in the more general setting of trigraphs.
Mapping (USPTO) Patent Data using Overlays to Google Maps
Venue: arXiv cs.CY 2012
Year: 2012

A technique is developed using patent information available online (at the US Patent and Trademark Office) for the generation of Google Maps. The overlays indicate both the quantity and quality of patents at the city level. This information is relevant for research questions in technology analysis, innovation studies and evolutionary economics, as well as economic geography. The resulting maps can also be relevant for technological innovation policies and R&D management, because the US market can be considered the leading market for patenting and patent competition. In addition to the maps, the routines provide quantitative data about the patents for statistical analysis. The cities on the map are colored according to the results of significance tests. The overlays are explored for the Netherlands as a "national system of innovations," and further elaborated in two cases of emerging technologies: "RNA interference" and "nanotechnology."
Making triangulations 4-connected using flips
Venue: arXiv cs.CG 2012
Year: 2012

We show that any combinatorial triangulation on n vertices can be transformed into a 4-connected one using at most floor((3n - 9)/5) edge flips. We also give an example of an infinite family of triangulations that requires this many flips to be made 4-connected, showing that our bound is tight. In addition, for n >= 19, we improve the upper bound on the number of flips required to transform any 4-connected triangulation into the canonical triangulation (the triangulation with two dominant vertices), matching the known lower bound of 2n - 15. Our results imply a new upper bound on the diameter of the flip graph of 5.2n - 33.6, improving on the previous best known bound of 6n - 30.
The Binary Perfect Phylogeny with Persistent characters
Venue: arXiv cs.DS 2012
Year: 2012

The binary perfect phylogeny model is too restrictive to model biological events such as back mutations. In this paper we consider a natural generalization of the model that allows a special type of back mutation. We investigate the problem of reconstructing a near perfect phylogeny over a binary set of characters where characters are persistent: characters can be gained and lost at most once. Based on this notion, we define the problem of the Persistent Perfect Phylogeny (referred as P-PP). We restate the P-PP problem as a special case of the Incomplete Directed Perfect Phylogeny, called Incomplete Perfect Phylogeny with Persistent Completion, (refereed as IP-PP), where the instance is an incomplete binary matrix M having some missing entries, denoted by symbol ?, that must be determined (or completed) as 0 or 1 so that M admits a binary perfect phylogeny. We show that the IP-PP problem can be reduced to a problem over an edge colored graph since the completion of each column of the input matrix can be represented by a graph operation. Based on this graph formulation, we develop an exact algorithm for solving the P-PP problem that is exponential in the number of characters and polynomial in the number of species.
Information Spreading in Dynamic Graphs
Venue: arXiv cs.DM 2012
Year: 2012

We present a general approach to study the flooding time (a measure of how fast information spreads) in dynamic graphs (graphs whose topology changes with time according to a random process). We consider arbitrary converging Markovian dynamic graph process, that is, processes in which the topology of the graph at time $t$ depends only on its topology at time $t-1$ and which have a unique stationary distribution. The most well studied models of dynamic graphs are all Markovian and converging. Under general conditions, we bound the flooding time in terms of the mixing time of the dynamic graph process. We recover, as special cases of our result, bounds on the flooding time for the \emph{random trip} model and the \emph{random path} models; previous analysis techniques provided bounds only in restricted settings for such models. Our result also provides the first bound for the \emph{random waypoint} model (which is tight for certain ranges of parameters) whose analysis had been an important open question.
Symmetrical Multilevel Diversity Coding and Subset Entropy Inequalities
Venue: arXiv cs.IT 2012
Year: 2012

Symmetrical multilevel diversity coding (SMDC) is a classical model for coding over distributed storage. In this setting, a simple separate encoding strategy known as superposition coding was shown to be optimal in terms of achieving the minimum sum rate (Roche, Yeung, and Hau, 1997) and the entire admissible rate region (Yeung and Zhang, 1999) of the problem. The proofs utilized carefully constructed induction arguments, for which the classical subset entropy inequality of Han (1978) played a key role. This paper includes two parts. In the first part the existing optimality proofs for classical SMDC are revisited, with a focus on their connections to subset entropy inequalities. First, a new sliding-window subset entropy inequality is introduced and then used to establish the optimality of superposition coding for achieving the minimum sum rate under a weaker source-reconstruction requirement. Second, a subset entropy inequality recently proved by Madiman and Tetali (2010) is used to develop a new structural understanding to the proof of Yeung and Zhang on the optimality of superposition coding for achieving the entire admissible rate region. Building on the connections between classical SMDC and the subset entropy inequalities developed in the first part, in the second part the optimality of superposition coding is further extended to the cases where there is either an additional all-access encoder (SMDC-A) or an additional secrecy constraint (S-SMDC).
On the Value of Job Migration in Online Makespan Minimization
Venue: arXiv cs.DS 2012
Year: 2012

Makespan minimization on identical parallel machines is a classical scheduling problem. We consider the online scenario where a sequence of $n$ jobs has to be scheduled non-preemptively on $m$ machines so as to minimize the maximum completion time of any job. The best competitive ratio that can be achieved by deterministic online algorithms is in the range $[1.88,1.9201]$. Currently no randomized online algorithm with a smaller competitiveness is known, for general $m$. In this paper we explore the power of job migration, i.e.\ an online scheduler is allowed to perform a limited number of job reassignments. Migration is a common technique used in theory and practice to balance load in parallel processing environments. As our main result we settle the performance that can be achieved by deterministic online algorithms. We develop an algorithm that is $α_m$-competitive, for any $m\geq 2$, where $α_m$ is the solution of a certain equation. For $m=2$, $α_2 = 4/3$ and $\lim_{m\rightarrow \infty} α_m = W_{-1}(-1/e^2)/(1+ W_{-1}(-1/e^2)) \approx 1.4659$. Here $W_{-1}$ is the lower branch of the Lambert $W$ function. For $m\geq 11$, the algorithm uses at most $7m$ migration operations. For smaller $m$, $8m$ to $10m$ operations may be performed. We complement this result by a matching lower bound: No online algorithm that uses $o(n)$ job migrations can achieve a competitive ratio smaller than $α_m$. We finally trade performance for migrations. We give a family of algorithms that is $c$-competitive, for any $5/3\leq c \leq 2$. For $c= 5/3$, the strategy uses at most $4m$ job migrations. For $c=1.75$, at most $2.5m$ migrations are used.
Towards Analyzing Crossover Operators in Evolutionary Search via General Markov Chain Switching Theorem
Venue: arXiv cs.NE 2012
Year: 2012

Evolutionary algorithms (EAs), simulating the evolution process of natural species, are used to solve optimization problems. Crossover (also called recombination), originated from simulating the chromosome exchange phenomena in zoogamy reproduction, is widely employed in EAs to generate offspring solutions, of which the effectiveness has been examined empirically in applications. However, due to the irregularity of crossover operators and the complicated interactions to mutation, crossover operators are hard to analyze and thus have few theoretical results. Therefore, analyzing crossover not only helps in understanding EAs, but also helps in developing novel techniques for analyzing sophisticated metaheuristic algorithms. In this paper, we derive the General Markov Chain Switching Theorem (GMCST) to facilitate theoretical studies of crossover-enabled EAs. The theorem allows us to analyze the running time of a sophisticated EA from an easy-to-analyze EA. Using this tool, we analyze EAs with several crossover operators on the LeadingOnes and OneMax problems, which are noticeably two well studied problems for mutation-only EAs but with few results for crossover-enabled EAs. We first derive the bounds of running time of the (2+2)-EA with crossover operators; then we study the running time gap between the mutation-only (2:2)-EA and the (2:2)-EA with crossover operators; finally, we develop strategies that apply crossover operators only when necessary, which improve from the mutation-only as well as the crossover-all-the-time (2:2)-EA. The theoretical results are verified by experiments.
A scheme to protect against multiple quantum erasures
Venue: arXiv cs.IT 2012
Year: 2012

We present a scheme able to protect k >= 3 qubits of information against the occurrence of multiple erasures, based on the code proposed by Yang et al. (2004 JETP Letters 79 236). In this scheme redundant blocks are used and we restrict to the case that each erasure must occur in distinct blocks. We explicitly characterize the encoding operation and the restoring operation required to implement this scheme. The operators used in these operations can be adjusted to construct different quantum erasure-correcting codes. A special feature of this scheme is that no measurement is required. To illustrate our scheme, we present an example in which five-qubits of information are protected against the occurrence of two erasures.
Flow Computations on Imprecise Terrains
Venue: arXiv cs.CG 2012
Year: 2012

We study the computation of the flow of water on imprecise terrains. We consider two approaches to modeling flow on a terrain: one where water flows across the surface of a polyhedral terrain in the direction of steepest descent, and one where water only flows along the edges of a predefined graph, for example a grid or a triangulation. In both cases each vertex has an imprecise elevation, given by an interval of possible values, while its (x,y)-coordinates are fixed. For the first model, we show that the problem of deciding whether one vertex may be contained in the watershed of another is NP-hard. In contrast, for the second model we give a simple O(n log n) time algorithm to compute the minimal and the maximal watershed of a vertex, where n is the number of edges of the graph. On a grid model, we can compute the same in O(n) time.
Improved Bound for the Nystrom's Method and its Application to Kernel Classification
Venue: arXiv cs.LG 2012
Year: 2012

We develop two approaches for analyzing the approximation error bound for the Nyström method, one based on the concentration inequality of integral operator, and one based on the compressive sensing theory. We show that the approximation error, measured in the spectral norm, can be improved from $O(N/\sqrt{m})$ to $O(N/m^{1 - ρ})$ in the case of large eigengap, where $N$ is the total number of data points, $m$ is the number of sampled data points, and $ρ\in (0, 1/2)$ is a positive constant that characterizes the eigengap. When the eigenvalues of the kernel matrix follow a $p$-power law, our analysis based on compressive sensing theory further improves the bound to $O(N/m^{p - 1})$ under an incoherence assumption, which explains why the Nyström method works well for kernel matrix with skewed eigenvalues. We present a kernel classification approach based on the Nyström method and derive its generalization performance using the improved bound. We show that when the eigenvalues of kernel matrix follow a $p$-power law, we can reduce the number of support vectors to $N^{2p/(p^2 - 1)}$, a number less than $N$ when $p > 1+\sqrt{2}$, without seriously sacrificing its generalization performance.
Large-scale games in large-scale systems
Venue: arXiv cs.SY 2012
Year: 2012

Many real-world problems modeled by stochastic games have huge state and/or action spaces, leading to the well-known curse of dimensionality. The complexity of the analysis of large-scale systems is dramatically reduced by exploiting mean field limit and dynamical system viewpoints. Under regularity assumptions and specific time-scaling techniques, the evolution of the mean field limit can be expressed in terms of deterministic or stochastic equation or inclusion (difference or differential). In this paper, we overview recent advances of large-scale games in large-scale systems. We focus in particular on population games, stochastic population games and mean field stochastic games. Considering long-term payoffs, we characterize the mean field systems using Bellman and Kolmogorov forward equations.
Full-Duplex MIMO Relaying: Achievable Rates under Limited Dynamic Range
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we consider the problem of full-duplex multiple-input multiple-output (MIMO) relaying between multi-antenna source and destination nodes. The principal difficulty in implementing such a system is that, due to the limited attenuation between the relay's transmit and receive antenna arrays, the relay's outgoing signal may overwhelm its limited-dynamic-range input circuitry, making it difficult---if not impossible---to recover the desired incoming signal. While explicitly modeling transmitter/receiver dynamic-range limitations and channel estimation error, we derive tight upper and lower bounds on the end-to-end achievable rate of decode-and-forward-based full-duplex MIMO relay systems, and propose a transmission scheme based on maximization of the lower bound. The maximization requires us to (numerically) solve a nonconvex optimization problem, for which we detail a novel approach based on bisection search and gradient projection. To gain insights into system design tradeoffs, we also derive an analytic approximation to the achievable rate and numerically demonstrate its accuracy. We then study the behavior of the achievable rate as a function of signal-to-noise ratio, interference-to-noise ratio, transmitter/receiver dynamic range, number of antennas, and training length, using optimized half-duplex signaling as a baseline.
From Caesar to Twitter: An Axiomatic Approach to Elites of Social Networks
Venue: arXiv cs.SI 2012
Year: 2012

In many societies there is an elite, a relatively small group of powerful individuals that is well-connected and highly influential. Since the ancient days of Julius Caesar's senate of Rome to the recent days of celebrities on Twitter, the size of the elite is a result of conflicting social forces competing to increase or decrease it. The main contribution of this paper is the answer to the question how large the elite is at equilibrium. We take an axiomatic approach to solve this: assuming that an elite exists and it is influential, stable and either minimal or dense, we prove that its size must be $Θ(\sqrt{m})$ (where $m$ is the number of edges in the network). As an approximation for the elite, we then present an empirical study on nine large real-world networks of the subgraph formed by the highest degree nodes, also known as the rich-club. Our findings indicate that elite properties such as disproportionate influence, stability and density of $Θ(\sqrt{m})$-rich-clubs are universal properties and should join a growing list of common phenomena shared by social networks and complex systems such as "small world," power law degree distributions, high clustering, etc.
Higher-order Erdos--Szekeres theorems
Venue: arXiv cs.CG 2012
Year: 2012

Let P=(p_1,p_2,...,p_N) be a sequence of points in the plane, where p_i=(x_i,y_i) and x_1<x_2<...<x_N. A famous 1935 Erdos--Szekeres theorem asserts that every such P contains a monotone subsequence S of $\sqrt N$ points. Another, equally famous theorem from the same paper implies that every such P contains a convex or concave subsequence of $Ω(\log N)$ points. Monotonicity is a property determined by pairs of points, and convexity concerns triples of points. We propose a generalization making both of these theorems members of an infinite family of Ramsey-type results. First we define a (k+1)-tuple $K\subseteq P$ to be positive if it lies on the graph of a function whose kth derivative is everywhere nonnegative, and similarly for a negative (k+1)-tuple. Then we say that $S\subseteq P$ is kth-order monotone if its (k+1)-tuples are all positive or all negative. We investigate quantitative bound for the corresponding Ramsey-type result (i.e., how large kth-order monotone subsequence can be guaranteed in every N-point P). We obtain an $Ω(\log^{(k-1)}N)$ lower bound ((k-1)-times iterated logarithm). This is based on a quantitative Ramsey-type theorem for what we call transitive colorings of the complete (k+1)-uniform hypergraph; it also provides a unified view of the two classical Erdos--Szekeres results mentioned above. For k=3, we construct a geometric example providing an $O(\log\log N)$ upper bound, tight up to a multiplicative constant. As a consequence, we obtain similar upper bounds for a Ramsey-type theorem for order-type homogeneous subsets in R^3, as well as for a Ramsey-type theorem for hyperplanes in R^4 recently used by Dujmovic and Langerman.
Minimum degree, independence number and pseudo [2,b]-factors in graphs
Venue: arXiv cs.DM 2012
Year: 2012

A pseudo [2,b]-factor of a graph G is a spanning subgraph in which each component C on at least three vertices is a [2,b]-graph. The main contibution of this paper, is to give an upper bound to the number of components that are edges or vertices in a pseudo [2,b]-factor of a graph G. This bound is sharp.
Recipe recommendation using ingredient networks
Venue: arXiv cs.SI 2012
Year: 2012

The recording and sharing of cooking recipes, a human activity dating back thousands of years, naturally became an early and prominent social use of the web. The resulting online recipe collections are repositories of ingredient combinations and cooking methods whose large-scale and variety yield interesting insights about both the fundamentals of cooking and user preferences. At the level of an individual ingredient we measure whether it tends to be essential or can be dropped or added, and whether its quantity can be modified. We also construct two types of networks to capture the relationships between ingredients. The complement network captures which ingredients tend to co-occur frequently, and is composed of two large communities: one savory, the other sweet. The substitute network, derived from user-generated suggestions for modifications, can be decomposed into many communities of functionally equivalent ingredients, and captures users' preference for healthier variants of a recipe. Our experiments reveal that recipe ratings can be well predicted with features derived from combinations of ingredient networks and nutrition information.
Unpredictability and Computational Irreducibility
Venue: arXiv cs.CC 2012
Year: 2012

We explore several concepts for analyzing the intuitive notion of computational irreducibility and we propose a robust formal definition, first in the field of cellular automata and then in the general field of any computable function f from N to N. We prove that, through a robust definition of what means "to be unable to compute the nth step without having to follow the same path than simulating the automaton or the function", this implies genuinely, as intuitively expected, that if the behavior of an object is computationally irreducible, no computation of its nth state can be faster than the simulation itself.
Compressed Sensing with General Frames via Optimal-dual-based $\ell_1$-analysis
Venue: arXiv cs.IT 2012
Year: 2012

Compressed sensing with sparse frame representations is seen to have much greater range of practical applications than that with orthonormal bases. In such settings, one approach to recover the signal is known as $\ell_1$-analysis. We expand in this article the performance analysis of this approach by providing a weaker recovery condition than existing results in the literature. Our analysis is also broadly based on general frames and alternative dual frames (as analysis operators). As one application to such a general-dual-based approach and performance analysis, an optimal-dual-based technique is proposed to demonstrate the effectiveness of using alternative dual frames as analysis operators. An iterative algorithm is outlined for solving the optimal-dual-based $\ell_1$-analysis problem. The effectiveness of the proposed method and algorithm is demonstrated through several experiments.
Ground interpolation for the theory of equality
Venue: arXiv cs.LO 2012
Year: 2012

Theory interpolation has found several successful applications in model checking. We present a novel method for computing interpolants for ground formulas in the theory of equality. The method produces interpolants from colored congruence graphs representing derivations in that theory. These graphs can be produced by conventional congruence closure algorithms in a straightforward manner. By working with graphs, rather than at the level of individual proof steps, we are able to derive interpolants that are pleasingly simple (conjunctions of Horn clauses) and smaller than those generated by other tools. Our interpolation method can be seen as a theory-specific implementation of a cooperative interpolation game between two provers. We present a generic version of the interpolation game, parametrized by the theory T, and define a general method to extract runs of the game from proofs in T and then generate interpolants from these runs.