OpenRaiser/Intern-Atlas huggingface dataset:
Decidable Models of Recursive Asynchronous Concurrency
Venue: arXiv cs.LO 2015
Year: 2015

Asynchronously communicating pushdown systems (ACPS) that satisfy the empty-stack constraint (a pushdown process may receive only when its stack is empty) are a popular decidable model for recursive programs with asynchronous atomic procedure calls. We study a relaxation of the empty-stack constraint for ACPS that permits concurrency and communication actions at any stack height, called the shaped stack constraint, thus enabling a larger class of concurrent programs to be modelled. We establish a close connection between ACPS with shaped stacks and a novel extension of Petri nets: Nets with Nested Coloured Tokens (NNCTs). Tokens in NNCTs are of two types: simple and complex. Complex tokens carry an arbitrary number of coloured tokens. The rules of NNCT can synchronise complex and simple tokens, inject coloured tokens into a complex token, and eject all tokens of a specified set of colours to predefined places. We show that the coverability problem for NNCTs is Tower-complete. To our knowledge, NNCT is the first extension of Petri nets, in the class of nets with an infinite set of token types, that has primitive recursive coverability. This result implies Tower-completeness of coverability for ACPS with shaped stacks.
Achievable and Converse bounds over a general channel and general decoding metric
Venue: arXiv cs.IT 2015
Year: 2015

Achievable and converse bounds for general channels and mismatched decoding are derived. The direct (achievable) bound is derived using random coding and the analysis is tight up to factor 2. The converse is given in term of the achievable bound and the factor between them is given. This gives performance of the best rate-R code with possible mismatched decoding metric over a general channel, up to the factor that is identified. In the matched case we show that the converse equals the minimax meta-converse of Polyanskiy et al.
Sparse Signal Processing Concepts for Efficient 5G System Design
Venue: arXiv cs.IT 2015
Year: 2015

As it becomes increasingly apparent that 4G will not be able to meet the emerging demands of future mobile communication systems, the question what could make up a 5G system, what are the crucial challenges and what are the key drivers is part of intensive, ongoing discussions. Partly due to the advent of compressive sensing, methods that can optimally exploit sparsity in signals have received tremendous attention in recent years. In this paper we will describe a variety of scenarios in which signal sparsity arises naturally in 5G wireless systems. Signal sparsity and the associated rich collection of tools and algorithms will thus be a viable source for innovation in 5G wireless system design. We will discribe applications of this sparse signal processing paradigm in MIMO random access, cloud radio access networks, compressive channel-source network coding, and embedded security. We will also emphasize important open problem that may arise in 5G system design, for which sparsity will potentially play a key role in their solution.
Rank-Based Inference over Web Databases
Venue: arXiv cs.DB 2015
Year: 2015

In recent years, there has been much research in Ranked Retrieval model in structured databases, especially those in web databases. With this model, a search query returns top-k tuples according to not just exact matches of selection conditions, but a suitable ranking function. This paper studies a novel problem on the privacy implications of database ranking. The motivation is a novel yet serious privacy leakage we found on real-world web databases which is caused by the ranking function design. Many such databases feature private attributes - e.g., a social network allows users to specify certain attributes as only visible to him/herself, but not to others. While these websites generally respect the privacy settings by not directly displaying private attribute values in search query answers, many of them nevertheless take into account such private attributes in the ranking function design. The conventional belief might be that tuple ranks alone are not enough to reveal the private attribute values. Our investigation, however, shows that this is not the case in reality. To address the problem, we introduce a taxonomy of the problem space with two dimensions, (1) the type of query interface and (2) the capability of adversaries. For each subspace, we develop a novel technique which either guarantees the successful inference of private attributes, or does so for a significant portion of real-world tuples. We demonstrate the effectiveness and efficiency of our techniques through theoretical analysis, extensive experiments over real-world datasets, as well as successful online attacks over websites with tens to hundreds of millions of users - e.g., Amazon Goodreads and Renren.com.
Optimization of Discrete-parameter Multiprocessor Systems using a Novel Ergodic Interpolation Technique
Venue: arXiv cs.DC 2015
Year: 2015

