OpenRaiser/Intern-Atlas huggingface dataset:
Sieving for closest lattice vectors (with preprocessing)
Venue: arXiv cs.CR 2016
Year: 2016

Lattice-based cryptography has recently emerged as a prime candidate for efficient and secure post-quantum cryptography. The two main hard problems underlying its security are the shortest vector problem (SVP) and the closest vector problem (CVP). Various algorithms have been studied for solving these problems, and for SVP, lattice sieving currently dominates in terms of the asymptotic time complexity: one can heuristically solve SVP in time $2^{0.292d}$ in high dimensions $d$ [BDGL'16]. Although several SVP algorithms can also be used to solve CVP, it is not clear whether this also holds for heuristic lattice sieving methods. The best time complexity for CVP is currently $2^{0.377d}$ [BGJ'14]. In this paper we revisit sieving algorithms for solving SVP, and study how these algorithms can be modified to solve CVP and its variants as well. Our first method is aimed at solving one problem instance and minimizes the overall time complexity for a single CVP instance with a time complexity of $2^{0.292d}$. Our second method minimizes the amortized time complexity for several instances on the same lattice, at the cost of a larger preprocessing cost. We can solve the closest vector problem with preprocessing (CVPP) with $2^{0.636d}$ space and preprocessing, in $2^{0.136d}$ time, while the query complexity can even be reduced to $2^{εd}$ at the cost of preprocessing time and memory complexities of $(1/ε)^{O(d)}$. For easier variants of CVP, such as approximate CVP and bounded distance decoding (BDD), we further show how the preprocessing method achieves even better complexities. For instance, we can solve approximate CVPP with large approximation factors $k$ with polynomial-sized advice in polynomial time if $k = Ω(\sqrt{d/\log d})$, heuristically closing the gap between the decision-CVPP result of [AR'04] and the search-CVPP result of [DRS'14].
Caching as a Service: Small-cell Caching Mechanism Design for Service Providers
Venue: arXiv cs.GT 2016
Year: 2016

Wireless network virtualization has been well recognized as a way to improve the flexibility of wireless networks by decoupling the functionality of the system and implementing infrastructure and spectrum as services. Recent studies have shown that caching provides a better performance to serve the content requests from mobile users. In this paper, we propose that \emph{caching can be applied as a service} in mobile networks, i.e., different service providers (SPs) cache their contents in the storages of wireless facilities that owned by mobile network operators (MNOs). Specifically, we focus on the scenario of \emph{small-cell networks}, where cache-enabled small-cell base stations (SBSs) are the facilities to cache contents. To deal with the competition for storages among multiple SPs, we design a mechanism based on multi-object auctions, where the time-dependent feature of system parameters and the frequency of content replacement are both taken into account. Simulation results show that our solution leads to a satisfactory outcome.
Piecewise convexity of artificial neural networks
Venue: arXiv cs.LG 2016
Year: 2016

Although artificial neural networks have shown great promise in applications including computer vision and speech recognition, there remains considerable practical and theoretical difficulty in optimizing their parameters. The seemingly unreasonable success of gradient descent methods in minimizing these non-convex functions remains poorly understood. In this work we offer some theoretical guarantees for networks with piecewise affine activation functions, which have in recent years become the norm. We prove three main results. Firstly, that the network is piecewise convex as a function of the input data. Secondly, that the network, considered as a function of the parameters in a single layer, all others held constant, is again piecewise convex. Finally, that the network as a function of all its parameters is piecewise multi-convex, a generalization of biconvexity. From here we characterize the local minima and stationary points of the training objective, showing that they minimize certain subsets of the parameter space. We then analyze the performance of two optimization algorithms on multi-convex problems: gradient descent, and a method which repeatedly solves a number of convex sub-problems. We prove necessary convergence conditions for the first algorithm and both necessary and sufficient conditions for the second, after introducing regularization to the objective. Finally, we remark on the remaining difficulty of the global optimization problem. Under the squared error objective, we show that by varying the training data, a single rectifier neuron admits local minima arbitrarily far apart, both in objective value and parameter space.
Composite Kernel Local Angular Discriminant Analysis for Multi-Sensor Geospatial Image Analysis
Venue: arXiv cs.CV 2016
Year: 2016

