OpenRaiser/Intern-Atlas huggingface dataset:
SPREE: Spoofing Resistant GPS Receiver
Venue: arXiv cs.CR 2016
Year: 2016

Global Positioning System (GPS) is used ubiquitously in a wide variety of applications ranging from navigation and tracking to modern smart grids and communication networks. However, it has been demonstrated that modern GPS receivers are vulnerable to signal spoofing attacks. For example, today it is possible to change the course of a ship or force a drone to land in an hostile area by simply spoofing GPS signals. Several countermeasures have been proposed in the past to detect GPS spoofing attacks. These countermeasures offer protection only against naive attackers. They are incapable of detecting strong attackers such as those capable of seamlessly taking over a GPS receiver, which is currently receiving legitimate satellite signals, and spoofing them to an arbitrary location. Also, there is no hardware platform that can be used to compare and evaluate the effectiveness of existing countermeasures in real-world scenarios. In this work, we present SPREE, which is, to the best of our knowledge, the first GPS receiver capable of detecting all spoofing attacks described in literature. Our novel spoofing detection technique called auxiliary peak tracking enables detection of even a strong attacker capable of executing the seamless takeover attack. We implement and evaluate our receiver against three different sets of GPS signal traces and show that SPREE constrains even a strong attacker (capable of seamless takeover attack) from spoofing the receiver to a location not more than 1 km away from its true location. This is a significant improvement over modern GPS receivers that can be spoofed to any arbitrary location. Finally, we release our implementation and datasets to the community for further research and development.
Predictive Functional Connectivity of Real-World Systems
Venue: arXiv cs.SI 2016
Year: 2016

We are flooded with large-scale dynamic networked data. Analyses requiring exact comparisons between networks are computationally intractable, so new methodologies are sought. We extend the graphlet-based statistics to directed networks and demonstrate that they are superior to other measures. We predict a country's gross domestic product (GDP) solely from its wiring patterns in the world trade network (WTN) that could inform policy makers on benefits of trade agreements. Surprisingly, we find that it is not enough for a country to be in a densely connected core in the WTN to have a high GDP, as was previously believed. In addition to being in the core, a country must also trade with peripheral countries, while only being in the core and not trading with peripheral economies makes a country prone to debt. Furthermore, by tracking the dynamics of a country's positioning in the WTN over years, we predict success or failure of an emerging economy. We validate our methodology on metabolic networks, yielding insights into preservation of enzyme function from the network wiring patterns rather than sequence data. Overall, our methodology enables advanced analyses of directed networked data from any area of science, allowing domain-specific interpretation of a directed network's topology.
Predicate Gradual Logic and Linguistics
Venue: arXiv cs.CL 2016
Year: 2016

There are several major proposals for treating donkey anaphora such as discourse representation theory and the likes, or E-Type theories and the likes. Every one of them works well for a set of specific examples that they use to demonstrate validity of their approaches. As I show in this paper, however, they are not very generalisable and do not account for essentially the same problem that they remedy when it manifests in other examples. I propose another logical approach. I develoop logic that extends a recent, propositional gradual logic, and show that it can treat donkey anaphora generally. I also identify and address a problem around the modern convention on existential import. Furthermore, I show that Aristotle's syllogisms and conversion are realisable in this logic.
On the Multiplexing Gain of Discrete-Time MIMO Phase Noise Channels
Venue: arXiv cs.IT 2016
Year: 2016

