OpenRaiser/Intern-Atlas huggingface dataset:
Optimizing Teleportation Cost in Distributed Quantum Circuits
Venue: arXiv cs.ET 2016
Year: 2016

The presented work provides a procedure for optimizing the communication cost of a distributed quantum circuit (DQC) in terms of the number of qubit teleportations. Because of technology limitations which do not allow large quantum computers to work as a single processing element, distributed quantum computation is an appropriate solution to overcome this difficulty. Previous studies have applied ad-hoc solutions to distribute a quantum system for special cases and applications. In this study, a general approach is proposed to optimize the number of teleportations for a DQC consisting of two spatially separated and long-distance quantum subsystems. To this end, different configurations of locations for executing gates whose qubits are in distinct subsystems are considered and for each of these configurations, the proposed algorithm is run to find the minimum number of required teleportations. Finally, the configuration which leads to the minimum number of teleportations is reported. The proposed method can be used as an automated procedure to find the configuration with the optimal communication cost for the DQC.
Steganalysis via a Convolutional Neural Network using Large Convolution Filters for Embedding Process with Same Stego Key
Venue: arXiv cs.MM 2016
Year: 2016

For the past few years, in the race between image steganography and steganalysis, deep learning has emerged as a very promising alternative to steganalyzer approaches based on rich image models combined with ensemble classifiers. A key knowledge of image steganalyzer, which combines relevant image features and innovative classification procedures, can be deduced by a deep learning approach called Convolutional Neural Networks (CNN). These kind of deep learning networks is so well-suited for classification tasks based on the detection of variations in 2D shapes that it is the state-of-the-art in many image recognition problems. In this article, we design a CNN-based steganalyzer for images obtained by applying steganography with a unique embedding key. This one is quite different from the previous study of {\em Qian et al.} and its successor, namely {\em Pibre et al.} The proposed architecture embeds less convolutions, with much larger filters in the final convolutional layer, and is more general: it is able to deal with larger images and lower payloads. For the "same embedding key" scenario, our proposal outperforms all other steganalyzers, in particular the existing CNN-based ones, and defeats many state-of-the-art image steganography schemes.
A Power Law Approach to Estimating Fake Social Network Accounts
Venue: arXiv cs.SI 2016
Year: 2016

This paper presents a method to validate the true patrons of a brand, group, artist or any other entity on the social networking site Twitter. We analyze the trend of total number of tweets, average retweets and total number of followers for various nodes for different social and political backgrounds. We argue that average retweets to follower ratio reveals the overall value of the individual accounts and helps estimate the true to fake account ratio.
Toward a general, scaleable framework for Bayesian teaching with applications to topic models
Venue: arXiv cs.LG 2016
Year: 2016

Machines, not humans, are the world's dominant knowledge accumulators but humans remain the dominant decision makers. Interpreting and disseminating the knowledge accumulated by machines requires expertise, time, and is prone to failure. The problem of how best to convey accumulated knowledge from computers to humans is a critical bottleneck in the broader application of machine learning. We propose an approach based on human teaching where the problem is formalized as selecting a small subset of the data that will, with high probability, lead the human user to the correct inference. This approach, though successful for modeling human learning in simple laboratory experiments, has failed to achieve broader relevance due to challenges in formulating general and scalable algorithms. We propose general-purpose teaching via pseudo-marginal sampling and demonstrate the algorithm by teaching topic models. Simulation results show our sampling-based approach: effectively approximates the probability where ground-truth is possible via enumeration, results in data that are markedly different from those expected by random sampling, and speeds learning especially for small amounts of data. Application to movie synopsis data illustrates differences between teaching and random sampling for teaching distributions and specific topics, and demonstrates gains in scalability and applicability to real-world problems.
A PAC RL Algorithm for Episodic POMDPs
Venue: arXiv cs.LG 2016
Year: 2016