With the emergence of passive and active optical sensors available for geospatial imaging, information fusion across sensors is becoming ever more important. An important aspect of single (or multiple) sensor geospatial image analysis is feature extraction - the process of finding "optimal" lower dimensional subspaces that adequately characterize class-specific information for subsequent analysis tasks, such as classification, change and anomaly detection etc. In recent work, we proposed and developed an angle-based discriminant analysis approach that projected data onto subspaces with maximal "angular" separability in the input (raw) feature space and Reproducible Kernel Hilbert Space (RKHS). We also developed an angular locality preserving variant of this algorithm. In this letter, we advance this work and make it suitable for information fusion - we propose and validate a composite kernel local angular discriminant analysis projection, that can operate on an ensemble of feature sources (e.g. from different sources), and project the data onto a unified space through composite kernels where the data are maximally separated in an angular sense. We validate this method with the multi-sensor University of Houston hyperspectral and LiDAR dataset, and demonstrate that the proposed method significantly outperforms other composite kernel approaches to sensor (information) fusion.
An optimization approach to locally-biased graph algorithms
Venue: arXiv cs.SI 2016
Year: 2016

Locally-biased graph algorithms are algorithms that attempt to find local or small-scale structure in a large data graph. In some cases, this can be accomplished by adding some sort of locality constraint and calling a traditional graph algorithm; but more interesting are locally-biased graph algorithms that compute answers by running a procedure that does not even look at most of the input graph. This corresponds more closely to what practitioners from various data science domains do, but it does not correspond well with the way that algorithmic and statistical theory is typically formulated. Recent work from several research communities has focused on developing locally-biased graph algorithms that come with strong complementary algorithmic and statistical theory and that are useful in practice in downstream data science applications. We provide a review and overview of this work, highlighting commonalities between seemingly-different approaches, and highlighting promising directions for future work.
End-to-end optimization of nonlinear transform codes for perceptual quality
Venue: arXiv cs.IT 2016
Year: 2016

We introduce a general framework for end-to-end optimization of the rate--distortion performance of nonlinear transform codes assuming scalar quantization. The framework can be used to optimize any differentiable pair of analysis and synthesis transforms in combination with any differentiable perceptual metric. As an example, we consider a code built from a linear transform followed by a form of multi-dimensional local gain control. Distortion is measured with a state-of-the-art perceptual metric. When optimized over a large database of images, this representation offers substantial improvements in bitrate and perceptual appearance over fixed (DCT) codes, and over linear transform codes optimized for mean squared error.
Adaptive Artificial Intelligence in Games: Issues, Requirements, and a Solution through Behavlets-based General Player Modelling
Venue: arXiv cs.HC 2016
Year: 2016

We present the last of a series of three academic essays which deal with the question of how and why to build a generalized player model. We propose that a general player model needs parameters for subjective experience of play, including: player psychology, game structure, and actions of play. Based on this proposition, we pose three linked research questions: RQ1 what is a necessary and sufficient foundation to a general player model?; RQ2 can such a foundation improve performance of a computational intelligence- based player model?; and RQ3 can such a player model improve efficacy of adaptive artificial intelligence in games? We set out the arguments behind these research questions in each of the three essays, presented as three preprints. The third essay, in this preprint, presents the argument that adaptive game artificial intelligence will be enhanced by a generalised player model. This is because games are inherently human artefacts which therefore, require some encoding of the human perspective in order to effectively autonomously respond to the individual player. The player model informs the necessary constraints on the adaptive artificial intelligence. A generalised player model is not only more efficient than a per-game solution, but also allows comparison between games which makes it a useful tool for studying play in general. We describe the concept and meaning of an adaptive game. We propose requirements for functional adaptive AI, arguing from first principles drawn from the games research literature. We propose solutions to these requirements, based on a formal model approach to our existing 'Behavlets' method for psychologically-derived player modelling: Cowley, B., & Charles, D. (2016). Behavlets: a Method for Practical Player Modelling using Psychology-Based Player Traits and Domain Specific Features. User Modeling and User-Adapted Interaction, 26(2), 257-306.
Minimum cycle and homology bases of surface embedded graphs
Venue: arXiv cs.DS 2016
Year: 2016

We study the problems of finding a minimum cycle basis (a minimum weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum weight set of cycles that generates the $1$-dimensional ($\mathbb{Z}_2$)-homology classes) of an undirected graph embedded on a surface. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the $1$-skeleton of any graph is exactly its minimum cycle basis. For the minimum cycle basis problem, we give a deterministic $O(n^ω+2^{2g}n^2+m)$-time algorithm for graphs embedded on an orientable surface of genus $g$. The best known existing algorithms for surface embedded graphs are those for general graphs: an $O(m^ω)$ time Monte Carlo algorithm and a deterministic $O(nm^2/\log n + n^2 m)$ time algorithm. For the minimum homology basis problem, we give a deterministic $O((g+b)^3 n \log n + m)$-time algorithm for graphs embedded on an orientable or non-orientable surface of genus $g$ with $b$ boundary components, assuming shortest paths are unique, improving on existing algorithms for many values of $g$ and $n$. The assumption of unique shortest paths can be avoided with high probability using randomization or deterministically by increasing the running time of the homology basis algorithm by a factor of $O(\log n)$.
Partitioning a Graph into Small Pieces with Applications to Path Transversal
Venue: arXiv cs.DS 2016
Year: 2016

