OpenRaiser/Intern-Atlas huggingface dataset:
Sublinear Time Algorithms for Earth Mover's Distance
Venue: arXiv cs.DS 2009
Year: 2009

We study the problem of estimating the Earth Mover's Distance (EMD) between probability distributions when given access only to samples. We give closeness testers and additive-error estimators over domains in $[0, Δ]^d$, with sample complexities independent of domain size - permitting the testability even of continuous distributions over infinite domains. Instead, our algorithms depend on other parameters, such as the diameter of the domain space, which may be significantly smaller. We also prove lower bounds showing the dependencies on these parameters to be essentially optimal. Additionally, we consider whether natural classes of distributions exist for which there are algorithms with better dependence on the dimension, and show that for highly clusterable data, this is indeed the case. Lastly, we consider a variant of the EMD, defined over tree metrics instead of the usual L1 metric, and give optimal algorithms.
Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families
Venue: arXiv cs.DS 2009
Year: 2009

Star-shaped bodies are an important nonconvex generalization of convex bodies (e.g., linear programming with violations). Here we present an efficient algorithm for sampling a given star-shaped body. The complexity of the algorithm grows polynomially in the dimension and inverse polynomially in the fraction of the volume taken up by the kernel of the star-shaped body. The analysis is based on a new isoperimetric inequality. Our main technical contribution is a tool for proving such inequalities when the domain is not convex. As a consequence, we obtain a polynomial algorithm for computing the volume of such a set as well. In contrast, linear optimization over star-shaped sets is NP-hard.
Performing Nonlinear Blind Source Separation with Signal Invariants
Venue: arXiv cs.AI 2009
Year: 2009

Given a time series of multicomponent measurements x(t), the usual objective of nonlinear blind source separation (BSS) is to find a "source" time series s(t), comprised of statistically independent combinations of the measured components. In this paper, the source time series is required to have a density function in (s,ds/dt)-space that is equal to the product of density functions of individual components. This formulation of the BSS problem has a solution that is unique, up to permutations and component-wise transformations. Separability is shown to impose constraints on certain locally invariant (scalar) functions of x, which are derived from local higher-order correlations of the data's velocity dx/dt. The data are separable if and only if they satisfy these constraints, and, if the constraints are satisfied, the sources can be explicitly constructed from the data. The method is illustrated by using it to separate two speech-like sounds recorded with a single microphone.
Evaluating and Optimising Models of Network Growth
Venue: arXiv cs.NI 2009
Year: 2009

This paper presents a statistically sound method for measuring the accuracy with which a probabilistic model reflects the growth of a network, and a method for optimising parameters in such a model. The technique is data-driven, and can be used for the modeling and simulation of any kind of evolving network. The overall framework, a Framework for Evolving Topology Analysis (FETA), is tested on data sets collected from the Internet AS-level topology, social networking websites and a co-authorship network. Statistical models of the growth of these networks are produced and tested using a likelihood-based method. The models are then used to generate artificial topologies with the same statistical properties as the originals. This work can be used to predict future growth patterns for a known network, or to generate artificial models of graph topology evolution for simulation purposes. Particular application examples include strategic network planning, user profiling in social networks or infrastructure deployment in managed overlay-based services.
The density of weights of Generalized Reed--Muller codes
Venue: arXiv cs.IT 2009
Year: 2009

We study the density of the weights of Generalized Reed--Muller codes. Let $RM_p(r,m)$ denote the code of multivariate polynomials over $\F_p$ in $m$ variables of total degree at most $r$. We consider the case of fixed degree $r$, when we let the number of variables $m$ tend to infinity. We prove that the set of relative weights of codewords is quite sparse: for every $α\in [0,1]$ which is not rational of the form $\frac{\ell}{p^k}$, there exists an interval around $α$ in which no relative weight exists, for any value of $m$. This line of research is to the best of our knowledge new, and complements the traditional lines of research, which focus on the weight distribution and the divisibility properties of the weights. Equivalently, we study distributions taking values in a finite field, which can be approximated by distributions coming from constant degree polynomials, where we do not bound the number of variables. We give a complete characterization of all such distributions.
Stability Analysis and Learning Bounds for Transductive Regression Algorithms
Venue: arXiv cs.LG 2009
Year: 2009

