OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm
Venue: arXiv cs.DS 2015
Year: 2015

Motivated by the observation that FIFO-based push-relabel algorithms are able to outperform highest label-based variants on modern, large maximum flow problem instances, we introduce an efficient implementation of the algorithm that uses coarse-grained parallelism to avoid the problems of existing parallel approaches. We demonstrate good relative and absolute speedups of our algorithm on a set of large graph instances taken from real-world applications. On a modern 40-core machine, our parallel implementation outperforms existing sequential implementations by up to a factor of 12 and other parallel implementations by factors of up to 3.
Adapting sentiment analysis for tweets linking to scientific papers
Venue: arXiv cs.DL 2015
Year: 2015

In the context of altmetrics, tweets have been discussed as potential indicators of immediate and broader societal impact of scientific documents. However, it is not yet clear to what extent Twitter captures actual research impact. A small case study (Thelwall et al., 2013b) suggests that tweets to journal articles neither comment on nor express any sentiments towards the publication, which suggests that tweets merely disseminate bibliographic information, often even automatically. This study analyses the sentiments of tweets for a large representative set of scientific papers by specifically adapting different methods to academic articles distributed on Twitter. Results will help to improve the understanding of Twitter's role in scholarly communication and the meaning of tweets as impact metrics.
Triggering Wave-Like Convergence of Tail-biting Spatially Coupled LDPC Codes
Venue: arXiv cs.IT 2015
Year: 2015

Spatially coupled low-density parity-check (SC-LDPC) codes can achieve the channel capacity under low-complexity belief propagation (BP) decoding, however, there is a non-negligible rate-loss because of termination effects for practical finite coupling lengths. In this paper, we study how we can approach the performance of terminated SC-LDPC codes by random shortening of tail-biting SC-LDPC codes. We find the minimum required rate-loss in order to achieve the same performance than terminated codes. We additionally study the use of tail-biting SC-LDPC codes for transmission over parallel channels (e.g., bit-interleaved-coded-modulation (BICM)) and investigate how the distribution of the coded bits between two parallel channels can change the performance of the code. We show that a tail-biting SC-LDPC code can be used with BP decoding almost anywhere within the achievable region of MAP decoding. The optimization comes with a mandatory buffer at the encoder side. We evaluate different distributions of coded bits in order to reduce this buffer length.
Computationally Aware Sum-Rate Optimal Scheduling for Centralized Radio Access Networks
Venue: arXiv cs.NI 2015
Year: 2015

In a centralized or cloud radio access network, certain portions of the digital baseband processing of a group of several radio access points are executed at a central data center. Centralizing the processing improves the flexibility, scalability, and utilization of computational assets. However, the performance depends critically on how the limited data processing resources are allocated to serve the needs of the different wireless devices. As the processing load imposed by each device depends on its allocated transmission rate and channel quality, the rate-allocation aspect of the scheduling should take into account the available computing. In this paper, two computationally aware schedulers are proposed that have the objective of maximizing the sum-rate of the system while satisfying a constraint on the offered computational load. The first scheduler optimally allocates resources and is implemented according to a water-filling algorithm. The second scheduler is suboptimal, but uses a simpler and intuitive complexity-cut-off approach. The performance of both schedulers is evaluated using an LTE-compliant system level simulator. It is found that both schedulers avoid outages that are caused by an overflow of computational load (i.e., computational outages) at the cost of a slight loss of sum-rate.
Topical Discovery of Web Content
Venue: arXiv cs.IR 2015
Year: 2015

This work describes the theory and the implementation of a new software tool, the "Web Topical Discovery System" (WTDS), which provides an approach to the automatic discovery and selection of new web pages relevant to specific analytical needs. We will see how it is possible to specify the research context with search keywords related to the area of interest and consider the important problem of removing extraneous data from a web page containing an article in order to reduce, to a minimum, false positives represented by a match on a keyword that is showing up on the latest news box of the same page. The removal of duplicates, the analysis of richness of information contained in the article and lexical diversity are all taken into consideration in order to provide the optimum set of recommendations to the end user or system.
A Bayesian Approach for Online Classifier Ensemble
Venue: arXiv cs.LG 2015
Year: 2015

We propose a Bayesian approach for recursively estimating the classifier weights in online learning of a classifier ensemble. In contrast with past methods, such as stochastic gradient descent or online boosting, our approach estimates the weights by recursively updating its posterior distribution. For a specified class of loss functions, we show that it is possible to formulate a suitably defined likelihood function and hence use the posterior distribution as an approximation to the global empirical loss minimizer. If the stream of training data is sampled from a stationary process, we can also show that our approach admits a superior rate of convergence to the expected loss minimizer than is possible with standard stochastic gradient descent. In experiments with real-world datasets, our formulation often performs better than state-of-the-art stochastic gradient descent and online boosting algorithms.
Random Walks and Evolving Sets: Faster Convergences and Limitations
Venue: arXiv cs.DS 2015
Year: 2015