Given a graph $G = (V, E)$ and an integer $k$, we study $k$-Vertex Seperator (resp. $k$-Edge Separator), where the goal is to remove the minimum number of vertices (resp. edges) such that each connected component in the resulting graph has at most $k$ vertices. Our primary focus is on the case where $k$ is either a constant or a slowly growing function of $n$ (e.g. $O(\log n)$ or $n^{o(1)}$). Our problems can be interpreted as a special case of three general classes of problems that have been studied separately (balanced graph partitioning, Hypergraph Vertex Cover (HVC), and fixed parameter tractability (FPT)). Our main result is an $O(\log k)$-approximation algorithm for $k$-Vertex Seperator that runs in time $2^{O(k)} n^{O(1)}$, and an $O(\log k)$-approximation algorithm for $k$-Edge Separator that runs in time $n^{O(1)}$. Our result on $k$-Edge Seperator improves the best previous graph partitioning algorithm for small $k$. Our result on $k$-Vertex Seperator improves the simple $(k+1)$-approximation from HVC. When $OPT > k$, the running time $2^{O(k)} n^{O(1)}$ is faster than the lower bound $k^{Ω(OPT)} n^{Ω(1)}$ for exact algorithms assuming the Exponential Time Hypothesis. While the running time of $2^{O(k)} n^{O(1)}$ for $k$-Vertex Separator seems unsatisfactory, we show that the superpolynomial dependence on $k$ may be needed to achieve a polylogarithmic approximation ratio, based on hardness of Densest $k$-Subgraph. We also study $k$-Path Transversal, where the goal is to remove the minimum number of vertices such that there is no simple path of length $k$. With additional ideas from FPT algorithms and graph theory, we present an $O(\log k)$-approximation algorithm for $k$-Path Transversal that runs in time $2^{O(k^3 \log k)} n^{O(1)}$. Previously, the existence of even $(1 - δ)k$-approximation algorithm for fixed $δ> 0$ was open.
Towards a Universal Approach for Monotonic Searchability in Self-Stabilizing Overlay Networks
Venue: arXiv cs.DC 2016
Year: 2016

For overlay networks, the ability to recover from a variety of problems like membership changes or faults is a key element to preserve their functionality. In recent years, various self-stabilizing overlay networks have been proposed that have the advantage of being able to recover from any illegal state. However, the vast majority of these networks cannot give any guarantees on its functionality while the recovery process is going on. We are especially interested in searchability, i.e., the functionality that search messages for a specific identifier are answered successfully if a node with that identifier exists in the network. We investigate overlay networks that are not only self-stabilizing but that also ensure that monotonic searchability is maintained while the recovery process is going on, as long as there are no corrupted messages in the system. More precisely, once a search message from node $u$ to another node $v$ is successfully delivered, all future search messages from $u$ to $v$ succeed as well. Monotonic searchability was recently introduced in OPODIS 2015, in which the authors provide a solution for a simple line topology. We present the first universal approach to maintain monotonic searchability that is applicable to a wide range of topologies. As the base for our approach, we introduce a set of primitives for manipulating overlay networks that allows us to maintain searchability and show how existing protocols can be transformed to use theses primitives. We complement this result with a generic search protocol that together with the use of our primitives guarantees monotonic searchability. As an additional feature, searching existing nodes with the generic search protocol is as fast as searching a node with any other fixed routing protocol once the topology has stabilized.
Imitation Learning with Recurrent Neural Networks
Venue: arXiv cs.CL 2016
Year: 2016

We present a novel view that unifies two frameworks that aim to solve sequential prediction problems: learning to search (L2S) and recurrent neural networks (RNN). We point out equivalences between elements of the two frameworks. By complementing what is missing from one framework comparing to the other, we introduce a more advanced imitation learning framework that, on one hand, augments L2S s notion of search space and, on the other hand, enhances RNNs training procedure to be more robust to compounding errors arising from training on highly correlated examples.
Emotional Storytelling using Virtual and Robotic Agents
Venue: arXiv cs.RO 2016
Year: 2016

In order to create effective storytelling agents three fundamental questions must be answered: first, is a physically embodied agent preferable to a virtual agent or a voice-only narration? Second, does a human voice have an advantage over a synthesised voice? Third, how should the emotional trajectory of the different characters in a story be related to a storyteller's facial expressions during storytelling time, and how does this correlate with the apparent emotions on the faces of the listeners? The results of two specially designed studies indicate that the physically embodied robot produces more attention to the listener as compared to a virtual embodiment, that a human voice is preferable over the current state of the art of text-to-speech, and that there is a complex yet interesting relation between the emotion lines of the story, the facial expressions of the narrating agent, and the emotions of the listener, and that the empathising of the listener is evident through its facial expressions. This work constitutes an important step towards emotional storytelling robots that can observe their listeners and adapt their style in order to maximise their effectiveness.
Towards Analytics Aware Ontology Based Access to Static and Streaming Data (Extended Version)
Venue: arXiv cs.AI 2016
Year: 2016