This paper uses the notion of algorithmic stability to derive novel generalization bounds for several families of transductive regression algorithms, both by using convexity and closed-form solutions. Our analysis helps compare the stability of these algorithms. It also shows that a number of widely used transductive regression algorithms are in fact unstable. Finally, it reports the results of experiments with local transductive regression demonstrating the benefit of our stability bounds for model selection, for one of the algorithms, in particular for determining the radius of the local neighborhood used by the algorithm.
On Superposition Coding for the Wyner-Ziv Problem
Venue: arXiv cs.IT 2009
Year: 2009

In problems of lossy source/noisy channel coding with side information, the theoretical bounds are achieved using "good" source/channel codes that can be partitioned into "good" channel/source codes. A scheme that achieves optimality in channel coding with side information at the encoder using independent channel and source codes was outlined in previous works. In practice, the original problem is transformed into a multiple-access problem in which the superposition of the two independent codes can be decoded using successive interference cancellation. Inspired by this work, we analyze the superposition approach for source coding with side information at the decoder. We present a random coding analysis that shows achievability of the Wyner-Ziv bound. Then, we discuss some issues related to the practical implementation of this method.
Approche conceptuelle par un processus d'annotation pour la représentation et la valorisation de contenus informationnels en intelligence économique (IE)
Venue: arXiv cs.IR 2009
Year: 2009

In the era of the information society, the impact of the information systems on the economy of material and immaterial is certainly perceptible. With regards to the information resources of an organization, the annotation involved to enrich informational content, to track the intellectual activities on a document and to set the added value on information for the benefit of solving a decision-making problem in the context of economic intelligence. Our contribution is distinguished by the representation of an annotation process and its inherent concepts to lead the decisionmaker to an anticipated decision: the provision of relevant and annotated information. Such information in the system is made easy by taking into account the diversity of resources and those that are well annotated so formally and informally by the EI actors. A capital research framework consist of integrating in the decision-making process the annotator activity, the software agent (or the reasoning mechanisms) and the information resources enhancement.
A Program to Determine the Exact Competitive Ratio of List s-Batching with Unit Jobs
Venue: arXiv cs.DS 2009
Year: 2009

We consider the online list s-batch problem, where all the jobs have processing time 1 and we seek to minimize the sum of the completion times of the jobs. We give a Java program which is used to verify that the competitiveness of this problem is 619/583.
k-Means has Polynomial Smoothed Complexity
Venue: arXiv cs.DS 2009
Year: 2009

The k-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential worst-case running time. In order to close the gap between practical performance and theoretical analysis, the k-means method has been studied in the model of smoothed analysis. But even the smoothed analyses so far are unsatisfactory as the bounds are still super-polynomial in the number n of data points. In this paper, we settle the smoothed running time of the k-means method. We show that the smoothed number of iterations is bounded by a polynomial in n and 1/σ, where σis the standard deviation of the Gaussian perturbations. This means that if an arbitrary input data set is randomly perturbed, then the k-means method will run in expected polynomial time on that input set.
Coherence Analysis of Iterative Thresholding Algorithms
Venue: arXiv cs.IT 2009
Year: 2009

There is a recent surge of interest in developing algorithms for finding sparse solutions of underdetermined systems of linear equations $y = Φx$. In many applications, extremely large problem sizes are envisioned, with at least tens of thousands of equations and hundreds of thousands of unknowns. For such problem sizes, low computational complexity is paramount. The best studied $\ell_1$ minimization algorithm is not fast enough to fulfill this need. Iterative thresholding algorithms have been proposed to address this problem. In this paper we want to analyze two of these algorithms theoretically, and give sufficient conditions under which they recover the sparsest solution.
Language Diversity across the Consonant Inventories: A Study in the Framework of Complex Networks
Venue: arXiv cs.CL 2009
Year: 2009