Many interesting real world domains involve reinforcement learning (RL) in partially observable environments. Efficient learning in such domains is important, but existing sample complexity bounds for partially observable RL are at least exponential in the episode length. We give, to our knowledge, the first partially observable RL algorithm with a polynomial bound on the number of episodes on which the algorithm may not achieve near-optimal performance. Our algorithm is suitable for an important class of episodic POMDPs. Our approach builds on recent advances in method of moments for latent variable model estimation.
On Pollaczek-Khinchine Formula for Peer-to-Peer Networks
Venue: arXiv cs.PF 2016
Year: 2016

The performance analysis of peer-to-peer (P2P) networks calls for a new kind of queueing model, in which jobs and service stations arrive randomly. Except in some simple special cases, in general, the queueing model with varying service rate is mathematically intractable. Motivated by the P-K formula for M/G/1 queue, we developed a limiting analysis approach based on the connection between the fluctuation of service rate and the mean queue length. Considering the two extreme service rates, we proved the conjecture on the lower bound and upper bound of mean queue length previously postulated. Furthermore, an approximate P-K formula to estimate the mean queue length is derived from the convex combination of these two bounds and the conditional mean queue length under the overload condition. We confirmed the accuracy of our approximation by extensive simulation studies with different system parameters. We also verified that all limiting cases of the system behavior are consistent with the predictions of our formula.
Analyzing the Gadgets Towards a Metric to Measure Gadget Quality
Venue: arXiv cs.SE 2016
Year: 2016

Current low-level exploits often rely on code-reuse, whereby short sections of code (gadgets) are chained together into a coherent exploit that can be executed without the need to inject any code. Several protection mechanisms attempt to eliminate this attack vector by applying code transformations to reduce the number of available gadgets. Nevertheless, it has emerged that the residual gadgets can still be sufficient to conduct a successful attack. Crucially, the lack of a common metric for "gadget quality" hinders the effective comparison of current mitigations. This work proposes four metrics that assign scores to a set of gadgets, measuring quality, usefulness, and practicality. We apply these metrics to binaries produced when compiling programs for architectures implementing Intel's recent MPX CPU extensions. Our results demonstrate a 17% increase in useful gadgets in MPX binaries, and a decrease in side-effects and preconditions, making them better suited for ROP attacks.
Centrality in the Global Network of Corporate Control
Venue: arXiv cs.SI 2016
Year: 2016

Corporations across the world are highly interconnected in a large global network of corporate control. This paper investigates the global board interlock network, covering 400,000 firms linked through 1,700,000 edges representing shared directors between these firms. The main focus is on the concept of centrality, which is used to investigate the embeddedness of firms from a particular country within the global network. The study results in three contributions. First, to the best of our knowledge for the first time we can investigate the topology as well as the concept of centrality in corporate networks at a global scale, allowing for the largest cross-country comparison ever done in interlocking directorates literature. We demonstrate, amongst other things, extremely similar network topologies, yet large differences between countries when it comes to the relation between economic prominence indicators and firm centrality. Second, we introduce two new metrics that are specifically suitable for comparing the centrality ranking of a partition to that of the full network. Using the notion of centrality persistence we propose to measure the persistence of a partition's centrality ranking in the full network. In the board interlock network, it allows us to assess the extent to which the footprint of a national network is still present within the global network. Next, the measure of centrality ranking dominance tells us whether a partition (country) is more dominant at the top or the bottom of the centrality ranking of the full (global) network. Finally, comparing these two new measures of persistence and dominance between different countries allows us to classify these countries based the their embeddedness, measured using the relation between the centrality of a country's firms on the national and the global scale of the board interlock network.
Aerial image geolocalization from recognition and matching of roads and intersections
Venue: arXiv cs.CV 2016
Year: 2016

