OpenRaiser/Intern-Atlas huggingface dataset:
Exploiting Anonymity in Approximate Linear Programming: Scaling to Large Multiagent MDPs (Extended Version)
Venue: arXiv cs.AI 2016
Year: 2016

Many exact and approximate solution methods for Markov Decision Processes (MDPs) attempt to exploit structure in the problem and are based on factorization of the value function. Especially multiagent settings, however, are known to suffer from an exponential increase in value component sizes as interactions become denser, meaning that approximation architectures are restricted in the problem sizes and types they can handle. We present an approach to mitigate this limitation for certain types of multiagent systems, exploiting a property that can be thought of as "anonymous influence" in the factored MDP. Anonymous influence summarizes joint variable effects efficiently whenever the explicit representation of variable identity in the problem can be avoided. We show how representational benefits from anonymity translate into computational efficiencies, both for general variable elimination in a factor graph but in particular also for the approximate linear programming solution to factored MDPs. The latter allows to scale linear programming to factored MDPs that were previously unsolvable. Our results are shown for the control of a stochastic disease process over a densely connected graph with 50 nodes and 25 agents.
Combinatorial Constructions of Optimal $(m, n,4,2)$ Optical Orthogonal Signature Pattern Codes
Venue: arXiv cs.DM 2016
Year: 2016

Optical orthogonal signature pattern codes (OOSPCs) play an important role in a novel type of optical code-division multiple-access (CDMA) network for 2-dimensional image transmission. There is a one-to-one correspondence between an $(m, n, w, λ)$-OOSPC and a $(λ+1)$-$(mn,w,1)$ packing design admitting an automorphism group isomorphic to $\mathbb{Z}_m\times \mathbb{Z}_n$. In 2010, Sawa gave the first infinite class of $(m, n, 4, 2)$-OOSPCs by using $S$-cyclic Steiner quadruple systems. In this paper, we use various combinatorial designs such as strictly $\mathbb{Z}_m\times \mathbb{Z}_n$-invariant $s$-fan designs, strictly $\mathbb{Z}_m\times \mathbb{Z}_n$-invariant $G$-designs and rotational Steiner quadruple systems to present some constructions for $(m, n, 4, 2)$-OOSPCs. As a consequence, our new constructions yield more infinite families of optimal $(m, n, 4, 2)$-OOSPCs. Especially, we shall see that in some cases an optimal $(m, n, 4, 2)$-OOSPC can not achieve the Johnson bound.
Approximating Optimal Bounds in Prompt-LTL Realizability in Doubly-exponential Time
Venue: arXiv cs.LO 2016
Year: 2016

We consider the optimization variant of the realizability problem for Prompt Linear Temporal Logic, an extension of Linear Temporal Logic (LTL) by the prompt eventually operator whose scope is bounded by some parameter. In the realizability optimization problem, one is interested in computing the minimal such bound that allows to realize a given specification. It is known that this problem is solvable in triply-exponential time, but not whether it can be done in doubly-exponential time, i.e., whether it is just as hard as solving LTL realizability. We take a step towards resolving this problem by showing that the optimum can be approximated within a factor of two in doubly-exponential time. Also, we report on a proof-of-concept implementation of the algorithm based on bounded LTL synthesis, which computes the smallest implementation of a given specification. In our experiments, we observe a tradeoff between the size of the implementation and the bound it realizes. We investigate this tradeoff in the general case and prove upper bounds, which reduce the search space for the algorithm, and matching lower bounds.
Entropies of weighted sums in cyclic groups and an application to polar codes
Venue: arXiv cs.IT 2016
Year: 2016

In this note, the following basic question is explored: in a cyclic group, how are the Shannon entropies of the sum and difference of i.i.d. random variables related to each other? For the integer group, we show that they can differ by any real number additively, but not too much multiplicatively; on the other hand, for $\mathbb{Z}/3\mathbb{Z}$, the entropy of the difference is always at least as large as that of the sum. These results are closely related to the study of more-sum-than-difference (i.e. MSTD) sets in additive combinatorics. We also investigate polar codes for $q$-ary input channels using non-canonical kernels to construct the generator matrix, and present applications of our results to constructing polar codes with significantly improved error probability compared to the canonical construction.
A Multi-Service Oriented Multiple-Access Scheme for Next-Generation Mobile Networks
Venue: arXiv cs.IT 2016
Year: 2016

