OpenRaiser/Intern-Atlas huggingface dataset:
Phase Retrieval: An Overview of Recent Developments
Venue: arXiv cs.IT 2015
Year: 2015

The problem of phase retrieval is a classic one in optics and arises when one is interested in recovering an unknown signal from the magnitude (intensity) of its Fourier transform. While there have existed quite a few approaches to phase retrieval, recent developments in compressed sensing and convex optimization-based signal recovery have inspired a host of new ones. This work presents an overview of these approaches. Since phase retrieval, by its very nature, is ill-posed, to make the problem meaningful one needs to either assume prior structure on the signal (e.g., sparsity) or obtain additional measurements (e.g., masks, structured illuminations). For both the cases, we review conditions for the identifiability of the signal, as well as practical algorithms for signal recovery. In particular, we demonstrate that it is possible to robustly and efficiently identify an unknown signal solely from phaseless Fourier measurements, a fact with potentially far-reaching implications.
Multipath-TCP in ns-3
Venue: arXiv cs.NI 2015
Year: 2015

In this paper we present our work on designing and implementing an ns-3 model for MultiPath TCP (MPTCP). Our MPTCP model closely follows MPTCP specifications, as described in RFC 6824, and supports TCP NewReno loss recovery on a per subflow basis. Subflow management is based on MPTCP's kernel implementation. We briefly describe how we integrate our MPTCP model with ns-3 and present example simulation results to showcase its working state.
Design of Raptor Codes in the Low SNR Regime with Applications in Quantum Key Distribution
Venue: arXiv cs.IT 2015
Year: 2015

The focus of this work is on the design of Raptor codes for continuous variable Quantum key distribution (CV-QKD) systems. We design a highly efficient Raptor code for very low signal to noise ratios (SNRs), which enables CV-QKD systems to operate over long distances with a significantly higher secret key rate compared to conventional fixed rate codes. The degree distribution design of Raptor codes in the low SNR regime is formulated as a linear program, where a set of optimized degree distributions are also obtained through linear programming. Simulation results show that the designed code achieves efficiencies higher than 94\% for SNRs as low as -20 dB and -30 dB. We further propose a new error reconciliation protocol for CV-QKD systems by using Raptor codes and show that it can achieve higher secret key rates over long distances compared to existing protocols.
A partition-based Summary-Graph-Driven Method for Efficient RDF Query Processing
Venue: arXiv cs.DB 2015
Year: 2015

RDF query optimization is a challenging problem. Although considerable factors and their impacts on query efficiency have been investigated, this problem still needs further investigation. We identify that decomposing query into a series of light-weight operations is also effective in boosting query processing. Considering the linked nature of RDF data, the correlations among operations should be carefully handled. In this paper, we present SGDQ, a novel framework that features a partition-based Summary Graph Driven Query for efficient query processing. Basically, SGDQ partitions data and models partitions as a summary graph. A query is decomposed into subqueries that can be answered without inter-partition processing. The final results are derived by perform summary graph matching and join the results generated by all matched subqueries. In essence, SGDQ combines the merits of graph match processing and relational join-based query implementation. It intentionally avoids maintain huge intermediate results by organizing sub-query processing in a summary graph driven fashion. Our extensive evaluations show that SGDQ is an effective framework for efficient RDF query processing. Its query performance consistently outperforms the representative state-of-the-art systems.
Improvised Broadcast Algorithm for Wireless Networks
Venue: arXiv cs.NI 2015
Year: 2015

Broadcasting problem is an important issue in the wireless networks, especially in dynamic wireless networks. In dynamic wireless networks the node density and mobility is high, due to several problems which arise during broadcasting. Two major problems faced are namely, Broadcast Storm Problem and Disconnected network problem. In a highly dense network, if information is being flooded in a loop, it could lead to broadcast storm. The broadcast storm may eventually crash the entire network and lead to loss of information. Mobility of the nodes may lead to the problem of Disconnected Network. If the two nodes sending and receiving information are mobile with different speeds, it could lead to a disconnection between them as soon as the receiver moves out of the communication range. In this paper, we are trying to solve both the problems based on our proposed algorithms.
Rules in Play: On the Complexity of Routing Tables and Firewalls
Venue: arXiv cs.NI 2015
Year: 2015

