OpenRaiser/Intern-Atlas huggingface dataset:
A note on Solving Parametric Polynomial Systems
Venue: arXiv cs.SC 2011
Year: 2011

Lazard and Rouillier in [9], by introducing the concept of discriminant variety, have described a new and efficient algorithm for solving parametric polynomial systems. In this paper we modify this algorithm, and we show that with our improvements the output of our algorithm is always minimal and it does not need to compute the radical of ideals.
Minimum diameter and cycle-diameter orientations on planar graphs
Venue: arXiv cs.DM 2011
Year: 2011

Let G be an edge weighted undirected graph. For every pair of nodes consider the shortest cycle containing these nodes in G. The cycle diameter of G is the maximum length of a cycle in this set. Let H be a directed graph obtained by directing the edges of G. The cycle diameter of H is similarly defined except for that cycles are replaced by directed closed walks. Is there always an orientation H of G whose cycle diameter is bounded by a constant times the cycle diameter of G? We prove this property for planar graphs. These results have implications on the problem of approximating an orientation with minimum diameter
SOAP vs REST: Comparing a master-slave GA implementation
Venue: arXiv cs.NE 2011
Year: 2011

In this paper, a high-level comparison of both SOAP (Simple Object Access Protocol) and REST (Representational State Transfer) is made. These are the two main approaches for interfacing to the web with web services. Both approaches are different and present some advantages and disadvantages for interfacing to web services: SOAP is conceptually more difficult (has a steeper learning curve) and more "heavy-weight" than REST, although it lacks of standards support for security. In order to test their eficiency (in time), two experiments have been performed using both technologies: a client-server model implementation and a master-slave based genetic algorithm (GA). The results obtained show clear differences in time between SOAP and REST implementations. Although both techniques are suitable for developing parallel systems, SOAP is heavier than REST, mainly due to the verbosity of SOAP communications (XML increases the time taken to parse the messages).
Scheduling under Precedence, Communication, and Energy Constraints
Venue: arXiv cs.DS 2011
Year: 2011

We consider the problem of scheduling a set of $n$ tasks on $m$ processors under precedence, communication, and global system energy constraints to minimize makespan. We extend existing scheduling models to account for energy usage and give convex programming algorithms that yield essentially the same results as existing algorithms that do not consider energy, while adhering to a strict energy bound.
State Space Reduction in the Maude-NRL Protocol Analyzer
Venue: arXiv cs.CR 2011
Year: 2011

The Maude-NRL Protocol Analyzer (Maude-NPA) is a tool and inference system for reasoning about the security of cryptographic protocols in which the cryptosystems satisfy different equational properties. It both extends and provides a formal framework for the original NRL Protocol Analyzer, which supported equational reasoning in a more limited way. Maude-NPA supports a wide variety of algebraic properties that includes many crypto-systems of interest such as, for example, one-time pads and Diffie-Hellman. Maude-NPA, like the original NPA, looks for attacks by searching backwards from an insecure attack state, and assumes an unbounded number of sessions. Because of the unbounded number of sessions and the support for different equational theories, it is necessary to develop ways of reducing the search space and avoiding infinite search paths. In order for the techniques to prove useful, they need not only to speed up the search, but should not violate completeness, so that failure to find attacks still guarantees security. In this paper we describe some state space reduction techniques that we have implemented in Maude-NPA. We also provide completeness proofs, and experimental evaluations of their effect on the performance of Maude-NPA.
Efficient Learning of Sparse Invariant Representations
Venue: arXiv cs.CV 2011
Year: 2011

We propose a simple and efficient algorithm for learning sparse invariant representations from unlabeled data with fast inference. When trained on short movies sequences, the learned features are selective to a range of orientations and spatial frequencies, but robust to a wide range of positions, similar to complex cells in the primary visual cortex. We give a hierarchical version of the algorithm, and give guarantees of fast convergence under certain conditions.
Extensions to the Theory of Widely Linear Complex Kalman Filtering
Venue: arXiv cs.SY 2011
Year: 2011

For an improper complex signal x, its complementary covariance ExxT is not zero and thus it carries useful statistical information about x. Widely linear processing exploits Hermitian and complementary covariance to improve performance. In this paper we extend the existing theory of widely linear complex Kalman filters (WLCKF) and unscented WLCKFs [1]. We propose a WLCKF which can deal with more general dynamical models of complex-valued states and measurements than the WLCKFs in [1]. The proposed WLCKF has an equivalency with the corresponding dual channel real KF. Our analytical and numerical results show the performance improvement of a WLCKF over a complex Kalman filter (CKF) that does not exploit complementary covariance. We also develop an unscented WLCKF which uses modified complex sigma points. The modified complex sigma points preserve complete first and second moments of complex signals, while the sigma points in [1] only carry the mean and Hermitian covariance, but not complementary covariance of complex signals.
The Divide-and-Conquer Subgoal-Ordering Algorithm for Speeding up Logic Inference
Venue: arXiv cs.AI 2011
Year: 2011