One of the key requirements for fifth-generation (5G) cellular networks is their ability to handle densely connected devices with different quality of service (QoS) requirements. In this article, we present multi-service oriented multiple access (MOMA), an integrated access scheme for massive connections with diverse QoS profiles and/or traffic patterns originating from both handheld devices and machine-to-machine (M2M) transmissions. MOMA is based on a) stablishing separate classes of users based on relevant criteria that go beyond the simple handheld/M2M split, b) class dependent hierarchical spreading of the data signal and c) a mix of multiuser and single-user detection schemes at the receiver. Practical implementations of the MOMA principle are provided for base stations (BSs) that are equipped with a large number of antenna elements. Finally, it is shown that such a massive-multiple-input-multiple-output (MIMO) scenario enables the achievement of all the benefits of MOMA even with a simple receiver structure that allows to concentrate the receiver complexity where effectively needed.
On Constructing Secure and Hardware-Efficient Invertible Mappings
Venue: arXiv cs.CR 2016
Year: 2016

Our society becomes increasingly dependent on wireless communications. The tremendous growth in the number and type of wirelessly connected devices in a combination with the dropping cost for performing cyberattacks create new challenges for assuring security of services and applications provided by the next generation of wireless communication networks. The situation is complicated even further by the fact that many end-point Internet of Things (IoT) devices have very limited resources for implementing security functionality. This paper addresses one of the aspects of this important, many-faceted problem - the design of hardware-efficient cryptographic primitives suitable for the protection of resource-constrained IoT devices. We focus on cryptographic primitives based on the invertible mappings of type $\{0,1,\ldots,2^n-1\} \rightarrow \{0,1,\ldots,2^n-1\}$. In order to check if a given mapping is invertible or not, we generally need an exponential in $n$ number of steps. In this paper, we derive a sufficient condition for invertibility which can be checked in $O(n^2 N)$ time, where $N$ is the size of representation of the largest function in the mapping. Our results can be used for constructing cryptographically secure invertible mappings which can be efficiently implemented in hardware.
Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions
Venue: arXiv cs.CG 2016
Year: 2016

Given $n$ non-vertical lines in 3-space, their vertical depth (above/below) relation can contain cycles. We show that the lines can be cut into $O(n^{3/2}\mathop{\mathrm{polylog}} n)$ pieces, such that the depth relation among these pieces is now a proper partial order. This bound is nearly tight in the worst case. Previous results on this topic could only handle restricted cases of the problem (such as handling only triangular cycles, by Aronov, Koltun, and Sharir (2005), or only cycles in grid-like patterns, by Chazelle et al. (1992)), and the bounds were considerably weaker---much closer to the trivial quadratic bound. Our proof uses a recent variant of the polynomial partitioning technique, due to Guth, and some simple tools from algebraic geometry. It is much more straightforward than the previous "purely combinatorial" methods. Our technique can be extended to eliminating all cycles in the depth relation among segments, and among constant-degree algebraic arcs. We hope that a suitable extension of this technique could be used to handle the much more difficult case of pairwise-disjoint triangles. We also discuss several algorithms for constructing a small set of cuts so as to eliminate all depth-relation cycles among the lines (minimizing such a set, for the case of line segments, is known to be NP-complete). The performance of these algorithms improves due to our new bound, but, so far, none of them both (a) produce close to $n^{3/2}$ cuts, and (b) run in time close to $n^{3/2}$, in the worst case. Our results almost completely settle a 35-year-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics.
Hitting Set for hypergraphs of low VC-dimension
Venue: arXiv cs.DS 2016
Year: 2016

