OpenRaiser/Intern-Atlas huggingface dataset:
Cryptographic Enforcement of Information Flow Policies without Public Information via Tree Partitions
Venue: arXiv cs.CR 2016
Year: 2016

We may enforce an information flow policy by encrypting a protected resource and ensuring that only users authorized by the policy are able to decrypt the resource. In most schemes in the literature that use symmetric cryptographic primitives, each user is assigned a single secret and derives decryption keys using this secret and publicly available information. Recent work has challenged this approach by developing schemes, based on a chain partition of the information flow policy, that do not require public information for key derivation, the trade-off being that a user may need to be assigned more than one secret. In general, many different chain partitions exist for the same policy and, until now, it was not known how to compute an appropriate one. In this paper, we introduce the notion of a tree partition, of which chain partitions are a special case. We show how a tree partition may be used to define a cryptographic enforcement scheme and prove that such schemes can be instantiated in such a way as to preserve the strongest security properties known for cryptographic enforcement schemes. We establish a number of results linking the amount of secret material that needs to be distributed to users with a weighted acyclic graph derived from the tree partition. These results enable us to develop efficient algorithms for deriving tree and chain partitions that minimize the amount of secret material that needs to be distributed.
Simultaneous Orthogonal Planarity
Venue: arXiv cs.CG 2016
Year: 2016

We introduce and study the $\textit{OrthoSEFE}-k$ problem: Given $k$ planar graphs each with maximum degree 4 and the same vertex set, do they admit an OrthoSEFE, that is, is there an assignment of the vertices to grid points and of the edges to paths on the grid such that the same edges in distinct graphs are assigned the same path and such that the assignment induces a planar orthogonal drawing of each of the $k$ graphs? We show that the problem is NP-complete for $k \geq 3$ even if the shared graph is a Hamiltonian cycle and has sunflower intersection and for $k \geq 2$ even if the shared graph consists of a cycle and of isolated vertices. Whereas the problem is polynomial-time solvable for $k=2$ when the union graph has maximum degree five and the shared graph is biconnected. Further, when the shared graph is biconnected and has sunflower intersection, we show that every positive instance has an OrthoSEFE with at most three bends per edge.
A Compression-Complexity Measure of Integrated Information
Venue: arXiv cs.IT 2016
Year: 2016

Quantifying integrated information is a leading approach towards building a fundamental theory of consciousness. Integrated Information Theory (IIT) has gained attention in this regard due to its theoretically strong framework. However, it faces some limitations such as current state dependence, computationally expensive and inability to be applied to real brain data. On the other hand, Perturbational Complexity Index (PCI) is a clinical measure for distinguishing different levels of consciousness. Though PCI claims to capture the functional differentiation and integration in brain networks (similar to IIT), its link to integrated information theories is rather weak. Inspired by these two approaches, we propose a new measure - $Φ^C$ using a novel compression-complexity perspective that serves as a bridge between the two, for the first time. $Φ^C$ is founded on the principles of lossless data compression based complexity measures which characterize the dynamical complexity of brain networks. $Φ^{C}$ exhibits following salient innovations: (i) mathematically well bounded, (ii) negligible current state dependence unlike $Φ$, (iii) integrated information measured as compression-complexity rather than as an infotheoretic quantity, and (iv) faster to compute since number of atomic bipartitions scales linearly with the number of nodes of the network, thus avoiding combinatorial explosion. Our computer simulations show that $Φ^C$ has similar hierarchy to $<Φ>$ for several multiple-node networks and it demonstrates a rich interplay between differentiation, integration and entropy of the nodes of a network. $Φ^C$ is a promising heuristic measure to characterize the quantity of integrated information (and hence a measure of quantity of consciousness) in larger networks like human brain and provides an opportunity to test the predictions of brain complexity on real neural data.
Language Detection For Short Text Messages In Social Media
Venue: arXiv cs.CL 2016
Year: 2016

With the constant growth of the World Wide Web and the number of documents in different languages accordingly, the need for reliable language detection tools has increased as well. Platforms such as Twitter with predominantly short texts are becoming important information resources, which additionally imposes the need for short texts language detection algorithms. In this paper, we show how incorporating personalized user-specific information into the language detection algorithm leads to an important improvement of detection results. To choose the best algorithm for language detection for short text messages, we investigate several machine learning approaches. These approaches include the use of the well-known classifiers such as SVM and logistic regression, a dictionary based approach, and a probabilistic model based on modified Kneser-Ney smoothing. Furthermore, the extension of the probabilistic model to include additional user-specific information such as evidence accumulation per user and user interface language is explored, with the goal of improving the classification performance. The proposed approaches are evaluated on randomly collected Twitter data containing Latin as well as non-Latin alphabet languages and the quality of the obtained results is compared, followed by the selection of the best performing algorithm. This algorithm is then evaluated against two already existing general language detection tools: Chromium Compact Language Detector 2 (CLD2) and langid, where our method significantly outperforms the results achieved by both of the mentioned methods. Additionally, a preview of benefits and possible applications of having a reliable language detection algorithm is given.
Low Ply Drawings of Trees
Venue: arXiv cs.DS 2016
Year: 2016

