OpenRaiser/Intern-Atlas huggingface dataset:
A simple and optimal ancestry labeling scheme for trees
Venue: arXiv cs.DS 2015
Year: 2015

We present a $\lg n + 2 \lg \lg n+3$ ancestry labeling scheme for trees. The problem was first presented by Kannan et al. [STOC 88'] along with a simple $2 \lg n$ solution. Motivated by applications to XML files, the label size was improved incrementally over the course of more than 20 years by a series of papers. The last, due to Fraigniaud and Korman [STOC 10'], presented an asymptotically optimal $\lg n + 4 \lg \lg n+O(1)$ labeling scheme using non-trivial tree-decomposition techniques. By providing a framework generalizing interval based labeling schemes, we obtain a simple, yet asymptotically optimal solution to the problem. Furthermore, our labeling scheme is attained by a small modification of the original $2 \lg n$ solution.
Checking Whether an Automaton Is Monotonic Is NP-complete
Venue: arXiv cs.FL 2015
Year: 2015

An automaton is monotonic if its states can be arranged in a linear order that is preserved by the action of every letter. We prove that the problem of deciding whether a given automaton is monotonic is NP-complete. The same result is obtained for oriented automata, whose states can be arranged in a cyclic order. Moreover, both problems remain hard under the restriction to binary input alphabets.
How the Experts Algorithm Can Help Solve LPs Online
Venue: arXiv cs.DS 2015
Year: 2015

We consider the problem of solving packing/covering LPs online, when the columns of the constraint matrix are presented in random order. This problem has received much attention and the main focus is to figure out how large the right-hand sides of the LPs have to be (compared to the entries on the left-hand side of the constraints) to allow $(1+ε)$-approximations online. It is known that the right-hand sides have to be $Ω(ε^{-2} \log m)$ times the left-hand sides, where $m$ is the number of constraints. In this paper we give a primal-dual algorithm that achieve this bound for mixed packing/covering LPs. Our algorithms construct dual solutions using a regret-minimizing online learning algorithm in a black-box fashion, and use them to construct primal solutions. The adversarial guarantee that holds for the constructed duals helps us to take care of most of the correlations that arise in the algorithm; the remaining correlations are handled via martingale concentration and maximal inequalities. These ideas lead to conceptually simple and modular algorithms, which we hope will be useful in other contexts.
Complexity of Grundy coloring and its variants
Venue: arXiv cs.DS 2015
Year: 2015

The Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity of GRUNDY COLORING, the problem of determining whether a given graph has Grundy number at least $k$. We also study the variants WEAK GRUNDY COLORING (where the coloring is not necessarily proper) and CONNECTED GRUNDY COLORING (where at each step of the greedy coloring algorithm, the subgraph induced by the colored vertices must be connected). We show that GRUNDY COLORING can be solved in time $O^*(2.443^n)$ and WEAK GRUNDY COLORING in time $O^*(2.716^n)$ on graphs of order $n$. While GRUNDY COLORING and WEAK GRUNDY COLORING are known to be solvable in time $O^*(2^{O(wk)})$ for graphs of treewidth $w$ (where $k$ is the number of colors), we prove that under the Exponential Time Hypothesis (ETH), they cannot be solved in time $O^*(2^{o(w\log w)})$. We also describe an $O^*(2^{2^{O(k)}})$ algorithm for WEAK GRUNDY COLORING, which is therefore $\fpt$ for the parameter $k$. Moreover, under the ETH, we prove that such a running time is essentially optimal (this lower bound also holds for GRUNDY COLORING). Although we do not know whether GRUNDY COLORING is in $\fpt$, we show that this is the case for graphs belonging to a number of standard graph classes including chordal graphs, claw-free graphs, and graphs excluding a fixed minor. We also describe a quasi-polynomial time algorithm for GRUNDY COLORING and WEAK GRUNDY COLORING on apex-minor graphs. In stark contrast with the two other problems, we show that CONNECTED GRUNDY COLORING is $\np$-complete already for $k=7$ colors.
Secrecy Capacity Region of Some Classes of Wiretap Broadcast Channels
Venue: arXiv cs.IT 2015
Year: 2015