Analyzing the mixing time of random walks is a well-studied problem with applications in random sampling and more recently in graph partitioning. In this work, we present new analysis of random walks and evolving sets using more combinatorial graph structures, and show some implications in approximating small-set expansion. On the other hand, we provide examples showing the limitations of using random walks and evolving sets in disproving the small-set expansion hypothesis. - We define a combinatorial analog of the spectral gap, and use it to prove the convergence of non-lazy random walks. A corollary is a tight lower bound on the small-set expansion of graph powers for any graph. - We prove that random walks converge faster when the robust vertex expansion of the graph is larger. This provides an improved analysis of the local graph partitioning algorithm using the evolving set process. - We give an example showing that the evolving set process fails to disprove the small-set expansion hypothesis. This refutes a conjecture of Oveis Gharan and shows the limitations of local graph partitioning algorithms in approximating small-set expansion.
Economic Viability of Paris Metro Pricing for Digital Services
Venue: arXiv cs.GT 2015
Year: 2015

Nowadays digital services, such as cloud computing and network access services, allow dynamic resource allocation and virtual resource isolation. This trend can create a new paradigm of flexible pricing schemes. A simple pricing scheme is to allocate multiple isolated service classes with differentiated prices, namely Paris Metro Pricing (PMP). The benefits of PMP are its simplicity and applicability to a wide variety of general digital services, without considering specific performance guarantees for different service classes. The central issue of our study is whether PMP is economically viable, namely whether it will produce more profit for the service provider and whether it will achieve more social welfare. Prior studies had only considered specific models and arrived at conflicting conclusions. In this article, we identify unifying principles in a general setting and derive general sufficient conditions that can guarantee the viability of PMP. We further apply the results to analyze various examples of digital services.
Mining and Analyzing the Future Works in Scientific Articles
Venue: arXiv cs.DL 2015
Year: 2015

Future works in scientific articles are valuable for researchers and they can guide researchers to new research directions or ideas. In this paper, we mine the future works in scientific articles in order to 1) provide an insight for future work analysis and 2) facilitate researchers to search and browse future works in a research area. First, we study the problem of future work extraction and propose a regular expression based method to address the problem. Second, we define four different categories for the future works by observing the data and investigate the multi-class future work classification problem. Third, we apply the extraction method and the classification model to a paper dataset in the computer science field and conduct a further analysis of the future works. Finally, we design a prototype system to search and demonstrate the future works mined from the scientific papers. Our evaluation results show that our extraction method can get high precision and recall values and our classification model can also get good results and it outperforms several baseline models. Further analysis of the future work sentences also indicates interesting results.
Spotlight the Negatives: A Generalized Discriminative Latent Model
Venue: arXiv cs.CV 2015
Year: 2015

Discriminative latent variable models (LVM) are frequently applied to various visual recognition tasks. In these systems the latent (hidden) variables provide a formalism for modeling structured variation of visual features. Conventionally, latent variables are de- fined on the variation of the foreground (positive) class. In this work we augment LVMs to include negative latent variables corresponding to the background class. We formalize the scoring function of such a generalized LVM (GLVM). Then we discuss a framework for learning a model based on the GLVM scoring function. We theoretically showcase how some of the current visual recognition methods can benefit from this generalization. Finally, we experiment on a generalized form of Deformable Part Models with negative latent variables and show significant improvements on two different detection tasks.
Iris Recognition Using Scattering Transform and Textural Features
Venue: arXiv cs.CV 2015
Year: 2015

Iris recognition has drawn a lot of attention since the mid-twentieth century. Among all biometric features, iris is known to possess a rich set of features. Different features have been used to perform iris recognition in the past. In this paper, two powerful sets of features are introduced to be used for iris recognition: scattering transform-based features and textural features. PCA is also applied on the extracted features to reduce the dimensionality of the feature vector while preserving most of the information of its initial value. Minimum distance classifier is used to perform template matching for each new test sample. The proposed scheme is tested on a well-known iris database, and showed promising results with the best accuracy rate of 99.2%.
Extending local features with contextual information in graph kernels
Venue: arXiv cs.LG 2015
Year: 2015