We consider the recently introduced model of \emph{low ply graph drawing}, in which the ply-disks of the vertices do not have many common overlaps, which results in a good distribution of the vertices in the plane. The \emph{ply-disk} of a vertex in a straight-line drawing is the disk centered at it whose radius is half the length of its longest incident edge. The largest number of ply-disks having a common overlap is called the \emph{ply-number} of the drawing. We focus on trees. We first consider drawings of trees with constant ply-number, proving that they may require exponential area, even for stars, and that they may not even exist for bounded-degree trees. Then, we turn our attention to drawings with logarithmic ply-number and show that trees with maximum degree $6$ always admit such drawings in polynomial area.
What makes ImageNet good for transfer learning?
Venue: arXiv cs.CV 2016
Year: 2016

The tremendous success of ImageNet-trained deep features on a wide range of transfer tasks begs the question: what are the properties of the ImageNet dataset that are critical for learning good, general-purpose features? This work provides an empirical investigation of various facets of this question: Is more pre-training data always better? How does feature quality depend on the number of training examples per class? Does adding more object classes improve performance? For the same data budget, how should the data be split into classes? Is fine-grained recognition necessary for learning good features? Given the same number of training classes, is it better to have coarse classes or fine-grained classes? Which is better: more classes or more examples per class? To answer these and related questions, we pre-trained CNN features on various subsets of the ImageNet dataset and evaluated transfer performance on PASCAL detection, PASCAL action classification, and SUN scene classification tasks. Our overall findings suggest that most changes in the choice of pre-training data long thought to be critical do not significantly affect transfer performance.? Given the same number of training classes, is it better to have coarse classes or fine-grained classes? Which is better: more classes or more examples per class?
A Colored Petri Net Model of Simulation for Performance Evaluation for IEEE 802.22 based Network
Venue: arXiv cs.NI 2016
Year: 2016

Cognitive Radio is a new concept that allows radio devices access to licensed bands since they do not cause harmful interferences to systems that hold the license of use. The main motivation for the increase of research on Cognitive Radio is the scarcity of non-licensed bands due to the large employment of wireless networks on cities. In this paper, we describe a Cognitive Radio Model of Simulation designed through the Colored Petri Net Formalism. This represents an effort to deliver to scientific community a model of simulation that is easily extensible and graphically validated. Through comparison with literature, we have demonstrated that this model is not invalid.
A Dictionary-based Approach to Racism Detection in Dutch Social Media
Venue: arXiv cs.CL 2016
Year: 2016

We present a dictionary-based approach to racism detection in Dutch social media comments, which were retrieved from two public Belgian social media sites likely to attract racist reactions. These comments were labeled as racist or non-racist by multiple annotators. For our approach, three discourse dictionaries were created: first, we created a dictionary by retrieving possibly racist and more neutral terms from the training data, and then augmenting these with more general words to remove some bias. A second dictionary was created through automatic expansion using a \texttt{word2vec} model trained on a large corpus of general Dutch text. Finally, a third dictionary was created by manually filtering out incorrect expansions. We trained multiple Support Vector Machines, using the distribution of words over the different categories in the dictionaries as features. The best-performing model used the manually cleaned dictionary and obtained an F-score of 0.46 for the racist class on a test set consisting of unseen Dutch comments, retrieved from the same sites used for the training set. The automated expansion of the dictionary only slightly boosted the model's performance, and this increase in performance was not statistically significant. The fact that the coverage of the expanded dictionaries did increase indicates that the words that were automatically added did occur in the corpus, but were not able to meaningfully impact performance. The dictionaries, code, and the procedure for requesting the corpus are available at: https://github.com/clips/hades
hi-RF: Incremental Learning Random Forest for large-scale multi-class Data Classification
Venue: arXiv cs.LG 2016
Year: 2016

