OpenRaiser/Intern-Atlas huggingface dataset:
Sparser Random 3SAT Refutation Algorithms and the Interpolation Problem
Venue: arXiv cs.CC 2014
Year: 2014

We formalize a combinatorial principle, called the 3XOR principle, due to Feige, Kim and Ofek (2006), as a family of unsatisfiable propositional formulas for which refutations of small size in any propositional proof system that possesses the feasible interpolation property imply an efficient deterministic refutation algorithm for random 3SAT with n variables and Ω(n^{1.4}) clauses. Such small size refutations would improve the state-of-the-art (with respect to the clause density) efficient refutation algorithm, which works only for Ω(n^{1.5}) many clauses (Feige and Ofek (2007)). We demonstrate polynomial-size refutations of the 3XOR principle in resolution operating with disjunctions of quadratic equations with small integer coefficients, denoted R(quad); this is a weak extension of cutting planes with small coefficients. We show that R(quad) is weakly automatizable iff R(lin) is weakly automatizable, where R(lin) is similar to R(quad) but with linear instead of quadratic equations (introduced in Raz and Tzameret (2008)). This reduces the problem of refuting random 3CNF with n variables and Ω(n^{1.4}) clauses to the interpolation problem of R(quad) and to the weak automatizability of R(lin).
A New Approach to Decoding of Rational Irreducible Goppa code
Venue: arXiv cs.CR 2014
Year: 2014

The interesting properties of classical Goppa code and its effective decoding algorithm (algorithm of patterson) make the most appropriate candidate for use in the MC Eliece cryptosystem. Information leakage which results from the relationship between the error vector weight and the number of iterations in the decoding algorithm, presented a weakness of the cryptosystem. In this paper, we introduce a new approach to decoding, the use of binary Goppa code in system design MC Eliece which solve the problem of the leak of information, on the contrary in case of patterson algorithm. We treat this decoding method using the Newton identities and results of linear algebra.
Analyzing the citation characteristics of books: edited books, book series and types of publishers in the Book Citation Index
Venue: arXiv cs.DL 2014
Year: 2014

This paper presents a first approach to analyzing the factors that determine the citation characteristics of books. For this we use the Thomson Reuters' Book Citation Index, a novel multidisciplinary database launched in 2010 which offers bibliometric data of books. We analyze three possible factors which are considered to affect the citation impact of books: the presence of editors, the inclusion in series and the type of publisher. Also, we focus on highly cited books to see if these factors may affect them as well. We considered as highly cited books, those in the top 5% of the most highly cited ones of the database. We define these three aspects and we present the results for four major scientific areas in order to identify field-based differences (Science, Engineering & Technology, Social Sciences and Arts & Humanities). Finally we conclude observing that differences were noted for edited books and types of publishers. Although books included in series showed higher impact in two areas.
Architecture and Production Readiness Reviews in Practice
Venue: arXiv cs.SE 2014
Year: 2014

Detailed description of procedures around architecture reviews. In order to succeed in building and deploying complex software solutions, an architecture is essential. For many in the industry structured reviews of these architectures is also de rigor. Practices for such reviews have been developed and reported on for years. One aspect that does not receive as much attention but is no less important is the relationship between these architectures and the requirements for deploying them into production environments. At Wolters Kluwer's Corporate Legal Services we first established a typical architecture review process and then established a two phase production preparation review process. This paper describes in detail how these practices work and some of the technical results of these reviews including the frequency and style of the reviews, the process automation around them, and the number and nature of some of the technical flaws eliminated by enforcing these reviews. This paper lays the ground work for others who would be interested in following similar practices.
Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning
Venue: arXiv cs.RO 2014
Year: 2014

We present a sampling-based framework for multi-robot motion planning which combines an implicit representation of a roadmap with a novel approach for pathfinding in geometrically embedded graphs tailored for our setting. Our pathfinding algorithm, discrete-RRT (dRRT), is an adaptation of the celebrated RRT algorithm for the discrete case of a graph, and it enables a rapid exploration of the high-dimensional configuration space by carefully walking through an implicit representation of a tensor product of roadmaps for the individual robots. We demonstrate our approach experimentally on scenarios of up to 60 degrees of freedom where our algorithm is faster by a factor of at least ten when compared to existing algorithms that we are aware of.
Object Detection with Pixel Intensity Comparisons Organized in Decision Trees
Venue: arXiv cs.CV 2014
Year: 2014