n this paper, we attempt to explain the emergence of the linguistic diversity that exists across the consonant inventories of some of the major language families of the world through a complex network based growth model. There is only a single parameter for this model that is meant to introduce a small amount of randomness in the otherwise preferential attachment based growth process. The experiments with this model parameter indicates that the choice of consonants among the languages within a family are far more preferential than it is across the families. The implications of this result are twofold -- (a) there is an innate preference of the speakers towards acquiring certain linguistic structures over others and (b) shared ancestry propels the stronger preferential connection between the languages within a family than across them. Furthermore, our observations indicate that this parameter might bear a correlation with the period of existence of the language families under investigation.
On the Parameterised Intractability of Monadic Second-Order Logic
Venue: arXiv cs.LO 2009
Year: 2009

One of Courcelle's celebrated results states that if C is a class of graphs of bounded tree-width, then model-checking for monadic second order logic is fixed-parameter tractable on C by linear time parameterised algorithms. An immediate question is whether this is best possible or whether the result can be extended to classes of unbounded tree-width. In this paper we show that in terms of tree-width, the theorem can not be extended much further. More specifically, we show that if C is a class of graphs which is closed under colourings and satisfies certain constructibility conditions such that the tree-width of C is not bounded by log^{16}(n) then MSO_2-model checking is not fixed-parameter tractable unless the satisfiability problem SAT for propositional logic can be solved in sub-exponential time. If the tree-width of C is not poly-logarithmically bounded, then MSO_2-model checking is not fixed-parameter tractable unless all problems in the polynomial-time hierarchy, and hence in particular all problems in NP, can be solved in sub-exponential time.
A Class of Novel STAP Algorithms Using Sparse Recovery Technique
Venue: arXiv cs.IT 2009
Year: 2009

A class of novel STAP algorithms based on sparse recovery technique were presented. Intrinsic sparsity of distribution of clutter and target energy on spatial-frequency plane was exploited from the viewpoint of compressed sensing. The original sample data and distribution of target and clutter energy was connected by a ill-posed linear algebraic equation and popular $L_1$ optimization method could be utilized to search for its solution with sparse characteristic. Several new filtering algorithm acting on this solution were designed to clean clutter component on spatial-frequency plane effectively for detecting invisible targets buried in clutter. The method above is called CS-STAP in general. CS-STAP showed their advantage compared with conventional STAP technique, such as SMI, in two ways: Firstly, the resolution of CS-STAP on estimation for distribution of clutter and target energy is ultra-high such that clutter energy might be annihilated almost completely by carefully tuned filter. Output SCR of CS-STAP algorithms is far superior to the requirement of detection; Secondly, a much smaller size of training sample support compared with SMI method is requested for CS-STAP method. Even with only one snapshot (from target range cell) could CS-STAP method be able to reveal the existence of target clearly. CS-STAP method display its great potential to be used in heterogeneous situation. Experimental result on dataset from mountaintop program has provided the evidence for our assertion on CS-STAP.
On the word problem for SP-categories, and the properties of two-way communication
Venue: arXiv cs.LO 2009
Year: 2009

