OpenRaiser/Intern-Atlas huggingface dataset:
An approximate analytical (structural) superposition in terms of two, or more, "alfa"-circuits of the same topology: Pt.1 - description of the superposition
Venue: arXiv cs.OH 2010
Year: 2010

One-ports named "f-circuits", composed of similar conductors described by a monotonic polynomial, or quasi-polynomial (i.e. with positive but not necessarily integer, powers) characteristic i = f(v) are studied, focusing on the algebraic map f --> F. Here F(.) is the input conductivity characteristic; i.e., iin = F(vin) is the input current. The "power-law" "alfa-circuit" introduced in [1], for which f(v) ~ v^"alfa", is an important particular case. By means of a generalization of a parallel connection, the f-circuits are constructed from the alfa-circuits of the same topology, with different "alfa", so that the given topology is kept, and 'f' is an additive function of the connection. We observe and consider an associated, generally approximated, but, in all of the cases studied, always high-precision, specific superposition. This superposition is in terms of f --> F, and it means that F(.) of the connection is close to the sum of the input currents of the independent "alfa"-circuits, all connected in parallel to the same source. In other words, F(.) is well approximated by a linear combination of the same degrees of the independent variable as in f(.), i.e. the map of the characteristics f --> F is close to a linear one. This unexpected result is useful for understanding nonlinear algebraic circuits, and is missed in the classical theory. The cases of f(v) = D1v + D2v^2 and f(v) = D1v + D3v^3, are analyzed in examples. Special topologies when the superposition must be ideal, are also considered. In the second part [2] of the work the "circuit mechanism" that is responsible for the high precision of the superposition, in the most general case, will be explained.
Settling the Polynomial Learnability of Mixtures of Gaussians
Venue: arXiv cs.LG 2010
Year: 2010

Given data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately estimate the mixture parameters. We give an algorithm for this problem that has a running time, and data requirement polynomial in the dimension and the inverse of the desired accuracy, with provably minimal assumptions on the Gaussians. As simple consequences of our learning algorithm, we can perform near-optimal clustering of the sample points and density estimation for mixtures of k Gaussians, efficiently. The building blocks of our algorithm are based on the work Kalai et al. [STOC 2010] that gives an efficient algorithm for learning mixtures of two Gaussians by considering a series of projections down to one dimension, and applying the method of moments to each univariate projection. A major technical hurdle in Kalai et al. is showing that one can efficiently learn univariate mixtures of two Gaussians. In contrast, because pathological scenarios can arise when considering univariate projections of mixtures of more than two Gaussians, the bulk of the work in this paper concerns how to leverage an algorithm for learning univariate mixtures (of many Gaussians) to yield an efficient algorithm for learning in high dimensions. Our algorithm employs hierarchical clustering and rescaling, together with delicate methods for backtracking and recovering from failures that can occur in our univariate algorithm. Finally, while the running time and data requirements of our algorithm depend exponentially on the number of Gaussians in the mixture, we prove that such a dependence is necessary.
Average case performance of heuristics for multi-dimensional assignment problems
Venue: arXiv cs.DM 2010
Year: 2010

We consider multi-dimensional assignment problems in a probabilistic setting. Our main results are: (i) A new efficient algorithm for the 3-dimensional planar problem, based on enumerating and selecting from a set of "alternating-path trees"; (ii) A new efficient matching-based algorithm for the 3-dimensional axial problem.
A Sparse Johnson--Lindenstrauss Transform
Venue: arXiv cs.DS 2010
Year: 2010