We study the complexity of the Hitting Set problem in set systems (hypergraphs) that avoid certain sub-structures. In particular, we characterize the classical and parameterized complexity of the problem when the Vapnik-Chervonenkis dimension (VC-dimension) of the input is small. VC-dimension is a natural measure of complexity of set systems. Several tractable instances of Hitting Set with a geometric or graph-theoretical flavor are known to have low VC-dimension. In set systems of bounded VC-dimension, Hitting Set is known to admit efficient and almost optimal approximation algorithms (Brönnimann and Goodrich, 1995; Even, Rawitz, and Shahar, 2005; Agarwal and Pan, 2014). In contrast to these approximation-results, a low VC-dimension does not necessarily imply tractability in the parameterized sense. In fact, we show that Hitting Set is W[1]-hard already on inputs with VC-dimension 2, even if the VC-dimension of the dual set system is also 2. Thus, Hitting Set is very unlikely to be fixed-parameter tractable even in this arguably simple case. This answers an open question raised by King in 2010. For set systems whose (primal or dual) VC-dimension is 1, we show that Hitting Set is solvable in polynomial time. To bridge the gap in complexity between the classes of inputs with VC-dimension 1 and 2, we use a measure that is more fine-grained than VC-dimension. In terms of this measure, we identify a sharp threshold where the complexity of Hitting Set transitions from polynomial-time-solvable to NP-hard. The tractable class that lies just under the threshold is a generalization of Edge Cover, and thus extends the domain of polynomial-time tractability of Hitting Set.
Random Access Protocol for Massive MIMO: Strongest-User Collision Resolution (SUCR)
Venue: arXiv cs.IT 2016
Year: 2016

Wireless networks with many antennas at the base stations and multiplexing of many users, known as Massive MIMO systems, are key to handle the rapid growth of data traffic. As the number of users increases, the random access in contemporary networks will be flooded by user collisions. In this paper, we propose a reengineered random access protocol, coined strongest-user collision resolution (SUCR). It exploits the channel hardening feature of Massive MIMO channels to enable each user to detect collisions, determine how strong the contenders' channels are, and only keep transmitting if it has the strongest channel gain. The proposed SUCR protocol can quickly and distributively resolve the vast majority of all pilot collisions.
Toward an Efficient Website Fingerprinting Defense
Venue: arXiv cs.CR 2016
Year: 2016

Website Fingerprinting attacks enable a passive eavesdropper to recover the user's otherwise anonymized web browsing activity by matching the observed traffic with prerecorded web traffic templates. The defenses that have been proposed to counter these attacks are impractical for deployment in real-world systems due to their high cost in terms of added delay and bandwidth overhead. Further, these defenses have been designed to counter attacks that, despite their high success rates, have been criticized for assuming unrealistic attack conditions in the evaluation setting. In this paper, we propose a novel, lightweight defense based on Adaptive Padding that provides a sufficient level of security against website fingerprinting, particularly in realistic evaluation conditions. In a closed-world setting, this defense reduces the accuracy of the state-of-the-art attack from 91% to 20%, while introducing zero latency overhead and less than 60% bandwidth overhead. In an open-world, the attack precision is just 1% and drops further as the number of sites grows.
Benchmarking sentiment analysis methods for large-scale texts: A case for using continuum-scored words and word shift graphs
Venue: arXiv cs.CL 2016
Year: 2016

The emergence and global adoption of social media has rendered possible the real-time estimation of population-scale sentiment, bearing profound implications for our understanding of human behavior. Given the growing assortment of sentiment measuring instruments, comparisons between them are evidently required. Here, we perform detailed tests of 6 dictionary-based methods applied to 4 different corpora, and briefly examine a further 20 methods. We show that a dictionary-based method will only perform both reliably and meaningfully if (1) the dictionary covers a sufficiently large enough portion of a given text's lexicon when weighted by word usage frequency; and (2) words are scored on a continuous scale.
Reachable Set Approach to Collision Avoidance for UAVs
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, we propose a reachable set based collision avoidance algorithm for unmanned aerial vehicles (UAVs). UAVs have been deployed for agriculture research and management, surveillance and sensor coverage for threat detection and disaster search and rescue operations. It is essential for the aircraft to have on-board collision avoidance capability to guarantee safety. Instead of the traditional approach of collision avoidance between trajectories, we propose a collision avoidance scheme based on reachable sets and tubes. We then formulate the problem as a convex optimization problem seeking suitable control constraint sets for participating aircraft. We have applied the approach on a case study of two quadrotors and two fix-wing aircraft collision avoidance scenario.
Pruning Algorithms for Pretropisms of Newton Polytopes
Venue: arXiv cs.CG 2016
Year: 2016

