OpenRaiser/Intern-Atlas huggingface dataset:
On the Optimality of Treating Interference as Noise
Venue: arXiv cs.IT 2013
Year: 2013

It is shown that in the K-user interference channel, if for each user the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all values in dB scale), then the simple scheme of using point to point Gaussian codebooks with appropriate power levels at each transmitter and treating interference as noise at every receiver (in short, TIN scheme) achieves all points in the capacity region to within a constant gap. The generalized degrees of freedom (GDoF) region under this condition is a polyhedron, which is shown to be fully achieved by the same scheme, without the need for time-sharing. The results are proved by first deriving a polyhedral relaxation of the GDoF region achieved by TIN, then providing a dual characterization of this polyhedral region via the use of potential functions, and finally proving the optimality of this region in the desired regime.
A Lower Bound for Fourier Transform Computation in a Linear Model Over 2x2 Unitary Gates Using Matrix Entropy
Venue: arXiv cs.CC 2013
Year: 2013

Obtaining a non-trivial (super-linear) lower bound for computation of the Fourier transform in the linear circuit model has been a long standing open problem. All lower bounds so far have made strong restrictions on the computational model. One of the most well known results, by Morgenstern from 1973, provides an $Ω(n \log n)$ lower bound for the \emph{unnormalized} FFT when the constants used in the computation are bounded. The proof uses a potential function related to a determinant. The determinant of the unnormalized Fourier transform is $n^{n/2}$, and thus by showing that it can grow by at most a constant factor after each step yields the result. This classic result, however, does not explain why the \emph{normalized} Fourier transform, which has a unit determinant, should take $Ω(n\log n)$ steps to compute. In this work we show that in a layered linear circuit model restricted to unitary $2\times 2$ gates, one obtains an $Ω(n\log n)$ lower bound. The well known FFT works in this model. The main argument concluded from this work is that a potential function that might eventually help proving the $Ω(n\log n)$ conjectured lower bound for computation of Fourier transform is not related to matrix determinant, but rather to a notion of matrix entropy.
Power to the Points: Validating Data Memberships in Clusterings
Venue: arXiv cs.LG 2013
Year: 2013

A clustering is an implicit assignment of labels of points, based on proximity to other points. It is these labels that are then used for downstream analysis (either focusing on individual clusters, or identifying representatives of clusters and so on). Thus, in order to trust a clustering as a first step in exploratory data analysis, we must trust the labels assigned to individual data. Without supervision, how can we validate this assignment? In this paper, we present a method to attach affinity scores to the implicit labels of individual points in a clustering. The affinity scores capture the confidence level of the cluster that claims to "own" the point. This method is very general: it can be used with clusterings derived from Euclidean data, kernelized data, or even data derived from information spaces. It smoothly incorporates importance functions on clusters, allowing us to eight different clusters differently. It is also efficient: assigning an affinity score to a point depends only polynomially on the number of clusters and is independent of the number of points in the data. The dimensionality of the underlying space only appears in preprocessing. We demonstrate the value of our approach with an experimental study that illustrates the use of these scores in different data analysis tasks, as well as the efficiency and flexibility of the method. We also demonstrate useful visualizations of these scores; these might prove useful within an interactive analytics framework.
How modular structure can simplify tasks on networks
Venue: arXiv cs.SI 2013
Year: 2013

By considering the task of finding the shortest walk through a network we find an algorithm for which the run time is not as O(2^n), with n being the number of nodes, but instead scales with the number of nodes in a coarsened network. This coarsened network has a number of nodes related to the number of dense regions in the original graph. Since we exploit a form of local community detection as a preprocessing, this work gives support to the project of developing heuristic algorithms for detecting dense regions in networks: preprocessing of this kind can accelerate optimization tasks on networks. Our work also suggests a class of empirical conjectures for how structural features of efficient networked systems might scale with system size.
Computational molecular engineering as an emerging technology in process engineering
Venue: arXiv cs.DC 2013
Year: 2013

