OpenRaiser/Intern-Atlas huggingface dataset:
Balls and Funnels: Energy Efficient Group-to-Group Anycasts
Venue: arXiv cs.NI 2016
Year: 2016

We introduce group-to-group anycast (g2g-anycast), a network design problem of substantial practical importance and considerable generality. Given a collection of groups and requirements for directed connectivity from source groups to destination groups, the solution network must contain, for each requirement, an omni-directional down-link broadcast, centered at any node of the source group, called the ball; the ball must contain some node from the destination group in the requirement and all such destination nodes in the ball must aggregate into a tree directed towards the source, called the funnel-tree. The solution network is a collection of balls along with the funnel-trees they contain. g2g-anycast models DBS (Digital Broadcast Satellite), Cable TV systems and drone swarms. It generalizes several well known network design problems including minimum energy unicast, multicast, broadcast, Steiner-tree, Steiner-forest and Group-Steiner tree. Our main achievement is an $O(\log^4 n)$ approximation, counterbalanced by an $\log^{(2-ε)}n$ hardness of approximation, for general weights. Given the applicability to wireless communication, we present a scalable and easily implemented $O(\log n)$ approximation algorithm, Cover-and-Grow for fixed-dimensional Euclidean space with path-loss exponent at least 2.
Diagnosing editorial strategies of Chilean media on Twitter using an automatic news classifier
Venue: arXiv cs.AI 2016
Year: 2016

In Chile, does not exist an independent entity that publishes quantitative or qualitative surveys to understand the traditional media environment and its adaptation on the Social Web. Nowadays, Chilean newsreaders are increasingly using social web platforms as their primary source of information, among which Twitter plays a central role. Historical media and pure players are developing different strategies to increase their audience and influence on this platform. In this article, we propose a methodology based on data mining techniques to provide a first level of analysis of the new Chilean media environment. We use a crawling technique to mine news streams of 37 different Chilean media actively presents on Twitter and propose several indicators to compare them. We analyze their volumes of production, their potential audience, and using NLP techniques, we explore the content of their production: their editorial line and their geographic coverage.
DeepText: A Unified Framework for Text Proposal Generation and Text Detection in Natural Images
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we develop a novel unified framework called DeepText for text region proposal generation and text detection in natural images via a fully convolutional neural network (CNN). First, we propose the inception region proposal network (Inception-RPN) and design a set of text characteristic prior bounding boxes to achieve high word recall with only hundred level candidate proposals. Next, we present a powerful textdetection network that embeds ambiguous text category (ATC) information and multilevel region-of-interest pooling (MLRP) for text and non-text classification and accurate localization. Finally, we apply an iterative bounding box voting scheme to pursue high recall in a complementary manner and introduce a filtering algorithm to retain the most suitable bounding box, while removing redundant inner and outer boxes for each text instance. Our approach achieves an F-measure of 0.83 and 0.85 on the ICDAR 2011 and 2013 robust text detection benchmarks, outperforming previous state-of-the-art results.
On model of information system for management of information flows
Venue: arXiv cs.SE 2016
Year: 2016

In this article are discussed some problems in developing software related to the management of information flows. We presented the basic stages in their development. We bold a methodology for conceptual modeling and design of information systems of this type. In order to demonstrate the effectiveness of the proposed model is an information system for administrative services of graduate students in the university.
Spatio-Temporal Image Boundary Extrapolation
Venue: arXiv cs.CV 2016
Year: 2016

Boundary prediction in images as well as video has been a very active topic of research and organizing visual information into boundaries and segments is believed to be a corner stone of visual perception. While prior work has focused on predicting boundaries for observed frames, our work aims at predicting boundaries of future unobserved frames. This requires our model to learn about the fate of boundaries and extrapolate motion patterns. We experiment on established real-world video segmentation dataset, which provides a testbed for this new task. We show for the first time spatio-temporal boundary extrapolation in this challenging scenario. Furthermore, we show long-term prediction of boundaries in situations where the motion is governed by the laws of physics. We successfully predict boundaries in a billiard scenario without any assumptions of a strong parametric model or any object notion. We argue that our model has with minimalistic model assumptions derived a notion of 'intuitive physics' that can be applied to novel scenes.
Towards Bin Packing (preliminary problem survey, models with multiset estimates)
Venue: arXiv cs.AI 2016
Year: 2016

