OpenRaiser/Intern-Atlas huggingface dataset:
The Computational Complexity of the Frobenius Problem
Venue: arXiv cs.CC 2016
Year: 2016

In this paper, as a main theorem, we prove that the decision version of the Frobenius problem is Sigma_2^P-complete under Karp reductions.Given a finite set A of coprime positive integers, we call the greatest integer that cannot be represented as a nonnegative integer combination of A the Frobenius number, and we denote it as g(A). We call a problem of finding g(A) for a given A the Frobenius problem; moreover, we call a problem of determining whether g(A) >= k for a given pair (A, k) the decision version of the Frobenius problem, where A is a finite set of coprime positive integers and k is a positive integer. For the proof, we construct two Karp reductions. First, we reduce a 2-alternating version of the 3-dimensional matching problem, which is known to be Pi_2^P-complete, to a 2-alternating version of the integer knapsack problem. Then, we reduce the variant of the integer knapsack problem to the complement of the decision version of the Frobenius problem. As a corollary, we obtain the main theorem.
Feature-Area Optimization: A Novel SAR Image Registration Method
Venue: arXiv cs.CV 2016
Year: 2016

This letter proposes a synthetic aperture radar (SAR) image registration method named Feature-Area Optimization (FAO). First, the traditional area-based optimization model is reconstructed and decomposed into three key but uncertain factors: initialization, slice set and regularization. Next, structural features are extracted by scale invariant feature transform (SIFT) in dual-resolution space (SIFT-DRS), a novel SIFT-Like method dedicated to FAO. Then, the three key factors are determined based on these features. Finally, solving the factor-determined optimization model can get the registration result. A series of experiments demonstrate that the proposed method can register multi-temporal SAR images accurately and efficiently.
Maximum Weight Independent Set in lClaw-Free Graphs in Polynomial Time
Venue: arXiv cs.DM 2016
Year: 2016

The Maximum Weight Independent Set (MWIS) problem is a well-known NP-hard problem. For graphs $G_1, G_2$, $G_1+G_2$ denotes the disjoint union of $G_1$ and $G_2$, and for a constant $l \ge 2$, $lG$ denotes the disjoint union of $l$ copies of $G$. A {\em claw} has vertices $a,b,c,d$, and edges $ab,ac,ad$. MWIS can be solved for claw-free graphs in polynomial time; the first two polynomial time algorithms were introduced in 1980 by \cite{Minty1980,Sbihi1980}, then revisited by \cite{NakTam2001}, and recently improved by \cite{FaeOriSta2011,FaeOriSta2014}, and by \cite{NobSas2011,NobSas2015} with the best known time bound in \cite{NobSas2015}. Furthermore MWIS can be solved for the following extensions of claw-free graphs in polynomial time: fork-free graphs \cite{LozMil2008}, $K_2$+claw-free graphs \cite{LozMos2005}, and apple-free graphs \cite{BraLozMos2010,BraKleLozMos2008}. This manuscript shows that for any constant $l$, MWIS can be solved for $l$claw-free graphs in polynomial time. Our approach is based on Farber's approach showing that every $2K_2$-free graph has ${\cal O}(n^2)$ maximal independent sets \cite{Farbe1989}, which directly leads to a polynomial time algorithm for MWIS on $2K_2$-free graphs by dynamic programming. Solving MWIS for $l$claw-free graphs in polynomial time extends known results for claw-free graphs, for $lK_2$-free graphs for any constant $l$ \cite{Aleks1991,FarHujTuz1993,Prisn1995,TsuIdeAriShi1977}, for $K_2$+claw-free graphs, for $2P_3$-free graphs \cite{LozMos2012}, and solves the open questions for $2K_2+P_3$-free graphs and for $P_3$+claw-free graphs being two of the minimal graph classes, defined by forbidding one induced subgraph, for which the complexity of MWIS was an open problem.
Distortion-Resistant Hashing for rapid search of similar DNA subsequence
Venue: arXiv cs.DS 2016
Year: 2016

