OpenRaiser/Intern-Atlas huggingface dataset:
Roughly Polynomial Time: A Concept of Tractability Covering All Known Natural NP-complete Problems
Venue: arXiv cs.CC 2016
Year: 2016

We introduce a concept of efficiency for which we can prove that it applies to all paddable languages, but still does not conflict with potential worst case intractability. Note that the family of paddable languages apparently includes all known natural NP-complete problems. We call our concept Roughly Polynomial Time (RoughP). A language $L,$ over an at least 2-symbol alphabet, is in RoughP, if the following hold: (1) there exists a bijective encoding $α$ of strings, such that both $α$ and its inverse are computable in polynomial time; (2) there is a polynomial time algorithm $\cal A$, which is an errorless heuristic for $L,$ with exponentially vanishing failure rate relative to the $α$-spheres $S^{(α)}_n=\{α(x)\,|\;\, |x|=n\}$. It means, $\cal A$ always correctly decides whether $x\in L$ or $x\notin L$, whenever it outputs a decision. For some inputs, however, it may not output a decision, rather it may return a special sign, meaning "don't know." But the latter can happen only on an exponentially small fraction of each $α$-sphere. We prove that RoughP contains all paddable languages. This may contribute to the explanation of the often observed gap between practical algorithm performance and theoretical worst case analysis for hard problems. Furthermore, the proof also provides a general method to construct the desired encoding and the errorless heuristic. Additionally, we also show how to use it for efficiently generating large, random, guaranteed positive and negative test instances for any paddable language, including all known natural NP-complete problems. In fact, it appears that every practical decision task (whether in NP or not) can be represented by paddable languages, and, therefore, our RoughP framework applies to all of them. We also explore some connections between RoughP and other complexity classes.
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps
Venue: arXiv cs.LO 2016
Year: 2016