Graph kernels are usually defined in terms of simpler kernels over local substructures of the original graphs. Different kernels consider different types of substructures. However, in some cases they have similar predictive performances, probably because the substructures can be interpreted as approximations of the subgraphs they induce. In this paper, we propose to associate to each feature a piece of information about the context in which the feature appears in the graph. A substructure appearing in two different graphs will match only if it appears with the same context in both graphs. We propose a kernel based on this idea that considers trees as substructures, and where the contexts are features too. The kernel is inspired from the framework in [6], even if it is not part of it. We give an efficient algorithm for computing the kernel and show promising results on real-world graph classification datasets.
Reverse Engineering of RFID devices
Venue: arXiv cs.CR 2015
Year: 2015

This paper discusses the relevance and potential impact of both RFID and reverse engineering of RFID technology, followed by a discussion of common protocols and internals of RFID technology. The focus of the paper is on providing an overview of the different approaches to reverse engineering RFID technology and possible countermeasures that could limit the potential of such reverse engineering attempts.
Secure Degrees of Freedom of Multi-user Networks: One-Time-Pads in the Air via Alignment
Venue: arXiv cs.IT 2015
Year: 2015

We revisit the recent secure degrees of freedom (s.d.o.f.) results for one-hop multi-user wireless networks by considering three fundamental wireless network structures: Gaussian wiretap channel with helpers, Gaussian multiple access wiretap channel, and Gaussian interference channel with secrecy constraints. We present main enabling tools and resulting communication schemes in an expository manner, along with key insights and design principles emerging from them. The main achievable schemes are based on real interference alignment, channel prefixing via cooperative jamming, and structured signalling. Real interference alignment enables aligning the cooperative jamming signals together with the message carrying signals at the eavesdroppers to protect them akin to one-time-pad protecting messages in wired systems. Real interference alignment also enables decodability at the legitimate receivers by rendering message carrying and cooperative jamming signals separable, and simultaneously aligning the cooperative jamming signals in the smallest possible sub-space. The main converse techniques are based on two key lemmas which quantify the secrecy penalty by showing that the net effect of an eavesdropper on the system is that it eliminates one of the independent channel inputs; and the role of a helper by developing a direct relationship between the cooperative jamming signal of a helper and the message rate. These two lemmas when applied according to the unique structure of individual networks provide tight converses. Finally, we present a blind cooperative jamming scheme for the helper network with no eavesdropper channel state information at the transmitters that achieves the same optimal s.d.o.f. as in the case of full eavesdropper channel state information.
Feature Representation in Convolutional Neural Networks
Venue: arXiv cs.CV 2015
Year: 2015

Convolutional Neural Networks (CNNs) are powerful models that achieve impressive results for image classification. In addition, pre-trained CNNs are also useful for other computer vision tasks as generic feature extractors. This paper aims to gain insight into the feature aspect of CNN and demonstrate other uses of CNN features. Our results show that CNN feature maps can be used with Random Forests and SVM to yield classification results that outperforms the original CNN. A CNN that is less than optimal (e.g. not fully trained or overfitting) can also extract features for Random Forest/SVM that yield competitive classification accuracy. In contrast to the literature which uses the top-layer activations as feature representation of images for other tasks, using lower-layer features can yield better results for classification.
Algorithmic Complexity of Power Law Networks
Venue: arXiv cs.DS 2015
Year: 2015

It was experimentally observed that the majority of real-world networks follow power law degree distribution. The aim of this paper is to study the algorithmic complexity of such "typical" networks. The contribution of this work is twofold. First, we define a deterministic condition for checking whether a graph has a power law degree distribution and experimentally validate it on real-world networks. This definition allows us to derive interesting properties of power law networks. We observe that for exponents of the degree distribution in the range $[1,2]$ such networks exhibit double power law phenomenon that was observed for several real-world networks. Our observation indicates that this phenomenon could be explained by just pure graph theoretical properties. The second aim of our work is to give a novel theoretical explanation why many algorithms run faster on real-world data than what is predicted by algorithmic worst-case analysis. We show how to exploit the power law degree distribution to design faster algorithms for a number of classical P-time problems including transitive closure, maximum matching, determinant, PageRank and matrix inverse. Moreover, we deal with the problems of counting triangles and finding maximum clique. Previously, it has been only shown that these problems can be solved very efficiently on power law graphs when these graphs are random, e.g., drawn at random from some distribution. However, it is unclear how to relate such a theoretical analysis to real-world graphs, which are fixed. Instead of that, we show that the randomness assumption can be replaced with a simple condition on the degrees of adjacent vertices, which can be used to obtain similar results. As a result, in some range of power law exponents, we are able to solve the maximum clique problem in polynomial time, although in general power law networks the problem is NP-complete.
Towards Log-Linear Logics with Concrete Domains
Venue: arXiv cs.AI 2015
Year: 2015

