OpenRaiser/Intern-Atlas huggingface dataset:
Fisheye Consistency: Keeping Data in Synch in a Georeplicated World
Venue: arXiv cs.DC 2015
Year: 2015

Over the last thirty years, numerous consistency conditions for replicated data have been proposed and implemented. Popular examples of such conditions include linearizability (or atomicity), sequential consistency, causal consistency, and eventual consistency. These consistency conditions are usually defined independently from the computing entities (nodes) that manipulate the replicated data; i.e., they do not take into account how computing entities might be linked to one another, or geographically distributed. To address this lack, as a first contribution, this paper introduces the notion of proximity graph between computing nodes. If two nodes are connected in this graph, their operations must satisfy a strong consistency condition, while the operations invoked by other nodes are allowed to satisfy a weaker condition. The second contribution is the use of such a graph to provide a generic approach to the hybridization of data consistency conditions into the same system. We illustrate this approach on sequential consistency and causal consistency, and present a model in which all data operations are causally consistent, while operations by neighboring processes in the proximity graph are sequentially consistent. The third contribution of the paper is the design and the proof of a distributed algorithm based on this proximity graph, which combines sequential consistency and causal consistency (the resulting condition is called fisheye consistency). In doing so the paper not only extends the domain of consistency conditions, but provides a generic provably correct solution of direct relevance to modern georeplicated systems.
Rigorous and Practical Proportional-fair Allocation for Multi-rate Wi-Fi
Venue: arXiv cs.NI 2015
Year: 2015

Recent experimental studies confirm the prevalence of the widely known performance anomaly problem in current Wi-Fi networks, and report on the severe network utility degradation caused by this phenomenon. Although a large body of work addressed this issue, we attribute the refusal of prior solutions to their poor implementation feasibility with off-the-shelf hardware and their imprecise modelling of the 802.11 protocol. Their applicability is further challenged today by very high throughput enhancements (802.11n/ac) whereby link speeds can vary by two orders of magnitude. Unlike earlier approaches, in this paper we introduce the first rigorous analytical model of 802.11 stations' throughput and airtime in multi-rate settings, without sacrificing accuracy for tractability. We use the proportional-fair allocation criterion to formulate network utility maximisation as a convex optimisation problem for which we give a closed-form solution. We present a fully functional light-weight implementation of our scheme on commodity access points and evaluate this extensively via experiments in a real deployment, over a broad range of network conditions. Results demonstrate that our proposal achieves up to 100\% utility gains, can double video streaming goodput and reduces TCP download times by 8x.
$1$-String $B_2$-VPG Representation of Planar Graphs
Venue: arXiv cs.CG 2015
Year: 2015

In this paper, we prove that every planar graph has a 1-string $B_2$-VPG representation---a string representation using paths in a rectangular grid that contain at most two bends. Furthermore, two paths representing vertices $u,v$ intersect precisely once whenever there is an edge between $u$ and $v$.
Detour Planning for Fast and Reliable Failure Recovery in SDN with OpenState
Venue: arXiv cs.NI 2015
Year: 2015

A reliable and scalable mechanism to provide protection against a link or node failure has additional requirements in the context of SDN and OpenFlow. Not only it has to minimize the load on the controller, but it must be able to react even when the controller is unreachable. In this paper we present a protection scheme based on precomputed backup paths and inspired by MPLS crankback routing, that guarantees instantaneous recovery times and aims at zero packet-loss after failure detection, regardless of controller reachability, even when OpenFlow's "fast-failover" feature cannot be used. The proposed mechanism is based on OpenState, an OpenFlow extension that allows a programmer to specify how forwarding rules should autonomously adapt in a stateful fashion, reducing the need to rely on remote controllers. We present the scheme as well as two different formulations for the computation of backup paths.
FPTAS for #BIS with Degree Bounds on One Side
Venue: arXiv cs.DS 2015
Year: 2015

