OpenRaiser/Intern-Atlas huggingface dataset:
A Generalization of the Fibonacci Word Fractal and the Fibonacci Snowflake
Venue: arXiv cs.DM 2014
Year: 2014

In this paper we introduce a family of infinite words that generalize the Fibonacci word and we study their combinatorial properties. Moreover, we associate to this family of words a family of curves, which have fractal properties, in particular these curves have as attractor the Fibonacci word fractal. Finally, we describe an infinite family of polyominoes (double squares) from the generalized Fibonacci words and we study some of their geometric properties. These last polyominoes generalize the Fibonacci snowflake.
Lossy Compression via Sparse Linear Regression: Computationally Efficient Encoding and Decoding
Venue: arXiv cs.IT 2014
Year: 2014

We propose computationally efficient encoders and decoders for lossy compression using a Sparse Regression Code. The codebook is defined by a design matrix and codewords are structured linear combinations of columns of this matrix. The proposed encoding algorithm sequentially chooses columns of the design matrix to successively approximate the source sequence. It is shown to achieve the optimal distortion-rate function for i.i.d Gaussian sources under the squared-error distortion criterion. For a given rate, the parameters of the design matrix can be varied to trade off distortion performance with encoding complexity. An example of such a trade-off as a function of the block length n is the following. With computational resource (space or time) per source sample of O((n/\log n)^2), for a fixed distortion-level above the Gaussian distortion-rate function, the probability of excess distortion decays exponentially in n. The Sparse Regression Code is robust in the following sense: for any ergodic source, the proposed encoder achieves the optimal distortion-rate function of an i.i.d Gaussian source with the same variance. Simulations show that the encoder has good empirical performance, especially at low and moderate rates.
Semi-explicit Parareal method based on convergence acceleration technique
Venue: arXiv cs.SY 2014
Year: 2014

The Parareal algorithm is used to solve time-dependent problems considering multiple solvers that may work in parallel. The key feature is a initial rough approximation of the solution that is iteratively refined by the parallel solvers. We report a derivation of the Parareal method that uses a convergence acceleration technique to improve the accuracy of the solution. Our approach uses firstly an explicit ODE solver to perform the parallel computations with different time-steps and then, a decomposition of the solution into specific convergent series, based on an extrapolation method, allows to refine the precision of the solution. Our proposed method exploits basic explicit integration methods, such as for example the explicit Euler scheme, in order to preserve the simplicity of the global parallel algorithm. The first part of the paper outlines the proposed method applied to the simple explicit Euler scheme and then the derivation of the classical Parareal algorithm is discussed and illustrated with numerical examples.
International Scientific Migration and Collaboration Patterns Following a Bibliometrics Line of Investigation
Venue: arXiv cs.DL 2014
Year: 2014

A bibliometric approach is explored to tracking international scientific migration, based on an analysis of the affiliation countries of authors publishing in peer reviewed journals indexed in Scopus. The paper introduces a model that relates base concepts in the study of migration to bibliometric constructs, and discusses the potentialities and limitations of a bibliometric approach both with respect to data accuracy and interpretation. Synchronous and asynchronous analyses are presented for 10 rapidly growing countries and 7 scientifically established countries. Rough error rates of the proposed indicators are estimated. It is concluded that the bibliometric approach is promising provided that its outcomes are interpreted with care, based on insight into the limits and potentialities of the bibliometric approach, and combined with complementary data, obtained, for instance, from researchers Curricula Vitae or survey or questionnaire based data. Error rates for units of assessment with indicator values based on sufficiently large numbers are estimated to be fairly below 10 per cent, but can be expected to vary substantially among countries of origin, especially between Asian countries and Western countries.
Distributed Full-duplex via Wireless Side Channels: Bounds and Protocols
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we study a three-node full-duplex network, where a base station is engaged in simultaneous up- and downlink communication in the same frequency band with two half-duplex mobile nodes. To reduce the impact of inter- node interference between the two mobile nodes on the system capacity, we study how an orthogonal side-channel between the two mobile nodes can be leveraged to achieve full-duplex-like multiplexing gains. We propose and characterize the achievable rates of four distributed full-duplex schemes, labeled bin-and- cancel, compress-and-cancel, estimate-and-cancel and decode- and-cancel. Of the four, bin-and-cancel is shown to achieve within 1 bit/s/Hz of the capacity region for all values of channel parameters. In contrast, the other three schemes achieve the near-optimal performance only in certain regimes of channel values. Asymptotic multiplexing gains of all proposed schemes are derived to show that the side-channel is extremely effective in regimes where inter-node interference has the highest impact.
Interactive Ant Colony Optimisation (iACO) for Early Lifecycle Software Design
Venue: arXiv cs.SE 2014
Year: 2014