A fundamental component of networking infras- tructure is the policy, used in routing tables and firewalls. Accordingly, there has been extensive study of policies. However, the theory of such policies indicates that the size of the decision tree for a policy is very large ( O((2n)d), where the policy has n rules and examines d features of packets). If this was indeed the case, the existing algorithms to detect anomalies, conflicts, and redundancies would not be tractable for practical policies (say, n = 1000 and d = 10). In this paper, we clear up this apparent paradox. Using the concept of 'rules in play', we calculate the actual upper bound on the size of the decision tree, and demonstrate how three other factors - narrow fields, singletons, and all-matches make the problem tractable in practice. We also show how this concept may be used to solve an open problem: pruning a policy to the minimum possible number of rules, without changing its meaning.
Learning Constructive Primitives for Online Level Generation and Real-time Content Adaptation in Super Mario Bros
Venue: arXiv cs.AI 2015
Year: 2015

Procedural content generation (PCG) is of great interest to game design and development as it generates game content automatically. Motivated by the recent learning-based PCG framework and other existing PCG works, we propose an alternative approach to online content generation and adaptation in Super Mario Bros (SMB). Unlike most of existing works in SMB, our approach exploits the synergy between rule-based and learning-based methods to produce constructive primitives, quality yet controllable game segments in SMB. As a result, a complete quality game level can be generated online by integrating relevant constructive primitives via controllable parameters regarding geometrical features and procedure-level properties. Also the adaptive content can be generated in real time by dynamically selecting proper constructive primitives via an adaptation criterion, e.g., dynamic difficulty adjustment (DDA). Our approach is of several favorable properties in terms of content quality assurance, generation efficiency and controllability. Extensive simulation results demonstrate that the proposed approach can generate controllable yet quality game levels online and adaptable content for DDA in real time.
Core-satellite Graphs. Clustering, Assortativity and Spectral Properties
Venue: arXiv cs.SI 2015
Year: 2015

Core-satellite graphs (sometimes referred to as generalized friendship graphs) are an interesting class of graphs that generalize many well known types of graphs. In this paper we show that two popular clustering measures, the average Watts-Strogatz clustering coefficient and the transitivity index, diverge when the graph size increases. We also show that these graphs are disassortative. In addition, we completely describe the spectrum of the adjacency and Laplacian matrices associated with core-satellite graphs. Finally, we introduce the class of generalized core-satellite graphs, and we analyze the spectral properties of such graphs.
Estimating Subgraph Frequencies with or without Attributes from Egocentrically Sampled Data
Venue: arXiv cs.SI 2015
Year: 2015

In this paper we show how to efficiently produce unbiased estimates of subgraph frequencies from a probability sample of egocentric networks (i.e., focal nodes, their neighbors, and the induced subgraphs of ties among their neighbors). A key feature of our proposed method that differentiates it from prior methods is the use of egocentric data. Because of this, our method is suitable for estimation in large unknown graphs, is easily parallelizable, handles privacy sensitive network data (e.g. egonets with no neighbor labels), and supports counting of large subgraphs (e.g. maximal clique of size 205 in Section 6) by building on top of existing exact subgraph counting algorithms that may not support sampling. It gracefully handles a variety of sampling designs such as uniform or weighted independence or random walk sampling. Our method can be used for subgraphs that are: (i) undirected or directed; (ii) induced or non-induced; (iii) maximal or non-maximal; and (iv) potentially annotated with attributes. We compare our estimators on a variety of real-world graphs and sampling methods and provide suggestions for their use. Simulation shows that our method outperforms the state-of-the-art approach for relative subgraph frequencies by up to an order of magnitude for the same sample size. Finally, we apply our methodology to a rare sample of Facebook users across the social graph to estimate and interpret the clique size distribution and gender composition of cliques.
Enabling Multiple QR Codes in Close Proximity
Venue: arXiv cs.CY 2015
Year: 2015