This work investigates the secrecy capacity of the Wiretap Broadcast Channel (WBC) with an external eavesdropper where a source wishes to communicate two private messages over a Broadcast Channel (BC) while keeping them secret from the eavesdropper. We derive a non-trivial outer bound on the secrecy capacity region of this channel which, in absence of security constraints, reduces to the best known outer bound to the capacity of the standard BC. An inner bound is also derived which follows the behavior of both the best known inner bound for the BC and the Wiretap Channel. These bounds are shown to be tight for the deterministic BC with a general eavesdropper, the semi-deterministic BC with a more-noisy eavesdropper and the Wiretap BC where users exhibit a less-noisiness order between them. Finally, by rewriting our outer bound to encompass the characteristics of parallel channels, we also derive the secrecy capacity region of the product of two inversely less-noisy BCs with a more-noisy eavesdropper. We illustrate our results by studying the impact of security constraints on the capacity of the WBC with binary erasure (BEC) and binary symmetric (BSC) components.
The recent Italian regulations about the open-access availability of publicly-funded research publications, and the documentation landscape in astrophysics
Venue: arXiv cs.DL 2015
Year: 2015

In October 2013 Italy enacted Law 112 2013, containing the first national regulations about the open access availability of publicly-funded research results (publications). The impact of these new regulations with the specific situation of that open access discipline which is astrophysics, has been considered. Under a strictly technical point of view, in the light of the new dispositions the open nature of a part of the astrophysical scholarly literature which has been made available online free to the reader during the last twenty years, might be questionable. Some possible ways to make astrophysicists' scholarly dissemination entirely compliant with law requirements are considered.
Dynamic Set Intersection
Venue: arXiv cs.DS 2015
Year: 2015

Consider the problem of maintaining a family $F$ of dynamic sets subject to insertions, deletions, and set-intersection reporting queries: given $S,S'\in F$, report every member of $S\cap S'$ in any order. We show that in the word RAM model, where $w$ is the word size, given a cap $d$ on the maximum size of any set, we can support set intersection queries in $O(\frac{d}{w/\log^2 w})$ expected time, and updates in $O(\log w)$ expected time. Using this algorithm we can list all $t$ triangles of a graph $G=(V,E)$ in $O(m+\frac{mα}{w/\log^2 w} +t)$ expected time, where $m=|E|$ and $α$ is the arboricity of $G$. This improves a 30-year old triangle enumeration algorithm of Chiba and Nishizeki running in $O(m α)$ time. We provide an incremental data structure on $F$ that supports intersection {\em witness} queries, where we only need to find {\em one} $e\in S\cap S'$. Both queries and insertions take $O\paren{\sqrt \frac{N}{w/\log^2 w}}$ expected time, where $N=\sum_{S\in F} |S|$. Finally, we provide time/space tradeoffs for the fully dynamic set intersection reporting problem. Using $M$ words of space, each update costs $O(\sqrt {M \log N})$ expected time, each reporting query costs $O(\frac{N\sqrt{\log N}}{\sqrt M}\sqrt{op+1})$ expected time where $op$ is the size of the output, and each witness query costs $O(\frac{N\sqrt{\log N}}{\sqrt M} + \log N)$ expected time.
The DUNE-ALUGrid Module
Venue: arXiv cs.MS 2015
Year: 2015

In this paper we present the new DUNE-ALUGrid module. This module contains a major overhaul of the sources from the ALUgrid library and the binding to the DUNE software framework. The main changes include user defined load balancing, parallel grid construction, and an redesign of the 2d grid which can now also be used for parallel computations. In addition many improvements have been introduced into the code to increase the parallel efficiency and to decrease the memory footprint. The original ALUGrid library is widely used within the DUNE community due to its good parallel performance for problems requiring local adaptivity and dynamic load balancing. Therefore, this new model will benefit a number of DUNE users. In addition we have added features to increase the range of problems for which the grid manager can be used, for example, introducing a 3d tetrahedral grid using a parallel newest vertex bisection algorithm for conforming grid refinement. In this paper we will discuss the new features, extensions to the DUNE interface, and explain for various examples how the code is used in parallel environments.
Real-Time Bidding Benchmarking with iPinYou Dataset
Venue: arXiv cs.GT 2015
Year: 2015