The paper described a generalized integrated glance to bin packing problems including a brief literature survey and some new problem formulations for the cases of multiset estimates of items. A new systemic viewpoint to bin packing problems is suggested: (a) basic element sets (item set, bin set, item subset assigned to bin), (b) binary relation over the sets: relation over item set as compatibility, precedence, dominance; relation over items and bins (i.e., correspondence of items to bins). A special attention is targeted to the following versions of bin packing problems: (a) problem with multiset estimates of items, (b) problem with colored items (and some close problems). Applied examples of bin packing problems are considered: (i) planning in paper industry (framework of combinatorial problems), (ii) selection of information messages, (iii) packing of messages/information packages in WiMAX communication system (brief description).
Characterizing and Avoiding Routing Detours Through Surveillance States
Venue: arXiv cs.NI 2016
Year: 2016

An increasing number of countries are passing laws that facilitate the mass surveillance of Internet traffic. In response, governments and citizens are increasingly paying attention to the countries that their Internet traffic traverses. In some cases, countries are taking extreme steps, such as building new Internet Exchange Points (IXPs), which allow networks to interconnect directly, and encouraging local interconnection to keep local traffic local. We find that although many of these efforts are extensive, they are often futile, due to the inherent lack of hosting and route diversity for many popular sites. By measuring the country-level paths to popular domains, we characterize transnational routing detours. We find that traffic is traversing known surveillance states, even when the traffic originates and ends in a country that does not conduct mass surveillance. Then, we investigate how clients can use overlay network relays and the open DNS resolver infrastructure to prevent their traffic from traversing certain jurisdictions. We find that 84\% of paths originating in Brazil traverse the United States, but when relays are used for country avoidance, only 37\% of Brazilian paths traverse the United States. Using the open DNS resolver infrastructure allows Kenyan clients to avoid the United States on 17\% more paths. Unfortunately, we find that some of the more prominent surveillance states (e.g., the U.S.) are also some of the least avoidable countries.
Small Representations of Big Kidney Exchange Graphs
Venue: arXiv cs.AI 2016
Year: 2016

Kidney exchanges are organized markets where patients swap willing but incompatible donors. In the last decade, kidney exchanges grew from small and regional to large and national---and soon, international. This growth results in more lives saved, but exacerbates the empirical hardness of the $\mathcal{NP}$-complete problem of optimally matching patients to donors. State-of-the-art matching engines use integer programming techniques to clear fielded kidney exchanges, but these methods must be tailored to specific models and objective functions, and may fail to scale to larger exchanges. In this paper, we observe that if the kidney exchange compatibility graph can be encoded by a constant number of patient and donor attributes, the clearing problem is solvable in polynomial time. We give necessary and sufficient conditions for losslessly shrinking the representation of an arbitrary compatibility graph. Then, using real compatibility graphs from the UNOS nationwide kidney exchange, we show how many attributes are needed to encode real compatibility graphs. The experiments show that, indeed, small numbers of attributes suffice.
Recursive SDN for Carrier Networks
Venue: arXiv cs.NI 2016
Year: 2016

Control planes for global carrier networks should be programmable (so that new functionality can be easily introduced) and scalable (so they can handle the numerical scale and geographic scope of these networks). Neither traditional control planes nor new SDN-based control planes meet both of these goals. In this paper, we propose a framework for recursive routing computations that combines the best of SDN (programmability) and traditional networks (scalability through hierarchy) to achieve these two desired properties. Through simulation on graphs of up to 10,000 nodes, we evaluate our design's ability to support a variety of routing and traffic engineering solutions, while incorporating a fast failure recovery mechanism.
Solving discrete logarithms on a 170-bit MNT curve by pairing reduction
Venue: arXiv cs.CR 2016
Year: 2016