One of the basic tasks in bioinformatics is localizing a short subsequence $S$, read while sequencing, in a long reference sequence $R$, like the human geneome. A natural rapid approach would be finding a hash value for $S$ and compare it with a prepared database of hash values for each of length $|S|$ subsequences of $R$. The problem with such approach is that it would only spot a perfect match, while in reality there are lots of small changes: substitutions, deletions and insertions. This issue could be repaired if having a hash function designed to tolerate some small distortion accordingly to an alignment metric (like Needleman-Wunch): designed to make that two similar sequences should most likely give the same hash value. This paper discusses construction of Distortion-Resistant Hashing (DRH) to generate such fingerprints for rapid search of similar subsequences. The proposed approach is based on the rate distortion theory: in a nearly uniform subset of length $|S|$ sequences, the hash value represents the closest sequence to $S$. This gives some control of the distance of collisions: sequences having the same hash value.
One-Counter Automata with Counter Observability
Venue: arXiv cs.FL 2016
Year: 2016

In a one-counter automaton (OCA), one can produce a letter from some finite alphabet, increment and decrement the counter by one, or compare it with constants up to some threshold. It is well-known that universality and language inclusion for OCAs are undecidable. In this paper, we consider OCAs with counter observability: Whenever the automaton produces a letter, it outputs the current counter value along with it. Hence, its language is now a set of words over an infinite alphabet. We show that universality and inclusion for that model are PSPACE-complete, thus no harder than the corresponding problems for finite automata. In fact, by establishing a link with visibly one-counter automata, we show that OCAs with counter observability are effectively determinizable and closed under all boolean operations.
Revise Saturated Activation Functions
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we revise two commonly used saturated functions, the logistic sigmoid and the hyperbolic tangent (tanh). We point out that, besides the well-known non-zero centered property, slope of the activation function near the origin is another possible reason making training deep networks with the logistic function difficult to train. We demonstrate that, with proper rescaling, the logistic sigmoid achieves comparable results with tanh. Then following the same argument, we improve tahn by penalizing in the negative part. We show that "penalized tanh" is comparable and even outperforms the state-of-the-art non-saturated functions including ReLU and leaky ReLU on deep convolution neural networks. Our results contradict to the conclusion of previous works that the saturation property causes the slow convergence. It suggests further investigation is necessary to better understand activation functions in deep architectures.
On Edge Caching with Secrecy Constraints
Venue: arXiv cs.IT 2016
Year: 2016

In this paper we investigate the problem of optimal cache placement under secrecy constraints in heterogeneous networks, where small-cell base stations are equipped with caches to reduce the overall backhaul load. For two models for eavesdropping attacks, we formally derive the necessary conditions for secrecy and we derive the corresponding achievable backhaul rate. In particular we formulate the optimal caching schemes with secrecy constraints as a convex optimization problem. We then thoroughly investigate the backhaul rate performance of the heterogeneous network with secrecy constraints using numerical simulations. We compare the system performance with and without secrecy constraints and we analyze the influence of the system parameters, such as the file popularity, size of the library files and the capabilities of the small-cell base stations, on the overall performance of our optimal caching strategy. Our results highlight the considerable impact of the secrecy requirements on the overall caching performance of the network.
On the security of 2-key triple DES
Venue: arXiv cs.CR 2016
Year: 2016

This paper reconsiders the security offered by 2-key triple DES, an encryption technique that remains widely used despite recently being de-standardised by NIST. A generalisation of the 1990 van Oorschot-Wiener attack is described, constituting the first advance in cryptanalysis of 2-key triple DES since 1990. We give further attack enhancements that together imply that the widely used estimate that 2-key triple DES provides 80 bits of security can no longer be regarded as conservative; the widely stated assertion that the scheme is secure as long as the key is changed regularly is also challenged. The main conclusion is that, whilst not completely broken, the margin of safety for 2-key triple DES is slim, and efforts to replace it, at least with its 3-key variant, should be pursued with some urgency.
Cross Validation in Compressive Sensing and its Application of OMP-CV Algorithm
Venue: arXiv cs.IT 2016
Year: 2016