The word problem for categories with free products and coproducts (sums), SP-categories, is directly related to the problem of determining the equivalence of certain processes. Indeed, the maps in these categories may be directly interpreted as processes which communicate by two-way channels. The maps of an SP-category may also be viewed as a proof theory for a simple logic with a game theoretic intepretation. The cut-elimination procedure for this logic determines equality only up to certain permuting conversions. As the equality classes under these permuting conversions are finite, it is easy to see that equality between cut-free terms (even in the presence of the additive units) is decidable. Unfortunately, this does not yield a tractable decision algorithm as these equivalence classes can contain exponentially many terms. However, the rather special properties of these free categories -- and, thus, of two-way communication -- allow one to devise a tractable algorithm for equality. We show that, restricted to cut-free terms s,t : X --> A, the decision procedure runs in time polynomial on |X||A|, the product of the sizes of the domain and codomain type.
Mathematical and Statistical Opportunities in Cyber Security
Venue: arXiv cs.CR 2009
Year: 2009

The role of mathematics in a complex system such as the Internet has yet to be deeply explored. In this paper, we summarize some of the important and pressing problems in cyber security from the viewpoint of open science environments. We start by posing the question "What fundamental problems exist within cyber security research that can be helped by advanced mathematics and statistics?" Our first and most important assumption is that access to real-world data is necessary to understand large and complex systems like the Internet. Our second assumption is that many proposed cyber security solutions could critically damage both the openness and the productivity of scientific research. After examining a range of cyber security problems, we come to the conclusion that the field of cyber security poses a rich set of new and exciting research opportunities for the mathematical and statistical sciences.
Bounded Max-Colorings of Graphs
Venue: arXiv cs.DS 2009
Year: 2009

In a bounded max-coloring of a vertex/edge weighted graph, each color class is of cardinality at most $b$ and of weight equal to the weight of the heaviest vertex/edge in this class. The bounded max-vertex/edge-coloring problems ask for such a coloring minimizing the sum of all color classes' weights. In this paper we present complexity results and approximation algorithms for those problems on general graphs, bipartite graphs and trees. We first show that both problems are polynomial for trees, when the number of colors is fixed, and $H_b$ approximable for general graphs, when the bound $b$ is fixed. For the bounded max-vertex-coloring problem, we show a 17/11-approximation algorithm for bipartite graphs, a PTAS for trees as well as for bipartite graphs when $b$ is fixed. For unit weights, we show that the known 4/3 lower bound for bipartite graphs is tight by providing a simple 4/3 approximation algorithm. For the bounded max-edge-coloring problem, we prove approximation factors of $3-2/\sqrt{2b}$, for general graphs, $\min\{e, 3-2/\sqrt{b}\}$, for bipartite graphs, and 2, for trees. Furthermore, we show that this problem is NP-complete even for trees. This is the first complexity result for max-coloring problems on trees.
Feasibility of Motion Planning on Acyclic and Strongly Connected Directed Graphs
Venue: arXiv cs.DM 2009
Year: 2009

Motion planning is a fundamental problem of robotics with applications in many areas of computer science and beyond. Its restriction to graphs has been investigated in the literature for it allows to concentrate on the combinatorial problem abstracting from geometric considerations. In this paper, we consider motion planning over directed graphs, which are of interest for asymmetric communication networks. Directed graphs generalize undirected graphs, while introducing a new source of complexity to the motion planning problem: moves are not reversible. We first consider the class of acyclic directed graphs and show that the feasibility can be solved in time linear in the product of the number of vertices and the number of arcs. We then turn to strongly connected directed graphs. We first prove a structural theorem for decomposing strongly connected directed graphs into strongly biconnected components.Based on the structural decomposition, we give an algorithm for the feasibility of motion planning on strongly connected directed graphs, and show that it can also be decided in time linear in the product of the number of vertices and the number of arcs.
Personalized Recommendation via Integrated Diffusion on User-Item-Tag Tripartite Graphs
Venue: arXiv cs.IR 2009
Year: 2009