Modern multi-core systems have a large number of design parameters, most of which are discrete-valued, and this number is likely to keep increasing as chip complexity rises. Further, the accurate evaluation of a potential design choice is computationally expensive because it requires detailed cycle-accurate system simulation. If the discrete parameter space can be embedded into a larger continuous parameter space, then continuous space techniques can, in principle, be applied to the system optimization problem. Such continuous space techniques often scale well with the number of parameters. We propose a novel technique for embedding the discrete parameter space into an extended continuous space so that continuous space techniques can be applied to the embedded problem using cycle accurate simulation for evaluating the objective function. This embedding is implemented using simulation-based ergodic interpolation, which, unlike spatial interpolation, produces the interpolated value within a single simulation run irrespective of the number of parameters. We have implemented this interpolation scheme in a cycle-based system simulator. In a characterization study, we observe that the interpolated performance curves are continuous, piece-wise smooth, and have low statistical error. We use the ergodic interpolation-based approach to solve a large multi-core design optimization problem with 31 design parameters. Our results indicate that continuous space optimization using ergodic interpolation-based embedding can be a viable approach for large multi-core design optimization problems.
Tiling rectangles with holey polyominoes
Venue: arXiv cs.CG 2015
Year: 2015

We present a new type of polyominoes that can have transparent squares (holes). We show how these polyominoes can tile rectangles and we categorise them according to their tiling ability. We were able to categorise all but 6 polyominoes with 5 or fewer visible squares.
HypTrails: A Bayesian Approach for Comparing Hypotheses About Human Trails on the Web
Venue: arXiv cs.SI 2015
Year: 2015

When users interact with the Web today, they leave sequential digital trails on a massive scale. Examples of such human trails include Web navigation, sequences of online restaurant reviews, or online music play lists. Understanding the factors that drive the production of these trails can be useful for e.g., improving underlying network structures, predicting user clicks or enhancing recommendations. In this work, we present a general approach called HypTrails for comparing a set of hypotheses about human trails on the Web, where hypotheses represent beliefs about transitions between states. Our approach utilizes Markov chain models with Bayesian inference. The main idea is to incorporate hypotheses as informative Dirichlet priors and to leverage the sensitivity of Bayes factors on the prior for comparing hypotheses with each other. For eliciting Dirichlet priors from hypotheses, we present an adaption of the so-called (trial) roulette method. We demonstrate the general mechanics and applicability of HypTrails by performing experiments with (i) synthetic trails for which we control the mechanisms that have produced them and (ii) empirical trails stemming from different domains including website navigation, business reviews and online music played. Our work expands the repertoire of methods available for studying human trails on the Web.
Query-driven Data Completeness Management (PhD Thesis)
Venue: arXiv cs.DB 2015
Year: 2015

Knowledge about data completeness is essentially in data-supported decision making. In this thesis we present a framework for metadata-based assessment of database completeness. We discuss how to express information about data completeness and how to use such information to draw conclusions about the completeness of query answers. In particular, we introduce formalisms for stating completeness for parts of relational databases. We then present techniques for drawing inferences between such statements and statements about the completeness of query answers, and show how the techniques can be extended to databases that contain null values. We show that the framework for relational databases can be transferred to RDF data, and that a similar framework can also be applied to spatial data. We also discuss how completeness information can be verified over processes, and introduce a data-aware process model that allows this verification.
Can Technology Life-Cycles Be Indicated by Diversity in Patent Classifications? The crucial role of variety
Venue: arXiv cs.DL 2015
Year: 2015

In a previous study of patent classifications in nine material technologies for photovoltaic cells, Leydesdorff et al. (2015) reported cyclical patterns in the longitudinal development of Rao-Stirling diversity. We suggested that these cyclical patterns can be used to indicate technological life-cycles. Upon decomposition, however, the cycles are exclusively due to increases and decreases in the variety of the classifications, and not to disparity or technological distance, measured as (1 - cosine). A single frequency component can accordingly be shown in the periodogram. Furthermore, the cyclical patterns are associated with the numbers of inventors in the respective technologies. Sometimes increased variety leads to a boost in the number of inventors, but in early phases--when the technology is still under constructio--it can also be the other way round. Since the development of the cycles thus seems independent of technological distances among the patents, the visualization in terms of patent maps can be considered as addressing an analytically different set of research questions.
Modeling Populations of Thermostatic Loads with Switching Rate Actuation
Venue: arXiv cs.SY 2015
Year: 2015

We model thermostatic devices using a stochastic hybrid description, and introduce an external actuation mechanism that creates random switch events in the discrete dynamics. We then conjecture the form of the Fokker-Planck equation and successfully verify it numerically using Monte Carlo simulations. The actuation mechanism and subsequent modeling result are relevant for power system operation.
Polynomial Fourier Domain as a Domain of Signal Sparsity
Venue: arXiv cs.IT 2015
Year: 2015