Dimension reduction is a key algorithmic tool with many applications including nearest-neighbor search, compressed sensing and linear algebra in the streaming model. In this work we obtain a {\em sparse} version of the fundamental tool in dimension reduction --- the Johnson--Lindenstrauss transform. Using hashing and local densification, we construct a sparse projection matrix with just $\tilde{O}(\frac{1}ε)$ non-zero entries per column. We also show a matching lower bound on the sparsity for a large class of projection matrices. Our bounds are somewhat surprising, given the known lower bounds of $Ω(\frac{1}{ε^2})$ both on the number of rows of any projection matrix and on the sparsity of projection matrices generated by natural constructions. Using this, we achieve an $\tilde{O}(\frac{1}ε)$ update time per non-zero element for a $(1\pmε)$-approximate projection, thereby substantially outperforming the $\tilde{O}(\frac{1}{ε^2})$ update time required by prior approaches. A variant of our method offers the same guarantees for sparse vectors, yet its $\tilde{O}(d)$ worst case running time matches the best approach of Ailon and Liberty.
Intelligent Technologies in Model Base Management System Design Automation
Venue: arXiv cs.OH 2010
Year: 2010

The article describes the prospects of model base management system design automation for decision support systems and suggests the toolbox scheme for design automation based on intelligent technologies.
Analysis of Graphs for Digital Preservation Suitability
Venue: arXiv cs.DL 2010
Year: 2010

We investigate the use of autonomically created small-world graphs as a framework for the long term storage of digital objects on the Web in a potentially hostile environment. We attack the classic Erdos - Renyi random, Barab'asi and Albert power law, Watts - Strogatz small world and our Unsupervised Small-World (USW) graphs using different attacker strategies and report their respective robustness. Using different attacker profiles, we construct a game where the attacker is allowed to use a strategy of his choice to remove a percentage of each graph's elements. The graph is then allowed to repair some portion of its self. We report on the number of alternating attack and repair turns until either the graph is disconnected, or the game exceeds the number of permitted turns. Based on our analysis, an attack strategy that focuses on removing the vertices with the highest betweenness value is most advantageous to the attacker. Power law graphs can become disconnected with the removal of a single edge; random graphs with the removal of as few as 1% of their vertices, small-world graphs with the removal of 14% vertices, and USW with the removal of 17% vertices. Watts - Strogatz small-world graphs are more robust and resilient than random or power law graphs. USW graphs are more robust and resilient than small world graphs. A graph of USW connected web objects (WOs) filled with data could outlive the individuals and institutions that created the data in an environment where WOs are lost due to random failures or directed attacks.
NgViz: Detecting DNS Tunnels through N-Gram Visualization and Quantitative Analysis
Venue: arXiv cs.CR 2010
Year: 2010

This paper introduced NgViz, a tool that examines DNS traffic and shows anomalies in n-gram frequencies. This is accomplished by comparing input files against a fingerprint of legitimate traffic. Both quantitative analysis and visual aids are provided that allow the user to make determinations about the legitimacy of the DNS traffic.
LIKWID: A lightweight performance-oriented tool suite for x86 multicore environments
Venue: arXiv cs.DC 2010
Year: 2010

Exploiting the performance of today's processors requires intimate knowledge of the microarchitecture as well as an awareness of the ever-growing complexity in thread and cache topology. LIKWID is a set of command-line utilities that addresses four key problems: Probing the thread and cache topology of a shared-memory node, enforcing thread-core affinity on a program, measuring performance counter metrics, and toggling hardware prefetchers. An API for using the performance counting features from user code is also included. We clearly state the differences to the widely used PAPI interface. To demonstrate the capabilities of the tool set we show the influence of thread pinning on performance using the well-known OpenMP STREAM triad benchmark, and use the affinity and hardware counter tools to study the performance of a stencil code specifically optimized to utilize shared caches on multicore chips.
Maintainability Estimation Model for Object-Oriented Software in Design Phase (MEMOOD)
Venue: arXiv cs.SE 2010
Year: 2010

Measuring software maintainability early in the development life cycle, especially at the design phase, may help designers to incorporate required enhancement and corrections for improving maintainability of the final software. This paper developed a multivariate linear model 'Maintainability Estimation Model for Object-Oriented software in Design phase' (MEMOOD), which estimates the maintainability of class diagrams in terms of their understandability and modifiability. While, in order to quantify class diagram's understandability and modifiability the paper further developed two more multivariate models. These two models use design level object-oriented metrics, to quantify understandability and modifiability of class diagram. Such early quantification of maintainability provides an opportunity to improve the maintainability of class diagram and consequently the maintainability of final software. All the three models have been validated through appropriate statistical measures and contextual interpretation has been drawn.
Crosstalk Noise Modeling for RC and RLC interconnects in Deep Submicron VLSI Circuits
Venue: arXiv cs.OH 2010
Year: 2010

