OpenRaiser/Intern-Atlas huggingface dataset:
Polar Codes with Mixed-Kernels
Venue: arXiv cs.IT 2015
Year: 2015

A generalization of the polar coding scheme called mixed-kernels is introduced. This generalization exploits several homogeneous kernels over alphabets of different sizes. An asymptotic analysis of the proposed scheme shows that its polarization properties are strongly related to the ones of the constituent kernels. Simulation of finite length instances of the scheme indicate their advantages both in error correction performance and complexity compared to the known polar coding structures.
Managing key multicasting through orthogonal systems
Venue: arXiv cs.CR 2015
Year: 2015

In this paper we propose a new protocol to manage multicast key distribution. The protocol is based on the use of orthogonal systems in vector spaces. The main advantage in comparison to other existing multicast key management protocols is that the length and the number of the messages which have to be sent are considerably smaller. This makes the protocol especially attractive when the number of legitimate receivers is large.
Extropy: Complementary Dual of Entropy
Venue: arXiv cs.IT 2015
Year: 2015

This article provides a completion to theories of information based on entropy, resolving a longstanding question in its axiomatization as proposed by Shannon and pursued by Jaynes. We show that Shannon's entropy function has a complementary dual function which we call "extropy." The entropy and the extropy of a binary distribution are identical. However, the measure bifurcates into a pair of distinct measures for any quantity that is not merely an event indicator. As with entropy, the maximum extropy distribution is also the uniform distribution, and both measures are invariant with respect to permutations of their mass functions. However, they behave quite differently in their assessments of the refinement of a distribution, the axiom which concerned Shannon and Jaynes. Their duality is specified via the relationship among the entropies and extropies of course and fine partitions. We also analyze the extropy function for densities, showing that relative extropy constitutes a dual to the Kullback-Leibler divergence, widely recognized as the continuous entropy measure. These results are unified within the general structure of Bregman divergences. In this context they identify half the $L_2$ metric as the extropic dual to the entropic directed distance. We describe a statistical application to the scoring of sequential forecast distributions which provoked the discovery.
Quantitative Languages Defined by Functional Automata
Venue: arXiv cs.FL 2015
Year: 2015

A weighted automaton is functional if any two accepting runs on the same finite word have the same value. In this paper, we investigate functional weighted automata for four different measures: the sum, the mean, the discounted sum of weights along edges and the ratio between rewards and costs. On the positive side, we show that functionality is decidable for the four measures. Furthermore, the existential and universal threshold problems, the language inclusion problem and the equivalence problem are all decidable when the weighted automata are functional. On the negative side, we also study the quantitative extension of the realizability problem and show that it is undecidable for sum, mean and ratio. We finally show how to decide whether the language associated with a given functional automaton can be defined with a deterministic one, for sum, mean and discounted sum. The results on functionality and determinizability are expressed for the more general class of functional group automata. This allows one to formulate within the same framework new results related to discounted sum automata and known results on sum and mean automata. Ratio automata do not fit within this general scheme and different techniques are required to decide functionality.
tym: Typed Matlab
Venue: arXiv cs.PL 2015
Year: 2015

Although, many scientists and engineers use Octave or MATLAB as their preferred programming language, dynamic nature of these languages can lead to slower running-time of programs written in these languages compared to programs written in languages which are not as dynamic, like C, C++ and Fortran. In this work we developed a translator for a new programming language (tym) which tries to address performance issues, common in scientific programs, by adding new constructs to a subset of Octave/MATLAB language. Our translator compiles programs written in tym, to efficient C++ code.
On Strong Graph Partitions and Universal Steiner Trees
Venue: arXiv cs.DS 2015
Year: 2015