The capacity of a point-to-point discrete-time multi-input-multiple-output (MIMO) channel with phase uncertainty (MIMO phase noise channel) is still open. As a matter of fact, even the pre-log (multiplexing gain) of the capacity in the high signal-to-noise ratio (SNR) regime is unknown in general. We make some progresses in this direction for two classes of such channels. With phase noise on the individual paths of the channel (model A), we show that the multiplexing gain is 1/2, which implies that the capacity does not scale with the channel dimension at high SNR. With phase noise at both the input and output of the channel (model B), the multiplexing gain is upper-bounded by 1/2 min{nt,(nr-2)^+ + 1}, and lower-bounded by 1/2 min{nt, floor((nr+1)/2)}, where nt and nr are the number of transmit and receive antennas, respectively. The multiplexing gain is enhanced to 1/2 min{nt,nr} without receive phase noise, and to 1/2 min{2nt-1,nr} without transmit phase noise. In all the cases of model B, the multiplexing gain scales linearly with min{nt,nr}. Our main results rely on the derivation of non-trivial upper and lower bounds on the capacity of such channels.
Mapping Temporal Variables into the NeuCube for Improved Pattern Recognition, Predictive Modelling and Understanding of Stream Data
Venue: arXiv cs.NE 2016
Year: 2016

This paper proposes a new method for an optimized mapping of temporal variables, describing a temporal stream data, into the recently proposed NeuCube spiking neural network architecture. This optimized mapping extends the use of the NeuCube, which was initially designed for spatiotemporal brain data, to work on arbitrary stream data and to achieve a better accuracy of temporal pattern recognition, a better and earlier event prediction and a better understanding of complex temporal stream data through visualization of the NeuCube connectivity. The effect of the new mapping is demonstrated on three bench mark problems. The first one is early prediction of patient sleep stage event from temporal physiological data. The second one is pattern recognition of dynamic temporal patterns of traffic in the Bay Area of California and the last one is the Challenge 2012 contest data set. In all cases the use of the proposed mapping leads to an improved accuracy of pattern recognition and event prediction and a better understanding of the data when compared to traditional machine learning techniques or spiking neural network reservoirs with arbitrary mapping of the variables.
"What happens if..." Learning to Predict the Effect of Forces in Images
Venue: arXiv cs.CV 2016
Year: 2016

What happens if one pushes a cup sitting on a table toward the edge of the table? How about pushing a desk against a wall? In this paper, we study the problem of understanding the movements of objects as a result of applying external forces to them. For a given force vector applied to a specific location in an image, our goal is to predict long-term sequential movements caused by that force. Doing so entails reasoning about scene geometry, objects, their attributes, and the physical rules that govern the movements of objects. We design a deep neural network model that learns long-term sequential dependencies of object movements while taking into account the geometry and appearance of the scene by combining Convolutional and Recurrent Neural Networks. Training our model requires a large-scale dataset of object movements caused by external forces. To build a dataset of forces in scenes, we reconstructed all images in SUN RGB-D dataset in a physics simulator to estimate the physical movements of objects caused by external forces applied to them. Our Forces in Scenes (ForScene) dataset contains 10,335 images in which a variety of external forces are applied to different types of objects resulting in more than 65,000 object movements represented in 3D. Our experimental evaluations show that the challenging task of predicting long-term movements of objects as their reaction to external forces is possible from a single image.
ABCDepth: efficient algorithm for Tukey depth
Venue: arXiv cs.CG 2016
Year: 2016

We present a new algorithm for Tukey (halfspace) depth level sets and its implementation. Given $d$-dimensional data set for any $d\geq 2$, the algorithm is based on representation of level sets as intersections of balls in $R^d$, and can be easily adapted to related depths (Type D, Zuo and Serfling (Ann. Stat. {\bf 28} (2000), 461--482)). The algorithm complexity is $O(dn^2 + n^2\log{n})$ where $n$ is the data set size. Examples with real and synthetic data show that the algorithm is much faster than other implemented algorithms and that it can accept thousands of multidimensional observations, while other algorithms are tested with two-dimensional data or with a couple of hundreds multidimensional observations.
Predicting health inspection results from online restaurant reviews
Venue: arXiv cs.CL 2016
Year: 2016