Aerial image analysis at a semantic level is important in many applications with strong potential impact in industry and consumer use, such as automated mapping, urban planning, real estate and environment monitoring, or disaster relief. The problem is enjoying a great interest in computer vision and remote sensing, due to increased computer power and improvement in automated image understanding algorithms. In this paper we address the task of automatic geolocalization of aerial images from recognition and matching of roads and intersections. Our proposed method is a novel contribution in the literature that could enable many applications of aerial image analysis when GPS data is not available. We offer a complete pipeline for geolocalization, from the detection of roads and intersections, to the identification of the enclosing geographic region by matching detected intersections to previously learned manually labeled ones, followed by accurate geometric alignment between the detected roads and the manually labeled maps. We test on a novel dataset with aerial images of two European cities and use the publicly available OpenStreetMap project for collecting ground truth roads annotations. We show in extensive experiments that our approach produces highly accurate localizations in the challenging case when we train on images from one city and test on the other and the quality of the aerial images is relatively poor. We also show that the the alignment between detected roads and pre-stored manual annotations can be effectively used for improving the quality of the road detection results.
Suppressing Background Radiation Using Poisson Principal Component Analysis
Venue: arXiv cs.LG 2016
Year: 2016

Performance of nuclear threat detection systems based on gamma-ray spectrometry often strongly depends on the ability to identify the part of measured signal that can be attributed to background radiation. We have successfully applied a method based on Principal Component Analysis (PCA) to obtain a compact null-space model of background spectra using PCA projection residuals to derive a source detection score. We have shown the method's utility in a threat detection system using mobile spectrometers in urban scenes (Tandon et al 2012). While it is commonly assumed that measured photon counts follow a Poisson process, standard PCA makes a Gaussian assumption about the data distribution, which may be a poor approximation when photon counts are low. This paper studies whether and in what conditions PCA with a Poisson-based loss function (Poisson PCA) can outperform standard Gaussian PCA in modeling background radiation to enable more sensitive and specific nuclear threat detection.
Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture
Venue: arXiv cs.LG 2016
Year: 2016

The best arm identification problem (BEST-1-ARM) is the most basic pure exploration problem in stochastic multi-armed bandits. The problem has a long history and attracted significant attention for the last decade. However, we do not yet have a complete understanding of the optimal sample complexity of the problem: The state-of-the-art algorithms achieve a sample complexity of $O(\sum_{i=2}^{n} Δ_{i}^{-2}(\lnδ^{-1} + \ln\lnΔ_i^{-1}))$ ($Δ_{i}$ is the difference between the largest mean and the $i^{th}$ mean), while the best known lower bound is $Ω(\sum_{i=2}^{n} Δ_{i}^{-2}\lnδ^{-1})$ for general instances and $Ω(Δ^{-2} \ln\ln Δ^{-1})$ for the two-arm instances. We propose to study the instance-wise optimality for the BEST-1-ARM problem. Previous work has proved that it is impossible to have an instance optimal algorithm for the 2-arm problem. However, we conjecture that modulo the additive term $Ω(Δ_2^{-2} \ln\ln Δ_2^{-1})$ (which is an upper bound and worst case lower bound for the 2-arm problem), there is an instance optimal algorithm for BEST-1-ARM. Moreover, we introduce a new quantity, called the gap entropy for a best-arm problem instance, and conjecture that it is the instance-wise lower bound. Hence, resolving this conjecture would provide a final answer to the old and basic problem.
On The 2D Phase Retrieval Problem
Venue: arXiv cs.IT 2016
Year: 2016

The recovery of a signal from the magnitude of its Fourier transform, also known as phase retrieval, is of fundamental importance in many scientific fields. It is well known that due to the loss of Fourier phase the problem in 1D is ill-posed. Without further constraints, there is no unique solution to the problem. In contrast, uniqueness up to trivial ambiguities very often exists in higher dimensions, with mild constraints on the input. In this paper we focus on the 2D phase retrieval problem and provide insight into this uniqueness property by exploring the connection between the 2D and 1D formulations. In particular, we show that 2D phase retrieval can be cast as a 1D problem with additional constraints, which limit the solution space. We then prove that only one additional constraint is sufficient to reduce the many feasible solutions in the 1D setting to a unique solution for almost all signals. These results allow to obtain an analytical approach (with combinatorial complexity) to solve the 2D phase retrieval problem when it is unique.
Secure Containers in Android: the Samsung KNOX Case Study
Venue: arXiv cs.CR 2016
Year: 2016

