OpenRaiser/Intern-Atlas huggingface dataset:
Stochastic Parity Games on Lossy Channel Systems
Venue: arXiv cs.LO 2015
Year: 2015

We give an algorithm for solving stochastic parity games with almost-sure winning conditions on {\it lossy channel systems}, under the constraint that both players are restricted to finite-memory strategies. First, we describe a general framework, where we consider the class of 2 1/2-player games with almost-sure parity winning conditions on possibly infinite game graphs, assuming that the game contains a {\it finite attractor}. An attractor is a set of states (not necessarily absorbing) that is almost surely re-visited regardless of the players' decisions. We present a scheme that characterizes the set of winning states for each player. Then, we instantiate this scheme to obtain an algorithm for {\it stochastic game lossy channel systems}.
Large Vocabulary Arabic Online Handwriting Recognition System
Venue: arXiv cs.CV 2015
Year: 2015

Arabic handwriting is a consonantal and cursive writing. The analysis of Arabic script is further complicated due to obligatory dots/strokes that are placed above or below most letters and usually written delayed in order. Due to ambiguities and diversities of writing styles, recognition systems are generally based on a set of possible words called lexicon. When the lexicon is small, recognition accuracy is more important as the recognition time is minimal. On the other hand, recognition speed as well as the accuracy are both critical when handling large lexicons. Arabic is rich in morphology and syntax which makes its lexicon large. Therefore, a practical online handwriting recognition system should be able to handle a large lexicon with reasonable performance in terms of both accuracy and time. In this paper, we introduce a fully-fledged Hidden Markov Model (HMM) based system for Arabic online handwriting recognition that provides solutions for most of the difficulties inherent in recognizing the Arabic script. A new preprocessing technique for handling the delayed strokes is introduced. We use advanced modeling techniques for building our recognition system from the training data to provide more detailed representation for the differences between the writing units, minimize the variances between writers in the training data and have a better representation for the features space. System results are enhanced using an additional post-processing step with a higher order language model and cross-word HMM models. The system performance is evaluated using two different databases covering small and large lexicons. Our system outperforms the state-of-art systems for the small lexicon database. Furthermore, it shows promising results (accuracy and time) when supporting large lexicon with the possibility for adapting the models for specific writers to get even better results.
Olfactory Signal Processing
Venue: arXiv cs.IT 2015
Year: 2015

Olfaction, the sense of smell, has received scant attention from a signal processing perspective in comparison to audition and vision. In this paper, we develop a signal processing paradigm for olfactory signals based on new scientific discoveries including the psychophysics concept of olfactory white. We describe a framework for predicting the perception of odorant compounds from their physicochemical features and use the prediction as a foundation for several downstream processing tasks. We detail formulations for odor cancellation and food steganography, and provide real-world empirical examples for the two tasks. We also discuss adaptive filtering and other olfactory signal processing tasks at a high level.
Gowers Norm, Function Limits, and Parameter Estimation
Venue: arXiv cs.CC 2015
Year: 2015

Let $\{f_i:\mathbb{F}_p^i \to \{0,1\}\}$ be a sequence of functions, where $p$ is a fixed prime and $\mathbb{F}_p$ is the finite field of order $p$. The limit of the sequence can be syntactically defined using the notion of ultralimit. Inspired by the Gowers norm, we introduce a metric over limits of function sequences, and study properties of it. One application of this metric is that it provides a characterization of affine-invariant parameters of functions that are constant-query estimable. Using this characterization, we show that the property of being a function of a constant number of low-degree polynomials and a constant number of factored polynomials (of arbitrary degrees) is constant-query testable if it is closed under blowing-up. Examples of this property include the property of having a constant spectral norm and degree-structural properties with rank conditions.
Structural Parameterizations of the Mixed Chinese Postman Problem
Venue: arXiv cs.CC 2015
Year: 2015