Being an emerging paradigm for display advertising, Real-Time Bidding (RTB) drives the focus of the bidding strategy from context to users' interest by computing a bid for each impression in real time. The data mining work and particularly the bidding strategy development becomes crucial in this performance-driven business. However, researchers in computational advertising area have been suffering from lack of publicly available benchmark datasets, which are essential to compare different algorithms and systems. Fortunately, a leading Chinese advertising technology company iPinYou decided to release the dataset used in its global RTB algorithm competition in 2013. The dataset includes logs of ad auctions, bids, impressions, clicks, and final conversions. These logs reflect the market environment as well as form a complete path of users' responses from advertisers' perspective. This dataset directly supports the experiments of some important research problems such as bid optimisation and CTR estimation. To the best of our knowledge, this is the first publicly available dataset on RTB display advertising. Thus, they are valuable for reproducible research and understanding the whole RTB ecosystem. In this paper, we first provide the detailed statistical analysis of this dataset. Then we introduce the research problem of bid optimisation in RTB and the simple yet comprehensive evaluation protocol. Besides, a series of benchmark experiments are also conducted, including both click-through rate (CTR) estimation and bid optimisation.
Toward a multilevel representation of protein molecules: comparative approaches to the aggregation/folding propensity problem
Venue: arXiv cs.CE 2015
Year: 2015

This paper builds upon the fundamental work of Niwa et al. [34], which provides the unique possibility to analyze the relative aggregation/folding propensity of the elements of the entire Escherichia coli (E. coli) proteome in a cell-free standardized microenvironment. The hardness of the problem comes from the superposition between the driving forces of intra- and inter-molecule interactions and it is mirrored by the evidences of shift from folding to aggregation phenotypes by single-point mutations [10]. Here we apply several state-of-the-art classification methods coming from the field of structural pattern recognition, with the aim to compare different representations of the same proteins gathered from the Niwa et al. data base; such representations include sequences and labeled (contact) graphs enriched with chemico-physical attributes. By this comparison, we are able to identify also some interesting general properties of proteins. Notably, (i) we suggest a threshold around 250 residues discriminating "easily foldable" from "hardly foldable" molecules consistent with other independent experiments, and (ii) we highlight the relevance of contact graph spectra for folding behavior discrimination and characterization of the E. coli solubility data. The soundness of the experimental results presented in this paper is proved by the statistically relevant relationships discovered among the chemico-physical description of proteins and the developed cost matrix of substitution used in the various discrimination systems.
On the necessity of looped-functionals arising in the analysis of pseudo-periodic, sampled-data and hybrid systems
Venue: arXiv cs.SY 2015
Year: 2015

Looped-functionals have been shown to be relevant for the analysis of a wide variety of systems. However, the conditions obtained in previous works on the analysis of sampled-data, impulsive and switched systems have only been shown to be sufficient for the characterization of their associated discrete-time stability conditions. We prove here that these conditions are also \necessary. This result is derived for a wider class of linear systems, referred to as impulsive pseudo-periodic systems, that encompass periodic, impulsive, sampled-data and switched systems as special cases.
On the Equivalence between Interference and Eavesdropping in Wireless Communications
Venue: arXiv cs.IT 2015
Year: 2015

We show that the problem of analyzing the outage probability in cellular systems affected by co-channel interference and background noise is mathematically equivalent to the problem of analyzing the wireless information-theoretic security in terms of the maximum secrecy rate in fading channels. Hence, these both apparently unrelated problems can be addressed by using a common approach. We illustrate the applicability of the connection unveiled herein to provide new results for the secrecy outage probability in different scenarios.
FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs
Venue: arXiv cs.DC 2015
Year: 2015