We study the problem of constructing universal Steiner trees for undirected graphs. Given a graph $G$ and a root node $r$, we seek a single spanning tree $T$ of minimum {\em stretch}, where the stretch of $T$ is defined to be the maximum ratio, over all terminal sets $X$, of the cost of the minimal sub-tree $T_X$ of $T$ that connects $X$ to $r$ to the cost of an optimal Steiner tree connecting $X$ to $r$ in $G$. Universal Steiner trees (USTs) are important for data aggregation problems where computing the Steiner tree from scratch for every input instance of terminals is costly, as for example in low energy sensor network applications. We provide a polynomial time \ust\ construction for general graphs with $2^{O(\sqrt{\log n})}$-stretch. We also give a polynomial time $\polylog(n)$-stretch construction for minor-free graphs. One basic building block of our algorithms is a hierarchy of graph partitions, each of which guarantees small strong diameter for each cluster and bounded neighbourhood intersections for each node. We show close connections between the problems of constructing USTs and building such graph partitions. Our construction of partition hierarchies for general graphs is based on an iterative cluster merging procedure, while the one for minor-free graphs is based on a separator theorem for such graphs and the solution to a cluster aggregation problem that may be of independent interest even for general graphs. To our knowledge, this is the first subpolynomial-stretch ($o(n^ε)$ for any $ε> 0$) UST construction for general graphs, and the first polylogarithmic-stretch UST construction for minor-free graphs.
Un protocole de routage à basse consommation d'énergie selon l'approche de clustering pour les réseaux de capteurs sans fils
Venue: arXiv cs.NI 2015
Year: 2015

In this paper we propose a new routing protocol with low energy consumption for wireless sensor networks based on the clustering approach. Our protocol is based on a strategy which aims at providing a more equitable exploitation of the selected nodes (cluster-heads) energy by distributing their load of the managed sensors during the clustering process. In order to save the energy dissipated while transmitting sensed data to the base station, the multi-hops routing strategy is used to arrange the communication of the data between cluster-heads nodes. Simulation results demonstrate that our proposed protocol decreases the energy consumption and prolongs the network lifetime.
On Zarankiewicz Problem and Depth-Two Superconcentrators
Venue: arXiv cs.DM 2015
Year: 2015

We show tight necessary and sufficient conditions on the sizes of small bipartite graphs whose union is a larger bipartite graph that has no large bipartite independent set. Our main result is a common generalization of two classical results in graph theory: the theorem of Kővári, Sós and Turán on the minimum number of edges in a bipartite graph that has no large independent set, and the theorem of Hansel (also Katona and Szemerédi, Krichevskii) on the sum of the sizes of bipartite graphs that can be used to construct a graph (non-necessarily bipartite) that has no large independent set. As an application of our results, we show how they unify the underlying combinatorial principles developed in the proof of tight lower bounds for depth-two superconcentrators.
A Measurement Based Shadow Fading Model for Vehicle-to-Vehicle Network Simulations
Venue: arXiv cs.NI 2015
Year: 2015

The vehicle-to-vehicle (V2V) propagation channel has significant implications on the design and performance of novel communication protocols for vehicular ad hoc networks (VANETs). Extensive research efforts have been made to develop V2V channel models to be implemented in advanced VANET system simulators for performance evaluation. The impact of shadowing caused by other vehicles has, however, largely been neglected in most of the models, as well as in the system simulations. In this paper we present a shadow fading model targeting system simulations based on real measurements performed in urban and highway scenarios. The measurement data is separated into three categories, line-of-sight (LOS), obstructed line-of-sight (OLOS) by vehicles, and non line-of-sight due to buildings, with the help of video information recorded during the measurements. It is observed that vehicles obstructing the LOS induce an additional average attenuation of about 10 dB in the received signal power. An approach to incorporate the LOS/OLOS model into existing VANET simulators is also provided. Finally, system level VANET simulation results are presented, showing the difference between the LOS/OLOS model and a channel model based on Nakagami-m fading.
On the Easiest and Hardest Fitness Functions
Venue: arXiv cs.NE 2015
Year: 2015

