OpenRaiser/Intern-Atlas huggingface dataset:
Hybrid Centralized-Distributed Resource Allocation for Device-to-Device Communication Underlaying Cellular Networks
Venue: arXiv cs.GT 2015
Year: 2015

The basic idea of device-to-device (D2D) communication is that pairs of suitably selected wireless devices reuse the cellular spectrum to establish direct communication links, provided that the adverse effects of D2D communication on cellular users is minimized and cellular users are given a higher priority in using limited wireless resources. Despite its great potential in terms of coverage and capacity performance, implementing this new concept poses some challenges, in particular with respect to radio resource management. The main challenges arise from a strong need for distributed D2D solutions that operate in the absence of precise channel and network knowledge. In order to address this challenge, this paper studies a resource allocation problem in a single-cell wireless network with multiple D2D users sharing the available radio frequency channels with cellular users. We consider a realistic scenario where the base station (BS) is provided with strictly limited channel knowledge while D2D and cellular users have no information. We prove a lower-bound for the cellular aggregate utility in the downlink with fixed BS power, which allows for decoupling the channel allocation and D2D power control problems. An efficient graph-theoretical approach is proposed to perform the channel allocation, which offers flexibility with respect to allocation criterion (aggregate utility maximization, fairness, quality of service guarantee). We model the power control problem as a multi-agent learning game. We show that the game is an exact potential game with noisy rewards, defined on a discrete strategy set, and characterize the set of Nash equilibria. Q-learning better-reply dynamics is then used to achieve equilibrium.
The MSO+U theory of (N, <) is undecidable
Venue: arXiv cs.LO 2015
Year: 2015

We consider the logic MSO+U, which is monadic second-order logic extended with the unbounding quantifier. The unbounding quantifier is used to say that a property of finite sets holds for sets of arbitrarily large size. We prove that the logic is undecidable on infinite words, i.e. the MSO+U theory of (N,<) is undecidable. This settles an open problem about the logic, and improves a previous undecidability result, which used infinite trees and additional axioms from set theory.
Deep Transform: Error Correction via Probabilistic Re-Synthesis
Venue: arXiv cs.LG 2015
Year: 2015

Errors in data are usually unwelcome and so some means to correct them is useful. However, it is difficult to define, detect or correct errors in an unsupervised way. Here, we train a deep neural network to re-synthesize its inputs at its output layer for a given class of data. We then exploit the fact that this abstract transformation, which we call a deep transform (DT), inherently rejects information (errors) existing outside of the abstract feature space. Using the DT to perform probabilistic re-synthesis, we demonstrate the recovery of data that has been subject to extreme degradation.
Beyond the Runs Theorem
Venue: arXiv cs.FL 2015
Year: 2015

Recently, a short and elegant proof was presented showing that a binary word of length $n$ contains at most $n-3$ runs. Here we show, using the same technique and a computer search, that the number of runs in a binary word of length $n$ is at most $\frac{22}{23}n<0.957n$.
Optimizations for Decision Making and Planning in Description Logic Dynamic Knowledge Bases
Venue: arXiv cs.AI 2015
Year: 2015

Artifact-centric models for business processes recently raised a lot of attention, as they manage to combine structural (i.e. data related) with dynamical (i.e. process related) aspects in a seamless way. Many frameworks developed under this approach, although, are not built explicitly for planning, one of the most prominent operations related to business processes. In this paper, we try to overcome this by proposing a framework named Dynamic Knowledge Bases, aimed at describing rich business domains through Description Logic-based ontologies, and where a set of actions allows the system to evolve by modifying such ontologies. This framework, by offering action rewriting and knowledge partialization, represents a viable and formal environment to develop decision making and planning techniques for DL-based artifact-centric business domains.
Optimal Scanning Bandwidth Strategy Incorporating Uncertainty about Adversary's Characteristics
Venue: arXiv cs.GT 2015
Year: 2015