Pretropisms are candidates for the leading exponents of Puiseux series that represent solutions of polynomial systems. To find pretropisms, we propose an exact gift wrapping algorithm to prune the tree of edges of a tuple of Newton polytopes. We prefer exact arithmetic not only because of the exact input and the degrees of the output, but because of the often unpredictable growth of the coordinates in the face normals, even for polytopes in generic position. We provide experimental results with our preliminary implementation in Sage that compare favorably with the pruning method that relies only on cone intersections.
The Evolution of Wikipedia's Norm Network
Venue: arXiv cs.SI 2016
Year: 2016

Social norms have traditionally been difficult to quantify. In any particular society, their sheer number and complex interdependencies often limit a system-level analysis. One exception is that of the network of norms that sustain the online Wikipedia community. We study the fifteen-year evolution of this network using the interconnected set of pages that establish, describe, and interpret the community's norms. Despite Wikipedia's reputation for \textit{ad hoc} governance, we find that its normative evolution is highly conservative. The earliest users create norms that both dominate the network and persist over time. These core norms govern both content and interpersonal interactions using abstract principles such as neutrality, verifiability, and assume good faith. As the network grows, norm neighborhoods decouple topologically from each other, while increasing in semantic coherence. Taken together, these results suggest that the evolution of Wikipedia's norm network is akin to bureaucratic systems that predate the information age.
Partial permutation decoding for binary linear and Z4-linear Hadamard codes
Venue: arXiv cs.IT 2016
Year: 2016

Permutation decoding is a technique which involves finding a subset $S$, called PD-set, of the permutation automorphism group of a code $C$ in order to assist in decoding. An explicit construction of $\left \lfloor{\frac{2^m-m-1}{1+m}} \right \rfloor$-PD-sets of minimum size $\left \lfloor{\frac{2^m-m-1}{1+m}} \right \rfloor + 1$ for partial permutation decoding for binary linear Hadamard codes $H_m$ of length $2^m$, for all $m\geq 4$, is described. Moreover, a recursive construction to obtain $s$-PD-sets of size $l$ for $H_{m+1}$ of length $2^{m+1}$, from a given $s$-PD-set of the same size for $H_m$, is also established. These results are generalized to find $s$-PD-sets for (nonlinear) binary Hadamard codes of length $2^m$, called $\mathbb{Z}_4$-linear Hadamard codes, which are obtained as the Gray map image of quaternary linear codes of length $2^{m-1}$.
Fast extraction of the backbone of projected bipartite networks to aid community detection
Venue: arXiv cs.SI 2016
Year: 2016

This paper introduces a computationally inexpensive method of extracting the backbone of one-mode networks projected from bipartite networks. We show that the edge weights in the one-mode projections are distributed according to a Poisson binomial distribution and that finding the expected weight distribution of a one-mode network projected from a random bipartite network only requires knowledge of the bipartite degree distributions. Being able to extract the backbone of a projection is highly beneficial in filtering out redundant information in large complex networks and narrowing down the information in the one-mode projection to the most relevant. We demonstrate that the backbone of a one-mode projection aids in the detection of communities.
How to Discount Deep Reinforcement Learning: Towards New Dynamic Strategies
Venue: arXiv cs.LG 2016
Year: 2016

Using deep neural nets as function approximator for reinforcement learning tasks have recently been shown to be very powerful for solving problems approaching real-world complexity. Using these results as a benchmark, we discuss the role that the discount factor may play in the quality of the learning process of a deep Q-network (DQN). When the discount factor progressively increases up to its final value, we empirically show that it is possible to significantly reduce the number of learning steps. When used in conjunction with a varying learning rate, we empirically show that it outperforms original DQN on several experiments. We relate this phenomenon with the instabilities of neural networks when they are used in an approximate Dynamic Programming setting. We also describe the possibility to fall within a local optimum during the learning process, thus connecting our discussion with the exploration/exploitation dilemma.
Vertex-Coloring with Star-Defects
Venue: arXiv cs.DS 2016
Year: 2016