Counting the number of independent sets for a bipartite graph (#BIS) plays a crucial role in the study of approximate counting. It has been conjectured that there is no fully polynomial-time (randomized) approximation scheme (FPTAS/FPRAS) for #BIS, and it was proved that the problem for instances with a maximum degree of $6$ is already as hard as the general problem. In this paper, we obtain a surprising tractability result for a family of #BIS instances. We design a very simple deterministic fully polynomial-time approximation scheme (FPTAS) for #BIS when the maximum degree for one side is no larger than $5$. There is no restriction for the degrees on the other side, which do not even have to be bounded by a constant. Previously, FPTAS was only known for instances with a maximum degree of $5$ for both sides.
Analysis of Pivot Sampling in Dual-Pivot Quicksort
Venue: arXiv cs.DS 2015
Year: 2015

The new dual-pivot Quicksort by Vladimir Yaroslavskiy - used in Oracle's Java runtime library since version 7 - features intriguing asymmetries. They make a basic variant of this algorithm use less comparisons than classic single-pivot Quicksort. In this paper, we extend the analysis to the case where the two pivots are chosen as fixed order statistics of a random sample. Surprisingly, dual-pivot Quicksort then needs more comparisons than a corresponding version of classic Quicksort, so it is clear that counting comparisons is not sufficient to explain the running time advantages observed for Yaroslavskiy's algorithm in practice. Consequently, we take a more holistic approach and give also the precise leading term of the average number of swaps, the number of executed Java Bytecode instructions and the number of scanned elements, a new simple cost measure that approximates I/O costs in the memory hierarchy. We determine optimal order statistics for each of the cost measures. It turns out that the asymmetries in Yaroslavskiy's algorithm render pivots with a systematic skew more efficient than the symmetric choice. Moreover, we finally have a convincing explanation for the success of Yaroslavskiy's algorithm in practice: Compared with corresponding versions of classic single-pivot Quicksort, dual-pivot Quicksort needs significantly less I/Os, both with and without pivot sampling.
Secure Communication with a Wireless-Powered Friendly Jammer
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we propose to use a wireless-powered friendly jammer to enable secure communication between a source node and destination node, in the presence of an eavesdropper. We consider a two-phase communication protocol with fixed-rate transmission. In the first phase, wireless power transfer is conducted from the source to the jammer. In the second phase, the source transmits the information-bearing signal under the protection of a jamming signal sent by the jammer using the harvested energy in the first phase. We analytically characterize the long-time behavior of the proposed protocol and derive a closed-form expression for the throughput. We further optimize the rate parameters for maximizing the throughput subject to a secrecy outage probability constraint. Our analytical results show that the throughput performance differs significantly between the single-antenna jammer case and the multi-antenna jammer case. For instance, as the source transmit power increases, the throughput quickly reaches an upper bound with single-antenna jammer, while the throughput grows unbounded with multi-antenna jammer. Our numerical results also validate the derived analytical results.
An Infra-Structure for Performance Estimation and Experimental Comparison of Predictive Models in R
Venue: arXiv cs.MS 2015
Year: 2015

This document describes an infra-structure provided by the R package performanceEstimation that allows to estimate the predictive performance of different approaches (workflows) to predictive tasks. The infra-structure is generic in the sense that it can be used to estimate the values of any performance metrics, for any workflow on different predictive tasks, namely, classification, regression and time series tasks. The package also includes several standard workflows that allow users to easily set up their experiments limiting the amount of work and information they need to provide. The overall goal of the infra-structure provided by our package is to facilitate the task of estimating the predictive performance of different modeling approaches to predictive tasks in the R environment.
SmartPacket: Re-Distributing the Routing Intelligence among Network Components in SDNs
Venue: arXiv cs.NI 2015
Year: 2015

In this work, a new region-based, multipath-enabled packet routing is presented and called SmartPacket Routing. The proposed approach provides several opportunities to re-distribute the smartness and decision making among various elements of a network including the packets themselves toward providing a decentralized solution for SDNs. This would bring efficiency and scalability, and therefore also lower environmental footprint for the ever-growing networks. In particular, a region-based representation of the network topology is proposed which is then used to describe the routing actions along the possible paths for a packet flow. In addition to a region stack that expresses a partial or full regional path of a packet, QoS requirements of the packet (or its associated flow) is considered in the packet header in order to enable possible QoS-aware routing at region level without requiring a centralized controller.
Reconstruction of Randomly Sampled Sparse Signals Using an Adaptive Gradient Algorithm
Venue: arXiv cs.IT 2015
Year: 2015

Sparse signals can be recovered from a reduced set of samples by using compressive sensing algorithms. In common methods the signal is recovered in the sparse domain. A method for the reconstruction of sparse signal which reconstructs the remaining missing samples/measurements is recently proposed. The available samples are fixed, while the missing samples are considered as minimization variables. Recovery of missing samples/measurements is done using an adaptive gradient-based algorithm in the time domain. A new criterion for the parameter adaptation in this algorithm, based on the gradient direction angles, is proposed. It improves the algorithm computational efficiency. A theorem for the uniqueness of the recovered signal for given set of missing samples (reconstruction variables) is presented. The case when available samples are a random subset of a uniformly or nonuniformly sampled signal is considered in this paper. A recalculation procedure is used to reconstruct the nonuniformly sampled signal. The methods are illustrated on statistical examples.
A review of "Mem-computing NP-complete problems in polynomial time using polynomial resources" (arXiv:1411.4798)
Venue: arXiv cs.ET 2015
Year: 2015

The reviewed paper describes an analog device that empirically solves small instances of the NP-complete Subset Sum Problem (SSP). The authors claim that this device can solve the SSP in polynomial time using polynomial space, in principle, and observe no exponential scaling in resource requirements. We point out that (a) the properties ascribed by the authors to their device are insufficient to solve NP-complete problems in poly-time, (b) runtime analysis offered does not cover the spectral measurement step, (c) the overall technique requires exponentially increasing resources when scaled up because of the spectral measurement step.
Understanding confounding effects in linguistic coordination: an information-theoretic approach
Venue: arXiv cs.CL 2015
Year: 2015

We suggest an information-theoretic approach for measuring stylistic coordination in dialogues. The proposed measure has a simple predictive interpretation and can account for various confounding factors through proper conditioning. We revisit some of the previous studies that reported strong signatures of stylistic accommodation, and find that a significant part of the observed coordination can be attributed to a simple confounding effect - length coordination. Specifically, longer utterances tend to be followed by longer responses, which gives rise to spurious correlations in the other stylistic features. We propose a test to distinguish correlations in length due to contextual factors (topic of conversation, user verbosity, etc.) and turn-by-turn coordination. We also suggest a test to identify whether stylistic coordination persists even after accounting for length coordination and contextual factors.
Shortest Path in a Polygon using Sublinear Space
Venue: arXiv cs.CG 2015
Year: 2015

$\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)}$ We resolve an open problem due to Tetsuo Asano, showing how to compute the shortest path in a polygon, given in a read only memory, using sublinear space and subquadratic time. Specifically, given a simple polygon $\Polygon$ with $n$ vertices in a read only memory, and additional working memory of size $\Space$, the new algorithm computes the shortest path (in $\Polygon$) in $O( n^2 /\, \Space )$ expected time. This requires several new tools, which we believe to be of independent interest.
Fast Steerable Principal Component Analysis
Venue: arXiv cs.CV 2015
Year: 2015