The present level of development of molecular force field methods is assessed from the point of view of simulation-based engineering, outlining the immediate perspective for further development and highlighting the newly emerging discipline of Computational Molecular Engineering (CME) which makes basic research in soft matter physics fruitful for industrial applications. Within the coming decade, major breakthroughs can be reached if a research focus is placed on processes at interfaces, combining aspects where an increase in the accessible length and time scales due to massively parallel high-performance computing will lead to particularly significant improvements.
Errors and their mitigation at the Kirchhoff-law-Johnson-noise secure key exchange
Venue: arXiv cs.ET 2013
Year: 2013

A method to quantify the error probability at the Kirchhoff-law-Johnson-noise (KLJN) secure key exchange is introduced. The types of errors due to statistical inaccuracies in noise voltage measurements are classified and the error probability is calculated. The most interesting finding is that the error probability decays exponentially with the duration of the time window of single bit exchange. The results indicate that it is feasible to have so small error probabilities of the exchanged bits that error correction algorithms are not required. The results are demonstrated with practical considerations.
Computer-Assisted Proofs of Some Identities for Bessel Functions of Fractional Order
Venue: arXiv cs.SC 2013
Year: 2013

We employ computer algebra algorithms to prove a collection of identities involving Bessel functions with half-integer orders and other special functions. These identities appear in the famous Handbook of Mathematical Functions, as well as in its successor, the DLMF, but their proofs were lost. We use generating functions and symbolic summation techniques to produce new proofs for them.
Note on Evaluation of Hierarchical Modular Systems
Venue: arXiv cs.AI 2013
Year: 2013

This survey note describes a brief systemic view to approaches for evaluation of hierarchical composite (modular) systems. The list of considered issues involves the following: (i) basic assessment scales (quantitative scale, ordinal scale, multicriteria description, two kinds of poset-like scales), (ii) basic types of scale transformations problems, (iii) basic types of scale integration methods. Evaluation of the modular systems is considered as assessment of system components (and their compatibility) and integration of the obtained local estimates into the total system estimate(s). This process is based on the above-mentioned problems (i.e., scale transformation and integration). Illustrations of the assessment problems and evaluation approaches are presented (including numerical examples).
A Data Mining Approach to Solve the Goal Scoring Problem
Venue: arXiv cs.AI 2013
Year: 2013

In soccer, scoring goals is a fundamental objective which depends on many conditions and constraints. Considering the RoboCup soccer 2D-simulator, this paper presents a data mining-based decision system to identify the best time and direction to kick the ball towards the goal to maximize the overall chances of scoring during a simulated soccer match. Following the CRISP-DM methodology, data for modeling were extracted from matches of major international tournaments (10691 kicks), knowledge about soccer was embedded via transformation of variables and a Multilayer Perceptron was used to estimate the scoring chance. Experimental performance assessment to compare this approach against previous LDA-based approach was conducted from 100 matches. Several statistical metrics were used to analyze the performance of the system and the results showed an increase of 7.7% in the number of kicks, producing an overall increase of 78% in the number of goals scored.
Permutation Meets Parallel Compressed Sensing: How to Relax Restricted Isometry Property for 2D Sparse Signals
Venue: arXiv cs.IT 2013
Year: 2013

Traditional compressed sensing considers sampling a 1D signal. For a multidimensional signal, if reshaped into a vector, the required size of the sensing matrix becomes dramatically large, which increases the storage and computational complexity significantly. To solve this problem, we propose to reshape the multidimensional signal into a 2D signal and sample the 2D signal using compressed sensing column by column with the same sensing matrix. It is referred to as parallel compressed sensing, and it has much lower storage and computational complexity. For a given reconstruction performance of parallel compressed sensing, if a so-called acceptable permutation is applied to the 2D signal, we show that the corresponding sensing matrix has a smaller required order of restricted isometry property condition, and thus, storage and computation requirements are further lowered. A zigzag-scan-based permutation, which is shown to be particularly useful for signals satisfying a layer model, is introduced and investigated. As an application of the parallel compressed sensing with the zigzag-scan-based permutation, a video compression scheme is presented. It is shown that the zigzag-scan-based permutation increases the peak signal-to-noise ratio of reconstructed images and video frames.
Performance of Joint Channel and Physical Network Coding Based on Alamouti STBC
Venue: arXiv cs.IT 2013
Year: 2013