Graph analysis performs many random reads and writes, thus, these workloads are typically performed in memory. Traditionally, analyzing large graphs requires a cluster of machines so the aggregate memory exceeds the graph size. We demonstrate that a multicore server can process graphs with billions of vertices and hundreds of billions of edges, utilizing commodity SSDs with minimal performance loss. We do so by implementing a graph-processing engine on top of a user-space SSD file system designed for high IOPS and extreme parallelism. Our semi-external memory graph engine called FlashGraph stores vertex state in memory and edge lists on SSDs. It hides latency by overlapping computation with I/O. To save I/O bandwidth, FlashGraph only accesses edge lists requested by applications from SSDs; to increase I/O throughput and reduce CPU overhead for I/O, it conservatively merges I/O requests. These designs maximize performance for applications with different I/O characteristics. FlashGraph exposes a general and flexible vertex-centric programming interface that can express a wide variety of graph algorithms and their optimizations. We demonstrate that FlashGraph in semi-external memory performs many algorithms with performance up to 80% of its in-memory implementation and significantly outperforms PowerGraph, a popular distributed in-memory graph engine.
Approximation Bounds For Minimum Degree Matching
Venue: arXiv cs.DS 2015
Year: 2015

We consider the MINGREEDY strategy for Maximum Cardinality Matching. MINGREEDY repeatedly selects an edge incident with a node of minimum degree. For graphs of degree at most $Δ$ we show that MINGREEDY achieves approximation ratio at least $ \frac{Δ-1}{2Δ-3} $ in the worst case and that this performance is optimal among adaptive priority algorithms in the vertex model, which include many prominent greedy matching heuristics. Even when considering expected approximation ratios of randomized greedy strategies, no better worst case bounds are known for graphs of small degrees.
Second-Order Asymptotics for the Discrete Memoryless MAC with Degraded Message Sets
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies the second-order asymptotics of the discrete memoryless multiple-access channel with degraded message sets. For a fixed average error probability $ε\in(0,1)$ and an arbitrary point on the boundary of the capacity region, we characterize the speed of convergence of rate pairs that converge to that point for codes that have asymptotic error probability no larger than $ε$, thus complementing an analogous result given previously for the Gaussian setting.
Adaptive Millimeter Wave Beam Alignment for Dual-Polarized MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

Fifth generation wireless systems are expected to employ multiple antenna communication at millimeter wave (mmWave) frequencies using small cells within heterogeneous cellular networks. The high path loss of mmWave as well as physical obstructions make communication challenging. To compensate for the severe path loss, mmWave systems may employ a beam alignment algorithm that facilitates highly directional transmission by aligning the beam direction of multiple antenna arrays. This paper discusses a mmWave system employing dual-polarized antennas. First, we propose a practical soft-decision beam alignment (soft-alignment) algorithm that exploits orthogonal polarizations. By sounding the orthogonal polarizations in parallel, the equality criterion of the Welch bound for training sequences is relaxed. Second, the analog beamforming system is adapted to the directional characteristics of the mmWave link assuming a high Ricean K-factor and poor scattering environment. The soft-algorithm enables the mmWave system to align innumerable narrow beams to channel subspace in an attempt to effectively scan the mmWave channel. Thirds, we propose a method to efficiently adapt the number of channel sounding observations to the specific channel environment based on an approximate probability of beam misalignment. Simulation results show the proposed soft-alignment algorithm with adaptive sounding time effectively scans the channel subspace of a mobile user by exploiting polarization diversity.
Fast distributed almost stable marriages
Venue: arXiv cs.GT 2015
Year: 2015