We describe a method for visual object detection based on an ensemble of optimized decision trees organized in a cascade of rejectors. The trees use pixel intensity comparisons in their internal nodes and this makes them able to process image regions very fast. Experimental analysis is provided through a face detection problem. The obtained results are encouraging and demonstrate that the method has practical value. Additionally, we analyse its sensitivity to noise and show how to perform fast rotation invariant object detection. Complete source code is provided at https://github.com/nenadmarkus/pico.
Large Scale Model for Information Dissemination with Device to Device Communication using Call Details Records
Venue: arXiv cs.NI 2014
Year: 2014

In a network of devices in close proximity such as Device to Device ($D2D$) communication, we study the dissemination of public safety information at country scale level. In order to provide a realistic model for the information dissemination, we extract a spatial distribution of the population of Ivory Coast from census data and determine migration pattern from the Call Detail Records ($CDR$) obtained during the Data for Development ($D4D$) challenge. We later apply epidemic model towards the information dissemination process based on the spatial properties of the user mobility extracted from the provided $CDR$. We then propose enhancements by adding latent states to the epidemic model in order to model more realistic user dynamics. Finally, we study dynamics of the evolution of the information spreading through the population.
Efficient Classification for Metric Data
Venue: arXiv cs.LG 2014
Year: 2014

Recent advances in large-margin classification of data residing in general metric spaces (rather than Hilbert spaces) enable classification under various natural metrics, such as string edit and earthmover distance. A general framework developed for this purpose by von Luxburg and Bousquet [JMLR, 2004] left open the questions of computational efficiency and of providing direct bounds on generalization error. We design a new algorithm for classification in general metric spaces, whose runtime and accuracy depend on the doubling dimension of the data points, and can thus achieve superior classification performance in many common scenarios. The algorithmic core of our approach is an approximate (rather than exact) solution to the classical problems of Lipschitz extension and of Nearest Neighbor Search. The algorithm's generalization performance is guaranteed via the fat-shattering dimension of Lipschitz classifiers, and we present experimental evidence of its superiority to some common kernel methods. As a by-product, we offer a new perspective on the nearest neighbor classifier, which yields significantly sharper risk asymptotics than the classic analysis of Cover and Hart [IEEE Trans. Info. Theory, 1967].
Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems
Venue: arXiv cs.DS 2014
Year: 2014

Probabilistic analysis for metric optimization problems has mostly been conducted on random Euclidean instances, but little is known about metric instances drawn from distributions other than the Euclidean. This motivates our study of random metric instances for optimization problems obtained as follows: Every edge of a complete graph gets a weight drawn independently at random. The distance between two nodes is then the length of a shortest path (with respect to the weights drawn) that connects these nodes. We prove structural properties of the random shortest path metrics generated in this way. Our main structural contribution is the construction of a good clustering. Then we apply these findings to analyze the approximation ratios of heuristics for matching, the traveling salesman problem (TSP), and the k-median problem, as well as the running-time of the 2-opt heuristic for the TSP. The bounds that we obtain are considerably better than the respective worst-case bounds. This suggests that random shortest path metrics are easy instances, similar to random Euclidean instances, albeit for completely different structural reasons.
Big data and the SP theory of intelligence
Venue: arXiv cs.AI 2014
Year: 2014

This article is about how the "SP theory of intelligence" and its realisation in the "SP machine" may, with advantage, be applied to the management and analysis of big data. The SP system -- introduced in the article and fully described elsewhere -- may help to overcome the problem of variety in big data: it has potential as "a universal framework for the representation and processing of diverse kinds of knowledge" (UFK), helping to reduce the diversity of formalisms and formats for knowledge and the different ways in which they are processed. It has strengths in the unsupervised learning or discovery of structure in data, in pattern recognition, in the parsing and production of natural language, in several kinds of reasoning, and more. It lends itself to the analysis of streaming data, helping to overcome the problem of velocity in big data. Central in the workings of the system is lossless compression of information: making big data smaller and reducing problems of storage and management. There is potential for substantial economies in the transmission of data, for big cuts in the use of energy in computing, for faster processing, and for smaller and lighter computers. The system provides a handle on the problem of veracity in big data, with potential to assist in the management of errors and uncertainties in data. It lends itself to the visualisation of knowledge structures and inferential processes. A high-parallel, open-source version of the SP machine would provide a means for researchers everywhere to explore what can be done with the system and to create new versions of it.
The Academic Social Network
Venue: arXiv cs.SI 2014
Year: 2014