Bring Your Own Device (BYOD) is a growing trend among enterprises, aiming to improve workers' mobility and productivity via their smartphones. The threats and dangers posed by the smartphones to the enterprise are also ever-growing. Such dangers can be mitigated by running the enterprise software inside a "secure container" on the smartphone. In our work we present a systematic assessment of security critical areas in design and implementation of a secure container for Android using reverse engineering and attacker-inspired methods. We do this through a case-study of Samsung KNOX, a real-world product deployed on millions of devices. Our research shows how KNOX security features work behind the scenes and lets us compare the vendor's public security claims against reality. Along the way we identified several design weaknesses and a few vulnerabilities that were disclosed to Samsung.
Variational Bayesian Inference for Hidden Markov Models With Multivariate Gaussian Output Distributions
Venue: arXiv cs.LG 2016
Year: 2016

Hidden Markov Models (HMM) have been used for several years in many time series analysis or pattern recognitions tasks. HMM are often trained by means of the Baum-Welch algorithm which can be seen as a special variant of an expectation maximization (EM) algorithm. Second-order training techniques such as Variational Bayesian Inference (VI) for probabilistic models regard the parameters of the probabilistic models as random variables and define distributions over these distribution parameters, hence the name of this technique. VI can also bee regarded as a special case of an EM algorithm. In this article, we bring both together and train HMM with multivariate Gaussian output distributions with VI. The article defines the new training technique for HMM. An evaluation based on some case studies and a comparison to related approaches is part of our ongoing work.
Censors' Delay in Blocking Circumvention Proxies
Venue: arXiv cs.CR 2016
Year: 2016

Censors of the Internet must continually discover and block new circumvention proxy servers. We seek to understand this process; specifically, the length of the delay between when a proxy first becomes discoverable and when it is actually blocked. We measure this delay in the case of obfuscated Tor bridges, by testing their reachability before and after their introduction into Tor Browser. We test from sites in the U.S., China, and Iran, over a period of five months. China's national firewall blocked new bridges after a varying delay of between 2 and 36 days. Blocking occurred only after end-user software releases, despite bridges being potentially discoverable earlier through other channels. While the firewall eventually discovered the bridges of Tor Browser, those that appeared only in Orbot, a version of Tor for mobile devices, remained unblocked. Our findings highlight the fact that censors can behave in ways that defy intuition, presenting difficulties for threat modeling but also opportunities for evasion.
Dense Urban Channel Measurements for Utility Pole Fixed Wireless Links
Venue: arXiv cs.NI 2016
Year: 2016

This radio channel measurement campaign characterizes the propagation conditions experienced in a dense urban environment over fixed backhaul links between wireless devices that are mounted on utility or traffic light poles. The measurements characterize the 2x1 multiple input single output channel in the 2.45 GHz band for both spatially separated omni antennas and cross polarized directional antennas. Results presented include both small and large scale channel statistics, antenna correlation coefficient values and the off-broadside rejection achieved with the directional antennas.
Smart Societies: From Citizens as Sensors to Collective Action
Venue: arXiv cs.CY 2016
Year: 2016

Social media has become globally ubiquitous, transforming how people are networked and mobilized. This forum explores research and applications of these new networked publics at individual, organizational, and societal levels.
A Human-Centered Approach to Data Privacy : Political Economy, Power, and Collective Data Subjects
Venue: arXiv cs.CY 2016
Year: 2016