Real-time analytics that requires integration and aggregation of heterogeneous and distributed streaming and static data is a typical task in many industrial scenarios such as diagnostics of turbines in Siemens. OBDA approach has a great potential to facilitate such tasks; however, it has a number of limitations in dealing with analytics that restrict its use in important industrial applications. Based on our experience with Siemens, we argue that in order to overcome those limitations OBDA should be extended and become analytics, source, and cost aware. In this work we propose such an extension. In particular, we propose an ontology, mapping, and query language for OBDA, where aggregate and other analytical functions are first class citizens. Moreover, we develop query optimisation techniques that allow to efficiently process analytical tasks over static and streaming data. We implement our approach in a system and evaluate our system with Siemens turbine data.
On Secrecy Metrics for Physical Layer Security over Quasi-Static Fading Channels
Venue: arXiv cs.IT 2016
Year: 2016

Theoretical studies on physical layer security often adopt the secrecy outage probability as the performance metric for wireless communications over quasi-static fading channels. The secrecy outage probability has two limitations from a practical point of view: a) it does not give any insight into the eavesdropper's decodability of confidential messages; b) it cannot characterize the amount of information leakage to the eavesdropper when an outage occurs. Motivated by the limitations of the secrecy outage probability, we propose three new secrecy metrics for secure transmissions over quasi-static fading channels. The first metric establishes a link between the concept of secrecy outage and the decodability of messages at the eavesdropper. The second metric provides an error-probability-based secrecy metric which is typically used for the practical implementation of secure wireless systems. The third metric characterizes how much or how fast the confidential information is leaked to the eavesdropper. We show that the proposed secrecy metrics collectively give a more comprehensive understanding of physical layer security over fading channels and enable one to appropriately design secure communication systems with different views on how secrecy is measured.
Spanning Circuits in Regular Matroids
Venue: arXiv cs.DS 2016
Year: 2016

We consider the fundamental Matroid Theory problem of finding a circuit in a matroid spanning a set T of given terminal elements. For graphic matroids this corresponds to the problem of finding a simple cycle passing through a set of given terminal edges in a graph. The algorithmic study of the problem on regular matroids, a superclass of graphic matroids, was initiated by Gavenčiak, Král', and Oum [ICALP'12], who proved that the case of the problem with |T|=2 is fixed-parameter tractable (FPT) when parameterized by the length of the circuit. We extend the result of Gavenčiak, Král', and Oum by showing that for regular matroids - the Minimum Spanning Circuit problem, deciding whether there is a circuit with at most \ell elements containing T, is FPT parameterized by k=\ell-|T|; - the Spanning Circuit problem, deciding whether there is a circuit containing T, is FPT parameterized by |T|. We note that extending our algorithmic findings to binary matroids, a superclass of regular matroids, is highly unlikely: Minimum Spanning Circuit parameterized by \ell is W[1]-hard on binary matroids even when |T|=1. We also show a limit to how far our results can be strengthened by considering a smaller parameter. More precisely, we prove that Minimum Spanning Circuit parameterized by |T| is W[1]-hard even on cographic matroids, a proper subclass of regular matroids.
The Kalman Filter: a didactical overview
Venue: arXiv cs.SY 2016
Year: 2016

The present document aims at providing a short, didactical introduction to three standard versions of the Kalman filter, namely its variants identified as Basic, Extended, and Unscented. The application of these algorithms in three representative problems is discussed.
On Composition and Implementation of Sequential Consistency (Extended Version)
Venue: arXiv cs.DC 2016
Year: 2016

It has been proved that to implement a linearizable shared memory in synchronous message-passing systems it is necessary to wait for a time proportional to the uncertainty in the latency of the network for both read and write operations, while waiting during read or during write operations is sufficient for sequential consistency. This paper extends this result to crash-prone asynchronous systems. We propose a distributed algorithm that builds a sequentially consistent shared memory abstraction with snapshot on top of an asynchronous message-passing system where less than half of the processes may crash. We prove that it is only necessary to wait when a read/snapshot is immediately preceded by a write on the same process. We also show that sequential consistency is composable in some cases commonly encountered: 1) objects that would be linearizable if they were implemented on top of a linearizable memory become sequentially consistent when implemented on top of a sequential memory while remaining composable and 2) in round-based algorithms, where each object is only accessed within one round.