Compressive sensing (CS) is a data acquisition technique that measures sparse or compressible signals at a sampling rate lower than their Nyquist rate. Results show that sparse signals can be reconstructed using greedy algorithms, often requiring prior knowledge such as the signal sparsity or the noise level. As a substitute to prior knowledge, cross validation (CV), a statistical method that examines whether a model overfits its data, has been proposed to determine the stopping condition of greedy algorithms. This paper first analyzes cross validation in a general compressive sensing framework and developed general cross validation techniques which could be used to understand CV-based sparse recovery algorithms. Furthermore, we provide theoretical analysis for OMP-CV, a cross validation modification of orthogonal matching pursuit, which has very good sparse recovery performance. Finally, numerical experiments are given to validate our theoretical results and investigate the behaviors of OMP-CV.
Web Item Reviewing Made Easy By Leveraging Available User Feedback
Venue: arXiv cs.SI 2016
Year: 2016

The widespread use of online review sites over the past decade has motivated businesses of all types to possess an expansive arsenal of user feedback to mark their reputation. Though a significant proportion of purchasing decisions are driven by average rating, detailed reviews are critical for activities like buying expensive digital SLR camera. Since writing a detailed review for an item is usually time-consuming, the number of reviews available in the Web is far from many. Given a user and an item our goal is to identify the top-$k$ meaningful phrases/tags to help her review the item easily. We propose general-constrained optimization framework based on three measures - relevance (how well the result set of tags describes an item), coverage (how well the result set of tags covers the different aspects of an item), and polarity (how well sentiment is attached to the result set of tags). By adopting different definitions of coverage, we identify two concrete problem instances that enable a wide range of real-world scenarios. We develop practical algorithms with theoretical bounds to solve these problems efficiently. We conduct experiments on synthetic and real data crawled from the web to validate the effectiveness of our solutions.
Causes for Query Answers from Databases, Datalog Abduction and View-Updates: The Presence of Integrity Constraints
Venue: arXiv cs.DB 2016
Year: 2016

Causality has been recently introduced in databases, to model, characterize and possibly compute causes for query results (answers). Connections between queryanswer causality, consistency-based diagnosis, database repairs (wrt. integrity constraint violations), abductive diagnosis and the view-update problem have been established. In this work we further investigate connections between query-answer causality and abductive diagnosis and the view-update problem. In this context, we also define and investigate the notion of query-answer causality in the presence of integrity constraints.
Computational Narrative Intelligence: A Human-Centered Goal for Artificial Intelligence
Venue: arXiv cs.AI 2016
Year: 2016

Narrative intelligence is the ability to craft, tell, understand, and respond affectively to stories. We argue that instilling artificial intelligences with computational narrative intelligence affords a number of applications beneficial to humans. We lay out some of the machine learning challenges necessary to solve to achieve computational narrative intelligence. Finally, we argue that computational narrative is a practical step towards machine enculturation, the teaching of sociocultural values to machines.
Distributed Private Online Learning for Social Big Data Computing over Data Center Networks
Venue: arXiv cs.DC 2016
Year: 2016

With the rapid growth of Internet technologies, cloud computing and social networks have become ubiquitous. An increasing number of people participate in social networks and massive online social data are obtained. In order to exploit knowledge from copious amounts of data obtained and predict social behavior of users, we urge to realize data mining in social networks. Almost all online websites use cloud services to effectively process the large scale of social data, which are gathered from distributed data centers. These data are so large-scale, high-dimension and widely distributed that we propose a distributed sparse online algorithm to handle them. Additionally, privacy-protection is an important point in social networks. We should not compromise the privacy of individuals in networks, while these social data are being learned for data mining. Thus we also consider the privacy problem in this article. Our simulations shows that the appropriate sparsity of data would enhance the performance of our algorithm and the privacy-preserving method does not significantly hurt the performance of the proposed algorithm.
A Survey of Semantic Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