This work considers the protograph-coded physical network coding (PNC) based on Alamouti space-time block coding (STBC) over Nakagami-fading two-way relay channels, in which both the two sources and relay possess two antennas. We first propose a novel precoding scheme at the two sources so as to implement the iterative decoder efficiently at the relay. We further address a simplified updating rule of the log-likelihood-ratio (LLR) in such a decoder. Based on the simplified LLR-updating rule and Gaussian approximation, we analyze the theoretical bit-error-rate (BER) of the system, which is shown to be consistent with the decoding thresholds and simulated results. Moreover, the theoretical analysis has lower computational complexity than the protograph extrinsic information transfer (PEXIT) algorithm. Consequently, the analysis not only provides a simple way to evaluate the error performance but also facilitates the design of the joint channel-and-PNC (JCNC) in wireless communication scenarios.
A Parallel and Scalable Iterative Solver for Sequences of Dense Eigenproblems Arising in FLAPW
Venue: arXiv cs.DC 2013
Year: 2013

In one of the most important methods in Density Functional Theory - the Full-Potential Linearized Augmented Plane Wave (FLAPW) method - dense generalized eigenproblems are organized in long sequences. Moreover each eigenproblem is strongly correlated to the next one in the sequence. We propose a novel approach which exploits such correlation through the use of an eigensolver based on subspace iteration and accelerated with Chebyshev polynomials. The resulting solver, parallelized using the Elemental library framework, achieves excellent scalability and is competitive with current dense parallel eigensolvers.
Group detection in complex networks: An algorithm and comparison of the state of the art
Venue: arXiv cs.SI 2013
Year: 2013

Complex real-world networks commonly reveal characteristic groups of nodes like communities and modules. These are of value in various applications, especially in the case of large social and information networks. However, while numerous community detection techniques have been presented in the literature, approaches for other groups of nodes are relatively rare and often limited in some way. We present a simple propagation-based algorithm for general group detection that requires no a priori knowledge and has near ideal complexity. The main novelty here is that different types of groups are revealed through an adequate hierarchical group refinement procedure. The proposed algorithm is validated on various synthetic and real-world networks, and rigorously compared against twelve other state-of-the-art approaches on group detection, hierarchy discovery and link prediction tasks. The algorithm is comparable to the state of the art in community detection, while superior in general group detection and link prediction. Based on the comparison, we also dis- cuss some prominent directions for future work on group detection in complex networks.
Experiments in Information Sharing
Venue: arXiv cs.GT 2013
Year: 2013

This paper reports experimental data describing the dynamics of three key information-sharing outcomes: quantity of information shared, falsification and accuracy. The experimental design follows a formal model predicting that cooperative incentives are needed to motivate subsidiaries of large organizations to share information. Empirical reaction functions reveal how lagged values of information-sharing outcomes influence information sharing in the current round. Cooperative treatments pay bonuses to everyone if at least one individual (or subsidiary) achieves accuracy. Tournament treatments pay a single bonus to whoever achieves accuracy first. As expected, tournament incentives tend to reduce sharing, increase falsification and impair accuracy. Several surprises not predicted by the formal model emerge from the data. Conditional cooperation occurs regardless of the incentive scheme, implying that the mechanism through which incentives influence improvements in information sharing is indirect.
Introduction to Judea Pearl's Do-Calculus
Venue: arXiv cs.AI 2013
Year: 2013