Informatics around public health are increasingly shifting from the professional to the public spheres. In this work, we apply linguistic analytics to restaurant reviews, from Yelp, in order to automatically predict official health inspection reports. We consider two types of feature sets, i.e., keyword detection and topic model features, and use these in several classification methods. Our empirical analysis shows that these extracted features can predict public health inspection reports with over 90% accuracy using simple support vector machines.
From line segments to more organized Gestalts
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we reconsider the early computer vision bottom-up program, according to which higher level features (geometric structures) in an image could be built up recursively from elementary features by simple grouping principles coming from Gestalt theory. Taking advantage of the (recent) advances in reliable line segment detectors, we propose three feature detectors that constitute one step up in this bottom up pyramid. For any digital image, our unsupervised algorithm computes three classic Gestalts from the set of predetected line segments: good continuations, nonlocal alignments, and bars. The methodology is based on a common stochastic {\it a contrario model} yielding three simple detection formulas, characterized by their number of false alarms. This detection algorithm is illustrated on several digital images.
Lower Bounds for Graph Exploration Using Local Policies
Venue: arXiv cs.CG 2016
Year: 2016

We give lower bounds for various natural node- and edge-based local strategies for exploring a graph. We consider this problem both in the setting of an arbitrary graph as well as the abstraction of a geometric exploration of a space by a robot, both of which have been extensively studied. We consider local exploration policies that use time-of-last- visit or alternatively least-frequently-visited local greedy strategies to select the next step in the exploration path. Both of these strategies were previously considered by Cooper et al. (2011) for a scenario in which counters for the last visit or visit frequency are attached to the edges. In this work we consider the case in which the counters are associated with the nodes, which for the case of dual graphs of geometric spaces could be argued to be intuitively more natural and likely more efficient. Surprisingly, these alternate strategies give worst-case superpolynomial/ exponential time for exploration, whereas the least-frequently visited strategy for edges has a polynomially bounded exploration time, as shown by Cooper et al. (2011).
Readability-based Sentence Ranking for Evaluating Text Simplification
Venue: arXiv cs.CL 2016
Year: 2016

We propose a new method for evaluating the readability of simplified sentences through pair-wise ranking. The validity of the method is established through in-corpus and cross-corpus evaluation experiments. The approach correctly identifies the ranking of simplified and unsimplified sentences in terms of their reading level with an accuracy of over 80%, significantly outperforming previous results. To gain qualitative insights into the nature of simplification at the sentence level, we studied the impact of specific linguistic features. We empirically confirm that both word-level and syntactic features play a role in comparing the degree of simplification of authentic data. To carry out this research, we created a new sentence-aligned corpus from professionally simplified news articles. The new corpus resource enriches the empirical basis of sentence-level simplification research, which so far relied on a single resource. Most importantly, it facilitates cross-corpus evaluation for simplification, a key step towards generalizable results.
Philosophical Solution to P=?NP: P is Equal to NP
Venue: arXiv cs.GL 2016
Year: 2016

The P=?NP problem is philosophically solved by showing P is equal to NP in the random access with unit multiply (MRAM) model. It is shown that the MRAM model empirically best models computation hardness. The P=?NP problem is shown to be a scientific rather than a mathematical problem. The assumptions involved in the current definition of the P?=NP problem as a problem involving non deterministic Turing Machines (NDTMs) from axiomatic automata theory are criticized. The problem is also shown to be neither a problem in pure nor applied mathematics. The details of The MRAM model and the well known Hartmanis and Simon construction that shows how to code and simulate NDTMs on MRAM machines is described. Since the computation power of MRAMs is the same as NDTMs, P is equal to NP. The paper shows that the justification for the NDTM P?=NP problem using a letter from Kurt Godel to John Von Neumann is incorrect by showing Von Neumann explicitly rejected automata models of computation hardness and used his computer architecture for modeling computation that is exactly the MRAM model. The paper argues that Deolalikar's scientific solution showing P not equal to NP if assumptions from statistical physics are used, needs to be revisited.
L0-norm Sparse Graph-regularized SVD for Biclustering
Venue: arXiv cs.LG 2016
Year: 2016