We prove near-optimal trade-offs for quantifier depth versus number of variables in first-order logic by exhibiting pairs of $n$-element structures that can be distinguished by a $k$-variable first-order sentence but where every such sentence requires quantifier depth at least $n^{Ω(k/\log k)}$. Our trade-offs also apply to first-order counting logic, and by the known connection to the $k$-dimensional Weisfeiler--Leman algorithm imply near-optimal lower bounds on the number of refinement iterations. A key component in our proof is the hardness condensation technique recently introduced by [Razborov '16] in the context of proof complexity. We apply this method to reduce the domain size of relational structures while maintaining the minimal quantifier depth to distinguish them in finite variable logics.
A Programming Language With a POMDP Inside
Venue: arXiv cs.AI 2016
Year: 2016

We present POAPS, a novel planning system for defining Partially Observable Markov Decision Processes (POMDPs) that abstracts away from POMDP details for the benefit of non-expert practitioners. POAPS includes an expressive adaptive programming language based on Lisp that has constructs for choice points that can be dynamically optimized. Non-experts can use our language to write adaptive programs that have partially observable components without needing to specify belief/hidden states or reason about probabilities. POAPS is also a compiler that defines and performs the transformation of any program written in our language into a POMDP with control knowledge. We demonstrate the generality and power of POAPS in the rapidly growing domain of human computation by describing its expressiveness and simplicity by writing several POAPS programs for common crowdsourcing tasks.
Probabilistic Medium Access Control for Full-Duplex Networks with Half-Duplex Clients
Venue: arXiv cs.NI 2016
Year: 2016

The feasibility of practical in-band full-duplex radios has recently been demonstrated experimentally. One way to leverage full-duplex in a network setting is to enable three-node full-duplex, where a full- duplex access point (AP) transmits data to one node yet simultaneously receives data from another node. Such three-node full-duplex communication however introduces inter-client interference, directly impacting the full-duplex gain. It hence may not always be beneficial to enable three-node full-duplex transmissions. In this paper, we present a distributed full-duplex medium access control (MAC) protocol that allows an AP to adaptively switch between full-duplex and half-duplex modes. We formulate a model that determines the probabilities of full-duplex and half-duplex access so as to maximize the expected network throughput. A MAC protocol is further proposed to enable the AP and clients to contend for either full-duplex or half-duplex transmissions based on their assigned probabilities in a distributed way. Our evaluation shows that, by combining the advantages of centralized probabilistic scheduling and distributed random access, our design improves the overall throughput by 2.70x and 1.53x, on average, as compared to half-duplex 802.11 and greedy downlink-uplink client pairing.
Binary Particle Swarm Optimization versus Hybrid Genetic Algorithm for Inferring Well Supported Phylogenetic Trees
Venue: arXiv cs.AI 2016
Year: 2016

The amount of completely sequenced chloroplast genomes increases rapidly every day, leading to the possibility to build large-scale phylogenetic trees of plant species. Considering a subset of close plant species defined according to their chloroplasts, the phylogenetic tree that can be inferred by their core genes is not necessarily well supported, due to the possible occurrence of problematic genes (i.e., homoplasy, incomplete lineage sorting, horizontal gene transfers, etc.) which may blur the phylogenetic signal. However, a trustworthy phylogenetic tree can still be obtained provided such a number of blurring genes is reduced. The problem is thus to determine the largest subset of core genes that produces the best-supported tree. To discard problematic genes and due to the overwhelming number of possible combinations, this article focuses on how to extract the largest subset of sequences in order to obtain the most supported species tree. Due to computational complexity, a distributed Binary Particle Swarm Optimization (BPSO) is proposed in sequential and distributed fashions. Obtained results from both versions of the BPSO are compared with those computed using an hybrid approach embedding both genetic algorithms and statistical tests. The proposal has been applied to different cases of plant families, leading to encouraging results for these families.
Paradoxical examples of social networks games with product choice
Venue: arXiv cs.GT 2016
Year: 2016

Paradox of choice occurs when permitting new strategies to some players yields lower payoffs for all players in the new equilibrium via a sequence of individually rational actions. We consider social network games. In these games the payoff of each player increases when other players choose the same strategy. The definition of games on social networks was introduced by K. Apt and S. Simon. In an article written jointly with E. Markakis, they considered four types of paradox of choice in such games and gave examples of three of them. The existence of paradoxical networks of the fourth type was proven only in a weakened form. The existence of so-called vulnerable networks in the strong sense remained an open question. In the present paper we solve this open question by introducing a construction, called a cascade, and use it to provide uniform examples for all four definitions of paradoxical networks.
Facial Surface Analysis using Iso-Geodesic Curves in Three Dimensional Face Recognition System
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we present an automatic 3D face recognition system. This system is based on the representation of human faces surfaces as collections of Iso-Geodesic Curves (IGC) using 3D Fast Marching algorithm. To compare two facial surfaces, we compute a geodesic distance between a pair of facial curves using a Riemannian geometry. In the classifying step, we use: Neural Networks (NN), K-Nearest Neighbor (KNN) and Support Vector Machines (SVM). To test this method and evaluate its performance, a simulation series of experiments were performed on 3D Shape REtrieval Contest 2008 database (SHREC2008).
A High Speed Multi-label Classifier based on Extreme Learning Machines
Venue: arXiv cs.LG 2016
Year: 2016

In this paper a high speed neural network classifier based on extreme learning machines for multi-label classification problem is proposed and dis-cussed. Multi-label classification is a superset of traditional binary and multi-class classification problems. The proposed work extends the extreme learning machine technique to adapt to the multi-label problems. As opposed to the single-label problem, both the number of labels the sample belongs to, and each of those target labels are to be identified for multi-label classification resulting in in-creased complexity. The proposed high speed multi-label classifier is applied to six benchmark datasets comprising of different application areas such as multi-media, text and biology. The training time and testing time of the classifier are compared with those of the state-of-the-arts methods. Experimental studies show that for all the six datasets, our proposed technique have faster execution speed and better performance, thereby outperforming all the existing multi-label clas-sification methods.
Knowledge Representation Analysis of Graph Mining
Venue: arXiv cs.LO 2016
Year: 2016

Many problems, especially those with a composite structure, can naturally be expressed in higher order logic. From a KR perspective modeling these problems in an intuitive way is a challenging task. In this paper we study the graph mining problem as an example of a higher order problem. In short, this problem asks us to find a graph that frequently occurs as a subgraph among a set of example graphs. We start from the problem's mathematical definition to solve it in three state-of-the-art specification systems. For IDP and ASP, which have no native support for higher order logic, we propose the use of encoding techniques such as the disjoint union technique and the saturation technique. ProB benefits from the higher order support for sets. We compare the performance of the three approaches to get an idea of the overhead of the higher order support. We propose higher-order language extensions for IDP-like specification languages and discuss what kind of solver support is needed. Native higher order shifts the burden of rewriting specifications using encoding techniques from the user to the solver itself.
J-Viz: Sibling-First Recursive Graph Drawing for Visualizing Java Bytecode
Venue: arXiv cs.DS 2016
Year: 2016

We describe a graph visualization tool for visualizing Java bytecode. Our tool, which we call J-Viz, visualizes connected directed graphs according to a canonical node ordering, which we call the sibling-first recursive (SFR) numbering. The particular graphs we consider are derived from applying Shiver's k-CFA framework to Java bytecode, and our visualizer includes helpful links between the nodes of an input graph and the Java bytecode that produced it, as well as a decompiled version of that Java bytecode. We show through several case studies that the canonical drawing paradigm used in J-Viz is effective for identifying potential security vulnerabilities and repeated use of the same code in Java applications.
Design and Implementation of A Network Security Management System
Venue: arXiv cs.CR 2016
Year: 2016

In recent years, the emerged network worms and attacks have distributive characteristic, which can spread globally in a very short time. Security management crossing network to co-defense network-wide attacks and improve efficiency of security administration is urgently needed. This paper proposes a hierarchical distributed network security management system (HD-NSMS), which can centrally manage security across networks. First describes the system in macrostructure and microstructure; then discusses three key problems when building HD-NSMS: device model, alert mechanism and emergency response mechanism; at last, describes the implementation of HD-NSMS. The paper is valuable for implementing NSMS in that it derives from a practical network security management system (NSMS).
A Continuous-Time Model of an Autonomous Aerial Vehicle to Inform and Validate Formal Verification Methods
Venue: arXiv cs.RO 2016
Year: 2016

If autonomous vehicles are to be widely accepted, we need to ensure their safe operation. For this reason, verification and validation (V&V) approaches must be developed that are suitable for this domain. Model checking is a formal technique which allows us to exhaustively explore the paths of an abstract model of a system. Using a probabilistic model checker such as PRISM, we may determine properties such as the expected time for a mission, or the probability that a specific mission failure occurs. However, model checking of complex systems is difficult due to the loss of information during abstraction. This is especially so when considering systems such as autonomous vehicles which are subject to external influences. An alternative solution is the use of Monte Carlo simulation to explore the results of a continuous-time model of the system. The main disadvantage of this approach is that the approach is not exhaustive as not all executions of the system are analysed. We are therefore interested in developing a framework for formal verification of autonomous vehicles, using Monte Carlo simulation to inform and validate our symbolic models during the initial stages of development. In this paper, we present a continuous-time model of a quadrotor unmanned aircraft undertaking an autonomous mission. We employ this model in Monte Carlo simulation to obtain specific mission properties which will inform the symbolic models employed in formal verification.
Segmentation Free Object Discovery in Video
Venue: arXiv cs.CV 2016
Year: 2016

In this paper we present a simple yet effective approach to extend without supervision any object proposal from static images to videos. Unlike previous methods, these spatio-temporal proposals, to which we refer as tracks, are generated relying on little or no visual content by only exploiting bounding boxes spatial correlations through time. The tracks that we obtain are likely to represent objects and are a general-purpose tool to represent meaningful video content for a wide variety of tasks. For unannotated videos, tracks can be used to discover content without any supervision. As further contribution we also propose a novel and dataset-independent method to evaluate a generic object proposal based on the entropy of a classifier output response. We experiment on two competitive datasets, namely YouTube Objects and ILSVRC-2015 VID.
Random-Training-Assisted Pilot Spoofing Detection and Secure Transmission
Venue: arXiv cs.CR 2016
Year: 2016

The pilot spoofing attack is considered as an active eavesdropping activity launched by an adversary during the reverse channel training phase. By transmitting the same pilot signal as the legitimate user, the pilot spoofing attack is able to degrade the quality of legitimate transmission and, more severely, facilitate eavesdropping. In an effort to detect the pilot spoofing attack and minimize its damages, in this paper we propose a novel random-training-assisted (RTA) pilot spoofing detection algorithm. In particular, we develop a new training mechanism by adding a random training phase after the conventional pilot training phase. By examining the difference of the estimated legitimate channels during these two phases, the pilot spoofing attack can be detected accurately. If no spoofing attack is detected, we present a computationally efficient channel estimation enhancement algorithm to further improve the channel estimation accuracy. If the existence of the pilot spoofing attack is identified, a zero-forcing (ZF)-based secure transmission scheme is proposed to protect the confidential information from the active eavesdropper. Extensive simulation results demonstrate that the proposed RTA scheme can achieve efficient pilot spoofing detection, accurate channel estimation, and secure transmission.
Retrofitting Applications with Provenance-Based Security Monitoring
Venue: arXiv cs.CR 2016
Year: 2016

Data provenance is a valuable tool for detecting and preventing cyber attack, providing insight into the nature of suspicious events. For example, an administrator can use provenance to identify the perpetrator of a data leak, track an attacker's actions following an intrusion, or even control the flow of outbound data within an organization. Unfortunately, providing relevant data provenance for complex, heterogenous software deployments is challenging, requiring both the tedious instrumentation of many application components as well as a unified architecture for aggregating information between components. In this work, we present a composition of techniques for bringing affordable and holistic provenance capabilities to complex application workflows, with particular consideration for the exemplar domain of web services. We present DAP, a transparent architecture for capturing detailed data provenance for web service components. Our approach leverages a key insight that minimal knowledge of open protocols can be leveraged to extract precise and efficient provenance information by interposing on application components' communications, granting DAP compatibility with existing web services without requiring instrumentation or developer cooperation. We show how our system can be used in real time to monitor system intrusions or detect data exfiltration attacks while imposing less than 5.1 ms end-to-end overhead on web requests. Through the introduction of a garbage collection optimization, DAP is able to monitor system activity without suffering from excessive storage overhead. DAP thus serves not only as a provenance-aware web framework, but as a case study in the non-invasive deployment of provenance capabilities for complex applications workflows.
QoS Provisioning with Adaptive Backoff Algorithm for IEEE 802.11ac Under Multipacket Reception
Venue: arXiv cs.NI 2016
Year: 2016

Recent advances in physical layer communication techniques, enable receivers to decode multiple simultaneous transmissions. This technique is known as the multipacket reception (MPR). In this paper, we propose an enhancement to the IEEE 802.11ac EDCA protocol for channels supporting MPR for QoS provisioning. We show that in the case of MPR, in addition to CWmin, CWmax and AIFSN, we can use two more parameters namely (i) threshold and (ii) counter decrement value, that can offer service differentiation. The performance evaluation of the different metrics of the proposed protocol (throughput, delay, and jitter) is carried out using extensive simulations.
On-Chip Mechanisms to Reduce Effective Memory Access Latency
Venue: arXiv cs.AR 2016
Year: 2016

This dissertation develops hardware that automatically reduces the effective latency of accessing memory in both single-core and multi-core systems. To accomplish this, the dissertation shows that all last level cache misses can be separated into two categories: dependent cache misses and independent cache misses. Independent cache misses have all of the source data that is required to generate the address of the memory access available on-chip, while dependent cache misses depend on data that is located off-chip. This dissertation proposes that dependent cache misses are accelerated by migrating the dependence chain that generates the address of the memory access to the memory controller for execution. Independent cache misses are accelerated using a new mode for runahead execution that only executes filtered dependence chains. With these mechanisms, this dissertation demonstrates a 62% increase in performance and a 19% decrease in effective memory access latency for a quad-core processor on a set of high memory intensity workloads.
Language Classes Associated with Automata Over Matrix Groups
Venue: arXiv cs.FL 2016
Year: 2016

We investigate the language classes recognized by group automata over matrix groups. We present a summary of the results obtained so far together with a number of new results. We look at the computational power of time-bounded group automata where the group under consideration has polynomial growth.
Citation Classification for Behavioral Analysis of a Scientific Field
Venue: arXiv cs.CL 2016
Year: 2016

Citations are an important indicator of the state of a scientific field, reflecting how authors frame their work, and influencing uptake by future scholars. However, our understanding of citation behavior has been limited to small-scale manual citation analysis. We perform the largest behavioral study of citations to date, analyzing how citations are both framed and taken up by scholars in one entire field: natural language processing. We introduce a new dataset of nearly 2,000 citations annotated for function and centrality, and use it to develop a state-of-the-art classifier and label the entire ACL Reference Corpus. We then study how citations are framed by authors and use both papers and online traces to track how citations are followed by readers. We demonstrate that authors are sensitive to discourse structure and publication venue when citing, that online readers follow temporal links to previous and future work rather than methodological links, and that how a paper cites related work is predictive of its citation count. Finally, we use changes in citation roles to show that the field of NLP is undergoing a significant increase in consensus.
Qualitative Framing of Financial Incentives - A Case of Emotion Annotation
Venue: arXiv cs.HC 2016
Year: 2016

Online labor platforms, such as the Amazon Mechanical Turk, provide an effective framework for eliciting responses to judgment tasks. Previous work has shown that workers respond best to financial incentives, especially to extra bonuses. However, most of the tested incentives involve describing the bonus conditions in formulas instead of plain English. We believe that different incentives given in English (or in qualitative framing) will result in differences in workers' performance, especially when task difficulties vary. In this paper, we report the preliminary results of a crowdsourcing experiment comparing workers' performance using only qualitative framings of financial incentives. Our results demonstrate a significant increase in workers' performance using a specific well-formulated qualitative framing inspired by the Peer Truth Serum. This positive effect is observed only when the difficulty of the task is high, while when the task is easy there is no difference of which incentives to use.
Network clustering and community detection using modulus of families of loops
Venue: arXiv cs.SI 2016
Year: 2016

We study the structure of loops in networks using the notion of modulus of loop families. We introduce a new measure of network clustering by quantifying the richness of families of (simple) loops. Modulus tries to minimize the expected overlap among loops by spreading the expected link-usage optimally. We propose weighting networks using these expected link-usages to improve classical community detection algorithms. We show that the proposed method enhances the performance of certain algorithms, such as spectral partitioning and modularity maximization heuristics, on standard benchmarks.