This survey gives an overview over different techniques used for pixel-level semantic segmentation. Metrics and datasets for the evaluation of segmentation algorithms and traditional approaches for segmentation such as unsupervised methods, Decision Forests and SVMs are described and pointers to the relevant papers are given. Recently published approaches with convolutional neural networks are mentioned and typical problematic situations for segmentation algorithms are examined. A taxonomy of segmentation algorithms is given.
Creating Simplified 3D Models with High Quality Textures
Venue: arXiv cs.GR 2016
Year: 2016

This paper presents an extension to the KinectFusion algorithm which allows creating simplified 3D models with high quality RGB textures. This is achieved through (i) creating model textures using images from an HD RGB camera that is calibrated with Kinect depth camera, (ii) using a modified scheme to update model textures in an asymmetrical colour volume that contains a higher number of voxels than that of the geometry volume, (iii) simplifying dense polygon mesh model using quadric-based mesh decimation algorithm, and (iv) creating and mapping 2D textures to every polygon in the output 3D model. The proposed method is implemented in real-time by means of GPU parallel processing. Visualization via ray casting of both geometry and colour volumes provides users with a real-time feedback of the currently scanned 3D model. Experimental results show that the proposed method is capable of keeping the model texture quality even for a heavily decimated model and that, when reconstructing small objects, photorealistic RGB textures can still be reconstructed.
How Much Bandpass Filtering is Required in Massive MIMO Basestations?
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we study the impact of aliased out-of-band interference signals on the information sum-rate of the maximum ratio combining receiver in massive multiple-input multiple-output (MIMO) uplink, with both perfect and imperfect channel estimates, in order to determine the required out-of-band attenuation in RF bandpass filters (BPFs). With imperfect channel estimates, our study reveals that as the number of base-station (BS) antennas ($M$) increases, the required attenuation at the BPFs increases as $\mathcal{O}(\sqrt{M})$ with $M \to \infty$, provided the desired information sum-rate (both in the presence and in the absence of AOOBIs (aliased out-of-band interferers)) remains fixed. This implies a practical limit on the number of BS antennas due to the increase in BPF design complexity and power consumption with increasing $M$.
WeBrowse: Mining HTTP logs online for network-based content recommendation
Venue: arXiv cs.HC 2016
Year: 2016

A powerful means to help users discover new content in the overwhelming amount of information available today is sharing in online communities such as social networks or crowdsourced platforms. This means comes short in the case of what we call communities of a place: people who study, live or work at the same place. Such people often share common interests but either do not know each other or fail to actively engage in submitting and relaying information. To counter this effect, we propose passive crowdsourced content discovery, an approach that leverages the passive observation of web-clicks as an indication of users' interest in a piece of content. We design, implement, and evaluate WeBrowse , a passive crowdsourced system which requires no active user engagement to promote interesting content to users of a community of a place. Instead, it extracts the URLs users visit from traffic traversing a network link to identify popular and interesting pieces of information. We first prototype WeBrowse and evaluate it using both ground-truths and real traces from a large European Internet Service Provider. Then, we deploy WeBrowse in a campus of 15,000 users, and in a neighborhood. Evaluation based on our deployments shows the feasibility of our approach. The majority of WeBrowse's users welcome the quality of content it promotes. Finally, our analysis of popular topics across different communities confirms that users in the same community of a place share common interests, compared to users from different communities, thus confirming the promise of WeBrowse's approach.
Fast IDS Computing System Method and its Memristor Crossbar-based Hardware Implementation
Venue: arXiv cs.ET 2016
Year: 2016