This is a purely pedagogical paper with no new results. The goal of the paper is to give a fairly self-contained introduction to Judea Pearl's do-calculus, including proofs of his 3 rules.
Distributed Minimum Cut Approximation
Venue: arXiv cs.DS 2013
Year: 2013

We study the problem of computing approximate minimum edge cuts by distributed algorithms. We use a standard synchronous message passing model where in each round, $O(\log n)$ bits can be transmitted over each edge (a.k.a. the CONGEST model). We present a distributed algorithm that, for any weighted graph and any $ε\in (0, 1)$, with high probability finds a cut of size at most $O(ε^{-1}λ)$ in $O(D) + \tilde{O}(n^{1/2 + ε})$ rounds, where $λ$ is the size of the minimum cut. This algorithm is based on a simple approach for analyzing random edge sampling, which we call the random layering technique. In addition, we also present another distributed algorithm, which is based on a centralized algorithm due to Matula [SODA '93], that with high probability computes a cut of size at most $(2+ε)λ$ in $\tilde{O}((D+\sqrt{n})/ε^5)$ rounds for any $ε>0$. The time complexities of both of these algorithms almost match the $\tildeΩ(D + \sqrt{n})$ lower bound of Das Sarma et al. [STOC '11], thus leading to an answer to an open question raised by Elkin [SIGACT-News '04] and Das Sarma et al. [STOC '11]. Furthermore, we also strengthen the lower bound of Das Sarma et al. by extending it to unweighted graphs. We show that the same lower bound also holds for unweighted multigraphs (or equivalently for weighted graphs in which $O(w\log n)$ bits can be transmitted in each round over an edge of weight $w$), even if the diameter is $D=O(\log n)$. For unweighted simple graphs, we show that even for networks of diameter $\tilde{O}(\frac{1}λ\cdot \sqrt{\frac{n}{αλ}})$, finding an $α$-approximate minimum cut in networks of edge connectivity $λ$ or computing an $α$-approximation of the edge connectivity requires $\tildeΩ(D + \sqrt{\frac{n}{αλ}})$ rounds.
Replication based storage systems with local repair
Venue: arXiv cs.IT 2013
Year: 2013

We consider the design of regenerating codes for distributed storage systems that enjoy the property of local, exact and uncoded repair, i.e., (a) upon failure, a node can be regenerated by simply downloading packets from the surviving nodes and (b) the number of surviving nodes contacted is strictly smaller than the number of nodes that need to be contacted for reconstructing the stored file. Our codes consist of an outer MDS code and an inner fractional repetition code that specifies the placement of the encoded symbols on the storage nodes. For our class of codes, we identify the tradeoff between the local repair property and the minimum distance. We present codes based on graphs of high girth, affine resolvable designs and projective planes that meet the minimum distance bound for specific choices of file sizes.
Gray codes and Enumerative Coding for vector spaces
Venue: arXiv cs.IT 2013
Year: 2013

Gray codes for vector spaces are considered in two graphs: the Grassmann graph, and the projective-space graph, both of which have recently found applications in network coding. For the Grassmann graph, constructions of cyclic optimal codes are given for all parameters. As for the projective-space graph, two constructions for specific parameters are provided, as well some non-existence results. Furthermore, encoding and decoding algorithms are given for the Grassmannian Gray code, which induce an enumerative-coding scheme. The computational complexity of the algorithms is at least as low as known schemes, and for certain parameter ranges, the new scheme outperforms previously-known ones.
Semantic Web Search based on Ontology Modeling using Protege Reasoner
Venue: arXiv cs.IR 2013
Year: 2013

The Semantic Web works on the existing Web which presents the meaning of information as well-defined vocabularies understood by the people. Semantic Search, at the same time, works on improving the accuracy if a search by understanding the intent of the search and providing contextually relevant results. This paper describes a semantic approach toward web search through a PHP application. The goal was to parse through a user's browsing history and return semantically relevant web pages for the search query provided.
A remark on algebraic immunity of Boolean functions
Venue: arXiv cs.CR 2013
Year: 2013