Quick response codes - 2D patterns that can be scanned to access online resources - are being used in a variety of industrial and consumer applications. However, it is problematic to use multiple QR codes in close proximity: scans can fail or result in access to the wrong resource. While this problem is, strictly speaking, due to the design of the scanning software, the very large number of extant scanning applications makes changing the software a difficult logistical challenge. Instead, we describe the design of a new type of QR code that not only enables the use of multiple QR codes in close proximity, but also is compatible with existing scanning solutions. In an evaluation with 20 users, it was found that the new QR codes were as usable as traditional ones, and that they were superior for selecting one code from many. Users did have initial difficulty in discovering how to use the new QR code, so further work is required on that front. We conclude with a discussion of the pros and cons of pQR codes.
Bit Error Rate Analysis of Cooperative Beamforming for Transmitting Individual Data Streams
Venue: arXiv cs.IT 2015
Year: 2015

Cooperative beamforming (CB) has been proposed as a special case of coordinated multi-point techniques in wireless communications. In wireless sensor networks, CB can enable low power communication by allowing a collection of sensor nodes to transmit data simultaneously to a distant fusion center in one hop. Besides the traditional CB approach where all nodes need to share and transmit the same data, a more recent technique allows each node to transmit its own data while still achieving the benefits of cooperation. However, the intricacies of varying beamforming gains in the direct sequence spread spectrum with binary frequency shift keying multiple access scheme used in this context need to be taken into account when evaluating the performance of this beamforming technique. In this paper, we take the first step towards a more comprehensive understanding of this individual-data CB technique by proposing a best suited decoding scheme and analyzing its bit error rate (BER) performance over an additive white Gaussian noise channel. Through analytical expressions and simulation results BER curves are drawn and the achieved performance improvement offered by the CB gain is quantified.
Weak Resilience of Networked Control Systems
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we propose a method to establish a networked control system that maintains its stability in the presence of certain undesirable incidents on local controllers. We call such networked control systems weakly resilient. We first derive a necessary and sufficient condition for the weak resilience of networked systems. Networked systems do not generally satisfy this condition. Therefore, we provide a method for designing a compensator which ensures the weak resilience of the compensated system. Finally, we illustrate the efficiency of the proposed method by a power system example based on the IEEE 14-bus test system.
Quantum Oracle Classification - The Case of Group Structure
Venue: arXiv cs.CC 2015
Year: 2015

The Quantum Oracle Classification (QOC) problem is to classify a function, given only quantum black box access, into one of several classes without necessarily determining the entire function. Generally, QOC captures a very wide range of problems in quantum query complexity. However, relatively little is known about many of these problems. In this work, we analyze the a subclass of the QOC problems where there is a group structure. That is, suppose the range of the unknown function A is a commutative group G, which induces a commutative group law over the entire function space. Then we consider the case where A is drawn uniformly at random from some subgroup A of the function space. Moreover, there is a homomorpism f on A, and the goal is to determine f(A). This class of problems is very general, and covers several interesting cases, such as oracle evaluation; polynomial interpolation, evaluation, and extrapolation; and parity. These problems are important in the study of message authentication codes in the quantum setting, and may have other applications. We exactly characterize the quantum query complexity of every instance of QOC with group structure in terms of a particular counting problem. That is, we provide an algorithm for this general class of problems whose success probability is determined by the solution to the counting problem, and prove its exact optimality. Unfortunately, solving this counting problem in general is a non-trivial task, and we resort to analyzing special cases. Our bounds unify some existing results, such as the existing oracle evaluation and parity bounds. In the case of polynomial interpolation and evaluation, our bounds give new results for secret sharing and information theoretic message authentication codes in the quantum setting.
Canonical Representatives of Morphic Permutations
Venue: arXiv cs.DM 2015
Year: 2015