Active Learning Method (ALM) is one of the powerful tools in soft computing that is inspired by human brain capabilities in processing complicated information. ALM, which is in essence an adaptive fuzzy learning method, models a Multi-Input Single-Output (MISO) system with several Single-Input Single-Output (SISO) subsystems. Ink Drop Spread (IDS) operator, which is the main processing engine of this method, extracts useful features from the data without complicated computations and provides stability and convergence as well. Despite great performance of ALM in applications such as classification, clustering, and modelling, an efficient hardware implementation has remained a challenging problem. Large amount of memory required to store the information of IDS planes as well as the high computational cost of the IDS computing system are two main barriers to ALM becoming more popular. In this paper, a novel learning method is proposed based on the idea of IDS, but with a novel approach that eliminates the computational cost of IDS operator. Unlike traditional approaches, our proposed method finds functions to describe the IDS plane that eliminates the need for large amount of memory to a great extent. Narrow Path and Spread, which are two main features used in the inference engine of ALM, are then extracted from IDS planes with minimum amount of memory usage and power consumption. Our proposed algorithm is fully compatible with memristor-crossbar implementation that leads to a significant decrease in the number of required memristors (from O(n^2) to O(3n)). Simpler algorithm and higher speed make our algorithm suitable for applications where real-time process, low-cost and small implementation are paramount. Applications in clustering and function approximation are provided, which reveals the effective performance of our proposed algorithm.
Robust stabilization loop design for gimbaled electro-optical imaging system
Venue: arXiv cs.SY 2016
Year: 2016

For electro-optical imaging systems, line-of-sight stabilization against different disturbances created by mobile platforms is crucial property. The development of high resolution sensors and the demand in increased operating distances have recently increased the expectations from stabilization loops. For that reason, higher gains and larger bandwidths become necessary. As the stabilization loop satisfies these requirements for good disturbance attenuation, it must also satisfy sufficient loop stability. In gimbaled imaging systems, the main difficulties in satisfying sufficient loop stability are structural resonances and model uncertainties. Therefore, satisfying high stabilization performance in the presence of model uncertainties or modeling errors requires utilization of robust control methods. In this paper, robust LQG/LTR controller design is described for a two-axis gimbal. First, the classical LQG/LTR method is modified such that it becomes very powerful loop shaping method. Next, using this method, controller is synthesized. Robust stability and robust performance of stabilization loop is investigated by using singular value tests. The report is concluded with the experimental validation of the designed robust controller.
An Empirical Study on Computing Equilibria in Polymatrix Games
Venue: arXiv cs.GT 2016
Year: 2016

The Nash equilibrium is an important benchmark for behaviour in systems of strategic autonomous agents. Polymatrix games are a succinct and expressive representation of multiplayer games that model pairwise interactions between players. The empirical performance of algorithms to solve these games has received little attention, despite their wide-ranging applications. In this paper we carry out a comprehensive empirical study of two prominent algorithms for computing a sample equilibrium in these games, Lemke's algorithm that computes an exact equilibrium, and a gradient descent method that computes an approximate equilibrium. Our study covers games arising from a number of interesting applications. We find that Lemke's algorithm can compute exact equilibria in relatively large games in a reasonable amount of time. If we are willing to accept (high-quality) approximate equilibria, then we can deal with much larger games using the descent method. We also report on which games are most challenging for each of the algorithms.
Prime Factoring and The Complexity Of
Venue: arXiv cs.DM 2016
Year: 2016

A difference equation based method of determining two factors of a composite is presented. The feasibility of P-complexity is shown. Presentation of material is non-theoretical; intended to be accessible to a broader audience of non academic and theoretical practitioners.
Periodicity in Rectangular Arrays
Venue: arXiv cs.DM 2016
Year: 2016

We discuss several two-dimensional generalizations of the familiar Lyndon-Schutzenberger periodicity theorem for words. We consider the notion of primitive array (as one that cannot be expressed as the repetition of smaller arrays). We count the number of m x n arrays that are primitive. Finally, we show that one can test primitivity and compute the primitive root of an array in linear time.