The hardness of fitness functions is an important research topic in the field of evolutionary computation. In theory, the study can help understanding the ability of evolutionary algorithms. In practice, the study may provide a guideline to the design of benchmarks. The aim of this paper is to answer the following research questions: Given a fitness function class, which functions are the easiest with respect to an evolutionary algorithm? Which are the hardest? How are these functions constructed? The paper provides theoretical answers to these questions. The easiest and hardest fitness functions are constructed for an elitist (1+1) evolutionary algorithm to maximise a class of fitness functions with the same optima. It is demonstrated that the unimodal functions are the easiest and deceptive functions are the hardest in terms of the time-fitness landscape. The paper also reveals that the easiest fitness function to one algorithm may become the hardest to another algorithm, and vice versa.
Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process
Venue: arXiv cs.SI 2015
Year: 2015

Influence maximization is a problem of finding a small set of highly influential users, also known as seeds, in a social network such that the spread of influence under certain propagation models is maximized. In this paper, we consider time-critical influence maximization, in which one wants to maximize influence spread within a given deadline. Since timing is considered in the optimization, we also extend the Independent Cascade (IC) model and the Linear Threshold (LT) model to incorporate the time delay aspect of influence diffusion among individuals in social networks. We show that time-critical influence maximization under the time-delayed IC and LT models maintains desired properties such as submodularity, which allows a greedy approximation algorithm to achieve an approximation ratio of $1-1/e$. To overcome the inefficiency of the greedy algorithm, we design two heuristic algorithms: the first one is based on a dynamic programming procedure that computes exact influence in tree structures and directed acyclic subgraphs, while the second one converts the problem to one in the original models and then applies existing fast heuristic algorithms to it. Our simulation results demonstrate that our algorithms achieve the same level of influence spread as the greedy algorithm while running a few orders of magnitude faster, and they also outperform existing fast heuristics that disregard the deadline constraint and delays in diffusion.
Modular session types for objects
Venue: arXiv cs.PL 2015
Year: 2015

Session types allow communication protocols to be specified type-theoretically so that protocol implementations can be verified by static type checking. We extend previous work on session types for distributed object-oriented languages in three ways. (1) We attach a session type to a class definition, to specify the possible sequences of method calls. (2) We allow a session type (protocol) implementation to be modularized, i.e. partitioned into separately-callable methods. (3) We treat session-typed communication channels as objects, integrating their session types with the session types of classes. The result is an elegant unification of communication channels and their session types, distributed object-oriented programming, and a form of typestate supporting non-uniform objects, i.e. objects that dynamically change the set of available methods. We define syntax, operational se-mantics, a sound type system, and a sound and complete type checking algorithm for a small distributed class-based object-oriented language with structural subtyping. Static typing guarantees that both sequences of messages on channels, and sequences of method calls on objects, conform to type-theoretic specifications, thus ensuring type-safety. The language includes expected features of session types, such as delegation, and expected features of object-oriented programming, such as encapsulation of local state.
Interaction Graphs: Additives
Venue: arXiv cs.LO 2015
Year: 2015

Geometry of Interaction (GoI) is a kind of semantics of linear logic proofs that aims at accounting for the dynamical aspects of cut-elimination. We present here a parametrized construction of a Geometry of Interaction for Multiplicative Additive Linear Logic (MALL) in which proofs are represented by families of directed weighted graphs. Contrarily to former constructions dealing with additive connectives, we are able to solve the known issue of obtaining a denotational semantics for MALL by introducing a notion of observational equivalence. Moreover, our setting has the advantage of being the first construction dealing with additives where proofs of MALL are interpreted by finite objects. The fact that we obtain a denotational model of MALL relies on a single geometric property, which we call the trefoil property, from which we obtain, for each value of the parameter, adjunctions. We then proceed to show how this setting is related to Girard's various constructions: particular choices of the parameter respectively give a combinatorial version of his latest GoI, a refined version of older Geometries of Interaction based on nilpotency. This shows the importance of the trefoil property underlying our constructions since all known GoI construction to this day rely on particular cases of it.
Allocation of Divisible Goods under Lexicographic Preferences
Venue: arXiv cs.GT 2015
Year: 2015