Cryo-electron microscopy nowadays often requires the analysis of hundreds of thousands of 2D images as large as a few hundred pixels in each direction. Here we introduce an algorithm that efficiently and accurately performs principal component analysis (PCA) for a large set of two-dimensional images, and, for each image, the set of its uniform rotations in the plane and their reflections. For a dataset consisting of $n$ images of size $L \times L$ pixels, the computational complexity of our algorithm is $O(nL^3 + L^4)$, while existing algorithms take $O(nL^4)$. The new algorithm computes the expansion coefficients of the images in a Fourier-Bessel basis efficiently using the non-uniform fast Fourier transform. We compare the accuracy and efficiency of the new algorithm with traditional PCA and existing algorithms for steerable PCA.
The Kadison-Singer Problem for Strongly Rayleigh Measures and Applications to Asymmetric TSP
Venue: arXiv cs.DS 2015
Year: 2015

Marcus, Spielman, and Srivastava in their seminal work \cite{MSS13} resolved the Kadison-Singer conjecture by proving that for any set of finitely supported independently distributed random vectors $v_1,\dots, v_n$ which have "small" expected squared norm and are in isotropic position (in expectation), there is a positive probability that the sum $\sum v_i v_i^\intercal$ has small spectral norm. Their proof crucially employs real stability of polynomials which is the natural generalization of real-rootedness to multivariate polynomials. Strongly Rayleigh distributions are families of probability distributions whose generating polynomials are real stable \cite{BBL09}. As independent distributions are just special cases of strongly Rayleigh measures, it is a natural question to see if the main theorem of \cite{MSS13} can be extended to families of vectors assigned to the elements of a strongly Rayleigh distribution. In this paper we answer this question affirmatively; we show that for any homogeneous strongly Rayleigh distribution where the marginal probabilities are upper bounded by $ε_1$ and any isotropic set of vectors assigned to the underlying elements whose norms are at most $\sqrt{ε_2}$, there is a set in the support of the distribution such that the spectral norm of the sum of the natural quadratic forms of the vectors assigned to the elements of the set is at most $O(ε_1+ε_2)$. We employ our theorem to provide a sufficient condition for the existence of spectrally thin trees. This, together with a recent work of the authors \cite{AO14}, provides an improved upper bound on the integrality gap of the natural LP relaxation of the Asymmetric Traveling Salesman Problem.
Scalable, High-Quality Object Detection
Venue: arXiv cs.CV 2015
Year: 2015

