OpenRaiser/Intern-Atlas huggingface dataset:
Linear identification of nonlinear systems: A lifting technique based on the Koopman operator
Venue: arXiv cs.SY 2016
Year: 2016

We exploit the key idea that nonlinear system identification is equivalent to linear identification of the socalled Koopman operator. Instead of considering nonlinear system identification in the state space, we obtain a novel linear identification technique by recasting the problem in the infinite-dimensional space of observables. This technique can be described in two main steps. In the first step, similar to the socalled Extended Dynamic Mode Decomposition algorithm, the data are lifted to the infinite-dimensional space and used for linear identification of the Koopman operator. In the second step, the obtained Koopman operator is "projected back" to the finite-dimensional state space, and identified to the nonlinear vector field through a linear least squares problem. The proposed technique is efficient to recover (polynomial) vector fields of different classes of systems, including unstable, chaotic, and open systems. In addition, it is robust to noise, well-suited to model low sampling rate datasets, and able to infer network topology and dynamics.
Improved distance sensitivity oracles via tree partitioning
Venue: arXiv cs.DS 2016
Year: 2016

We introduce an improved structure of distance sensitivity oracle (DSO). The task is to pre-process a non-negatively weighted graph so that a data structure can quickly answer replacement path length for every triple of source, terminal and failed vertex. The previous best algorithm constructs in time $\tilde{O}(mn)$ a distance sensitivity oracle of size $O(n^2\log n)$ that processes queries in $O(1)$ time. As an improvement, our oracle takes up $O(n^2)$ space, while preserving $O(1)$ query efficiency and $\tilde{O}(mn)$ preprocessing time. One should notice that space complexity and query time of our novel data structure are asymptotically optimal.
Coding for Improved Throughput Performance in Network Switches
Venue: arXiv cs.NI 2016
Year: 2016

Network switches and routers need to serve packet writes and reads at rates that challenge the most advanced memory technologies. As a result, scaling the switching rates is commonly done by parallelizing the packet I/Os using multiple memory units. For improved read rates, packets can be coded upon write, thus giving more flexibility at read time to achieve higher utilization of the memory units. This paper presents a detailed study of coded network switches, and in particular how to design them to maximize the throughput advantages over standard uncoded switches. Toward that objective the paper contributes a variety of algorithmic and analytical tools to improve and evaluate the throughput performance. The most interesting finding of this study is that the placement of packets in the switch memory is the key to both high performance and algorithmic efficiency. One particular placement policy we call "design placement" is shown to enjoy the best combination of throughput performance and implementation feasibility.
Improving the Neural Algorithm of Artistic Style
Venue: arXiv cs.CV 2016
Year: 2016

In this work we investigate different avenues of improving the Neural Algorithm of Artistic Style (by Leon A. Gatys, Alexander S. Ecker and Matthias Bethge, arXiv:1508.06576). While showing great results when transferring homogeneous and repetitive patterns, the original style representation often fails to capture more complex properties, like having separate styles of foreground and background. This leads to visual artifacts and undesirable textures appearing in unexpected regions when performing style transfer. We tackle this issue with a variety of approaches, mostly by modifying the style representation in order for it to capture more information and impose a tighter constraint on the style transfer result. In our experiments, we subjectively evaluate our best method as producing from barely noticeable to significant improvements in the quality of style transfer.
Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes
Venue: arXiv cs.IT 2016
Year: 2016

This work constructs codes that are efficiently decodable from a constant fraction of \emph{worst-case} insertion and deletion errors in three parameter settings: (i) Binary codes with rate approaching 1; (ii) Codes with constant rate for error fraction approaching 1 over fixed alphabet size; and (iii) Constant rate codes over an alphabet of size $k$ for error fraction approaching $(k-1)/(k+1)$. When errors are constrained to deletions alone, efficiently decodable codes in each of these regimes were constructed recently. We complete the picture by constructing similar codes that are efficiently decodable in the insertion/deletion regime.
DeepLearningKit - an GPU Optimized Deep Learning Framework for Apple's iOS, OS X and tvOS developed in Metal and Swift
Venue: arXiv cs.LG 2016
Year: 2016