In their seminal work on the Stable Marriage Problem, Gale and Shapley describe an algorithm which finds a stable matching in $O(n^2)$ communication rounds. Their algorithm has a natural interpretation as a distributed algorithm where each player is represented by a single processor. In this distributed model, Floreen, Kaski, Polishchuk, and Suomela recently showed that for bounded preference lists, terminating the Gale-Shapley algorithm after a constant number of rounds results in an almost stable matching. In this paper, we describe a new deterministic distributed algorithm which finds an almost stable matching in $O(\log^5 n)$ communication rounds for arbitrary preferences. We also present a faster randomized variant which requires $O(\log^2 n)$ rounds. This run-time can be improved to $O(1)$ rounds for "almost regular" (and in particular complete) preferences. To our knowledge, these are the first sub-polynomial round distributed algorithms for any variant of the stable marriage problem with unbounded preferences.
Urban DNA for cities evolutions. Cities as physical expression of dynamic equilibriums between competitive and cooperative forces
Venue: arXiv cs.CY 2015
Year: 2015

Cities are physical manifestations of our competitive and cooperative behaviours. The tension between these two forces generates dynamic equilibriums whose material expressions are cities and their evolutions. In a Darwinian cooperative view, as Darwinism does not involve only competition, the public benefit obtained by cooperation, return in terms of private benefit too. An urban genetic code is proposed, according to which cities emerge connecting nature and urbanity, and as sum of multiuse, independent micro-areas, each one with its centrality, job locations, parks and daily shops-services and amenities. This mechanism, called Isobenefit Urbanism, is not static and pre-designed, but allows infinitely dynamic changes and expansions. Rather than describing The ideal city, which doesn't exist outside our own minds, Isobenefit Urbanism describes what a city should avoid to be in order to not become an unideal city. Its six principles are the urban DNA which does not give predetermined forms but indications to follow according to contexts and times. From an environmental angle, Isobenefit cities are resilient, low carbon, adaptive.
Highly Accurate Multispectral Palmprint Recognition Using Statistical and Wavelet Features
Venue: arXiv cs.CV 2015
Year: 2015

Palmprint is one of the most useful physiological biometrics that can be used as a powerful means in personal recognition systems. The major features of the palmprints are palm lines, wrinkles and ridges, and many approaches use them in different ways towards solving the palmprint recognition problem. Here we have proposed to use a set of statistical and wavelet-based features; statistical to capture the general characteristics of palmprints; and wavelet-based to find those information not evident in the spatial domain. Also we use two different classification approaches, minimum distance classifier scheme and weighted majority voting algorithm, to perform palmprint matching. The proposed method is tested on a well-known palmprint dataset of 6000 samples and has shown an impressive accuracy rate of 99.65\%-100\% for most scenarios.
Joint Resource Optimization for Multicell Networks with Wireless Energy Harvesting Relays
Venue: arXiv cs.IT 2015
Year: 2015

This paper first considers a multicell network deployment where the base station (BS) of each cell communicates with its cell-edge user with the assistance of an amplify-and-forward (AF) relay node. Equipped with a power splitter and a wireless energy harvester, the self-sustaining relay scavenges radio frequency (RF) energy from the received signals to process and forward the information. Our aim is to develop a resource allocation scheme that jointly optimizes (i) BS transmit powers, (ii) received power splitting factors for energy harvesting and information processing at the relays, and (iii) relay transmit powers. In the face of strong intercell interference and limited radio resources, we formulate three highly-nonconvex problems with the objectives of sum-rate maximization, max-min throughput fairness and sum-power minimization. To solve such challenging problems, we propose to apply the successive convex approximation (SCA) approach and devise iterative algorithms based on geometric programming and difference-of-convex-functions programming. The proposed algorithms transform the nonconvex problems into a sequence of convex problems, each of which is solved very efficiently by the interior-point method. We prove that our algorithms converge to the locally optimal solutions that satisfy the Karush-Kuhn-Tucker conditions of the original nonconvex problems. We then extend our results to the case of decode-and-forward (DF) relaying with variable timeslot durations. We show that our resource allocation solutions in this case offer better throughput than that of the AF counterpart with equal timeslot durations, albeit at a higher computational complexity. Numerical results confirm that the proposed joint optimization solutions substantially improve the network performance, compared with cases where the radio resource parameters are individually optimized.