It is common to view programs as a combination of logic and control: the logic part defines what the program must do, the control part -- how to do it. The Logic Programming paradigm was developed with the intention of separating the logic from the control. Recently, extensive research has been conducted on automatic generation of control for logic programs. Only a few of these works considered the issue of automatic generation of control for improving the efficiency of logic programs. In this paper we present a novel algorithm for automatic finding of lowest-cost subgoal orderings. The algorithm works using the divide-and-conquer strategy. The given set of subgoals is partitioned into smaller sets, based on co-occurrence of free variables. The subsets are ordered recursively and merged, yielding a provably optimal order. We experimentally demonstrate the utility of the algorithm by testing it in several domains, and discuss the possibilities of its cooperation with other existing methods.
A Temporal Description Logic for Reasoning about Actions and Plans
Venue: arXiv cs.AI 2011
Year: 2011

A class of interval-based temporal languages for uniformly representing and reasoning about actions and plans is presented. Actions are represented by describing what is true while the action itself is occurring, and plans are constructed by temporally relating actions and world states. The temporal languages are members of the family of Description Logics, which are characterized by high expressivity combined with good computational properties. The subsumption problem for a class of temporal Description Logics is investigated and sound and complete decision procedures are given. The basic language TL-F is considered first: it is the composition of a temporal logic TL -- able to express interval temporal networks -- together with the non-temporal logic F -- a Feature Description Logic. It is proven that subsumption in this language is an NP-complete problem. Then it is shown how to reason with the more expressive languages TLU-FU and TL-ALCF. The former adds disjunction both at the temporal and non-temporal sides of the language, the latter extends the non-temporal side with set-valued features (i.e., roles) and a propositionally complete language.
Order of Magnitude Comparisons of Distance
Venue: arXiv cs.AI 2011
Year: 2011

Order of magnitude reasoning - reasoning by rough comparisons of the sizes of quantities - is often called 'back of the envelope calculation', with the implication that the calculations are quick though approximate. This paper exhibits an interesting class of constraint sets in which order of magnitude reasoning is demonstrably fast. Specifically, we present a polynomial-time algorithm that can solve a set of constraints of the form 'Points a and b are much closer together than points c and d.' We prove that this algorithm can be applied if `much closer together' is interpreted either as referring to an infinite difference in scale or as referring to a finite difference in scale, as long as the difference in scale is greater than the number of variables in the constraint set. We also prove that the first-order theory over such constraints is decidable.
Squeaky Wheel Optimization
Venue: arXiv cs.AI 2011
Year: 2011

We describe a general approach to optimization which we term `Squeaky Wheel' Optimization (SWO). In SWO, a greedy algorithm is used to construct a solution which is then analyzed to find the trouble spots, i.e., those elements, that, if improved, are likely to improve the objective function score. The results of the analysis are used to generate new priorities that determine the order in which the greedy algorithm constructs the next solution. This Construct/Analyze/Prioritize cycle continues until some limit is reached, or an acceptable solution is found. SWO can be viewed as operating on two search spaces: solutions and prioritizations. Successive solutions are only indirectly related, via the re-prioritization that results from analyzing the prior solution. Similarly, successive prioritizations are generated by constructing and analyzing solutions. This `coupled search' has some interesting properties, which we discuss. We report encouraging experimental results on two domains, scheduling problems that arise in fiber-optic cable manufacturing, and graph coloring problems. The fact that these domains are very different supports our claim that SWO is a general technique for optimization.
Coarse-Grained Topology Estimation via Graph Sampling
Venue: arXiv cs.SI 2011
Year: 2011

Many online networks are measured and studied via sampling techniques, which typically collect a relatively small fraction of nodes and their associated edges. Past work in this area has primarily focused on obtaining a representative sample of nodes and on efficient estimation of local graph properties (such as node degree distribution or any node attribute) based on that sample. However, less is known about estimating the global topology of the underlying graph. In this paper, we show how to efficiently estimate the coarse-grained topology of a graph from a probability sample of nodes. In particular, we consider that nodes are partitioned into categories (e.g., countries or work/study places in OSNs), which naturally defines a weighted category graph. We are interested in estimating (i) the size of categories and (ii) the probability that nodes from two different categories are connected. For each of the above, we develop a family of estimators for design-based inference under uniform or non-uniform sampling, employing either of two measurement strategies: induced subgraph sampling, which relies only on information about the sampled nodes; and star sampling, which also exploits category information about the neighbors of sampled nodes. We prove consistency of these estimators and evaluate their efficiency via simulation on fully known graphs. We also apply our methodology to a sample of Facebook users to obtain a number of category graphs, such as the college friendship graph and the country friendship graph; we share and visualize the resulting data at www.geosocialmap.com.
Ontology Alignment at the Instance and Schema Level
Venue: arXiv cs.AI 2011
Year: 2011