In this paper we present DeepLearningKit - an open source framework that supports using pretrained deep learning models (convolutional neural networks) for iOS, OS X and tvOS. DeepLearningKit is developed in Metal in order to utilize the GPU efficiently and Swift for integration with applications, e.g. iOS-based mobile apps on iPhone/iPad, tvOS-based apps for the big screen, or OS X desktop applications. The goal is to support using deep learning models trained with popular frameworks such as Caffe, Torch, TensorFlow, Theano, Pylearn, Deeplearning4J and Mocha. Given the massive GPU resources and time required to train Deep Learning models we suggest an App Store like model to distribute and download pretrained and reusable Deep Learning models.
GMD-Based Hybrid Precoding For Millimeter-Wave Massive MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

Hybrid precoding can significantly reduce the number of required radio frequency (RF) chains and relieve the huge energy consumption in mmWave massive MIMO systems, thus attracting much interests from academic and industry. However, most existing hybrid precoding schemes are based on singular value decomposition (SVD). Due to the very different sub-channel signal-to-noise ratios (SNRs) after SVD, complicated bit allocations is usually required to match the sub-channel SNRs. To solve this problem, we propose a geometric mean decomposition (GMD)-based hybrid precoding scheme to avoid the complicated bit allocation. Its basic idea is to seek a pair of analog and digital precoding matrices that are sufficiently close to the optimal unconstrained GMD precoding matrix. Specifically, we design the analog (digital) precoding matrix while keeping the digital (analog) precoding matrix fixed. Further, the principle of basis pursuit is utilized in the design of analog precoding matrix, while we obtain the digital precoding matrix by projecting the GMD operation on the digital precoding matrix. Simulation results verify that the proposed GMD-based hybird precoding scheme outperforms conventional SVD-based hybrid precoding schemes and achieves much better bit error rate (BER) performance with low complexity.
On the Complexity of Connection Games
Venue: arXiv cs.CC 2016
Year: 2016

In this paper, we study three connection games among the most widely played: Havannah, Twixt, and Slither. We show that determining the outcome of an arbitrary input position is PSPACE-complete in all three cases. Our reductions are based on the popular graph problem Generalized Geography and on Hex itself. We also consider the complexity of generalizations of Hex parameterized by the length of the solution and establish that while Short Generalized Hex is W[1]-hard, Short Hex is FPT. Finally, we prove that the ultra-weak solution to the empty starting position in hex cannot be fully adapted to any of these three games.
Do Users Focus on the Correct Cues to Differentiate Between Phishing and Genuine Emails?
Venue: arXiv cs.CY 2016
Year: 2016

This paper examines the cues that typically differentiate phishing emails from genuine emails. The research is conducted in two stages. In the first stage, we identify the cues that actually differentiate between phishing and genuine emails. These are the consistency and personalisation of the message, the perceived legitimacy of links and sender, and the presence of spelling or grammatical irregularities. In the second stage, we identify the cues that participants use to differentiate between phishing and genuine emails. This revealed that participants often use cues that are not good indicators of whether an email is phishing or genuine. This includes the presence of legal disclaimers, the quality of visual presentation, and the positive consequences emphasised in the email. This study has implications for education and training and provides a basis for the design and development of targeted and more relevant training and risk communication strategies.
Concentration in the mobile operating systems market
Venue: arXiv cs.CY 2016
Year: 2016

Concentration phenomena concern the ICT market. Though the regulatory action has been active mainly in the telecom network operators industry, even more significant worldwide concentration phenomena affect other industries. The market of mobile operating systems is analysed through two concentration indices to get a quantitative picture of the current situation and its evolution over time: the Hirschman Herfindahl Index (HHI) and the Four-Firm Concentration Ratio (CR4). A strongly imbalanced oligopoly is shown to exist, where the four major operating systems take over 99% of the market, but the dominant operating system Android alone is installed on over 80% of the new devices.
Multilevel Thresholding Segmentation of T2 weighted Brain MRI images using Convergent Heterogeneous Particle Swarm Optimization
Venue: arXiv cs.CV 2016
Year: 2016