An infinite permutation can be defined as a linear ordering of the set of natural numbers. In particular, an infinite permutation can be constructed with an aperiodic infinite word over $\{0,\ldots,q-1\}$ as the lexicographic order of the shifts of the word. In this paper, we discuss the question if an infinite permutation defined this way admits a canonical representative, that is, can be defined by a sequence of numbers from [0, 1], such that the frequency of its elements in any interval is equal to the length of that interval. We show that a canonical representative exists if and only if the word is uniquely ergodic, and that is why we use the term ergodic permutations. We also discuss ways to construct the canonical representative of a permutation defined by a morphic word and generalize the construction of Makarov, 2009, for the Thue-Morse permutation to a wider class of infinite words.
A Lifting Construction for Scalar Linear Index Codes
Venue: arXiv cs.IT 2015
Year: 2015

This paper deals with scalar linear index codes for canonical multiple unicast index coding problems where there is a source with K messages and there are K receivers each wanting a unique message and having symmetric (with respect to the receiver index) antidotes (side information). Optimal scalar linear index codes for several such instances of this class of problems have been reported in \cite{MRRarXiv}. These codes can be viewed as special cases of the symmetric unicast index coding problems discussed in \cite{MCJ}. In this paper a lifting construction is given which constructs a sequence of multiple unicast index problems starting from a given multiple unicast index coding problem. Also, it is shown that if an optimal scalar linear index code is known for the problem given starting problem then optimal scalar linear index codes can be obtained from the known code for all the problems arising from the proposed lifting construction. For several of the known classes of multiple unicast problems our construction is used to obtain several sequences of multiple unicast problem with optimal scalar linear index codes.
No Need for Black Chambers: Testing TLS in the E-mail Ecosystem at Large
Venue: arXiv cs.CR 2015
Year: 2015

TLS is the most widely used cryptographic protocol on the Internet. While many recent studies focused on its use in HTTPS, none so far analyzed TLS usage in e-mail related protocols, which often carry highly sensitive information. Since end-to-end encryption mechanisms like PGP are seldomly used, today confidentiality in the e-mail ecosystem is mainly based on the encryption of the transport layer. A well-positioned attacker may be able to intercept plaintext passively and at global scale. In this paper we are the first to present a scalable methodology to assess the state of security mechanisms in the e-mail ecosystem using commodity hardware and open-source software. We draw a comprehensive picture of the current state of every e-mail related TLS configuration for the entire IPv4 range. We collected and scanned a massive data-set of 20 million IP/port combinations of all related protocols (SMTP, POP3, IMAP) and legacy ports. Over a time span of approx. three months we conducted more than 10 billion TLS handshakes. Additionally, we show that securing server-to-server communication using e.g. SMTP is inherently more difficult than securing client-to-server communication. Lastly, we analyze the volatility of TLS certificates and trust anchors in the e-mail ecosystem and argue that while the overall trend points in the right direction, there are still many steps needed towards secure e-mail.
In-Situ Data Analysis of Protein Folding Trajectories
Venue: arXiv cs.CE 2015
Year: 2015