We present a simple and natural non-pricing mechanism for allocating divisible goods among strategic agents having lexicographic preferences. Our mechanism has favorable properties of incentive compatibility (strategy-proofness), Pareto efficiency, envy-freeness, and time efficiency.
On the chromatic number of a random hypergraph
Venue: arXiv cs.DM 2015
Year: 2015

We consider the problem of $k$-colouring a random $r$-uniform hypergraph with $n$ vertices and $cn$ edges, where $k$, $r$, $c$ remain constant as $n$ tends to infinity. Achlioptas and Naor showed that the chromatic number of a random graph in this setting, the case $r=2$, must have one of two easily computable values as $n$ tends to infinity. We give a complete generalisation of this result to random uniform hypergraphs.
Network Routing Optimization Using Swarm Intelligence
Venue: arXiv cs.NE 2015
Year: 2015

The aim of this paper is to highlight and explore a traditional problem, which is the minimum spanning tree, and finding the shortest-path in network routing, by using Swarm Intelligence. This work to be considered as an investigation topic with combination between operations research, discrete mathematics, and evolutionary computing aiming to solve one of networking problems.
A Simple Proof for the Existence of "Good" Pairs of Nested Lattices
Venue: arXiv cs.IT 2015
Year: 2015

This paper provides a simplified proof for the existence of nested lattice codebooks allowing to achieve the capacity of the additive white Gaussian noise channel, as well as the optimal rate-distortion trade-off for a Gaussian source. The proof is self-contained and relies only on basic probabilistic and geometrical arguments. An ensemble of nested lattices that is different, and more elementary, than the one used in previous proofs is introduced. This ensemble is based on lifting different subcodes of a linear code to the Euclidean space using Construction A. In addition to being simpler, our analysis is less sensitive to the assumption that the additive noise is Gaussian. In particular, for additive ergodic noise channels it is shown that the achievable rates of the nested lattice coding scheme depend on the noise distribution only via its power. Similarly, the nested lattice source coding scheme attains the same rate-distortion trade-off for all ergodic sources with the same second moment.
Fast Rendezvous on a Cycle by Agents with Different Speeds
Venue: arXiv cs.DC 2015
Year: 2015

The difference between the speed of the actions of different processes is typically considered as an obstacle that makes the achievement of cooperative goals more difficult. In this work, we aim to highlight potential benefits of such asynchrony phenomena to tasks involving symmetry breaking. Specifically, in this paper, identical (except for their speeds) mobile agents are placed at arbitrary locations on a cycle of length $n$ and use their speed difference in order to rendezvous fast. We normalize the speed of the slower agent to be 1, and fix the speed of the faster agent to be some $c>1$. (An agent does not know whether it is the slower agent or the faster one.) The straightforward distributed-race DR algorithm is the one in which both agents simply start walking until rendezvous is achieved. It is easy to show that, in the worst case, the rendezvous time of DR is $n/(c-1)$. Note that in the interesting case, where $c$ is very close to 1 this bound becomes huge. Our first result is a lower bound showing that, up to a multiplicative factor of 2, this bound is unavoidable, even in a model that allows agents to leave arbitrary marks, even assuming sense of direction, and even assuming $n$ and $c$ are known to agents. That is, we show that under such assumptions, the rendezvous time of any algorithm is at least $\frac{n}{2(c-1)}$ if $c\leq 3$ and slightly larger if $c>3$. We then construct an algorithm that precisely matches the lower bound for the case $c\leq 2$, and almost matches it when $c>2$. Moreover, our algorithm performs under weaker assumptions than those stated above, as it does not assume sense of direction, and it allows agents to leave only a single mark (a pebble) and only at the place where they start the execution. Finally, we investigate the setting in which no marks can be used at all, and show tight bounds for $c\leq 2$, and almost tight bounds for $c>2$.
Certifying 3-Edge-Connectivity
Venue: arXiv cs.DS 2015
Year: 2015