The crosstalk noise model for noise constrained interconnects optimization is presented for RC interconnects. The proposed model has simple closed-form expressions, which is capable of predicting the noise amplitude and the noise pulse width of an RC interconnect as well as coupling locations (near-driver and near-receiver) on victim net. This paper also presents a crosstalk noise model for both identical and non identical coupled resistance-inductance-capacitance (RLC) interconnects, which is developed based on a decoupling technique exhibiting an average error of 6.8% as compared to SPICE. The crosstalk noise model, together with a proposed concept of effective mutual inductance, is applied to evaluate the effectiveness of the shielding technique.
On MMSE Properties and I-MMSE Implications in Parallel MIMO Gaussian Channels
Venue: arXiv cs.IT 2010
Year: 2010

This paper extends the "single crossing point" property of the scalar MMSE function, derived by Guo, Shamai and Verdú (first presented in ISIT 2008), to the parallel degraded MIMO scenario. It is shown that the matrix Q(t), which is the difference between the MMSE assuming a Gaussian input and the MMSE assuming an arbitrary input, has, at most, a single crossing point for each of its eigenvalues. Together with the I-MMSE relationship, a fundamental connection between Information Theory and Estimation Theory, this new property is employed to derive results in Information Theory. As a simple application of this property we provide an alternative converse proof for the broadcast channel (BC) capacity region under covariance constraint in this specific setting.
On the Impact of the Migration Topology on the Island Model
Venue: arXiv cs.DC 2010
Year: 2010

Parallel Global Optimization Algorithms (PGOA) provide an efficient way of dealing with hard optimization problems. One method of parallelization of GOAs that is frequently applied and commonly found in the contemporary literature is the so-called Island Model (IM). In this paper we analyze the impact of the migration topology on the performance of a PGOA which uses the Island Model. In particular we consider parallel Differential Evolution and Simulated Annealing with Adaptive Neighborhood and draw first conclusions that emerge from the conducted experiments.
Mobility Prediction in Wireless Ad Hoc Networks using Neural Networks
Venue: arXiv cs.NE 2010
Year: 2010

Mobility prediction allows estimating the stability of paths in a mobile wireless Ad Hoc networks. Identifying stable paths helps to improve routing by reducing the overhead and the number of connection interruptions. In this paper, we introduce a neural network based method for mobility prediction in Ad Hoc networks. This method consists of a multi-layer and recurrent neural network using back propagation through time algorithm for training.
Evaluation of Burst Loss Rate of an Optical Burst Switching (OBS) Network with Wavelength Conversion Capability
Venue: arXiv cs.OH 2010
Year: 2010

This paper presents a new analytical model for calculating burst loss rate (BLR) in a slotted optical burst switched network. The analytical result leads to a framework which provides guidelines for optical burst switched networks. Wavelength converter is used for burst contention resolution. The effect of several design parameters such as burst arrival probability, wavelength conversion capability, number of slots per burst and number of wavelengths is incorporated on the above performance measure. We also extend the analytical result of BLR for different types of service classes where each service class has a reserved number of wavelengths in a network with fixed number of wavelengths. We also introduce an algorithm to calculate the resultant number of wavelength for each service classes depending on the various scenarios.
On the Existence of Optimal Exact-Repair MDS Codes for Distributed Storage
Venue: arXiv cs.IT 2010
Year: 2010

The high repair cost of (n,k) Maximum Distance Separable (MDS) erasure codes has recently motivated a new class of codes, called Regenerating Codes, that optimally trade off storage cost for repair bandwidth. In this paper, we address bandwidth-optimal (n,k,d) Exact-Repair MDS codes, which allow for any failed node to be repaired exactly with access to arbitrary d survivor nodes, where k<=d<=n-1. We show the existence of Exact-Repair MDS codes that achieve minimum repair bandwidth (matching the cutset lower bound) for arbitrary admissible (n,k,d), i.e., k<n and k<=d<=n-1. Our approach is based on interference alignment techniques and uses vector linear codes which allow to split symbols into arbitrarily small subsymbols.
Modern Computer Arithmetic (version 0.5.1)
Venue: arXiv cs.DS 2010
Year: 2010