Current high-quality object detection approaches use the scheme of salience-based object proposal methods followed by post-classification using deep convolutional features. This spurred recent research in improving object proposal methods. However, domain agnostic proposal generation has the principal drawback that the proposals come unranked or with very weak ranking, making it hard to trade-off quality for running time. This raises the more fundamental question of whether high-quality proposal generation requires careful engineering or can be derived just from data alone. We demonstrate that learning-based proposal methods can effectively match the performance of hand-engineered methods while allowing for very efficient runtime-quality trade-offs. Using the multi-scale convolutional MultiBox (MSC-MultiBox) approach, we substantially advance the state-of-the-art on the ILSVRC 2014 detection challenge data set, with $0.5$ mAP for a single model and $0.52$ mAP for an ensemble of two models. MSC-Multibox significantly improves the proposal quality over its predecessor MultiBox~method: AP increases from $0.42$ to $0.53$ for the ILSVRC detection challenge. Finally, we demonstrate improved bounding-box recall compared to Multiscale Combinatorial Grouping with less proposals on the Microsoft-COCO data set.
Symmetric Weighted First-Order Model Counting
Venue: arXiv cs.DB 2015
Year: 2015

The FO Model Counting problem (FOMC) is the following: given a sentence $Φ$ in FO and a number $n$, compute the number of models of $Φ$ over a domain of size $n$; the Weighted variant (WFOMC) generalizes the problem by associating a weight to each tuple and defining the weight of a model to be the product of weights of its tuples. In this paper we study the complexity of the symmetric WFOMC, where all tuples of a given relation have the same weight. Our motivation comes from an important application, inference in Knowledge Bases with soft constraints, like Markov Logic Networks, but the problem is also of independent theoretical interest. We study both the data complexity, and the combined complexity of FOMC and WFOMC. For the data complexity we prove the existence of an FO$^{3}$ formula for which FOMC is #P$_1$-complete, and the existence of a Conjunctive Query for which WFOMC is #P$_1$-complete. We also prove that all $γ$-acyclic queries have polynomial time data complexity. For the combined complexity, we prove that, for every fragment FO$^{k}$, $k\geq 2$, the combined complexity of FOMC (or WFOMC) is #P-complete.
On $k$-piecewise testability (preliminary report)
Venue: arXiv cs.FL 2015
Year: 2015