We present PARIS, an approach for the automatic alignment of ontologies. PARIS aligns not only instances, but also relations and classes. Alignments at the instance-level cross-fertilize with alignments at the schema-level. Thereby, our system provides a truly holistic solution to the problem of ontology alignment. The heart of the approach is probabilistic. This allows PARIS to run without any parameter tuning. We demonstrate the efficiency of the algorithm and its precision through extensive experiments. In particular, we obtain a precision of around 90% in experiments with two of the world's largest ontologies.
Kernel Belief Propagation
Venue: arXiv cs.LG 2011
Year: 2011

We propose a nonparametric generalization of belief propagation, Kernel Belief Propagation (KBP), for pairwise Markov random fields. Messages are represented as functions in a reproducing kernel Hilbert space (RKHS), and message updates are simple linear operations in the RKHS. KBP makes none of the assumptions commonly required in classical BP algorithms: the variables need not arise from a finite domain or a Gaussian distribution, nor must their relations take any particular parametric form. Rather, the relations between variables are represented implicitly, and are learned nonparametrically from training data. KBP has the advantage that it may be used on any domain where kernels are defined (Rd, strings, groups), even where explicit parametric models are not known, or closed form expressions for the BP updates do not exist. The computational cost of message updates in KBP is polynomial in the training data size. We also propose a constant time approximate message update procedure by representing messages using a small number of basis functions. In experiments, we apply KBP to image denoising, depth prediction from still images, and protein configuration prediction: KBP is faster than competing classical and nonparametric approaches (by orders of magnitude, in some cases), while providing significantly more accurate results.
High Quality of Service on Video Streaming in P2P Networks using FST-MDC
Venue: arXiv cs.DC 2011
Year: 2011

Video streaming applications have newly attracted a large number of participants in a distribution network. Traditional client-server based video streaming solutions sustain precious bandwidth provision rate on the server. Recently, several P2P streaming systems have been organized to provide on-demand and live video streaming services on the wireless network at reduced server cost. Peer-to-Peer (P2P) computing is a new pattern to construct disseminated network applications. Typical error control techniques are not very well matched and on the other hand error prone channels has increased greatly for video transmission e.g., over wireless networks and IP. These two facts united together provided the essential motivation for the development of a new set of techniques (error concealment) capable of dealing with transmission errors in video systems. In this paper, we propose an flexible multiple description coding method named as Flexible Spatial-Temporal (FST) which improves error resilience in the sense of frame loss possibilities over independent paths. It introduces combination of both spatial and temporal concealment technique at the receiver and to conceal the lost frames more effectively. Experimental results show that, proposed approach attains reasonable quality of video performance over P2P wireless network.
Clustering and Classification in Text Collections Using Graph Modularity
Venue: arXiv cs.IR 2011
Year: 2011

A new fast algorithm for clustering and classification of large collections of text documents is introduced. The new algorithm employs the bipartite graph that realizes the word-document matrix of the collection. Namely, the modularity of the bipartite graph is used as the optimization functional. Experiments performed with the new algorithm on a number of text collections had shown a competitive quality of the clustering (classification), and a record-breaking speed.
A Combination of Testability and Decodability by Tensor Products
Venue: arXiv cs.CC 2011
Year: 2011

Ben-Sasson and Sudan (RSA 2006) showed that repeated tensor products of linear codes with a very large distance are locally testable. Due to the requirement of a very large distance the associated tensor products could be applied only over sufficiently large fields. Then Meir (SICOMP 2009) used this result (as a black box) to present a combinatorial construction of locally testable codes that match best known parameters. As a consequence, this construction was obtained over sufficiently large fields. In this paper we improve the result of Ben-Sasson and Sudan and show that for \emph{any} linear codes the associated tensor products are locally testable. Consequently, the construction of Meir can be taken over any field, including the binary field. Moreover, a combination of our result with the result of Spielman (IEEE IT, 1996) implies a construction of linear codes (over any field) that combine the following properties: have constant rate and constant relative distance; have blocklength $n$ and testable with $n^ε$ queries, for any constant $ε> 0$; linear time encodable and linear-time decodable from a constant fraction of errors. Furthermore, a combination of our result with the result of Guruswami et al. (STOC 2009) implies a similar corollary regarding the list-decodable codes.
On the random access performance of Cell Broadband Engine with graph analysis application
Venue: arXiv cs.CE 2011
Year: 2011