Defective coloring is a variant of traditional vertex-coloring, according to which adjacent vertices are allowed to have the same color, as long as the monochromatic components induced by the corresponding edges have a certain structure. Due to its important applications, as for example in the bipartisation of graphs, this type of coloring has been extensively studied, mainly with respect to the size, degree, and acyclicity of the monochromatic components. In this paper we focus on defective colorings in which the monochromatic components are acyclic and have small diameter, namely, they form stars. For outerplanar graphs, we give a linear-time algorithm to decide if such a defective coloring exists with two colors and, in the positive case, to construct one. Also, we prove that an outerpath (i.e., an outerplanar graph whose weak-dual is a path) always admits such a two-coloring. Finally, we present NP-completeness results for non-planar and planar graphs of bounded degree for the cases of two and three colors.
Computing Affine Combinations, Distances, and Correlations for Recursive Partition Functions
Venue: arXiv cs.DS 2016
Year: 2016

Recursive partitioning is the core of several statistical methods including CART, random forest, and boosted trees. Despite the popularity of tree based methods, to date, there did not exist methods for combining multiple trees into a single tree, or methods for systematically quantifying the discrepancy between two trees. Taking advantage of the recursive structure in trees we formulated fast algorithms for computing affine combinations, distances and correlations in a vector subspace of recursive partition functions.
On the Linear Complexity of Generalized Cyclotomic Quaternary Sequences with Length $2pq$
Venue: arXiv cs.CR 2016
Year: 2016

In this paper, the linear complexity over $\mathbf{GF}(r)$ of generalized cyclotomic quaternary sequences with period $2pq$ is determined, where $ r $ is an odd prime such that $r \ge 5$ and $r\notin \lbrace p,q\rbrace$. The minimal value of the linear complexity is equal to $\tfrac{5pq+p+q+1}{4}$ which is greater than the half of the period $2pq$. According to the Berlekamp-Massey algorithm, these sequences are viewed as enough good for the use in cryptography. We show also that if the character of the extension field $\mathbf{GF}(r^{m})$, $r$, is chosen so that $\bigl(\tfrac{r}{p}\bigr) = \bigl(\tfrac{r}{q}\bigr) = -1$, $r\nmid 3pq-1$, and $r\nmid 2pq-4$, then the linear complexity can reach the maximal value equal to the length of the sequences.
A Probabilistic Algorithm for Computing Data-Discriminants of Likelihood Equations
Venue: arXiv cs.SC 2016
Year: 2016

An algebraic approach to the maximum likelihood estimation problem is to solve a very structured parameterized polynomial system called likelihood equations that have finitely many complex (real or non-real) solutions. The only solutions that are statistically meaningful are the real solutions with positive coordinates. In order to classify the parameters (data) according to the number of real/positive solutions, we study how to efficiently compute the discriminants, say data-discriminants (DD), of the likelihood equations. We develop a probabilistic algorithm with three different strategies for computing DDs. Our implemented probabilistic algorithm based on Maple and FGb is more efficient than our previous version presented in ISSAC2015, and is also more efficient than the standard elimination for larger benchmarks. By applying RAGlib to a DD we compute, we give the real root classification of 3 by 3 symmetric matrix model.
Cross-dimensional Weighting for Aggregated Deep Convolutional Features
Venue: arXiv cs.CV 2016
Year: 2016

We propose a simple and straightforward way of creating powerful image representations via cross-dimensional weighting and aggregation of deep convolutional neural network layer outputs. We first present a generalized framework that encompasses a broad family of approaches and includes cross-dimensional pooling and weighting steps. We then propose specific non-parametric schemes for both spatial- and channel-wise weighting that boost the effect of highly active spatial responses and at the same time regulate burstiness effects. We experiment on different public datasets for image search and show that our approach outperforms the current state-of-the-art for approaches based on pre-trained networks. We also provide an easy-to-use, open source implementation that reproduces our results.