In this paper we investigate the problem of designing a spectrum scanning strategy to detect an intelligent Invader who wants to utilize spectrum undetected for his/her unapproved purposes. To deal with this problem we model the situation as two games, between a Scanner and an Invader, and solve them sequentially. The first game is formulated to design the optimal (in maxmin sense) scanning algorithm, while the second one allows one to find the optimal values of the parameters for the algorithm depending on parameters of the network. These games provide solutions for two dilemmas that the rivals face. The Invader's dilemma consists of the following: the more bandwidth the Invader attempts to use leads to a larger payoff if he is not detected, but at the same time also increases the probability of being detected and thus fined. Similarly, the Scanner faces a dilemma: the wider the bandwidth scanned, the higher the probability of detecting the Invader, but at the expense of increasing the cost of building the scanning system. The equilibrium strategies are found explicitly and reveal interesting properties. In particular, we have found a discontinuous dependence of the equilibrium strategies on the network parameters, fine and the type of the Invader's award. This discontinuity of the fine means that the network provider has to take into account a human/social factor since some threshold values of fine could be very sensible for the Invader, while in other situations simply increasing the fine has minimal deterrence impact. Also we show how incomplete information about the Invader's technical characteristics and reward (e.g. motivated by using different type of application, say, video-streaming or downloading files) can be incorporated into scanning strategy to increase its efficiency.
Where's My Drink? Enabling Peripheral Real World Interactions While Using HMDs
Venue: arXiv cs.HC 2015
Year: 2015

Head Mounted Displays (HMDs) allow users to experience virtual reality with a great level of immersion. However, even simple physical tasks like drinking a beverage can be difficult and awkward while in a virtual reality experience. We explore mixed reality renderings that selectively incorporate the physical world into the virtual world for interactions with physical objects. We conducted a user study comparing four rendering techniques that balances immersion in a virtual world with ease of interaction with the physical world. Finally, we discuss the pros and cons of each approach, suggesting guidelines for future rendering techniques that bring physical objects into virtual reality.
The Takeoff Towards Optimal Sorting Networks
Venue: arXiv cs.DS 2015
Year: 2015

A complete set of filters $F_n$ for the optimal-depth $n$-input sorting network problem is such that if there exists an $n$-input sorting network of depth $d$ then there exists one of the form $C \oplus C'$ for some $C \in F_n$. Previous work on the topic presents a method for finding complete set of filters $R_{n, 1}$ and $R_{n, 2}$ that consists only of networks of depths one and two respectively, whose outputs are minimal and representative up to permutation and reflection. Our main contribution is a practical approach for finding a complete set of filters $R_{n, 3}$ containing only networks of depth three whose outputs are minimal and representative up to permutation and reflection. In previous work, we have developed a highly efficient algorithm for finding extremal sets ( i.e. outputs of comparator networks; itemsets; ) up to permutation. In this paper we present a modification to this algorithm that identifies the representative itemsets up to permutation and reflection. Hence, the presented practical approach is the successful combination of known theory and practice that we apply to the domain of sorting networks. For $n < 17$, we empirically compute the complete set of filters $R_{n, 2}$, $R_{n, 3}$, $R_{n, 2} \upharpoonright w $ and $R_{n, 3}^w$ of the representative minimal up to permutation and reflection $n$-input networks, where all but $R_{n, 2}$ are novel to this work.
3D Pose from Detections
Venue: arXiv cs.CV 2015
Year: 2015

We present a novel method to infer, in closed-form, a general 3D spatial occupancy and orientation of a collection of rigid objects given 2D image detections from a sequence of images. In particular, starting from 2D ellipses fitted to bounding boxes, this novel multi-view problem can be reformulated as the estimation of a quadric (ellipsoid) in 3D. We show that an efficient solution exists in the dual-space using a minimum of three views while a solution with two views is possible through the use of regularization. However, this algebraic solution can be negatively affected in the presence of gross inaccuracies in the bounding boxes estimation. To this end, we also propose a robust ellipse fitting algorithm able to improve performance in the presence of errors in the detected objects. Results on synthetic tests and on different real datasets, involving real challenging scenarios, demonstrate the applicability and potential of our method.
Wave-Style Token Machines and Quantum Lambda Calculi
Venue: arXiv cs.LO 2015
Year: 2015