Personalized recommender systems are confronting great challenges of accuracy, diversification and novelty, especially when the data set is sparse and lacks accessorial information, such as user profiles, item attributes and explicit ratings. Collaborative tags contain rich information about personalized preferences and item contents, and are therefore potential to help in providing better recommendations. In this paper, we propose a recommendation algorithm based on an integrated diffusion on user-item-tag tripartite graphs. We use three benchmark data sets, Del.icio.us, MovieLens and BibSonomy, to evaluate our algorithm. Experimental results demonstrate that the usage of tag information can significantly improve accuracy, diversification and novelty of recommendations.
Selfish Bin Covering
Venue: arXiv cs.GT 2009
Year: 2009

In this paper, we address the selfish bin covering problem, which is greatly related both to the bin covering problem, and to the weighted majority game. What we mainly concern is how much the lack of coordination harms the social welfare. Besides the standard PoA and PoS, which are based on Nash equilibrium, we also take into account the strong Nash equilibrium, and several other new equilibria. For each equilibrium, the corresponding PoA and PoS are given, and the problems of computing an arbitrary equilibrium, as well as approximating the best one, are also considered.
A Weakly-Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
Venue: arXiv cs.CG 2009
Year: 2009

We consider the problem of partitioning the set of vertices of a given unit disk graph (UDG) into a minimum number of cliques. The problem is NP-hard and various constant factor approximations are known, with the current best ratio of 3. Our main result is a {\em weakly robust} polynomial time approximation scheme (PTAS) for UDGs expressed with edge-lengths, it either (i) computes a clique partition or (ii) gives a certificate that the graph is not a UDG; for the case (i) that it computes a clique partition, we show that it is guaranteed to be within $(1+\eps)$ ratio of the optimum if the input is UDG; however if the input is not a UDG it either computes a clique partition as in case (i) with no guarantee on the quality of the clique partition or detects that it is not a UDG. Noting that recognition of UDG's is NP-hard even if we are given edge lengths, our PTAS is a weakly-robust algorithm. Our algorithm can be transformed into an $O(\frac{\log^* n}{\eps^{O(1)}})$ time distributed PTAS. We consider a weighted version of the clique partition problem on vertex weighted UDGs that generalizes the problem. We note some key distinctions with the unweighted version, where ideas useful in obtaining a PTAS breakdown. Yet, surprisingly, it admits a $(2+\eps)$-approximation algorithm for the weighted case where the graph is expressed, say, as an adjacency matrix. This improves on the best known 8-approximation for the {\em unweighted} case for UDGs expressed in standard form.
A Comprehensive study of a New Multipath Energy Aware Routing Protocol for Mobile Ad-hoc Networks
Venue: arXiv cs.NI 2009
Year: 2009

Maximizing network lifetime is a very challenging issue in routing protocol design for Mobile Ad-hoc NETworks (MANETs), since mobile nodes are powered by limited-capacity batteries. Furthermore, replacing or recharging batteries is often impossible in critical environments (e.g. battlefields, disaster areas, etc.) The proposed MEA-DSR (Multipath Energy-Aware on Demand Source Routing) protocol uses a load distribution policy in order to maximize network lifetime. The simulation results have shown the efficiency of the proposed protocol in comparison to DSR routing protocol in many difficult scenarios
The Category Theoretic Solution of Recursive Program Schemes
Venue: arXiv cs.LO 2009
Year: 2009

This paper provides a general account of the notion of recursive program schemes, studying both uninterpreted and interpreted solutions. It can be regarded as the category-theoretic version of the classical area of algebraic semantics. The overall assumptions needed are small indeed: working only in categories with "enough final coalgebras" we show how to formulate, solve, and study recursive program schemes. Our general theory is algebraic and so avoids using ordered, or metric structures. Our work generalizes the previous approaches which do use this extra structure by isolating the key concepts needed to study substitution in infinite trees, including second-order substitution. As special cases of our interpreted solutions we obtain the usual denotational semantics using complete partial orders, and the one using complete metric spaces. Our theory also encompasses implicitly defined objects which are not usually taken to be related to recursive program schemes. For example, the classical Cantor two-thirds set falls out as an interpreted solution (in our sense) of a recursive program scheme.