Pairing based cryptography is in a dangerous position following the breakthroughs on discrete logarithms computations in finite fields of small characteristic. Remaining instances are built over finite fields of large characteristic and their security relies on the fact that the embedding field of the underlying curve is relatively large. How large is debatable. The aim of our work is to sustain the claim that the combination of degree 3 embedding and too small finite fields obviously does not provide enough security. As a computational example, we solve the DLP on a 170-bit MNT curve, by exploiting the pairing embedding to a 508-bit, degree-3 extension of the base field.
Deciding Maxmin Reachability in Half-Blind Stochastic Games
Venue: arXiv cs.GT 2016
Year: 2016

Two-player, turn-based, stochastic games with reachability conditions are considered, where the maximizer has no information (he is blind) and is restricted to deterministic strategies whereas the minimizer is perfectly informed. We ask the question of whether the game has maxmin 1, in other words we ask whether for all $ε>0$ there exists a deterministic strategy for the (blind) maximizer such that against all the strategies of the minimizer, it is possible to reach the set of final states with probability larger than $1-ε$. This problem is undecidable in general, but we define a class of games, called leaktight half-blind games where the problem becomes decidable. We also show that mixed strategies in general are stronger for both players and that optimal strategies for the minimizer might require infinite-memory.
Designing Distributed Fixed-Time Consensus Protocols for Linear Multi-Agent Systems Over Directed Graphs
Venue: arXiv cs.SY 2016
Year: 2016

This technical note addresses the distributed fixed-time consensus protocol design problem for multi-agent systems with general linear dynamics over directed communication graphs. By using motion planning approaches, a class of distributed fixed-time consensus algorithms are developed, which rely only on the sampling information at some sampling instants. For linear multi-agent systems, the proposed algorithms solve the fixed-time consensus problem for any directed graph containing a directed spanning tree. In particular, the settling time can be off-line pre-assigned according to task requirements. Compared with the existing results for multi-agent systems, to our best knowledge, it is the first-time to solve fixed-time consensus problems for general linear multi-agent systems over directed graphs having a directed spanning tree. Extensions to the fixed-time formation flying are further studied for multiple satellites described by Hill equations.
Projections for infinitary rewriting
Venue: arXiv cs.LO 2016
Year: 2016

Proof terms in term rewriting are a representation means for reduction sequences, and more in general for contraction activity, allowing to distinguish e.g simultaneous from sequential reduction. Proof terms for finitary, first-order, left-linear term rewriting are described in the Terese book, chapter 8. In a previous work, we defined an extension of the finitary proof-term formalism, that allows to describe contractions in infinitary first-order term rewriting, and gave a characterisation of permutation equivalence. In this work, we discuss how projections of possibly infinite rewrite sequences can be modeled using proof terms. Again, the foundation is a characterisation of projections for finitary rewriting described in Terese, Section 8.7. We extend this characterisation to infinitary rewriting and also refine it, by describing precisely the role that structural equivalence plays in the development of the notion of projection. The characterisation we propose yields a definite expression, i.e. a proof term, that describes the projection of an infinitary reduction over another. To illustrate the working of projections, we show how a common reduct of a (possibly infinite) reduction and a single step that makes part of it can be obtained via their respective projections. We show, by means of several examples, that the proposed definition yields the expected behavior also in cases beyond those covered by this result. Finally, we discuss how the notion of limit is used in our definition of projection for infinite reduction.
Efficient High-Speed WPA2 Brute Force Attacks using Scalable Low-Cost FPGA Clustering [Extended Version]
Venue: arXiv cs.CR 2016
Year: 2016