Through academic publications, the authors of these publications form a social network. Instead of sharing casual thoughts and photos (as in Facebook), authors pick co-authors and reference papers written by other authors. Thanks to various efforts (such as Microsoft Libra and DBLP), the data necessary for analyzing the academic social network is becoming more available on the Internet. What type of information and queries would be useful for users to find out, beyond the search queries already available from services such as Google Scholar? In this paper, we explore this question by defining a variety of ranking metrics on different entities -authors, publication venues and institutions. We go beyond traditional metrics such as paper counts, citations and h-index. Specifically, we define metrics such as influence, connections and exposure for authors. An author gains influence by receiving more citations, but also citations from influential authors. An author increases his/her connections by co-authoring with other authors, and specially from other authors with high connections. An author receives exposure by publishing in selective venues where publications received high citations in the past, and the selectivity of these venues also depends on the influence of the authors who publish there. We discuss the computation aspects of these metrics, and similarity between different metrics. With additional information of author-institution relationships, we are able to study institution rankings based on the corresponding authors' rankings for each type of metric as well as different domains. We are prepared to demonstrate these ideas with a web site (http://pubstat.org) built from millions of publications and authors.
New Analysis of Manifold Embeddings and Signal Recovery from Compressive Measurements
Venue: arXiv cs.IT 2014
Year: 2014

Compressive Sensing (CS) exploits the surprising fact that the information contained in a sparse signal can be preserved in a small number of compressive, often random linear measurements of that signal. Strong theoretical guarantees have been established concerning the embedding of a sparse signal family under a random measurement operator and on the accuracy to which sparse signals can be recovered from noisy compressive measurements. In this paper, we address similar questions in the context of a different modeling framework. Instead of sparse models, we focus on the broad class of manifold models, which can arise in both parametric and non-parametric signal families. Using tools from the theory of empirical processes, we improve upon previous results concerning the embedding of low-dimensional manifolds under random measurement operators. We also establish both deterministic and probabilistic instance-optimal bounds in $\ell_2$ for manifold-based signal recovery and parameter estimation from noisy compressive measurements. In line with analogous results for sparsity-based CS, we conclude that much stronger bounds are possible in the probabilistic setting. Our work supports the growing evidence that manifold-based models can be used with high accuracy in compressive signal processing.
Monetary Cost Optimizations for Hosting Workflow-as-a-Service in IaaS Clouds
Venue: arXiv cs.DC 2014
Year: 2014

Recently, we have witnessed workflows from science and other data-intensive applications emerging on Infrastructure-asa-Service (IaaS) clouds, and many workflow service providers offering workflow as a service (WaaS). The major concern of WaaS providers is to minimize the monetary cost of executing workflows in the IaaS cloud. While there have been previous studies on this concern, most of them assume static task execution time and static pricing scheme, and have the QoS notion of satisfying a deterministic deadline. However, cloud environment is dynamic, with performance dynamics caused by the interference from concurrent executions and price dynamics like spot prices offered by Amazon EC2. Therefore, we argue that WaaS providers should have the notion of offering probabilistic performance guarantees for individual workflows on IaaS clouds. We develop a probabilistic scheduling framework called Dyna to minimize the monetary cost while offering probabilistic deadline guarantees. The framework includes an A*-based instance configuration method for performance dynamics, and a hybrid instance configuration refinement for utilizing spot instances. Experimental results with three real-world scientific workflow applications on Amazon EC2 demonstrate (1) the accuracy of our framework on satisfying the probabilistic deadline guarantees required by the users; (2) the effectiveness of our framework on reducing monetary cost in comparison with the existing approaches.
Mixed Noisy Network Coding and Cooperative Unicasting in Wireless Networks
Venue: arXiv cs.IT 2014
Year: 2014

The problem of communicating a single message to a destination in presence of multiple relay nodes, referred to as cooperative unicast network, is considered. First, we introduce "Mixed Noisy Network Coding" (MNNC) scheme which generalizes "Noisy Network Coding" (NNC) where relays are allowed to decode-and-forward (DF) messages while all of them (without exception) transmit noisy descriptions of their observations. These descriptions are exploited at the destination and the DF relays aim to decode the transmitted messages while creating full cooperation among the nodes. Moreover, the destination and the DF relays can independently select the set of descriptions to be decoded or treated as interference. This concept is further extended to multi-hopping scenarios, referred to as "Layered MNNC" (LMNNC), where DF relays are organized into disjoint groups representing one hop in the network. For cooperative unicast additive white Gaussian noise (AWGN) networks we show that -provided DF relays are properly chosen- MNNC improves over all previously established constant gaps to the cut-set bound. Secondly, we consider the composite cooperative unicast network where the channel parameters are randomly drawn before communication starts and remain fixed during the transmission. Each draw is assumed to be unknown at the source and fully known at the destination but only partly known at the relays. We introduce through MNNC scheme the concept of "Selective Coding Strategy" (SCS) that enables relays to decide dynamically whether, in addition to communicate noisy descriptions, is possible to decode and forward messages. It is demonstrated through slow-fading AWGN relay networks that SCS clearly outperforms conventional coding schemes.
A branch and cut algorithm for minimum spanning trees under conflict constraints
Venue: arXiv cs.DS 2014
Year: 2014