In recent years, dynamically growing data and incrementally growing number of classes pose new challenges to large-scale data classification research. Most traditional methods struggle to balance the precision and computational burden when data and its number of classes increased. However, some methods are with weak precision, and the others are time-consuming. In this paper, we propose an incremental learning method, namely, heterogeneous incremental Nearest Class Mean Random Forest (hi-RF), to handle this issue. It is a heterogeneous method that either replaces trees or updates trees leaves in the random forest adaptively, to reduce the computational time in comparable performance, when data of new classes arrive. Specifically, to keep the accuracy, one proportion of trees are replaced by new NCM decision trees; to reduce the computational load, the rest trees are updated their leaves probabilities only. Most of all, out-of-bag estimation and out-of-bag boosting are proposed to balance the accuracy and the computational efficiency. Fair experiments were conducted and demonstrated its comparable precision with much less computational time.
Training Deep Spiking Neural Networks using Backpropagation
Venue: arXiv cs.NE 2016
Year: 2016

Deep spiking neural networks (SNNs) hold great potential for improving the latency and energy efficiency of deep neural networks through event-based computation. However, training such networks is difficult due to the non-differentiable nature of asynchronous spike events. In this paper, we introduce a novel technique, which treats the membrane potentials of spiking neurons as differentiable signals, where discontinuities at spike times are only considered as noise. This enables an error backpropagation mechanism for deep SNNs, which works directly on spike signals and membrane potentials. Thus, compared with previous methods relying on indirect training and conversion, our technique has the potential to capture the statics of spikes more precisely. Our novel framework outperforms all previously reported results for SNNs on the permutation invariant MNIST benchmark, as well as the N-MNIST benchmark recorded with event-based vision sensors.
Monotone Simultaneous Embeddings of Paths in R^d
Venue: arXiv cs.CG 2016
Year: 2016

We study the following problem: Given $k$ paths that share the same vertex set, is there a simultaneous geometric embedding of these paths such that each individual drawing is monotone in some direction? We prove that for any dimension $d \geq 2$, there is a set of $d+1$ paths that does not admit a monotone simultaneous geometric embedding.
Snapping Graph Drawings to the Grid Optimally
Venue: arXiv cs.CG 2016
Year: 2016

In geographic information systems and in the production of digital maps for small devices with restricted computational resources one often wants to round coordinates to a rougher grid. This removes unnecessary detail and reduces space consumption as well as computation time. This process is called snapping to the grid and has been investigated thoroughly from a computational-geometry perspective. In this paper we investigate the same problem for given drawings of planar graphs under the restriction that their combinatorial embedding must be kept and edges are drawn straight-line. We show that the problem is NP-hard for several objectives and provide an integer linear programming formulation. Given a plane graph G and a positive integer w, our ILP can also be used to draw G straight-line on a grid of width w and minimum height (if possible).
Efficient Two-Stream Motion and Appearance 3D CNNs for Video Classification
Venue: arXiv cs.CV 2016
Year: 2016

The video and action classification have extremely evolved by deep neural networks specially with two stream CNN using RGB and optical flow as inputs and they present outstanding performance in terms of video analysis. One of the shortcoming of these methods is handling motion information extraction which is done out side of the CNNs and relatively time consuming also on GPUs. So proposing end-to-end methods which are exploring to learn motion representation, like 3D-CNN can achieve faster and accurate performance. We present some novel deep CNNs using 3D architecture to model actions and motion representation in an efficient way to be accurate and also as fast as real-time. Our new networks learn distinctive models to combine deep motion features into appearance model via learning optical flow features inside the network.
Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition
Venue: arXiv cs.CG 2016
Year: 2016

A geometric graph is angle-monotone if every pair of vertices has a path between them that---after some rotation---is $x$- and $y$-monotone. Angle-monotone graphs are $\sqrt 2$-spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone---specifically, we prove that the half-$θ_6$-graph is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex $s$ to any vertex $t$ whose length is within $1 + \sqrt 2$ times the Euclidean distance from $s$ to $t$. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations.
A Sparse Stress Model
Venue: arXiv cs.CG 2016
Year: 2016

Force-directed layout methods constitute the most common approach to draw general graphs. Among them, stress minimization produces layouts of comparatively high quality but also imposes comparatively high computational demands. We propose a speed-up method based on the aggregation of terms in the objective function. It is akin to aggregate repulsion from far-away nodes during spring embedding but transfers the idea from the layout space into a preprocessing phase. An initial experimental study informs a method to select representatives, and subsequent more extensive experiments indicate that our method yields better approximations of minimum-stress layouts in less time than related methods.
Noisy Channel-Output Feedback Capacity of the Linear Deterministic Interference Channel
Venue: arXiv cs.IT 2016
Year: 2016