This paper proposes a new image thresholding segmentation approach using the heuristic method, Convergent Heterogeneous Particle Swarm Optimization algorithm. The proposed algorithm incorporates a new strategy of searching the problem space by dividing the swarm into subswarms. Each subswarm particles search for better solution separately lead to better exploitation while they cooperate with each other to find the best global position. The consequence of the aforementioned cooperation is better exploration, convergence and it able the algorithm to jump from local optimal solution to the better spots. A practical application of this method is demonstrated for the problem of medical image thresholding segmentation. We considered two classical thresholding techniques of Otsu and Kapur separately as the objective function for the optimization method and applied on a set of brain MR images. Comparative experimental results reveal that the proposed method outperforms another state of the art method from the literature in terms of accuracy, computation time and stable results.
Daala: A Perceptually-Driven Still Picture Codec
Venue: arXiv cs.MM 2016
Year: 2016

Daala is a new royalty-free video codec based on perceptually-driven coding techniques. We explore using its keyframe format for still picture coding and show how it has improved over the past year. We believe the technology used in Daala could be the basis of an excellent, royalty-free image format.
Multi-Prime RSA Over Galois Approach
Venue: arXiv cs.CR 2016
Year: 2016

Many variants of RSA cryptosystem exist in the literature. One of them is RSA over polynomials based on Galois approach. In standard RSA modulus is product of two large primes whereas in the Galois approach author considered the modulus as a product of two irriduciable polynomials. We use this idea and extend Multi-prime RSA over polynomials.
The polymake XML file format
Venue: arXiv cs.MS 2016
Year: 2016

We describe an XML file format for storing data from computations in algebra and geometry. We also present a formal specification based on a RELAX-NG schema.
Exact Online String Matching Bibliography
Venue: arXiv cs.DS 2016
Year: 2016

In this short note we present a comprehensive bibliography for the online exact string matching problem. The problem consists in finding all occurrences of a given pattern in a text. It is an extensively studied problem in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, data compression, information retrieval, computational biology and chemistry. Since 1970 more than 120 string matching algorithms have been proposed. In this note we present a comprehensive list of (almost) all string matching algorithms. The list is updated to May 2016.
Ad-Blocking and Counter Blocking: A Slice of the Arms Race
Venue: arXiv cs.CR 2016
Year: 2016

Adblocking tools like Adblock Plus continue to rise in popularity, potentially threatening the dynamics of advertising revenue streams. In response, a number of publishers have ramped up efforts to develop and deploy mechanisms for detecting and/or counter-blocking adblockers (which we refer to as anti-adblockers), effectively escalating the online advertising arms race. In this paper, we develop a scalable approach for identifying third-party services shared across multiple web-sites and use it to provide a first characterization of anti-adblocking across the Alexa Top-5K websites. We map websites that perform anti-adblocking as well as the entities that provide anti-adblocking scripts. We study the modus operandi of these scripts and their impact on popular adblockers. We find that at least 6.7% of websites in the Alexa Top-5K use anti-adblocking scripts, acquired from 12 distinct entities -- some of which have a direct interest in nourishing the online advertising industry.
Enumeration of Enumeration Algorithms
Venue: arXiv cs.DS 2016
Year: 2016

In this paper, we enumerate enumeration problems and algorithms. This survey is under construction. If you know some results not in this survey or there is anything wrong, please let me know.
Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks
Venue: arXiv cs.DC 2016
Year: 2016