We study approaches for the exact solution of the \NP--hard minimum spanning tree problem under conflict constraints. Given a graph $G(V,E)$ and a set $C \subset E \times E$ of conflicting edge pairs, the problem consists of finding a conflict-free minimum spanning tree, i.e. feasible solutions are allowed to include at most one of the edges from each pair in $C$. The problem was introduced recently in the literature, with several results on its complexity and approximability. Some formulations and both exact and heuristic algorithms were also discussed, but computational results indicate considerably large duality gaps and a lack of optimality certificates for benchmark instances. In this paper, we build on the representation of conflict constraints using an auxiliary conflict graph $\hat{G}(E,C)$, where stable sets correspond to conflict-free subsets of $E$. We introduce a general preprocessing method and a branch and cut algorithm using an IP formulation with exponentially sized classes of valid inequalities for both the spanning tree and the stable set polytopes. Encouraging computational results indicate that the dual bounds of our approach are significantly stronger than those previously available, already in the initial LP relaxation, and we are able to provide new feasibility and optimality certificates.
Robust Causality Check for Sampled Scattering Parameters via a Filtered Fourier Transform
Venue: arXiv cs.CE 2014
Year: 2014

We introduce a robust numerical technique to verify the causality of sampled scattering parameters given on a finite bandwidth. The method is based on a filtered Fourier transform and includes a rigorous estimation of the errors caused by missing out-of-band samples. Compared to existing techniques, the method is simpler to implement and provides a useful insight on the time-domain characteristics of the detected violation. Through an applicative example, we shows its usefulness to improve the accuracy and reliability of macromodeling techniques used to convert sampled scattering parameters into models for transient analysis.
B-tests: Low Variance Kernel Two-Sample Tests
Venue: arXiv cs.LG 2014
Year: 2014

A family of maximum mean discrepancy (MMD) kernel two-sample tests is introduced. Members of the test family are called Block-tests or B-tests, since the test statistic is an average over MMDs computed on subsets of the samples. The choice of block size allows control over the tradeoff between test power and computation time. In this respect, the $B$-test family combines favorable properties of previously proposed MMD two-sample tests: B-tests are more powerful than a linear time test where blocks are just pairs of samples, yet they are more computationally efficient than a quadratic time test where a single large block incorporating all the samples is used to compute a U-statistic. A further important advantage of the B-tests is their asymptotically Normal null distribution: this is by contrast with the U-statistic, which is degenerate under the null hypothesis, and for which estimates of the null distribution are computationally demanding. Recent results on kernel selection for hypothesis testing transfer seamlessly to the B-tests, yielding a means to optimize test power via kernel choice.
Integrating GPS, GSM and Cellular Phone for Location Tracking and Monitoring
Venue: arXiv cs.NI 2014
Year: 2014

The wide spread of mobiles as handheld devices leads to various innovative applications that makes use of their ever increasing presence in our daily life. One such application is location tracking and monitoring. This paper proposes a prototype model for location tracking using Geographical Positioning System (GPS) and Global System for Mobile Communication (GSM) technology. The system displays the object moving path on the monitor and the same information can also be communicated to the user cell phone, on demand of the user by asking the specific information via SMS. This system is very useful for car theft situations, for adolescent drivers being watched and monitored by parents. The result shows that the object is being tracked with a minimal tracking error.
Asymmetry of the Kolmogorov complexity of online predicting odd and even bits
Venue: arXiv cs.IT 2014
Year: 2014

Symmetry of information states that $C(x) + C(y|x) = C(x,y) + O(\log C(x))$. We show that a similar relation for online Kolmogorov complexity does not hold. Let the even (online Kolmogorov) complexity of an n-bitstring $x_1x_2... x_n$ be the length of a shortest program that computes $x_2$ on input $x_1$, computes $x_4$ on input $x_1x_2x_3$, etc; and similar for odd complexity. We show that for all n there exist an n-bit x such that both odd and even complexity are almost as large as the Kolmogorov complexity of the whole string. Moreover, flipping odd and even bits to obtain a sequence $x_2x_1x_4x_3\ldots$, decreases the sum of odd and even complexity to $C(x)$.