This is a draft of a book about algorithms for performing arithmetic, and their implementation on modern computers. We are concerned with software more than hardware - we do not cover computer architecture or the design of computer hardware. Instead we focus on algorithms for efficiently performing arithmetic operations such as addition, multiplication and division, and their connections to topics such as modular arithmetic, greatest common divisors, the Fast Fourier Transform (FFT), and the computation of elementary and special functions. The algorithms that we present are mainly intended for arbitrary-precision arithmetic. They are not limited by the computer word size, only by the memory and time available for the computation. We consider both integer and real (floating-point) computations. The book is divided into four main chapters, plus an appendix. Our aim is to present the latest developments in a concise manner. At the same time, we provide a self-contained introduction for the reader who is not an expert in the field, and exercises at the end of each chapter. Chapter titles are: 1, Integer Arithmetic; 2, Modular Arithmetic and the FFT; 3, Floating-Point Arithmetic; 4, Elementary and Special Function Evaluation; 5 (Appendix), Implementations and Pointers. The book also contains a bibliography of 236 entries, index, summary of notation, and summary of complexities.
Punctuation effects in English and Esperanto texts
Venue: arXiv cs.CL 2010
Year: 2010

A statistical physics study of punctuation effects on sentence lengths is presented for written texts: {\it Alice in wonderland} and {\it Through a looking glass}. The translation of the first text into esperanto is also considered as a test for the role of punctuation in defining a style, and for contrasting natural and artificial, but written, languages. Several log-log plots of the sentence length-rank relationship are presented for the major punctuation marks. Different power laws are observed with characteristic exponents. The exponent can take a value much less than unity ($ca.$ 0.50 or 0.30) depending on how a sentence is defined. The texts are also mapped into time series based on the word frequencies. The quantitative differences between the original and translated texts are very minutes, at the exponent level. It is argued that sentences seem to be more reliable than word distributions in discussing an author style.
Properties of Codes in the Johnson Scheme
Venue: arXiv cs.IT 2010
Year: 2010

Codes which attain the sphere packing bound are called perfect codes. The most important metrics in coding theory on which perfect codes are defined are the Hamming metric and the Johnson metric. While for the Hamming metric all perfect codes over finite fields are known, in the Johnson metric it was conjectured by Delsarte in 1970's that there are no nontrivial perfect codes. The general nonexistence proof still remains the open problem. In this work we examine constant weight codes as well as doubly constant weight codes, and reduce the range of parameters in which perfect codes may exist in both cases. We start with the constant weight codes. We introduce an improvement of Roos' bound for one-perfect codes, and present some new divisibility conditions, which are based on the connection between perfect codes in Johnson graph J(n,w) and block designs. Next, we consider binomial moments for perfect codes. We show which parameters can be excluded for one-perfect codes. We examine two-perfect codes in J(2w,w) and present necessary conditions for existence of such codes. We prove that there are no two-perfect codes in J(2w,w) with length less then 2.5*10^{15}. Next we examine perfect doubly constant weight codes. We present a family of parameters for codes whose size of sphere divides the size of whole space. We then prove a bound on length of such codes, similarly to Roos' bound for perfect codes in Johnson graph. Finally we describe Steiner systems and doubly Steiner systems, which are strongly connected with the constant weight and doubly constant weight codes respectively. We provide an anticode-based proof of a bound on length of Steiner system, prove that doubly Steiner system is a diameter perfect code and present a bound on length of doubly Steiner system.
Recursive Information Hiding in Visual Cryptography
Venue: arXiv cs.CR 2010
Year: 2010