We develop a new technique for constructing sparse graphs that allow us to prove near-linear lower bounds on the round complexity of computing distances in the CONGEST model. Specifically, we show an $\widetildeΩ(n)$ lower bound for computing the diameter in sparse networks, which was previously known only for dense networks [Frishknecht et al., SODA 2012]. In fact, we can even modify our construction to obtain graphs with constant degree, using a simple but powerful degree-reduction technique which we define. Moreover, our technique allows us to show $\widetildeΩ(n)$ lower bounds for computing $(\frac{3}{2}-\varepsilon)$-approximations of the diameter or the radius, and for computing a $(\frac{5}{3}-\varepsilon)$-approximation of all eccentricities. For radius, we are unaware of any previous lower bounds. For diameter, these greatly improve upon previous lower bounds and are tight up to polylogarithmic factors [Frishknecht et al., SODA 2012], and for eccentricities the improvement is both in the lower bound and in the approximation factor [Holzer and Wattenhofer, PODC 2012]. Interestingly, our technique also allows showing an almost-linear lower bound for the verification of $(α,β)$-spanners, for $α< β+1$.
Pushing the limits of the CyberGrasp for haptic rendering
Venue: arXiv cs.HC 2016
Year: 2016

The CyberGrasp is a well known dataglove-exoskeleton device combination that allows to render haptic feedback to the human fingers. Its design, however, restricts its usability for teleoperation through a limited control bandwidth and position sensor resolution. Therefore the system is restricted to low achievable contact stiffness and feedback gain magnitudes in haptic rendering. Moreover, the system prohibits simple adaption of its controller implementation. In this paper, the ExHand Box is presented, a newly designed back-end to widen the CyberGrasp's bandwidth restrictions and to open it up for fully customized controller implementations. The ExHand Box provides a new computer, interface electronics and motor controllers for the otherwise unmodified CyberGlove and CyberGrasp hand systems. The loop frequency of the new system can be freely varied up to 2 kHz and custom controllers can be implemented through an automatic code generation interface. System performance identification experiments are presented that demonstrate improved behavior in hard contact situations over a range of sampling periods. Maximum contact stiffnesses of up to 50kN/m in a stable condition are demonstrated, which is significantly higher than what could be achieved with the non-customized original system version. Moreover, a bilateral control experiment is conducted to demonstrate the new system's usability for generic teleoperation research. In this experiment a raycasting algorithm is introduced for pre-contact detection in order to compensate for high delay and jitter communication links between master and slave as they appear in an Ethernet network. It is demonstrated that the contact stiffness can be maintained in the order of magnitude of the system performance identification with a demonstrated stiffness of 41kN/m in a stable condition.
The Non-uniform Fast Fourier Transform in Computed Tomography
Venue: arXiv cs.DS 2016
Year: 2016

This project is aimed at designing the fast forward projection algorithm and also the backprojection algorithm for cone beam CT imaging systems with circular X-ray source trajectory. The principle of the designs is based on utilizing the potential computational efficiency which the Fourier Slice Theorem and the Non-uniform Fast Fourier Transform (NUFFT) will bring forth. In this Masters report, the detailed design of the NUFFT based forward projector including a novel 3D (derivative of) Radon space resampling method will be given. Meanwhile the complexity of the NUFFT based forward projector is analysed and compared with the non-Fourier based CT projector, and the advantage of the NUFFT based forward projection in terms of the computational efficiency is demonstrated in this report. Base on the design of the forward algorithm, the NUFFT based 3D direct reconstruction algorithm will be derived. The experiments will be taken to test the performance of the forward algorithm and the backprojection algorithm to show the practicability and accuracy of these designs by comparing them jointly with the well-acknowledged cone beam CT operators: the CT linear interpolation forward projector and the FDK algorithm. This Master report will demonstrate a novel and efficient way of implementing the cone beam CT operator, a detailed summary of the project, and the future research prospects of the NUFFT based cone beam CT algorithms.
Graph reconstruction from the observation of diffused signals
Venue: arXiv cs.IT 2016
Year: 2016