For a non-negative integer $k$, a language is $k$-piecewise test\-able ($k$-PT) if it is a finite boolean combination of languages of the form $Σ^* a_1 Σ^* \cdots Σ^* a_n Σ^*$ for $a_i\inΣ$ and $0\le n \le k$. We study the following problem: Given a DFA recognizing a piecewise testable language, decide whether the language is $k$-PT. We provide a complexity bound and a detailed analysis for small $k$'s. The result can be used to find the minimal $k$ for which the language is $k$-PT. We show that the upper bound on $k$ given by the depth of the minimal DFA can be exponentially bigger than the minimal possible $k$, and provide a tight upper bound on the depth of the minimal DFA recognizing a $k$-PT language.
PaREM: A Novel Approach for Parallel Regular Expression Matching
Venue: arXiv cs.FL 2015
Year: 2015

Regular expression matching is essential for many applications, such as finding patterns in text, exploring substrings in large DNA sequences, or lexical analysis. However, sequential regular expression matching may be time-prohibitive for large problem sizes. In this paper, we describe a novel algorithm for parallel regular expression matching via deterministic finite automata. Furthermore, we present our tool PaREM that accepts regular expressions and finite automata as input and automatically generates the corresponding code for our algorithm that is amenable for parallel execution on shared-memory systems. We evaluate our parallel algorithm empirically by comparing it with a commonly used algorithm for sequential regular expression matching. Experiments on a dual-socket shared-memory system with 24 physical cores show speed-ups of up to 21x for 48 threads.
Risk Estimation Without Using Stein's Lemma -- Application to Image Denoising
Venue: arXiv cs.CV 2015
Year: 2015

We address the problem of image denoising in additive white noise without placing restrictive assumptions on its statistical distribution. In the recent literature, specific noise distributions have been considered and correspondingly, optimal denoising techniques have been developed. One of the successful approaches for denoising relies on the notion of unbiased risk estimation, which enables one to obtain a useful substitute for the mean-square error. For the case of additive white Gaussian noise contamination, the risk estimation procedure relies on Stein's lemma. Sophisticated wavelet-based denoising techniques, which are essentially nonlinear, have been developed with the help of the lemma. We show that, for linear, shift-invariant denoisers, it is possible to obtain unbiased risk estimates of the mean-square error without using Stein's lemma. An interesting consequence of this development is that the unbiased risk estimator becomes agnostic to the statistical distribution of the noise. As a proof of principle, we show how the new methodology can be used to optimize the parameters of a simple Gaussian smoother. By locally adapting the parameters of the Gaussian smoother, we obtain a shift-variant smoother, which has a denoising performance (quantified by the improvement in peak signal-to-noise ratio (PSNR)) that is competitive to far more sophisticated methods reported in the literature. The proposed solution exhibits considerable parallelism, which we exploit in a Graphics Processing Unit (GPU) implementation.
Search of Complex Binary Cellular Automata Using Behavioral Metrics
Venue: arXiv cs.FL 2015
Year: 2015

We propose the characterization of binary cellular automata using a set of behavioral metrics that are applied to the minimal Boolean form of a cellular automaton's transition function. These behavioral metrics are formulated to satisfy heuristic criteria derived from elementary cellular automata. Behaviors characterized through these metrics are growth, decrease, chaoticity, and stability. From these metrics, two measures of global behavior are calculated: 1) a static measure that considers all possible input patterns and counts the occurrence of the proposed metrics in the truth table of the minimal Boolean form of the automaton; 2) a dynamic measure, corresponding to the mean of the behavioral metrics in $n$ executions of the automaton, starting from $n$ random initial states. We use these measures to characterize a cellular automaton and guide a genetic search algorithm, which selects cellular automata similar to the Game of Life. Using this method, we found an extensive set of complex binary cellular automata with interesting properties, including self-replication.