Software design is crucial to successful software development, yet is a demanding multi-objective problem for software engineers. In an attempt to assist the software designer, interactive (i.e. human in-the-loop) meta-heuristic search techniques such as evolutionary computing have been applied and show promising results. Recent investigations have also shown that Ant Colony Optimization (ACO) can outperform evolutionary computing as a potential search engine for interactive software design. With a limited computational budget, ACO produces superior candidate design solutions in a smaller number of iterations. Building on these findings, we propose a novel interactive ACO (iACO) approach to assist the designer in early lifecycle software design, in which the search is steered jointly by subjective designer evaluation as well as machine fitness functions relating the structural integrity and surrogate elegance of software designs. Results show that iACO is speedy, responsive and highly effective in enabling interactive, dynamic multi-objective search in early lifecycle software design. Study participants rate the iACO search experience as compelling. Results of machine learning of fitness measure weightings indicate that software design elegance does indeed play a significant role in designer evaluation of candidate software design. We conclude that the evenness of the number of attributes and methods among classes (NAC) is a significant surrogate elegance measure, which in turn suggests that this evenness of distribution, when combined with structural integrity, is an implicit but crucial component of effective early lifecycle software design.
Partial-indistinguishability obfuscation using braids
Venue: arXiv cs.CR 2014
Year: 2014

An obfuscator is an algorithm that translates circuits into functionally-equivalent similarly-sized circuits that are hard to understand. Efficient obfuscators would have many applications in cryptography. Until recently, theoretical progress has mainly been limited to no-go results. Recent works have proposed the first efficient obfuscation algorithms for classical logic circuits, based on a notion of indistinguishability against polynomial-time adversaries. In this work, we propose a new notion of obfuscation, which we call partial-indistinguishability. This notion is based on computationally universal groups with efficiently computable normal forms, and appears to be incomparable with existing definitions. We describe universal gate sets for both classical and quantum computation, in which our definition of obfuscation can be met by polynomial-time algorithms. We also discuss some potential applications to testing quantum computers. We stress that the cryptographic security of these obfuscators, especially when composed with translation from other gate sets, remains an open question.
Propelinear 1-perfect codes from quadratic functions
Venue: arXiv cs.IT 2014
Year: 2014

Perfect codes obtained by the Vasil'ev--Schönheim construction from a linear base code and quadratic switching functions are transitive and, moreover, propelinear. This gives at least $\exp(cN^2)$ propelinear $1$-perfect codes of length $N$ over an arbitrary finite field, while an upper bound on the number of transitive codes is $\exp(C(N\ln N)^2)$. Keywords: perfect code, propelinear code, transitive code, automorphism group, Boolean function.
The computational landscape of permutation patterns
Venue: arXiv cs.CC 2014
Year: 2014

In the last years, different types of patterns in permutations have been studied: vincular, bivincular and mesh patterns, just to name a few. Every type of permutation pattern naturally defines a corresponding computational problem: Given a pattern P and a permutation T (the text), is P contained in T? In this paper we draw a map of the computational landscape of permutation pattern matching with different types of patterns. We provide a classical complexity analysis and investigate the impact of the pattern length on the computational hardness. Furthermore, we highlight several directions in which the study of computational aspects of permutation patterns could evolve.
Coloring triangle-free rectangle overlap graphs with $O(\log\log n)$ colors
Venue: arXiv cs.CG 2014
Year: 2014

Recently, it was proved that triangle-free intersection graphs of $n$ line segments in the plane can have chromatic number as large as $Θ(\log\log n)$. Essentially the same construction produces $Θ(\log\log n)$-chromatic triangle-free intersection graphs of a variety of other geometric shapes---those belonging to any class of compact arc-connected sets in $\mathbb{R}^2$ closed under horizontal scaling, vertical scaling, and translation, except for axis-parallel rectangles. We show that this construction is asymptotically optimal for intersection graphs of boundaries of axis-parallel rectangles, which can be alternatively described as overlap graphs of axis-parallel rectangles. That is, we prove that triangle-free rectangle overlap graphs have chromatic number $O(\log\log n)$, improving on the previous bound of $O(\log n)$. To this end, we exploit a relationship between off-line coloring of rectangle overlap graphs and on-line coloring of interval overlap graphs. Our coloring method decomposes the graph into a bounded number of subgraphs with a tree-like structure that "encodes" strategies of the adversary in the on-line coloring problem. Then, these subgraphs are colored with $O(\log\log n)$ colors using a combination of techniques from on-line algorithms (first-fit) and data structure design (heavy-light decomposition).
Nearest Neighbor Decoding and Pilot-Aided Channel Estimation for Fading Channels
Venue: arXiv cs.IT 2014
Year: 2014