In this correspondence, an equivalent definition of algebraic immunity of Boolean functions is posed, which can clear up the confusion caused by the proof of optimal algebraic immunity of the Carlet-Feng function and some other functions constructed by virtue of Carlet and Feng's idea.
Semi-bounded Rationality: A model for decision making
Venue: arXiv cs.AI 2013
Year: 2013

In this paper the theory of semi-bounded rationality is proposed as an extension of the theory of bounded rationality. In particular, it is proposed that a decision making process involves two components and these are the correlation machine, which estimates missing values, and the causal machine, which relates the cause to the effect. Rational decision making involves using information which is almost always imperfect and incomplete as well as some intelligent machine which if it is a human being is inconsistent to make decisions. In the theory of bounded rationality this decision is made irrespective of the fact that the information to be used is incomplete and imperfect and the human brain is inconsistent and thus this decision that is to be made is taken within the bounds of these limitations. In the theory of semi-bounded rationality, signal processing is used to filter noise and outliers in the information and the correlation machine is applied to complete the missing information and artificial intelligence is used to make more consistent decisions.
New Construction of Authentication Codes with Arbitration from Pseudo-Symplectic Geometry over Finite Fields
Venue: arXiv cs.CR 2013
Year: 2013

A new construction of authentication codes with arbitration from pseudo-symplectic geometry over finite fields is given. The parameters and the probabilities of deceptions of the codes are also computed.
Full abstraction for fair testing in CCS
Venue: arXiv cs.LO 2013
Year: 2013

In previous work with Pous, we defined a semantics for CCS which may both be viewed as an innocent presheaf semantics and as a concurrent game semantics. It is here proved that a behavioural equivalence induced by this semantics on CCS processes is fully abstract for fair testing equivalence. The proof relies on a new algebraic notion called playground, which represents the 'rule of the game'. From any playground, two languages, equipped with labelled transition systems, are derived, as well as a strong, functional bisimulation between them.
Comparison of a citation-based indicator and peer review for absolute and specific measures of research-group excellence
Venue: arXiv cs.DL 2013
Year: 2013

Many different measures are used to assess academic research excellence and these are subject to ongoing discussion and debate within the scientometric, university-management and policy-making communities internationally. One topic of continued importance is the extent to which citation-based indicators compare with peer-review-based evaluation. Here we analyse the correlations between values of a particular citation-based impact indicator and peer-review scores in several academic disciplines, from natural to social sciences and humanities. We perform the comparison for research groups rather than for individuals. We make comparisons on two levels. At an absolute level, we compare total impact and overall strength of the group as a whole. At a specific level, we compare academic impact and quality, normalised by the size of the group. We find very high correlations at the former level for some disciplines and poor correlations at the latter level for all disciplines. This means that, although the citation-based scores could help to describe research-group strength, in particular for the so-called hard sciences, they should not be used as a proxy for ranking or comparison of research groups. Moreover, the correlation between peer-evaluated and citation-based scores is weaker for soft sciences.
Adaptive Reduced-Rank Processing Using a Projection Operator Based on Joint Iterative Optimization of Adaptive Filters For CDMA Interference Suppression
Venue: arXiv cs.IT 2013
Year: 2013

This paper proposes a novel adaptive reduced-rank filtering scheme based on the joint iterative optimization of adaptive filters. The proposed scheme consists of a joint iterative optimization of a bank of full-rank adaptive filters that constitutes the projection matrix and an adaptive reduced-rank filter that operates at the output of the bank of filters. We describe minimum mean-squared error (MMSE) expressions for the design of the projection matrix and the reduced-rank filter and simple least-mean squares (LMS) adaptive algorithms for its computationally efficient implementation. Simulation results for a CDMA interference suppression application reveals that the proposed scheme significantly outperforms the state-of-the-art reduced-rank schemes, while requiring a significantly lower computational complexity.