Visual Cryptography is a secret sharing scheme that uses the human visual system to perform computations. This paper presents a recursive hiding scheme for 3 out of 5 secret sharing. The idea used is to hide smaller secrets in the shares of a larger secret without an expansion in the size of the latter.
Graph Sparsification via Refinement Sampling
Venue: arXiv cs.DS 2010
Year: 2010

A graph G'(V,E') is an \eps-sparsification of G for some \eps>0, if every (weighted) cut in G' is within (1\pm \eps) of the corresponding cut in G. A celebrated result of Benczur and Karger shows that for every undirected graph G, an \eps-sparsification with O(n\log n/\e^2) edges can be constructed in O(m\log^2n) time. Applications to modern massive data sets often constrain algorithms to use computation models that restrict random access to the input. The semi-streaming model, in which the algorithm is constrained to use \tilde O(n) space, has been shown to be a good abstraction for analyzing graph algorithms in applications to large data sets. Recently, a semi-streaming algorithm for graph sparsification was presented by Anh and Guha; the total running time of their implementation is Ω(mn), too large for applications where both space and time are important. In this paper, we introduce a new technique for graph sparsification, namely refinement sampling, that gives an \tilde{O}(m) time semi-streaming algorithm for graph sparsification. Specifically, we show that refinement sampling can be used to design a one-pass streaming algorithm for sparsification that takes O(\log\log n) time per edge, uses O(\log^2 n) space per node, and outputs an \eps-sparsifier with O(n\log^3 n/\eps^2) edges. At a slightly increased space and time complexity, we can reduce the sparsifier size to O(n \log n/\e^2) edges matching the Benczur-Karger result, while improving upon the Benczur-Karger runtime for m=ω(n\log^3 n). Finally, we show that an \eps-sparsifier with O(n \log n/\eps^2) edges can be constructed in two passes over the data and O(m) time whenever m =Ω(n^{1+δ}) for some constant δ>0. As a by-product of our approach, we also obtain an O(m\log\log n+n \log n) time streaming algorithm to compute a sparse k-connectivity certificate of a graph.
Dimensions of Formality: A Case Study for MKM in Software Engineering
Venue: arXiv cs.DL 2010
Year: 2010

We study the formalization of a collection of documents created for a Software Engineering project from an MKM perspective. We analyze how document and collection markup formats can cope with an open-ended, multi-dimensional space of primary and secondary classifications and relationships. We show that RDFa-based extensions of MKM formats, employing flexible "metadata" relationships referencing specific vocabularies for distinct dimensions, are well-suited to encode this and to put it into service. This formalized knowledge can be used for enriching interactive document browsing, for enabling multi-dimensional metadata queries over documents and collections, and for exporting Linked Data to the Semantic Web and thus enabling further reuse.
Multiscale approach for the network compression-friendly ordering
Venue: arXiv cs.DS 2010
Year: 2010

We present a fast multiscale approach for the network minimum logarithmic arrangement problem. This type of arrangement plays an important role in a network compression and fast node/link access operations. The algorithm is of linear complexity and exhibits good scalability which makes it practical and attractive for using on large-scale instances. Its effectiveness is demonstrated on a large set of real-life networks. These networks with corresponding best-known minimization results are suggested as an open benchmark for a research community to evaluate new methods for this problem.
Clustering processes
Venue: arXiv cs.LG 2010
Year: 2010

The problem of clustering is considered, for the case when each data point is a sample generated by a stationary ergodic process. We propose a very natural asymptotic notion of consistency, and show that simple consistent algorithms exist, under most general non-parametric assumptions. The notion of consistency is as follows: two samples should be put into the same cluster if and only if they were generated by the same distribution. With this notion of consistency, clustering generalizes such classical statistical problems as homogeneity testing and process classification. We show that, for the case of a known number of clusters, consistency can be achieved under the only assumption that the joint distribution of the data is stationary ergodic (no parametric or Markovian assumptions, no assumptions of independence, neither between nor within the samples). If the number of clusters is unknown, consistency can be achieved under appropriate assumptions on the mixing rates of the processes. (again, no parametric or independence assumptions). In both cases we give examples of simple (at most quadratic in each argument) algorithms which are consistent.