Learning the "blocking" structure is a central challenge for high dimensional data (e.g., gene expression data). Recently, a sparse singular value decomposition (SVD) has been used as a biclustering tool to achieve this goal. However, this model ignores the structural information between variables (e.g., gene interaction graph). Although typical graph-regularized norm can incorporate such prior graph information to get accurate discovery and better interpretability, it fails to consider the opposite effect of variables with different signs. Motivated by the development of sparse coding and graph-regularized norm, we propose a novel sparse graph-regularized SVD as a powerful biclustering tool for analyzing high-dimensional data. The key of this method is to impose two penalties including a novel graph-regularized norm ($|\pmb{u}|\pmb{L}|\pmb{u}|$) and $L_0$-norm ($\|\pmb{u}\|_0$) on singular vectors to induce structural sparsity and enhance interpretability. We design an efficient Alternating Iterative Sparse Projection (AISP) algorithm to solve it. Finally, we apply our method and related ones to simulated and real data to show its efficiency in capturing natural blocking structures.
Deep Shading: Convolutional Neural Networks for Screen-Space Shading
Venue: arXiv cs.GR 2016
Year: 2016

In computer vision, convolutional neural networks (CNNs) have recently achieved new levels of performance for several inverse problems where RGB pixel appearance is mapped to attributes such as positions, normals or reflectance. In computer graphics, screen-space shading has recently increased the visual quality in interactive image synthesis, where per-pixel attributes such as positions, normals or reflectance of a virtual 3D scene are converted into RGB pixel appearance, enabling effects like ambient occlusion, indirect light, scattering, depth-of-field, motion blur, or anti-aliasing. In this paper we consider the diagonal problem: synthesizing appearance from given per-pixel attributes using a CNN. The resulting Deep Shading simulates various screen-space effects at competitive quality and speed while not being programmed by human experts but learned from example images.
Large scale near-duplicate image retrieval using Triples of Adjacent Ranked Features (TARF) with embedded geometric information
Venue: arXiv cs.CV 2016
Year: 2016

Most approaches to large-scale image retrieval are based on the construction of the inverted index of local image descriptors or visual words. A search in such an index usually results in a large number of candidates. This list of candidates is then re-ranked with the help of a geometric verification, using a RANSAC algorithm, for example. In this paper we propose a feature representation, which is built as a combination of three local descriptors. It allows one to significantly decrease the number of false matches and to shorten the list of candidates after the initial search in the inverted index. This combination of local descriptors is both reproducible and highly discriminative, and thus can be efficiently used for large-scale near-duplicate image retrieval.
Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem
Venue: arXiv cs.CR 2016
Year: 2016

The cryptogenography problem, introduced by Brody, Jakobsen, Scheder, and Winkler (ITCS 2014), is to collaboratively leak a piece of information known to only one member of a group (i)~without revealing who was the origin of this information and (ii)~without any private communication, neither during the process nor before. Despite several deep structural results, even the smallest case of leaking one bit of information present at one of two players is not well understood. Brody et al.\ gave a 2-round protocol enabling the two players to succeed with probability $1/3$ and showed the hardness result that no protocol can give a success probability of more than~$3/8$. In this work, we show that neither bound is tight. Our new hardness result, obtained by a different application of the concavity method used also in the previous work, states that a success probability better than 0.3672 is not possible. Using both theoretical and numerical approaches, we improve the lower bound to $0.3384$, that is, give a protocol leading to this success probability. To ease the design of new protocols, we prove an equivalent formulation of the cryptogenography problem as solitaire vector splitting game. Via an automated game tree search, we find good strategies for this game. We then translate the splits that occurred in this strategy into inequalities relating position values and use an LP solver to find an optimal solution for these inequalities. This gives slightly better game values, but more importantly, it gives a more compact representation of the protocol and a way to easily verify the claimed quality of the protocol. These improved bounds, as well as the large sizes and depths of the improved protocols we find, suggests that finding good protocols for the cryptogenography problem as well as understanding their structure are harder than what the simple problem formulation suggests.
A Big-Data Approach to Handle Process Variations: Uncertainty Quantification by Tensor Recovery
Venue: arXiv cs.CE 2016
Year: 2016