The transition from petascale to exascale computers is characterized by substantial changes in the computer architectures and technologies. The research community relying on computational simulations is being forced to revisit the algorithms for data generation and analysis due to various concerns, such as higher degrees of concurrency, deeper memory hierarchies, substantial I/O and communication constraints. Simulations today typically save all data to analyze later. Simulations at the exascale will require us to analyze data as it is generated and save only what is really needed for analysis, which must be performed predominately in-situ, i.e., executed sufficiently fast locally, limiting memory and disk usage, and avoiding the need to move large data across nodes. In this paper, we present a distributed method that enables in-situ data analysis for large protein folding trajectory datasets. Traditional trajectory analysis methods currently follow a centralized approach that moves the trajectory datasets to a centralized node and processes the data only after simulations have been completed. Our method, on the other hand, captures conformational information in-situ using local data only while reducing the storage space needed for the part of the trajectory under consideration. This method processes the input trajectory data in one pass, breaks from the centralized approach of traditional analysis, avoids the movement of trajectory data, and still builds the global knowledge on the formation of individual $α$-helices or $β$-strands as trajectory frames are generated.
Testing Visual Attention in Dynamic Environments
Venue: arXiv cs.LG 2015
Year: 2015

We investigate attention as the active pursuit of useful information. This contrasts with attention as a mechanism for the attenuation of irrelevant information. We also consider the role of short-term memory, whose use is critical to any model incapable of simultaneously perceiving all information on which its output depends. We present several simple synthetic tasks, which become considerably more interesting when we impose strong constraints on how a model can interact with its input, and on how long it can take to produce its output. We develop a model with a different structure from those seen in previous work, and we train it using stochastic variational inference with a learned proposal distribution.
Estimation of the direct-to-reverberant Energy Ratio using a spherical microphone array
Venue: arXiv cs.SD 2015
Year: 2015

This paper proposes a practical approach to estimate the direct-to-reverberant energy ratio (DRR) using a spherical microphone array without having knowledge of the source signal. We base our estimation on a theoretical relationship between the DRR and the coherence estimation function between coincident pressure and particle velocity. We discuss the proposed method's ability to estimate the DRR in a wide variety of room sizes, reverberation times and source receiver distances with appropriate examples. Test results show that the method can estimate the room DRR for frequencies between 199 - 2511 Hz, with $\pm$ 3 dB accuracy.
Robust Linear Temporal Logic
Venue: arXiv cs.LO 2015
Year: 2015

Although it is widely accepted that every system should be robust, in the sense that "small" violations of environment assumptions should lead to "small" violations of system guarantees, it is less clear how to make this intuitive notion of robustness mathematically precise. In this paper, we address this problem by developing a robust version of Linear Temporal Logic (LTL), which we call robust LTL and denote by rLTL. Formulas in rLTL are syntactically identical to LTL formulas but are endowed with a many-valued semantics that encodes robustness. In particular, the semantics of the rLTL formula $φ\Rightarrow ψ$ is such that a "small" violation of the environment assumption $φ$ is guaranteed to only produce a "small" violation of the system guarantee $ψ$. In addition to introducing rLTL, we study the verification and synthesis problems for this logic: similarly to LTL, we show that both problems are decidable, that the verification problem can be solved in time exponential in the number of subformulas of the rLTL formula at hand, and that the synthesis problem can be solved in doubly exponential time.
Prediction-Adaptation-Correction Recurrent Neural Networks for Low-Resource Language Speech Recognition
Venue: arXiv cs.CL 2015
Year: 2015

In this paper, we investigate the use of prediction-adaptation-correction recurrent neural networks (PAC-RNNs) for low-resource speech recognition. A PAC-RNN is comprised of a pair of neural networks in which a {\it correction} network uses auxiliary information given by a {\it prediction} network to help estimate the state probability. The information from the correction network is also used by the prediction network in a recurrent loop. Our model outperforms other state-of-the-art neural networks (DNNs, LSTMs) on IARPA-Babel tasks. Moreover, transfer learning from a language that is similar to the target language can help improve performance further.
Turing's Red Flag
Venue: arXiv cs.AI 2015
Year: 2015

Sometime in the future we will have to deal with the impact of AI's being mistaken for humans. For this reason, I propose that any autonomous system should be designed so that it is unlikely to be mistaken for anything besides an autonomous sysem, and should identify itself at the start of any interaction with another agent.