A compressive sensing (CS) reconstruction method for polynomial phase signals is proposed in this paper. It relies on the Polynomial Fourier transform, which is used to establish a relationship between the observation and sparsity domain. Polynomial phase signals are not sparse in commonly used domains such as Fourier or wavelet domain. Therefore, for polynomial phase signals standard CS algorithms applied in these transformation domains cannot provide satisfactory results. In that sense, the Polynomial Fourier transform is used to ensure sparsity. The proposed approach is generalized using time-frequency representations obtained by the Local Polynomial Fourier transform (LPFT). In particular, the first-order LPFT can produce linear time-frequency representation for chirps. It provides revealing signal local behavior, which leads to sparse representation. The theory is illustrated on examples.
Galois Transformers and Modular Abstract Interpreters
Venue: arXiv cs.PL 2015
Year: 2015

The design and implementation of static analyzers has become increasingly systematic. Yet for a given language or analysis feature, it often requires tedious and error prone work to implement an analyzer and prove it sound. In short, static analysis features and their proofs of soundness do not compose well, causing a dearth of reuse in both implementation and metatheory. We solve the problem of systematically constructing static analyzers by introducing Galois transformers: monad transformers that transport Galois connection properties. In concert with a monadic interpreter, we define a library of monad transformers that implement building blocks for classic analysis parameters like context, path, and heap (in)sensitivity. Moreover, these can be composed together independent of the language being analyzed. Significantly, a Galois transformer can be proved sound once and for all, making it a reusable analysis component. As new analysis features and abstractions are developed and mixed in, soundness proofs need not be reconstructed, as the composition of a monad transformer stack is sound by virtue of its constituents. Galois transformers provide a viable foundation for reusable and composable metatheory for program analysis. Finally, these Galois transformers shift the level of abstraction in analysis design and implementation to a level where non-specialists have the ability to synthesize sound analyzers over a number of parameters.
How to Scale Up Kernel Methods to Be As Good As Deep Neural Nets
Venue: arXiv cs.LG 2015
Year: 2015

The computational complexity of kernel methods has often been a major barrier for applying them to large-scale learning problems. We argue that this barrier can be effectively overcome. In particular, we develop methods to scale up kernel models to successfully tackle large-scale learning problems that are so far only approachable by deep learning architectures. Based on the seminal work by Rahimi and Recht on approximating kernel functions with features derived from random projections, we advance the state-of-the-art by proposing methods that can efficiently train models with hundreds of millions of parameters, and learn optimal representations from multiple kernels. We conduct extensive empirical studies on problems from image recognition and automatic speech recognition, and show that the performance of our kernel models matches that of well-engineered deep neural nets (DNNs). To the best of our knowledge, this is the first time that a direct comparison between these two methods on large-scale problems is reported. Our kernel methods have several appealing properties: training with convex optimization, cost for training a single model comparable to DNNs, and significantly reduced total cost due to fewer hyperparameters to tune for model selection. Our contrastive study between these two very different but equally competitive models sheds light on fundamental questions such as how to learn good representations.
Scalable Mining of Daily Behavioral Patterns in Context Sensing Life-Log Data
Venue: arXiv cs.HC 2015
Year: 2015

Despite the advent of wearable devices and the proliferation of smartphones, there still is no ideal platform that can continuously sense and precisely collect all available contextual information. Ideally, mobile sensing data collection approaches should deal with uncertainty and data loss originating from software and hardware restrictions. We have conducted life logging data collection experiments from 35 users and created a rich dataset (9.26 million records) to represent the real-world deployment issues of mobile sensing systems. We create a novel set of algorithms to identify human behavioral motifs while considering the uncertainty of collected data objects. Our work benefits from combinations of sensors available on a device and identifies behavioral patterns with a temporal granularity similar to human time perception. Employing a combination of sensors rather than focusing on only one sensor can handle uncertainty by neglecting sensor data that is not available and focusing instead on available data. Moreover, by experimenting on two real, large datasets, we demonstrate that using a sliding window significantly improves the scalability of our algorithms, which can be used by applications for small devices, such as smartphones and wearables.
Quantifying Redundant Information in Predicting a Target Random Variable
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers the problem of defining a measure of redundant information that quantifies how much common information two or more random variables specify about a target random variable. We discussed desired properties of such a measure, and propose new measures with some desirable properties.
Weighted automata on infinite words in the context of Attacker-Defender games
Venue: arXiv cs.FL 2015
Year: 2015

We consider infinite-state Attacker-Defender games with reachability objectives. The results of the paper are twofold. Firstly we prove a new language-theoretic result for weighted automata on infinite words and show its encoding into the framework of Attacker-Defender games. Secondly we use this novel concept to prove undecidability for checking existence of a winning strategy in several low-dimensional mathematical games including vector reachability games, word games and braid games.
Speed Partitioning for Indexing Moving Objects
Venue: arXiv cs.DB 2015
Year: 2015