Researchers find weaknesses in current strategies for protecting privacy in large datasets. Many anonymized datasets are reidentifiable, and norms for offering data subjects notice and consent over emphasize individual responsibility. Based on fieldwork with data managers in the City of Seattle, I identify ways that these conventional approaches break down in practice. Drawing on work from theorists in sociocultural anthropology, I propose that a Human Centered Data Science move beyond concepts like dataset identifiability and sensitivity toward a broader ontology of who is implicated by a dataset, and new ways of anticipating how data can be combined and used.
A Simplified Sub-Nyquist Receiver Architecture for Joint DOA and Frequency Estimation
Venue: arXiv cs.IT 2016
Year: 2016

Joint estimation of carrier frequency and direction of arrival (DOA) for multiple signals has been found in many practical applications such as Cognitive Radio (CR). However, Nyquist sampling mechanism is costly or implemented due to wide spectrum range. Taking advantage of sub-Nyquist sampling technology, some array receiver architectures are proposed to realize joint estimation of carrier frequency and DOA. To further decrease equivalent sampling rate and hardware complexity, we propose a simplifying receiver architecture based on our previous work. We come up with joint DOA and frequency estimation algorithms for the novel architecture. The simulations demonstrate that the receiver architecture and the proposed approaches are feasible.
A Channelized Binning Method for Extraction of Dominant Color Pixel Value
Venue: arXiv cs.CV 2016
Year: 2016

The Color is one of the most important and easily identifiable features for describing the visual content. The MPEG standard has developed a number of descriptors that covers different aspects of the visual content. The Dominant color descriptor is one of them. This paper proposes a channelized binning approach a novel method for extraction of the dominant color pixel value which is a variant of the dominant color descriptor. The Channelized binning method treats the problem as a statistical problem and tries to avoid color quantization and interpolation guessing of number and centroid of dominant colors. Channelized binning is an iterative approach which automatically estimates the number of dominant pixel values and their centroids. It operates on 24 bit full RGB color space, by considering one color channel at a time and hence avoiding the color quantization. Results show that the proposed method can successfully extract dominant color pixel values.
Video Key Frame Extraction using Entropy value as Global and Local Feature
Venue: arXiv cs.CV 2016
Year: 2016

Key frames play an important role in video annotation. It is one of the widely used methods for video abstraction as this will help us for processing a large set of video data with sufficient content representation in faster way. In this paper a novel approach for key-frame extraction using entropy value is proposed. The proposed approach classifies frames based on entropy values as global feature and selects frame from each class as representative key-frame. It also eliminates redundant frames from selected key-frames using entropy value as local feature. Evaluation of the approach on several video clips has been presented. Results show that the algorithm is successful in helping annotators automatically identify video key-frames.
New Constructions of MDS Symbol-Pair Codes
Venue: arXiv cs.IT 2016
Year: 2016

Motivated by the application of high-density data storage technologies, symbol-pair codes are proposed to protect against pair-errors in symbol-pair channels, whose outputs are overlapping pairs of symbols. The research of symbol-pair codes with the largest minimum pair-distance is interesting since such codes have the best possible error-correcting capability. A symbol-pair code attaining the maximal minimum pair-distance is called a maximum distance separable (MDS) symbol-pair code. In this paper, we focus on constructing linear MDS symbol-pair codes over the finite field $\mathbb{F}_{q}$. We show that a linear MDS symbol-pair code over $\mathbb{F}_{q}$ with pair-distance $5$ exists if and only if the length $n$ ranges from $5$ to $q^2+q+1$. As for codes with pair-distance $6$, length ranging from $6$ to $q^{2}+1$, we construct linear MDS symbol-pair codes by using a configuration called ovoid in projective geometry. With the help of elliptic curves, we present a construction of linear MDS symbol-pair codes for any pair-distance $d+2$ with length $n$ satisfying $7\le d+2\leq n\le q+\lfloor 2\sqrt{q}\rfloor+δ(q)-3$, where $δ(q)=0$ or $1$.