Stochastic spectral methods have become a popular technique to quantify the uncertainties of nano-scale devices and circuits. They are much more efficient than Monte Carlo for certain design cases with a small number of random parameters. However, their computational cost significantly increases as the number of random parameters increases. This paper presents a big-data approach to solve high-dimensional uncertainty quantification problems. Specifically, we simulate integrated circuits and MEMS at only a small number of quadrature samples, then, a huge number of (e.g., $1.5 \times 10^{27}$) solution samples are estimated from the available small-size (e.g., $500$) solution samples via a low-rank and tensor-recovery method. Numerical results show that our algorithm can easily extend the applicability of tensor-product stochastic collocation to IC and MEMS problems with over 50 random parameters, whereas the traditional algorithm can only handle several random parameters.
Buried object detection using handheld WEMI with task-driven extended functions of multiple instances
Venue: arXiv cs.CV 2016
Year: 2016

Many effective supervised discriminative dictionary learning methods have been developed in the literature. However, when training these algorithms, precise ground-truth of the training data is required to provide very accurate point-wise labels. Yet, in many applications, accurate labels are not always feasible. This is especially true in the case of buried object detection in which the size of the objects are not consistent. In this paper, a new multiple instance dictionary learning algorithm for detecting buried objects using a handheld WEMI sensor is detailed. The new algorithm, Task Driven Extended Functions of Multiple Instances, can overcome data that does not have very precise point-wise labels and still learn a highly discriminative dictionary. Results are presented and discussed on measured WEMI data.
Automated Correction for Syntax Errors in Programming Assignments using Recurrent Neural Networks
Venue: arXiv cs.PL 2016
Year: 2016

We present a method for automatically generating repair feedback for syntax errors for introductory programming problems. Syntax errors constitute one of the largest classes of errors (34%) in our dataset of student submissions obtained from a MOOC course on edX. The previous techniques for generating automated feed- back on programming assignments have focused on functional correctness and style considerations of student programs. These techniques analyze the program AST of the program and then perform some dynamic and symbolic analyses to compute repair feedback. Unfortunately, it is not possible to generate ASTs for student pro- grams with syntax errors and therefore the previous feedback techniques are not applicable in repairing syntax errors. We present a technique for providing feedback on syntax errors that uses Recurrent neural networks (RNNs) to model syntactically valid token sequences. Our approach is inspired from the recent work on learning language models from Big Code (large code corpus). For a given programming assignment, we first learn an RNN to model all valid token sequences using the set of syntactically correct student submissions. Then, for a student submission with syntax errors, we query the learnt RNN model with the prefix to- ken sequence to predict token sequences that can fix the error by either replacing or inserting the predicted token sequence at the error location. We evaluate our technique on over 14, 000 student submissions with syntax errors. Our technique can completely re- pair 31.69% (4501/14203) of submissions with syntax errors and in addition partially correct 6.39% (908/14203) of the submissions.
Robust Mechanisms Under Common Valuation
Venue: arXiv cs.GT 2016
Year: 2016

We study robust mechanisms to sell a common-value good. We assume that the mechanism designer knows the prior distribution of the buyers' common value but is unsure of the buyers' information structure about the common value. We use linear programming duality to derive mechanisms that guarantee a good revenue among all information structures and all equilibria. Our mechanism maximizes the revenue guarantee when there is one buyer. As the number of buyers tends to infinity, the revenue guarantee of our mechanism converges to the full surplus.