Particle-style token machines are a way to interpret proofs and programs, when the latter are written following the principles of linear logic. In this paper, we show that token machines also make sense when the programs at hand are those of a simple quantum lambda-calculus with implicit qubits. This, however, requires generalising the concept of a token machine to one in which more than one particle travel around the term at the same time. The presence of multiple tokens is intimately related to entanglement and allows us to give a simple operational semantics to the calculus, coherently with the principles of quantum computation.
Rank-Two Beamforming and Power Allocation in Multicasting Relay Networks
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we propose a novel single-group multicasting relay beamforming scheme. We assume a source that transmits common messages via multiple amplify-and-forward relays to multiple destinations. To increase the number of degrees of freedom in the beamforming design, the relays process two received signals jointly and transmit the Alamouti space-time block code over two different beams. Furthermore, in contrast to the existing relay multicasting scheme of the literature, we take into account the direct links from the source to the destinations. We aim to maximize the lowest received quality-of-service by choosing the proper relay weights and the ideal distribution of the power resources in the network. To solve the corresponding optimization problem, we propose an iterative algorithm which solves sequences of convex approximations of the original non-convex optimization problem. Simulation results demonstrate significant performance improvements of the proposed methods as compared with the existing relay multicasting scheme of the literature and an algorithm based on the popular semidefinite relaxation technique.
Measuring and Understanding Sensory Representations within Deep Networks Using a Numerical Optimization Framework
Venue: arXiv cs.NE 2015
Year: 2015

A central challenge in sensory neuroscience is describing how the activity of populations of neurons can represent useful features of the external environment. However, while neurophysiologists have long been able to record the responses of neurons in awake, behaving animals, it is another matter entirely to say what a given neuron does. A key problem is that in many sensory domains, the space of all possible stimuli that one might encounter is effectively infinite; in vision, for instance, natural scenes are combinatorially complex, and an organism will only encounter a tiny fraction of possible stimuli. As a result, even describing the response properties of sensory neurons is difficult, and investigations of neuronal functions are almost always critically limited by the number of stimuli that can be considered. In this paper, we propose a closed-loop, optimization-based experimental framework for characterizing the response properties of sensory neurons, building on past efforts in closed-loop experimental methods, and leveraging recent advances in artificial neural networks to serve as as a proving ground for our techniques. Specifically, using deep convolutional neural networks, we asked whether modern black-box optimization techniques can be used to interrogate the "tuning landscape" of an artificial neuron in a deep, nonlinear system, without imposing significant constraints on the space of stimuli under consideration. We introduce a series of measures to quantify the tuning landscapes, and show how these relate to the performances of the networks in an object recognition task. To the extent that deep convolutional neural networks increasingly serve as de facto working hypotheses for biological vision, we argue that developing a unified approach for studying both artificial and biological systems holds great potential to advance both fields together.
What makes for effective detection proposals?
Venue: arXiv cs.CV 2015
Year: 2015

Current top performing object detectors employ detection proposals to guide the search for objects, thereby avoiding exhaustive sliding window search across images. Despite the popularity and widespread use of detection proposals, it is unclear which trade-offs are made when using them during object detection. We provide an in-depth analysis of twelve proposal methods along with four baselines regarding proposal repeatability, ground truth annotation recall on PASCAL, ImageNet, and MS COCO, and their impact on DPM, R-CNN, and Fast R-CNN detection performance. Our analysis shows that for object detection improving proposal localisation accuracy is as important as improving recall. We introduce a novel metric, the average recall (AR), which rewards both high recall and good localisation and correlates surprisingly well with detection performance. Our findings show common strengths and weaknesses of existing methods, and provide insights and metrics for selecting and tuning proposal methods.
Cybersecurity Dynamics
Venue: arXiv cs.CR 2015
Year: 2015