We study the information rates of non-coherent, stationary, Gaussian, multiple-input multiple-output (MIMO) flat-fading channels that are achievable with nearest neighbor decoding and pilot-aided channel estimation. In particular, we investigate the behavior of these achievable rates in the limit as the signal- to-noise ratio (SNR) tends to infinity by analyzing the capacity pre-log, which is defined as the limiting ratio of the capacity to the logarithm of the SNR as the SNR tends to infinity. We demonstrate that a scheme estimating the channel using pilot symbols and detecting the message using nearest neighbor decoding (while assuming that the channel estimation is perfect) essentially achieves the capacity pre-log of non-coherent multiple-input single-output flat-fading channels, and it essentially achieves the best so far known lower bound on the capacity pre-log of non-coherent MIMO flat-fading channels. We then extend our analysis to the multiple-access channel.
The genus of regular languages
Venue: arXiv cs.FL 2014
Year: 2014

The article defines and studies the genus of finite state deterministic automata (FSA) and regular languages. Indeed, a FSA can be seen as a graph for which the notion of genus arises. At the same time, a FSA has a semantics via its underlying language. It is then natural to make a connection between the languages and the notion of genus. After we introduce and justify the the notion of the genus for regular languages, the following questions are addressed. First, depending on the size of the alphabet, we provide upper and lower bounds on the genus of regular languages : we show that under a relatively generic condition on the alphabet and the geometry of the automata, the genus grows at least linearly in terms of the size of the automata. Second, we show that the topological cost of the powerset determinization procedure is exponential. Third, we prove that the notion of minimization is orthogonal to the notion of genus. Fourth, we build regular languages of arbitrary large genus: the notion of genus defines a proper hierarchy of regular languages.
Decentralized Coded Caching Attains Order-Optimal Memory-Rate Tradeoff
Venue: arXiv cs.IT 2014
Year: 2014

Replicating or caching popular content in memories distributed across the network is a technique to reduce peak network loads. Conventionally, the main performance gain of this caching was thought to result from making part of the requested data available closer to end users. Instead, we recently showed that a much more significant gain can be achieved by using caches to create coded-multicasting opportunities, even for users with different demands, through coding across data streams. These coded-multicasting opportunities are enabled by careful content overlap at the various caches in the network, created by a central coordinating server. In many scenarios, such a central coordinating server may not be available, raising the question if this multicasting gain can still be achieved in a more decentralized setting. In this paper, we propose an efficient caching scheme, in which the content placement is performed in a decentralized manner. In other words, no coordination is required for the content placement. Despite this lack of coordination, the proposed scheme is nevertheless able to create coded-multicasting opportunities and achieves a rate close to the optimal centralized scheme.
On the Number of Interference Alignment Solutions for the K-User MIMO Channel with Constant Coefficients
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we study the number of different interference alignment (IA) solutions in a K-user multiple-input multiple-output (MIMO) interference channel, when the alignment is performed via beamforming and no symbol extensions are allowed. We focus on the case where the number of IA equations matches the number of variables. In this situation, the number of IA solutions is finite and constant for any channel realization out of a zero-measure set and, as we prove in the paper, it is given by an integral formula that can be numerically approximated using Monte Carlo integration methods. More precisely, the number of alignment solutions is the scaled average of the determinant of a certain Hermitian matrix related to the geometry of the problem. Interestingly, while the value of this determinant at an arbitrary point can be used to check the feasibility of the IA problem, its average (properly scaled) gives the number of solutions. For single-beam systems the asymptotic growth rate of the number of solutions is analyzed and some connections with classical combinatorial problems are presented. Nonetheless, our results can be applied to arbitrary interference MIMO networks, with any number of users, antennas and streams per user.
A Unified Community Detection, Visualization and Analysis method
Venue: arXiv cs.SI 2014
Year: 2014

Community detection in social graphs has attracted researchers' interest for a long time. With the widespread of social networks on the Internet it has recently become an important research domain. Most contributions focus upon the definition of algorithms for optimizing the so-called modularity function. In the first place interest was limited to unipartite graph inputs and partitioned community outputs. Recently bipartite graphs, directed graphs and overlapping communities have been investigated. Few contributions embrace at the same time the three types of nodes. In this paper we present a method which unifies commmunity detection for the three types of nodes and at the same time merges partitionned and overlapping communities. Moreover results are visualized in such a way that they can be analyzed and semantically interpreted. For validation we experiment this method on well known simple benchmarks. It is then applied to real data in three cases. In two examples of photos sets with tagged people we reveal social networks. A second type of application is of particularly interest. After applying our method to Human Brain Tractography Data provided by a team of neurologists, we produce clusters of white fibers in accordance with other well known clustering methods. Moreover our approach for visualizing overlapping clusters allows better understanding of the results by the neurologist team. These last results open up the possibility of applying community detection methods in other domains such as data analysis with original enhanced performances.
Probe Scheduling for Efficient Detection of Silent Failures
Venue: arXiv cs.NI 2014
Year: 2014