The Cell Broad Engine (BE) Processor has unique memory access architecture besides its powerful computing engines. Many computing-intensive applications have been ported to Cell/BE successfully. But memory-intensive applications are rarely investigated except for several micro benchmarks. Since Cell/BE has powerful software visible DMA engine, this paper studies on whether Cell/BE is suit for applica- tions with large amount of random memory accesses. Two benchmarks, GUPS and SSCA#2, are used. The latter is a rather complex one that in representative of real world graph analysis applications. We find both benchmarks have good performance on Cell/BE based IBM QS20/22. Com- pared with 2 conventional multi-processor systems with the same core/thread number, GUPS is about 40-80% fast and SSCA#2 about 17-30% fast. The dynamic load balanc- ing and software pipeline for optimizing SSCA#2 are intro- duced. Based on the experiment, the potential of Cell/BE for random access is analyzed in detail as well as its limita- tions of memory controller, atomic engine and TLB manage- ment.Our research shows although more programming effort are needed, Cell/BE has the potencial for irregular memory access applications.
A Polynomial Time Approximation Algorithm for the Two-Commodity Splittable Flow Problem
Venue: arXiv cs.DS 2011
Year: 2011

We consider a generalization of the unsplittable maximum two-commodity flow problem on undirected graphs where each commodity $i\in{1,2}$ can be split into a bounded number $k_i$ of equally-sized chunks that can be routed on different paths. We show that in contrast to the single-commodity case this problem is NP-hard, and hard to approximate to within a factor of $α>1/2$. We present a polynomial time 1/2-approximation algorithm for the case of uniform chunk size over both commodities and show that for even $k_i$ and a mild cut condition it can be modified to yield an exact method. The uniform case can be used to derive a 1/4-approximation for the maximum concurrent $(k_1,k_2)$-splittable flow without chunk size restrictions for fixed demand ratios.
A New Outer-Bound via Interference Localization and the Degrees of Freedom Regions of MIMO Interference Networks with no CSIT
Venue: arXiv cs.IT 2011
Year: 2011

The two-user multi-input, multi-output (MIMO) interference and cognitive radio channels are studied under the assumption of no channel state information at the transmitter (CSIT) from the degrees of freedom (DoF) region perspective. With $M_i$ and $N_i$ denoting the number of antennas at transmitter $i$ and receiver $i$ respectively, the DoF regions of the MIMO interference channel were recently characterized by Huang et al., Zhu and Guo, and by the authors of this paper for all values of numbers of antennas except when $\min(M_1,N_1) > N_2 > M_2$ (or $\min(M_2,N_2) > N_1 > M_1$). This latter case was solved more recently by Zhu and Guo who provided a tight outer-bound. Here, a simpler and more widely applicable proof of that outer-bound is given based on the idea of interference localization. Using it, the DoF region is also established for the class of MIMO cognitive radio channels when $\min(M_1+M_2,N_1) > N_2 > M_2$ (with the second transmitter cognitive) -- the only class for which the inner and outer bounds previously obtained by the authors were not tight -- thereby completing the DoF region characterization of the general 2-user MIMO cognitive radio channel as well.
Delay Optimal Event Detection on Ad Hoc Wireless Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

We consider a small extent sensor network for event detection, in which nodes take samples periodically and then contend over a {\em random access network} to transmit their measurement packets to the fusion center. We consider two procedures at the fusion center to process the measurements. The Bayesian setting is assumed; i.e., the fusion center has a prior distribution on the change time. In the first procedure, the decision algorithm at the fusion center is \emph{network-oblivious} and makes a decision only when a complete vector of measurements taken at a sampling instant is available. In the second procedure, the decision algorithm at the fusion center is \emph{network-aware} and processes measurements as they arrive, but in a time causal order. In this case, the decision statistic depends on the network delays as well, whereas in the network-oblivious case, the decision statistic does not depend on the network delays. This yields a Bayesian change detection problem with a tradeoff between the random network delay and the decision delay; a higher sampling rate reduces the decision delay but increases the random access delay. Under periodic sampling, in the network--oblivious case, the structure of the optimal stopping rule is the same as that without the network, and the optimal change detection delay decouples into the network delay and the optimal decision delay without the network. In the network--aware case, the optimal stopping problem is analysed as a partially observable Markov decision process, in which the states of the queues and delays in the network need to be maintained. A sufficient statistic for decision is found to be the network-state and the posterior probability of change having occurred given the measurements received and the state of the network. The optimal regimes are studied using simulation.