We explore the emerging field of {\em Cybersecurity Dynamics}, a candidate foundation for the Science of Cybersecurity.
Supervised cross-modal factor analysis for multiple modal data classification
Venue: arXiv cs.LG 2015
Year: 2015

In this paper we study the problem of learning from multiple modal data for purpose of document classification. In this problem, each document is composed two different modals of data, i.e., an image and a text. Cross-modal factor analysis (CFA) has been proposed to project the two different modals of data to a shared data space, so that the classification of a image or a text can be performed directly in this space. A disadvantage of CFA is that it has ignored the supervision information. In this paper, we improve CFA by incorporating the supervision information to represent and classify both image and text modals of documents. We project both image and text data to a shared data space by factor analysis, and then train a class label predictor in the shared space to use the class label information. The factor analysis parameter and the predictor parameter are learned jointly by solving one single objective function. With this objective function, we minimize the distance between the projections of image and text of the same document, and the classification error of the projection measured by hinge loss function. The objective function is optimized by an alternate optimization strategy in an iterative algorithm. Experiments in two different multiple modal document data sets show the advantage of the proposed algorithm over other CFA methods.
Knowledge-generating Efficiency in Innovation Systems: The relation between structural and temporal effects
Venue: arXiv cs.CY 2015
Year: 2015

Using time series of US patents per million inhabitants, knowledge-generating cycles can be distinguished. These cycles partly coincide with Kondratieff long waves. The changes in the slopes between them indicate discontinuities in the knowledge-generating paradigms. The knowledge-generating paradigms can be modeled in terms of interacting dimensions (for example, in university-industry-government relations) that set limits to the maximal efficiency of innovation systems. The maximum values of the parameters in the model are of the same order as the regression coefficients of the empirical waves. The mechanism of the increase in the dimensionality is specified as self-organization which leads to the breaking of existing relations into the more diversified structure of a fractal-like network. This breaking can be modeled in analogy to 2D and 3D (Koch) snowflakes. The boost of knowledge generation leads to newly emerging technologies that can be expected to be more diversified and show shorter life cycles than before. Time spans of the knowledge-generating cycles can also be analyzed in terms of Fibonacci numbers. This perspective allows for forecasting expected dates of future possible paradigm changes. In terms of policy implications, this suggests a shift in focus from the manufacturing technologies to developing new organizational technologies and formats of human interactions
Finitary semantics of linear logic and higher-order model-checking
Venue: arXiv cs.LO 2015
Year: 2015

In this paper, we explain how the connection between higher-order model-checking and linear logic recently exhibited by the authors leads to a new and conceptually enlightening proof of the selection problem originally established by Carayol and Serre using collapsible pushdown automata. The main idea is to start from an infinitary and colored relational semantics of the lambdaY-calculus already formulated, and to replace it by its finitary counterpart based on finite prime-algebraic lattices. Given a higher-order recursion scheme G, the finiteness of its interpretation in the model enables us to associate to any MSO formula phi a new higher-order recursion scheme G_phi resolving the selection problem.
Clustered Integer 3SUM via Additive Combinatorics
Venue: arXiv cs.DS 2015
Year: 2015