WPA2-Personal is widely used to protect Wi-Fi networks against illicit access. While attackers typically use GPUs to speed up the discovery of weak network passwords, attacking random passwords is considered to quickly become infeasible with increasing password length. Professional attackers may thus turn to commercial high-end FPGA-based cluster solutions to significantly increase the speed of those attacks. Well known manufacturers such as Elcomsoft have succeeded in creating world's fastest commercial FPGA-based WPA2 password recovery system, but since they rely on high-performance FPGAs the costs of these systems are well beyond the reach of amateurs. In this paper, we present a highly optimized low-cost FPGA cluster-based WPA-2 Personal password recovery system that can not only achieve similar performance at a cost affordable by amateurs, but in comparison our implementation would also be more than 5 times as fast on the original hardware. Since the currently fastest system is not only significantly slower but proprietary as well, we believe that we are the first to present the internals of a highly optimized and fully pipelined FPGA WPA2 password recovery system. In addition, we evaluated our approach with respect to performance and power usage and compare it to GPU-based systems. To assess the real-world impact of our system, we utilized the well known Wigle Wi-Fi network dataset to conduct a case study within the country and its border regions. Our results indicate that our system could be used to break into each of more than 160,000 existing Wi-Fi networks requiring 3 days per network on our low-cost FPGA cluster in the worst case.
Dimension Projection among Languages based on Pseudo-relevant Documents for Query Translation
Venue: arXiv cs.IR 2016
Year: 2016

Using top-ranked documents in response to a query has been shown to be an effective approach to improve the quality of query translation in dictionary-based cross-language information retrieval. In this paper, we propose a new method for dictionary-based query translation based on dimension projection of embedded vectors from the pseudo-relevant documents in the source language to their equivalents in the target language. To this end, first we learn low-dimensional vectors of the words in the pseudo-relevant collections separately and then aim to find a query-dependent transformation matrix between the vectors of translation pairs appeared in the collections. At the next step, representation of each query term is projected to the target language and then, after using a softmax function, a query-dependent translation model is built. Finally, the model is used for query translation. Our experiments on four CLEF collections in French, Spanish, German, and Italian demonstrate that the proposed method outperforms a word embedding baseline based on bilingual shuffling and a further number of competitive baselines. The proposed method reaches up to 87% performance of machine translation (MT) in short queries and considerable improvements in verbose queries.
Automatic Open Knowledge Acquisition via Long Short-Term Memory Networks with Feedback Negative Sampling
Venue: arXiv cs.CL 2016
Year: 2016

Previous studies in Open Information Extraction (Open IE) are mainly based on extraction patterns. They manually define patterns or automatically learn them from a large corpus. However, these approaches are limited when grasping the context of a sentence, and they fail to capture implicit relations. In this paper, we address this problem with the following methods. First, we exploit long short-term memory (LSTM) networks to extract higher-level features along the shortest dependency paths, connecting headwords of relations and arguments. The path-level features from LSTM networks provide useful clues regarding contextual information and the validity of arguments. Second, we constructed samples to train LSTM networks without the need for manual labeling. In particular, feedback negative sampling picks highly negative samples among non-positive samples through a model trained with positive samples. The experimental results show that our approach produces more precise and abundant extractions than state-of-the-art open IE systems. To the best of our knowledge, this is the first work to apply deep learning to Open IE.
Structural Analysis of User Choices for Mobile App Recommendation
Venue: arXiv cs.IR 2016
Year: 2016