We present a certifying algorithm that tests graphs for 3-edge-connectivity; the algorithm works in linear time. If the input graph is not 3-edge-connected, the algorithm returns a 2-edge-cut. If it is 3-edge-connected, it returns a construction sequence that constructs the input graph from the graph with two vertices and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity. Additionally, we show how compute and certify the 3-edge-connected components and a cactus representation of the 2-cuts in linear time. For 3-vertex-connectivity, we show how to compute the 3-vertex-connected components of a 2-connected graph.
Cost-Sensitive Support Vector Machines
Venue: arXiv cs.LG 2015
Year: 2015

A new procedure for learning cost-sensitive SVM(CS-SVM) classifiers is proposed. The SVM hinge loss is extended to the cost sensitive setting, and the CS-SVM is derived as the minimizer of the associated risk. The extension of the hinge loss draws on recent connections between risk minimization and probability elicitation. These connections are generalized to cost-sensitive classification, in a manner that guarantees consistency with the cost-sensitive Bayes risk, and associated Bayes decision rule. This ensures that optimal decision rules, under the new hinge loss, implement the Bayes-optimal cost-sensitive classification boundary. Minimization of the new hinge loss is shown to be a generalization of the classic SVM optimization problem, and can be solved by identical procedures. The dual problem of CS-SVM is carefully scrutinized by means of regularization theory and sensitivity analysis and the CS-SVM algorithm is substantiated. The proposed algorithm is also extended to cost-sensitive learning with example dependent costs. The minimum cost sensitive risk is proposed as the performance measure and is connected to ROC analysis through vector optimization. The resulting algorithm avoids the shortcomings of previous approaches to cost-sensitive SVM design, and is shown to have superior experimental performance on a large number of cost sensitive and imbalanced datasets.
Natural Proofs Versus Derandomization
Venue: arXiv cs.CC 2015
Year: 2015

We study connections between Natural Proofs, derandomization, and the problem of proving "weak" circuit lower bounds such as ${\sf NEXP} \not\subset {\sf TC^0}$. Natural Proofs have three properties: they are constructive (an efficient algorithm $A$ is embedded in them), have largeness ($A$ accepts a large fraction of strings), and are useful ($A$ rejects all strings which are truth tables of small circuits). Strong circuit lower bounds that are "naturalizing" would contradict present cryptographic understanding, yet the vast majority of known circuit lower bound proofs are naturalizing. So it is imperative to understand how to pursue un-Natural Proofs. Some heuristic arguments say constructivity should be circumventable: largeness is inherent in many proof techniques, and it is probably our presently weak techniques that yield constructivity. We prove: $\bullet$ Constructivity is unavoidable, even for $\sf NEXP$ lower bounds. Informally, we prove for all "typical" non-uniform circuit classes ${\cal C}$, ${\sf NEXP} \not\subset {\cal C}$ if and only if there is a polynomial-time algorithm distinguishing some function from all functions computable by ${\cal C}$-circuits. Hence ${\sf NEXP} \not\subset {\cal C}$ is equivalent to exhibiting a constructive property useful against ${\cal C}$. $\bullet$ There are no $\sf P$-natural properties useful against ${\cal C}$ if and only if randomized exponential time can be "derandomized" using truth tables of circuits from ${\cal C}$ as random seeds. Therefore the task of proving there are no $\sf P$-natural properties is inherently a derandomization problem, weaker than but implied by the existence of strong pseudorandom functions. These characterizations are applied to yield several new results, including improved ${\sf ACC}^0$ lower bounds and new unconditional derandomizations.