Signal processing on graphs has received a lot of attention in the recent years. A lot of techniques have arised, inspired by classical signal processing ones, to allow studying signals on any kind of graph. A common aspect of these technique is that they require a graph correctly modeling the studied support to explain the signals that are observed on it. However, in many cases, such a graph is unavailable or has no real physical existence. An example of this latter case is a set of sensors randomly thrown in a field which obviously observe related information. To study such signals, there is no intuitive choice for a support graph. In this document, we address the problem of inferring a graph structure from the observation of signals, under the assumption that they were issued of the diffusion of initially i.i.d. signals. To validate our approach, we design an experimental protocol, in which we diffuse signals on a known graph. Then, we forget the graph, and show that we are able to retrieve it very precisely from the only knowledge of the diffused signals.
Java Generics are Turing Complete
Venue: arXiv cs.PL 2016
Year: 2016

This paper describes a reduction from the halting problem of Turing machines to subtype checking in Java. It follows that subtype checking in Java is undecidable, which answers a question posed by Kennedy and Pierce in 2007. It also follows that Java's type checker can recognize any recursive language, which improves a result of Gil and Levy from 2016. The latter point is illustrated by a parser generator for fluent interfaces.
Random Access Preamble Design and Detection for 3GPP Narrowband IoT Systems
Venue: arXiv cs.NI 2016
Year: 2016

Narrowband internet of things (NB-IoT) is an emerging cellular technology that will provide improved coverage for massive number of low-throughput low-cost devices with low device power consumption in delay-tolerant applications. A new single tone signal with frequency hopping has been designed for NB-IoT physical random access channel (NPRACH). In this letter we describe this new NPRACH design and explain in detail the design rationale. We further propose possible receiver algorithms for NPRACH detection and time-of-arrival estimation. Simulation results on NPRACH performance including detection rate, false alarm rate, and time-of-arrival estimation accuracy are presented to shed light on the overall potential of NB-IoT systems.
The Information Flow Problem on Clock Networks
Venue: arXiv cs.IT 2016
Year: 2016

The information flow problem on a network asks whether $r$ senders, $v_1,v_2, \ldots ,v_r$ can each send messages to $r$ corresponding receivers $v_{n+1}, \ldots ,v_{n+r}$ via intermediate nodes $v_{r+1}, \ldots ,v_n$. For a given finite $R \subset \mathbb{Z}^+$, the clock network $N_n(R)$ has edge $v_iv_k$ if and only if $k>r$ and $k-i \in R$. We show that the information flow problem on $N_n(\{1,2, \ldots ,r\})$ can be solved for all $n \geq r$. We also show that for any finite $R$ such that $\gcd(R)=1$ and $r = \max(R)$, we show that the information flow problem can be solved on $N_n(R)$ for all $n \geq 3r^3$.
Pricing the Woman Card: Gender Politics between Hillary Clinton and Donald Trump
Venue: arXiv cs.SI 2016
Year: 2016

In this paper, we propose a data-driven method to measure the impact of the 'woman card' exchange between Hillary Clinton and Donald Trump. Building from a unique dataset of the two candidates' Twitter followers, we first examine the transition dynamics of the two candidates' Twitter followers one week before the exchange and one week after. Then we train a convolutional neural network to classify the gender of the followers and unfollowers, and study how women in particular are reacting to the 'woman card' exchange. Our study suggests that the 'woman card' comment has made women more likely to follow Hillary Clinton, less likely to unfollow her and that it has apparently not affected the gender composition of Trump followers.
Image segmentation with superpixel-based covariance descriptors in low-rank representation
Venue: arXiv cs.CV 2016
Year: 2016

This paper investigates the problem of image segmentation using superpixels. We propose two approaches to enhance the discriminative ability of the superpixel's covariance descriptors. In the first one, we employ the Log-Euclidean distance as the metric on the covariance manifolds, and then use the RBF kernel to measure the similarities between covariance descriptors. The second method is focused on extracting the subspace structure of the set of covariance descriptors by extending a low rank representation algorithm on to the covariance manifolds. Experiments are carried out with the Berkly Segmentation Dataset, and compared with the state-of-the-art segmentation algorithms, both methods are competitive.