Advances in smartphone technology have promoted the rapid development of mobile apps. However, the availability of a huge number of mobile apps in application stores has imposed the challenge of finding the right apps to meet the user needs. Indeed, there is a critical demand for personalized app recommendations. Along this line, there are opportunities and challenges posed by two unique characteristics of mobile apps. First, app markets have organized apps in a hierarchical taxonomy. Second, apps with similar functionalities are competing with each other. While there are a variety of approaches for mobile app recommendations, these approaches do not have a focus on dealing with these opportunities and challenges. To this end, in this paper, we provide a systematic study for addressing these challenges. Specifically, we develop a Structural User Choice Model (SUCM) to learn fine-grained user preferences by exploiting the hierarchical taxonomy of apps as well as the competitive relationships among apps. Moreover, we design an efficient learning algorithm to estimate the parameters for the SUCM model. Finally, we perform extensive experiments on a large app adoption data set collected from Google Play. The results show that SUCM consistently outperforms state-of-the-art top-N recommendation methods by a significant margin.
End-to-End Known-Interference Cancellation (E2E-KIC) with Multi-Hop Interference
Venue: arXiv cs.IT 2016
Year: 2016

Recently, end-to-end known-interference cancellation (E2E-KIC) has been proposed as a promising technique for wireless networks. It sequentially cancels out the known interferences at each node so that wireless multi-hop transmission can achieve a similar throughput as single-hop transmission. Existing work on E2E-KIC assumed that the interference of a transmitter to those nodes outside the transmitter's communication range is negligible. In practice, however, this assumption is not always valid. There are many cases where a transmitter causes notable interference to nodes beyond its communication distance. From a wireless networking perspective, such interference is caused by a node to other nodes that are multiple hops away, thus we call it multi-hop interference. The presence of multi-hop interference poses fundamental challenges to E2E-KIC, where known procedures cannot be directly applied. In this paper, we propose an E2E-KIC approach which allows the existence of multi-hop interference. In particular, we present a method that iteratively cancels unknown interferences transmitted across multiple hops. We analyze mathematically why and when this approach works and the performance of it. The analysis is further supported by numerical results.
Cryptographic applications of capacity theory: On the optimality of Coppersmith's method for univariate polynomials
Venue: arXiv cs.CR 2016
Year: 2016

We draw a new connection between Coppersmith's method for finding small solutions to polynomial congruences modulo integers and the capacity theory of adelic subsets of algebraic curves. Coppersmith's method uses lattice basis reduction to construct an auxiliary polynomial that vanishes at the desired solutions. Capacity theory provides a toolkit for proving when polynomials with certain boundedness properties do or do not exist. Using capacity theory, we prove that Coppersmith's bound for univariate polynomials is optimal in the sense that there are \emph{no} auxiliary polynomials of the type he used that would allow finding roots of size $N^{1/d+ε}$ for monic degree-$d$ polynomials modulo $N$. Our results rule out the existence of polynomials of any degree and do not rely on lattice algorithms, thus eliminating the possibility of even superpolynomial-time improvements to Coppersmith's bound. We extend this result to constructions of auxiliary polynomials using binomial polynomials, and rule out the existence of any auxiliary polynomial of this form that would find solutions of size $N^{1/d+ε}$ unless $N$ has a very small prime factor.
A Rank Revealing Randomized Singular Value Decomposition (R3SVD) Algorithm for Low-rank Matrix Approximations
Venue: arXiv cs.NA 2016
Year: 2016

In this paper, we present a Rank Revealing Randomized Singular Value Decomposition (R3SVD) algorithm to incrementally construct a low-rank approximation of a potentially large matrix while adaptively estimating the appropriate rank that can capture most of the actions of the matrix. Starting from a low-rank approximation with an initial guessed rank, R3SVD adopts an orthogonal Gaussian sampling approach to obtain the dominant subspace within the leftover space, which is used to add up to the existing low-rank approximation. Orthogonal Gaussian sampling is repeated until an appropriate low-rank approximation with satisfactory accuracy, measured by the overall energy percentage of the original matrix, is obtained. While being a fast algorithm, R3SVD is also a memory-aware algorithm where the computational process can be decomposed into a series of sampling tasks that use constant amount of memory. Numerical examples in image compression and matrix completion are used to demonstrate the effectiveness of R3SVD in low-rank approximation.