Indexing moving objects has been extensively studied in the past decades. Moving objects, such as vehicles and mobile device users, usually exhibit some patterns on their velocities, which can be utilized for velocity-based partitioning to improve performance of the indexes. Existing velocity-based partitioning techniques rely on some kinds of heuristics rather than analytically calculate the optimal solution. In this paper, we propose a novel speed partitioning technique based on a formal analysis over speed values of the moving objects. We first show that speed partitioning will significantly reduce the search space expansion which has direct impacts on query performance of the indexes. Next we formulate the optimal speed partitioning problem based on search space expansion analysis and then compute the optimal solution using dynamic programming. We then build the partitioned indexing system where queries are duplicated and processed in each index partition. Extensive experiments demonstrate that our method dramatically improves the performance of indexes for moving objects and outperforms other state-of-the-art velocity-based partitioning approaches.
Fast Iteratively Reweighted Least Squares Algorithms for Analysis-Based Sparsity Reconstruction
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we propose a novel algorithm for analysis-based sparsity reconstruction. It can solve the generalized problem by structured sparsity regularization with an orthogonal basis and total variation regularization. The proposed algorithm is based on the iterative reweighted least squares (IRLS) model, which is further accelerated by the preconditioned conjugate gradient method. The convergence rate of the proposed algorithm is almost the same as that of the traditional IRLS algorithms, that is, exponentially fast. Moreover, with the specifically devised preconditioner, the computational cost for each iteration is significantly less than that of traditional IRLS algorithms, which enables our approach to handle large scale problems. In addition to the fast convergence, it is straightforward to apply our method to standard sparsity, group sparsity, overlapping group sparsity and TV based problems. Experiments are conducted on a practical application: compressive sensing magnetic resonance imaging. Extensive results demonstrate that the proposed algorithm achieves superior performance over 14 state-of-the-art algorithms in terms of both accuracy and computational cost.
An Online Decoding Schedule Generating Algorithm for Successive Cancellation Decoder of Polar Codes
Venue: arXiv cs.IT 2015
Year: 2015

Successive cancellation (SC) is the first and widely known decoder of polar codes, which has received a lot of attentions recently. However, its decoding schedule generating algorithms are still primitive, which are not only complex but also offline. This paper proposes a simple and online algorithm to generate the decoding schedule of SC decoder. Firstly, the dependencies among likelihood ratios (LR) are explored, which lead to the discovery of a sharing factor. Secondly, based on the online calculation of the sharing factor, the proposed algorithm is presented, which is neither based on the depth-first traversal of the scheduling tree nor based on the recursive construction. As shown by the comparisons among the proposed algorithm and existed algorithms, the proposed algorithm has advantages of the online feature and the far less memory taken by the decoding schedule.
Statistical Recovery of Simultaneously Sparse Time-Varying Signals from Multiple Measurement Vectors
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we propose a new sparse signal recovery algorithm, referred to as sparse Kalman tree search (sKTS), that provides a robust reconstruction of the sparse vector when the sequence of correlated observation vectors are available. The proposed sKTS algorithm builds on expectation-maximization (EM) algorithm and consists of two main operations: 1) Kalman smoothing to obtain the a posteriori statistics of the source signal vectors and 2) greedy tree search to estimate the support of the signal vectors. Through numerical experiments, we demonstrate that the proposed sKTS algorithm is effective in recovering the sparse signals and performs close to the Oracle (genie-based) Kalman estimator.
Stochastic Block Transition Models for Dynamic Networks
Venue: arXiv cs.SI 2015
Year: 2015

There has been great interest in recent years on statistical models for dynamic networks. In this paper, I propose a stochastic block transition model (SBTM) for dynamic networks that is inspired by the well-known stochastic block model (SBM) for static networks and previous dynamic extensions of the SBM. Unlike most existing dynamic network models, it does not make a hidden Markov assumption on the edge-level dynamics, allowing the presence or absence of edges to directly influence future edge probabilities while retaining the interpretability of the SBM. I derive an approximate inference procedure for the SBTM and demonstrate that it is significantly better at reproducing durations of edges in real social network data.
Infinite games with finite knowledge gaps
Venue: arXiv cs.GT 2015
Year: 2015

Infinite games where several players seek to coordinate under imperfect information are deemed to be undecidable, unless the information is hierarchically ordered among the players. We identify a class of games for which joint winning strategies can be constructed effectively without restricting the direction of information flow. Instead, our condition requires that the players attain common knowledge about the actual state of the game over and over again along every play. We show that it is decidable whether a given game satisfies the condition, and prove tight complexity bounds for the strategy synthesis problem under $ω$-regular winning conditions given by parity automata.