In the Mixed Chinese Postman Problem (MCPP), given a weighted mixed graph $G$ ($G$ may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each edge and arc at least once. The MCPP parameterized by the number of edges in $G$ or the number of arcs in $G$ is fixed-parameter tractable as proved by van Bevern {\em et al.} (in press) and Gutin, Jones and Sheng (ESA 2014), respectively. In this paper, we consider the unweighted version of MCPP. Solving an open question of van Bevern {\em et al.} (in press), we show that somewhat unexpectedly MCPP parameterized by the (undirected) treewidth of $G$ is W[1]-hard. In fact, we prove that even the MCPP parameterized by the pathwidth of $G$ is W[1]-hard. On the positive side, we show that the unweighted version of MCPP parameterized by tree-depth is fixed-parameter tractable. We are unaware of any natural graph parameters between pathwidth and tree-depth and so our results provide a dichotomy of the complexity of MCPP. Furthermore, we believe that MCPP is the first problem known to be W[1]-hard with respect to treewidth but FPT with respect to tree-depth.
Performance Engineering of the Kernel Polynomial Method on Large-Scale CPU-GPU Systems
Venue: arXiv cs.CE 2015
Year: 2015

The Kernel Polynomial Method (KPM) is a well-established scheme in quantum physics and quantum chemistry to determine the eigenvalue density and spectral properties of large sparse matrices. In this work we demonstrate the high optimization potential and feasibility of peta-scale heterogeneous CPU-GPU implementations of the KPM. At the node level we show that it is possible to decouple the sparse matrix problem posed by KPM from main memory bandwidth both on CPU and GPU. To alleviate the effects of scattered data access we combine loosely coupled outer iterations with tightly coupled block sparse matrix multiple vector operations, which enables pure data streaming. All optimizations are guided by a performance analysis and modelling process that indicates how the computational bottlenecks change with each optimization step. Finally we use the optimized node-level KPM with a hybrid-parallel framework to perform large scale heterogeneous electronic structure calculations for novel topological materials on a petascale-class Cray XC30 system.
Non-Orthogonal Multiple Access for Degraded Broadcast Channels: RA-CEMA
Venue: arXiv cs.IT 2015
Year: 2015

A new non-orthogonal multiple access scheme performing simultaneous transmission to multiple users characterized by different signal-to-noise ratios is proposed. Different users are multiplexed by storing their codewords into a multiplexing matrix according to properly designed patterns and then mapping the columns of the matrix onto the symbols of a higher-order constellation. At the receiver, an interference cancellation algorithm is employed in order to achieve a higher spectral efficiency than orthogonal user multiplexing. Rate-Adaptive Constellation Expansion Multiple Access (RA-CEMA) is an alternative to conventional superposition coding as a solution for transmission on the degraded broadcast channel. It combines the benefits of an increased spectral efficiency with the advantages of reusing the coding and modulation schemes already used in contemporary communication systems, thereby facilitating its adoption in standards.
Cooperative Non-Orthogonal Multiple Access in 5G Systems
Venue: arXiv cs.IT 2015
Year: 2015

Non-orthogonal multiple access (NOMA) has recently received considerable attention as a promising candidate for 5G systems. A key feature of NOMA is that users with better channel conditions have prior information about the messages of the other users. This prior knowledge is fully exploited in this paper, where a cooperative NOMA scheme is proposed. Outage probability and diversity order achieved by this cooperative NOMA scheme are analyzed, and an approach based on user pairing is also proposed to reduce system complexity in practice.
Protecting Locations with Differential Privacy under Temporal Correlations
Venue: arXiv cs.DB 2015
Year: 2015

Concerns on location privacy frequently arise with the rapid development of GPS enabled devices and location-based applications. While spatial transformation techniques such as location perturbation or generalization have been studied extensively, most techniques rely on syntactic privacy models without rigorous privacy guarantee. Many of them only consider static scenarios or perturb the location at single timestamps without considering temporal correlations of a moving user's locations, and hence are vulnerable to various inference attacks. While differential privacy has been accepted as a standard for privacy protection, applying differential privacy in location based applications presents new challenges, as the protection needs to be enforced on the fly for a single user and needs to incorporate temporal correlations between a user's locations. In this paper, we propose a systematic solution to preserve location privacy with rigorous privacy guarantee. First, we propose a new definition, "$δ$-location set" based differential privacy, to account for the temporal correlations in location data. Second, we show that the well known $\ell_1$-norm sensitivity fails to capture the geometric sensitivity in multidimensional space and propose a new notion, sensitivity hull, based on which the error of differential privacy is bounded. Third, to obtain the optimal utility we present a planar isotropic mechanism (PIM) for location perturbation, which is the first mechanism achieving the lower bound of differential privacy. Experiments on real-world datasets also demonstrate that PIM significantly outperforms baseline approaches in data utility.
PSBS: Practical Size-Based Scheduling
Venue: arXiv cs.DC 2015
Year: 2015

Size-based schedulers have very desirable performance properties: optimal or near-optimal response time can be coupled with strong fairness guarantees. Despite this, such systems are very rarely implemented in practical settings, because they require knowing a priori the amount of work needed to complete jobs: this assumption is very difficult to satisfy in concrete systems. It is definitely more likely to inform the system with an estimate of the job sizes, but existing studies point to somewhat pessimistic results if existing scheduler policies are used based on imprecise job size estimations. We take the goal of designing scheduling policies that are explicitly designed to deal with inexact job sizes: first, we show that existing size-based schedulers can have bad performance with inexact job size information when job sizes are heavily skewed; we show that this issue, and the pessimistic results shown in the literature, are due to problematic behavior when large jobs are underestimated. Once the problem is identified, it is possible to amend existing size-based schedulers to solve the issue. We generalize FSP -- a fair and efficient size-based scheduling policy -- in order to solve the problem highlighted above; in addition, our solution deals with different job weights (that can be assigned to a job independently from its size). We provide an efficient implementation of the resulting protocol, which we call Practical Size-Based Scheduler (PSBS). Through simulations evaluated on synthetic and real workloads, we show that PSBS has near-optimal performance in a large variety of cases with inaccurate size information, that it performs fairly and it handles correctly job weights. We believe that this work shows that PSBS is indeed pratical, and we maintain that it could inspire the design of schedulers in a wide array of real-world use cases.
Constructions and Properties of Linear Locally Repairable Codes
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, locally repairable codes with all-symbol locality are studied. Methods to modify already existing codes are presented. Also, it is shown that with high probability, a random matrix with a few extra columns guaranteeing the locality property, is a generator matrix for a locally repairable code with a good minimum distance. The proof of this also gives a constructive method to find locally repairable codes. Constructions are given of three infinite classes of optimal vector-linear locally repairable codes over an alphabet of small size, not depending on the size of the code.
Contract-Based General-Purpose GPU Programming
Venue: arXiv cs.DC 2015
Year: 2015

Using GPUs as general-purpose processors has revolutionized parallel computing by offering, for a large and growing set of algorithms, massive data-parallelization on desktop machines. An obstacle to widespread adoption, however, is the difficulty of programming them and the low-level control of the hardware required to achieve good performance. This paper suggests a programming library, SafeGPU, that aims at striking a balance between programmer productivity and performance, by making GPU data-parallel operations accessible from within a classical object-oriented programming language. The solution is integrated with the design-by-contract approach, which increases confidence in functional program correctness by embedding executable program specifications into the program text. We show that our library leads to modular and maintainable code that is accessible to GPGPU non-experts, while providing performance that is comparable with hand-written CUDA code. Furthermore, runtime contract checking turns out to be feasible, as the contracts can be executed on the GPU.
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
Venue: arXiv cs.DS 2015
Year: 2015

We show how to approximate a data matrix $\mathbf{A}$ with a much smaller sketch $\mathbf{\tilde A}$ that can be used to solve a general class of constrained k-rank approximation problems to within $(1+ε)$ error. Importantly, this class of problems includes $k$-means clustering and unconstrained low rank approximation (i.e. principal component analysis). By reducing data points to just $O(k)$ dimensions, our methods generically accelerate any exact, approximate, or heuristic algorithm for these ubiquitous problems. For $k$-means dimensionality reduction, we provide $(1+ε)$ relative error results for many common sketching techniques, including random row projection, column selection, and approximate SVD. For approximate principal component analysis, we give a simple alternative to known algorithms that has applications in the streaming setting. Additionally, we extend recent work on column-based matrix reconstruction, giving column subsets that not only `cover' a good subspace for $\bv{A}$, but can be used directly to compute this subspace. Finally, for $k$-means clustering, we show how to achieve a $(9+ε)$ approximation by Johnson-Lindenstrauss projecting data points to just $O(\log k/ε^2)$ dimensions. This gives the first result that leverages the specific structure of $k$-means to achieve dimension independent of input size and sublinear in $k$.
A PTAS for Agnostically Learning Halfspaces
Venue: arXiv cs.DS 2015
Year: 2015

We present a PTAS for agnostically learning halfspaces w.r.t. the uniform distribution on the $d$ dimensional sphere. Namely, we show that for every $μ>0$ there is an algorithm that runs in time $\mathrm{poly}(d,\frac{1}ε)$, and is guaranteed to return a classifier with error at most $(1+μ)\mathrm{opt}+ε$, where $\mathrm{opt}$ is the error of the best halfspace classifier. This improves on Awasthi, Balcan and Long [ABL14] who showed an algorithm with an (unspecified) constant approximation ratio. Our algorithm combines the classical technique of polynomial regression (e.g. [LMN89, KKMS05]), together with the new localization technique of [ABL14].
Towards a General Framework for Actual Causation Using CP-logic
Venue: arXiv cs.AI 2015
Year: 2015

Since Pearl's seminal work on providing a formal language for causality, the subject has garnered a lot of interest among philosophers and researchers in artificial intelligence alike. One of the most debated topics in this context regards the notion of actual causation, which concerns itself with specific - as opposed to general - causal claims. The search for a proper formal definition of actual causation has evolved into a controversial debate, that is pervaded with ambiguities and confusion. The goal of our research is twofold. First, we wish to provide a clear way to compare competing definitions. Second, we also want to improve upon these definitions so they can be applied to a more diverse range of instances, including non-deterministic ones. To achieve these goals we will provide a general, abstract definition of actual causation, formulated in the context of the expressive language of CP-logic (Causal Probabilistic logic). We will then show that three recent definitions by Ned Hall (originally formulated for structural models) and a definition of our own (formulated for CP-logic directly) can be viewed and directly compared as instantiations of this abstract definition, which allows them to deal with a broader range of examples.
Generalized weights: an anticode approach
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we study generalized weights as an algebraic invariant of a code. We first describe anticodes in the Hamming and in the rank metric, proving in particular that optimal anticodes in the rank metric coincide with Frobenius-closed spaces. Then we characterize both generalized Hamming and rank weights of a code in terms of the intersection of the code with optimal anticodes in the respective metrics. Inspired by this description, we propose a new algebraic invariant, which we call "Delsarte generalized weights", for Delsarte rank-metric codes based on optimal anticodes of matrices. We show that our invariant refines the generalized rank weights for Gabidulin codes proposed by Kurihara, Matsumoto and Uyematsu, and establish a series of properties of Delsarte generalized weights. In particular, we characterize Delsarte optimal codes and anticodes in terms of their generalized weights. We also present a duality theory for the new algebraic invariant, proving that the Delsarte generalized weights of a code completely determine the Delsarte generalized weights of the dual code. Our results extend the theory of generalized rank weights for Gabidulin codes. Finally, we prove the analogue for Gabidulin codes of a theorem of Wei, proving that their generalized rank weights characterize the worst-case security drops of a Gabidulin rank-metric code.
Variable-length Convolutional Coding for Short Blocklengths with Decision Feedback
Venue: arXiv cs.IT 2015
Year: 2015

This paper presents a variable-length decision-feedback scheme that uses tail-biting convolutional codes and the tail-biting Reliability-Output Viterbi Algoritm (ROVA). Comparing with recent results in finite-blocklength information theory, simulation results for both the BSC and the AWGN channel show that the decision-feedback scheme using ROVA can surpass the random-coding lower bound on throughput for feedback codes at average blocklengths less than 100 symbols. This paper explores ROVA-based decision feedback both with decoding after every symbol and with decoding limited to a small number of increments. The performance of the reliability-based stopping rule with the ROVA is compared to retransmission decisions based on CRCs. For short blocklengths where the latency overhead of the CRC bits is severe, the ROVA-based approach delivers superior rates.
Towards a Visual Turing Challenge
Venue: arXiv cs.AI 2015
Year: 2015

As language and visual understanding by machines progresses rapidly, we are observing an increasing interest in holistic architectures that tightly interlink both modalities in a joint learning and inference process. This trend has allowed the community to progress towards more challenging and open tasks and refueled the hope at achieving the old AI dream of building machines that could pass a turing test in open domains. In order to steadily make progress towards this goal, we realize that quantifying performance becomes increasingly difficult. Therefore we ask how we can precisely define such challenges and how we can evaluate different algorithms on this open tasks? In this paper, we summarize and discuss such challenges as well as try to give answers where appropriate options are available in the literature. We exemplify some of the solutions on a recently presented dataset of question-answering task based on real-world indoor images that establishes a visual turing challenge. Finally, we argue despite the success of unique ground-truth annotation, we likely have to step away from carefully curated dataset and rather rely on 'social consensus' as the main driving force to create suitable benchmarks. Providing coverage in this inherently ambiguous output space is an emerging challenge that we face in order to make quantifiable progress in this area.
A channel under simultaneous jamming and eavesdropping attack---correlated random coding capacities under strong secrecy criteria
Venue: arXiv cs.IT 2015
Year: 2015

We give a complete characterization of the correlated random coding secrecy capacity of arbitrarily varying wiretap channels (AVWCs). We apply two alternative strong secrecy criteria, which both lead to the same multi-letter formula. The difference of these criteria lies in the treatment of correlated randomness, they coincide in the case of uncorrelated codes. On the basis of the derived formula, we show that the correlated random coding secrecy capacity is continuous as a function of the AVWC, in contrast to the discontinuous uncorrelated coding secrecy capacity. In the proof of the secrecy capacity formula for correlated random codes, we apply an auxiliary channel which is compound from the sender to the intended receiver and arbitrarily varying from the sender to the eavesdropper.
Equational properties of stratified least fixed points
Venue: arXiv cs.LO 2015
Year: 2015

Recently, a novel fixed point operation has been introduced over certain non-monotonic functions between stratified complete lattices and used to give semantics to logic programs with negation and boolean context-free grammars. We prove that this new operation satisfies `the standard' identities of fixed point operations as described by the axioms of iteration theories. We also study this new fixed point operation in connection with lambda-abstraction.