Most discovery systems for silent failures work in two phases: a continuous monitoring phase that detects presence of failures through probe packets and a localization phase that pinpoints the faulty element(s). This separation is important because localization requires significantly more resources than detection and should be initiated only when a fault is present. We focus on improving the efficiency of the detection phase, where the goal is to balance the overhead with the cost associated with longer failure detection times. We formulate a general model which unifies the treatment of probe scheduling mechanisms, stochastic or deterministic, and different cost objectives - minimizing average detection time (SUM) or worst-case detection time (MAX). We then focus on two classes of schedules. {\em Memoryless schedules} -- a subclass of stochastic schedules which is simple and suitable for distributed deployment. We show that the optimal memorlyess schedulers can be efficiently computed by convex programs (for SUM objectives) or linear programs (for MAX objectives), and surprisingly perhaps, are guaranteed to have expected detection times that are not too far off the (NP hard) stochastic optima. {\em Deterministic schedules} allow us to bound the maximum (rather than expected) cost of undetected faults, but like stochastic schedules, are NP hard to optimize. We develop novel efficient deterministic schedulers with provable approximation ratios. An extensive simulation study on real networks, demonstrates significant performance gains of our memoryless and deterministic schedulers over previous approaches. Our unified treatment also facilitates a clear comparison between different objectives and scheduling mechanisms.
Beyond Worst-Case Analysis for Joins with Minesweeper
Venue: arXiv cs.DB 2014
Year: 2014

We describe a new algorithm, Minesweeper, that is able to satisfy stronger runtime guarantees than previous join algorithms (colloquially, `beyond worst-case guarantees') for data in indexed search trees. Our first contribution is developing a framework to measure this stronger notion of complexity, which we call {\it certificate complexity}, that extends notions of Barbay et al. and Demaine et al.; a certificate is a set of propositional formulae that certifies that the output is correct. This notion captures a natural class of join algorithms. In addition, the certificate allows us to define a strictly stronger notion of runtime complexity than traditional worst-case guarantees. Our second contribution is to develop a dichotomy theorem for the certificate-based notion of complexity. Roughly, we show that Minesweeper evaluates $β$-acyclic queries in time linear in the certificate plus the output size, while for any $β$-cyclic query there is some instance that takes superlinear time in the certificate (and for which the output is no larger than the certificate size). We also extend our certificate-complexity analysis to queries with bounded treewidth and the triangle query.
Looking at Mean-Payoff and Total-Payoff through Windows
Venue: arXiv cs.GT 2014
Year: 2014

We consider two-player games played on weighted directed graphs with mean-payoff and total-payoff objectives, two classical quantitative objectives. While for single-dimensional games the complexity and memory bounds for both objectives coincide, we show that in contrast to multi-dimensional mean-payoff games that are known to be coNP-complete, multi-dimensional total-payoff games are undecidable. We introduce conservative approximations of these objectives, where the payoff is considered over a local finite window sliding along a play, instead of the whole play. For single dimension, we show that (i) if the window size is polynomial, deciding the winner takes polynomial time, and (ii) the existence of a bounded window can be decided in NP $\cap$ coNP, and is at least as hard as solving mean-payoff games. For multiple dimensions, we show that (i) the problem with fixed window size is EXPTIME-complete, and (ii) there is no primitive-recursive algorithm to decide the existence of a bounded window.
Unsupervised edge map scoring: a statistical complexity approach
Venue: arXiv cs.CV 2014
Year: 2014

We propose a new Statistical Complexity Measure (SCM) to qualify edge maps without Ground Truth (GT) knowledge. The measure is the product of two indices, an \emph{Equilibrium} index $\mathcal{E}$ obtained by projecting the edge map into a family of edge patterns, and an \emph{Entropy} index $\mathcal{H}$, defined as a function of the Kolmogorov Smirnov (KS) statistic. This new measure can be used for performance characterization which includes: (i)~the specific evaluation of an algorithm (intra-technique process) in order to identify its best parameters, and (ii)~the comparison of different algorithms (inter-technique process) in order to classify them according to their quality. Results made over images of the South Florida and Berkeley databases show that our approach significantly improves over Pratt's Figure of Merit (PFoM) which is the objective reference-based edge map evaluation standard, as it takes into account more features in its evaluation.