In this technical report, the capacity region of the two-user linear deterministic (LD) interference channel with noisy output feedback (IC-NOF) is fully characterized. This result allows the identification of several asymmetric scenarios in which implementing channel-output feedback in only one of the transmitter-receiver pairs is as beneficial as implementing it in both links, in terms of achievable individual rate and sum-rate improvements w.r.t. the case without feedback. In other scenarios, the use of channel-output feedback in any of the transmitter-receiver pairs benefits only one of the two pairs in terms of achievable individual rate improvements or simply, it turns out to be useless, i.e., the capacity regions with and without feedback turn out to be identical even in the full absence of noise in the feedback links.
Evaluation of two interaction techniques for visualization of dynamic graphs
Venue: arXiv cs.HC 2016
Year: 2016

Several techniques for visualization of dynamic graphs are based on different spatial arrangements of a temporal sequence of node-link diagrams. Many studies in the literature have investigated the importance of maintaining the user's mental map across this temporal sequence, but usually each layout is considered as a static graph drawing and the effect of user interaction is disregarded. We conducted a task-based controlled experiment to assess the effectiveness of two basic interaction techniques: the adjustment of the layout stability and the highlighting of adjacent nodes and edges. We found that generally both interaction techniques increase accuracy, sometimes at the cost of longer completion times, and that the highlighting outclasses the stability adjustment for many tasks except the most complex ones.
Axiomatization of if-then-else over possibly non-halting programs and tests
Venue: arXiv cs.LO 2016
Year: 2016

In order to study the axiomatization of the if-then-else construct over possibly non-halting programs and tests, this paper introduces the notion of $C$-sets by considering the tests from an abstract $C$-algebra. When the $C$-algebra is an ada, the axiomatization is shown to be complete by obtaining a subdirect representation of $C$-sets. Further, this paper considers the equality test with the if-then-else construct and gives a complete axiomatization through the notion of agreeable $C$-sets.
From Community Detection to Community Deception
Venue: arXiv cs.SI 2016
Year: 2016

The community deception problem is about how to hide a target community C from community detection algorithms. The need for deception emerges whenever a group of entities (e.g., activists, police enforcements) want to cooperate while concealing their existence as a community. In this paper we introduce and formalize the community deception problem. To solve this problem, we describe algorithms that carefully rewire the connections of C's members. We experimentally show how several existing community detection algorithms can be deceived, and quantify the level of deception by introducing a deception score. We believe that our study is intriguing since, while showing how deception can be realized it raises awareness for the design of novel detection algorithms robust to deception techniques.
Designing a semantic model for a wide-spectrum language with concurrency
Venue: arXiv cs.LO 2016
Year: 2016

A wide-spectrum language integrates specification constructs into a programming language in a manner that treats a specification command just like any other command. This paper investigates a semantic model for a wide-spectrum language that supports concurrency and a refinement calculus. In order to handle specifications with rely and guarantee conditions, the model includes explicit environment steps as well as program steps. A novelty of our approach is that we define a set of primitive commands and operators, from which more complex specification and programming language commands are built. The primitives have simple algebraic properties which support proof using algebraic reasoning. The model is general enough to specify notions as diverse as rely-guarantee reasoning, temporal logic, and progress properties of programs, and supports refining specifications to code. It also forms an instance of an abstract concurrent program algebra, which facilitates reasoning about properties of the model at a high level of abstraction.
Testing $k$-Monotonicity
Venue: arXiv cs.DS 2016
Year: 2016

A Boolean $k$-monotone function defined over a finite poset domain ${\cal D}$ alternates between the values $0$ and $1$ at most $k$ times on any ascending chain in ${\cal D}$. Therefore, $k$-monotone functions are natural generalizations of the classical monotone functions, which are the $1$-monotone functions. Motivated by the recent interest in $k$-monotone functions in the context of circuit complexity and learning theory, and by the central role that monotonicity testing plays in the context of property testing, we initiate a systematic study of $k$-monotone functions, in the property testing model. In this model, the goal is to distinguish functions that are $k$-monotone (or are close to being $k$-monotone) from functions that are far from being $k$-monotone. Our results include the following: - We demonstrate a separation between testing $k$-monotonicity and testing monotonicity, on the hypercube domain $\{0,1\}^d$, for $k\geq 3$; - We demonstrate a separation between testing and learning on $\{0,1\}^d$, for $k=ω(\log d)$: testing $k$-monotonicity can be performed with $2^{O(\sqrt d \cdot \log d\cdot \log{1/\varepsilon})}$ queries, while learning $k$-monotone functions requires $2^{Ω(k\cdot \sqrt d\cdot{1/\varepsilon})}$ queries (Blais et al. (RANDOM 2015)). - We present a tolerant test for functions $f\colon[n]^d\to \{0,1\}$ with complexity independent of $n$, which makes progress on a problem left open by Berman et al. (STOC 2014). Our techniques exploit the testing-by-learning paradigm, use novel applications of Fourier analysis on the grid $[n]^d$, and draw connections to distribution testing techniques.