We present $\mathcal{MEL}^{++}$ (M denotes Markov logic networks) an extension of the log-linear description logics $\mathcal{EL}^{++}$-LL with concrete domains, nominals, and instances. We use Markov logic networks (MLNs) in order to find the most probable, classified and coherent $\mathcal{EL}^{++}$ ontology from an $\mathcal{MEL}^{++}$ knowledge base. In particular, we develop a novel way to deal with concrete domains (also known as datatypes) by extending MLN's cutting plane inference (CPI) algorithm.
Avoidability of long $k$-abelian repetitions
Venue: arXiv cs.DM 2015
Year: 2015

We study the avoidability of long $k$-abelian-squares and $k$-abelian-cubes on binary and ternary alphabets. For $k=1$, these are Mäkelä's questions. We show that one cannot avoid abelian-cubes of abelian period at least $2$ in infinite binary words, and therefore answering negatively one question from Mäkelä. Then we show that one can avoid $3$-abelian-squares of period at least $3$ in infinite binary words and $2$-abelian-squares of period at least 2 in infinite ternary words. Finally we study the minimum number of distinct $k$-abelian-squares that must appear in an infinite binary word.
Power Talk in DC Micro Grids: Constellation Design and Error Probability Performance
Venue: arXiv cs.IT 2015
Year: 2015

Power talk is a novel concept for communication among units in a Micro Grid (MG), where information is sent by using power electronics as modems and the common bus of the MG as a communication medium. The technique is implemented by modifying the droop control parameters from the primary control level. In this paper, we consider power talk in a DC MG and introduce a channel model based on Thevenin equivalent. The result is a channel whose state that can be estimated by both the transmitter and the receiver. Using this model, we present design of symbol constellations of arbitrary order and analyze the error probability performance. Finally, we also show how to design adaptive modulation in the proposed communication framework, which leads to significant performance benefits.
On Distributed Computing with Beeps
Venue: arXiv cs.DC 2015
Year: 2015

We consider networks of processes which interact with beeps. Various beeping models are used. The basic one, defined by Cornejo and Kuhn [CK10], assumes that a process can choose either to beep or to listen; if it listens it can distinguish between silence or the presence of at least one beep. The aim of this paper is the study of the resolution of paradigms such as collision detection, computation of the degree of a vertex, colouring, or 2-hop-colouring in the framework of beeping models. For each of these problems we present Las Vegas or Monte Carlo algorithms and we analyse their complexities expressed in terms of the number of slots. We present also efficient randomised emulations of more powerful beeping models on the basic one. We illustrate emulation procedures with an efficient degree computation algorithm in the basic beeping model; this algorithm was given initially in a more powerful model.
An NL-Complete Puzzle
Venue: arXiv cs.CC 2015
Year: 2015

We investigate the complexity of a puzzle that turns out to be NL-complete.
Probabilistic Rateless Multiple Access for Machine-to-Machine Communication
Venue: arXiv cs.IT 2015
Year: 2015

Future machine to machine (M2M) communications need to support a massive number of devices communicating with each other with little or no human intervention. Random access techniques were originally proposed to enable M2M multiple access, but suffer from severe congestion and access delay in an M2M system with a large number of devices. In this paper, we propose a novel multiple access scheme for M2M communications based on the capacity-approaching analog fountain code to efficiently minimize the access delay and satisfy the delay requirement for each device. This is achieved by allowing M2M devices to transmit at the same time on the same channel in an optimal probabilistic manner based on their individual delay requirements. Simulation results show that the proposed scheme achieves a near optimal rate performance and at the same time guarantees the delay requirements of the devices. We further propose a simple random access strategy and characterized the required overhead. Simulation results show the proposed approach significantly outperforms the existing random access schemes currently used in long term evolution advanced (LTE-A) standard in terms of the access delay.
A Hybrid Graph-drawing Algorithm for Large, Naturally-clustered, Disconnected Graphs
Venue: arXiv cs.GR 2015
Year: 2015

In this paper, we present a hybrid graph-drawing algorithm (GDA) for layouting large, naturally-clustered, disconnected graphs. We called it a hybrid algorithm because it is an implementation of a series of already known graph-drawing and graph-theoretic procedures. We remedy in this hybrid the problematic nature of the current force-based GDA which has the inability to scale to large, naturally-clustered, and disconnected graphs. These kinds of graph usually model the complex inter-relationships among entities in social, biological, natural, and artificial networks. Obviously, the hybrid runs longer than the current GDAs. By using two extreme cases of graphs as inputs, we present in this paper the derivation of the time complexity of the hybrid which we found to be $O(|\V|^3)$.