We present a collection of new results on problems related to 3SUM, including: 1. The first truly subquadratic algorithm for $\ \ \ \ \ $ 1a. computing the (min,+) convolution for monotone increasing sequences with integer values bounded by $O(n)$, $\ \ \ \ \ $1b. solving 3SUM for monotone sets in 2D with integer coordinates bounded by $O(n)$, and $\ \ \ \ \ $1c. preprocessing a binary string for histogram indexing (also called jumbled indexing). The running time is: $O(n^{(9+\sqrt{177})/12}\,\textrm{polylog}\,n)=O(n^{1.859})$ with randomization, or $O(n^{1.864})$ deterministically. This greatly improves the previous $n^2/2^{Ω(\sqrt{\log n})}$ time bound obtained from Williams' recent result on all-pairs shortest paths [STOC'14], and answers an open question raised by several researchers studying the histogram indexing problem. 2. The first algorithm for histogram indexing for any constant alphabet size that achieves truly subquadratic preprocessing time and truly sublinear query time. 3. A truly subquadratic algorithm for integer 3SUM in the case when the given set can be partitioned into $n^{1-δ}$ clusters each covered by an interval of length $n$, for any constant $δ>0$. 4. An algorithm to preprocess any set of $n$ integers so that subsequently 3SUM on any given subset can be solved in $O(n^{13/7}\,\textrm{polylog}\,n)$ time. All these results are obtained by a surprising new technique, based on the Balog--Szemerédi--Gowers Theorem from additive combinatorics.
Formalizing Size-Optimal Sorting Networks: Extracting a Certified Proof Checker
Venue: arXiv cs.LO 2015
Year: 2015

Since the proof of the four color theorem in 1976, computer-generated proofs have become a reality in mathematics and computer science. During the last decade, we have seen formal proofs using verified proof assistants being used to verify the validity of such proofs. In this paper, we describe a formalized theory of size-optimal sorting networks. From this formalization we extract a certified checker that successfully verifies computer-generated proofs of optimality on up to 8 inputs. The checker relies on an untrusted oracle to shortcut the search for witnesses on more than 1.6 million NP-complete subproblems.
F0 Modeling In Hmm-Based Speech Synthesis System Using Deep Belief Network
Venue: arXiv cs.LG 2015
Year: 2015

In recent years multilayer perceptrons (MLPs) with many hid- den layers Deep Neural Network (DNN) has performed sur- prisingly well in many speech tasks, i.e. speech recognition, speaker verification, speech synthesis etc. Although in the context of F0 modeling these techniques has not been ex- ploited properly. In this paper, Deep Belief Network (DBN), a class of DNN family has been employed and applied to model the F0 contour of synthesized speech which was generated by HMM-based speech synthesis system. The experiment was done on Bengali language. Several DBN-DNN architectures ranging from four to seven hidden layers and up to 200 hid- den units per hidden layer was presented and evaluated. The results were compared against clustering tree techniques pop- ularly found in statistical parametric speech synthesis. We show that from textual inputs DBN-DNN learns a high level structure which in turn improves F0 contour in terms of ob- jective and subjective tests.
Cultural Anthropology Through the Lens of Wikipedia - A Comparison of Historical Leadership Networks in the English, Chinese, Japanese and German Wikipedia
Venue: arXiv cs.SI 2015
Year: 2015

In this paper we study the differences in historical worldview between Western and Eastern cultures, represented through the English, Chinese, Japanese, and German Wikipedia. In particular, we analyze the historical networks of the World's leaders since the beginning of written history, comparing them in the four different Wikipedias.
Lessons from the Coinseminar
Venue: arXiv cs.SI 2015
Year: 2015

This paper describes lessons learned from teaching a distributed virtual course on COINs (Collaborative Innovation Networks) over the last 12 years at five different sites located in four different time zones.
Comparing Online Community Structure of Patients of Chronic Diseases
Venue: arXiv cs.SI 2015
Year: 2015

In this paper we compare the social network structure of people talking about Crohn's disease, Cystic Fibrosis, and Type 1 diabetes on Facebook and Twitter. We find that the Crohn's community's contributors are most emotional on Facebook and Twitter and most negative on Twitter, while the T1D community's communication network structure is most cohesive.
Cross-bifix-free sets in two dimensions
Venue: arXiv cs.DM 2015
Year: 2015

A bidimensional bifix (in short bibifix) of a square matrix T is a square submatrix of T which occurs in the top-left and bottom-right corners of T. This allows us to extend the definition of bifix-free words and cross-bifix-free set of words to bidimensional structures. In this paper we exhaustively generate all the bibifix-free square matrices and we construct a particular non-expandable cross-bibifix-free set of square matrices. Moreover, we provide a Gray code for listing this set.