OpenRaiser/Intern-Atlas huggingface dataset:
Private Information Retrieval from MDS Coded Data in Distributed Storage Systems
Venue: arXiv cs.IT 2018
Year: 2018

The problem of providing privacy, in the private information retrieval (PIR) sense, to users requesting data from a distributed storage system (DSS), is considered. The DSS is coded by an $(n,k,d)$ Maximum Distance Separable (MDS) code to store the data reliably on unreliable storage nodes. Some of these nodes can be spies which report to a third party, such as an oppressive regime, which data is being requested by the user. An information theoretic PIR scheme ensures that a user can satisfy its request while revealing, to the spy nodes, no information on which data is being requested. A user can trivially achieve PIR by downloading all the data in the DSS. However, this is not a feasible solution due to its high communication cost. We construct PIR schemes with low download communication cost. When there is $b=1$ spy node in the DSS, we construct PIR schemes with download cost $\frac{1}{1-R}$ per unit of requested data ($R=k/n$ is the code rate), achieving the information theoretic limit for linear schemes. The proposed schemes are universal since they depend on the code rate, but not on the generator matrix of the code. Also, when $b\leq n-δk$, for some $δ\in \mathbb{N^+}$, we construct linear PIR schemes with $cPoP = \frac{b+δk}δ$.
Sign-Compute-Resolve for Tree Splitting Random Access
Venue: arXiv cs.IT 2018
Year: 2018

We present a framework for random access that is based on three elements: physical-layer network coding (PLNC), signature codes and tree splitting. In presence of a collision, physical-layer network coding enables the receiver to decode, i.e. compute, the sum of the packets that were transmitted by the individual users. For each user, the packet consists of the user's signature, as well as the data that the user wants to communicate. As long as no more than K users collide, their identities can be recovered from the sum of their signatures. This framework for creating and transmitting packets can be used as a fundamental building block in random access algorithms, since it helps to deal efficiently with the uncertainty of the set of contending terminals. In this paper we show how to apply the framework in conjunction with a tree-splitting algorithm, which is required to deal with the case that more than K users collide. We demonstrate that our approach achieves throughput that tends to 1 rapidly as K increases. We also present results on net data-rate of the system, showing the impact of the overheads of the constituent elements of the proposed protocol. We compare the performance of our scheme with an upper bound that is obtained under the assumption that the active users are a priori known. Also, we consider an upper bound on the net data-rate for any PLNC based strategy in which one linear equation per slot is decoded. We show that already at modest packet lengths, the net data-rate of our scheme becomes close to the second upper bound, i.e. the overhead of the contention resolution algorithm and the signature codes vanishes.
Weighted Unsupervised Learning for 3D Object Detection
Venue: arXiv cs.CV 2018
Year: 2018

This paper introduces a novel weighted unsupervised learning for object detection using an RGB-D camera. This technique is feasible for detecting the moving objects in the noisy environments that are captured by an RGB-D camera. The main contribution of this paper is a real-time algorithm for detecting each object using weighted clustering as a separate cluster. In a preprocessing step, the algorithm calculates the pose 3D position X, Y, Z and RGB color of each data point and then it calculates each data point's normal vector using the point's neighbor. After preprocessing, our algorithm calculates k-weights for each data point; each weight indicates membership. Resulting in clustered objects of the scene.
Asymptotic Analysis and Spatial Coupling of Counter Braids
Venue: arXiv cs.IT 2018
Year: 2018

A counter braid (CB) is a novel counter architecture introduced by Lu et al. in 2007 for per-flow measurements on high-speed links which can be decoded with low complexity using message passing (MP). CBs achieve an asymptotic compression rate (under optimal decoding) that matches the entropy lower bound of the flow size distribution. In this paper, we apply the concept of spatial coupling to CBs to improve the performance of the original CBs and analyze the performance of the resulting spatially-coupled CBs (SC-CBs). We introduce an equivalent bipartite graph representation of CBs with identical iteration-by-iteration finite-length and asymptotic performance. Based on this equivalent representation, we then analyze the asymptotic performance of single-layer CBs and SC-CBs under the MP decoding algorithm proposed by Lu et al.. In particular, we derive the potential threshold of the uncoupled system and show that it is equal to the area threshold. We also derive the Maxwell decoder for CBs and prove that the potential threshold is an upper bound on the Maxwell decoding threshold. We show that the area under the extended MP extrinsic information transfer curve is equal to zero precisely at the area threshold. This, combined with the analysis of the Maxwell decoder and simulation results, leads us to the conjecture that the potential threshold is equal to the Maxwell decoding threshold and hence a lower bound on the maximum a posteriori decoding threshold. Interestingly, SC-CBs do not show the well-known phenomenon of threshold saturation of the MP decoding threshold to the potential threshold characteristic of spatially-coupled low-density parity-check codes and other coupled systems. However, SC-CBs yield better MP decoding thresholds than their uncoupled counterparts. Finally, we also consider SC-CBs as a compressed sensing scheme and show that low undersampling factors can be achieved.
A loopless and branchless $O(1)$ algorithm to generate the next Dyck word
Venue: arXiv cs.DS 2018
Year: 2018

Let integer be any C/C++ unsigned integer type up to 64-bits long. Given a Dyck word the following code returns the next Dyck word of the same size, provided it exists. integer next_dyck_word(integer w) { integer const a = w & -w; integer const b = w + a; integer c = w ^ b; c = (c / a >> 2) + 1; c = ((c * c - 1) & 0xaaaaaaaaaaaaaaaa) | b; return c; }
Non-Truthful Position Auctions Are More Robust to Misspecification
Venue: arXiv cs.GT 2018
Year: 2018

In the standard single-dimensional model of position auctions, bidders agree on the relative values of the positions and each of them submits a single bid that is interpreted in terms of these values. Motivated by current practice in sponsored search we consider a situation where the auctioneer uses estimates of the relative values, which may be imprecise, and show that under both complete and incomplete information a non-truthful mechanism is able to support an efficient outcome in equilibrium for a wider range of these estimates than the VCG mechanism. We thus exhibit a property of the VCG mechanism that may help explain the surprising rarity with which it is used even in settings with unit demand, a relative lack of robustness to misspecification of the bidding language. The result for complete information concerns the generalized second-price mechanism and lends additional theoretical support to the use of this mechanism in practice. Particularly interesting from a technical perspective is the result for incomplete information, which is driven by a surprising connection between equilibrium bids in the VCG mechanism and the generalized first-price mechanism.
Capacity Limits of Diffusion-Based Molecular Timing Channels
Venue: arXiv cs.IT 2018
Year: 2018

This work introduces capacity limits for molecular timing (MT) channels, where information is modulated in the release timing of small information particles, and decoded from the time of arrivals at the receiver. It is shown that the random time of arrival can be represented as an additive noise channel, and for the diffusion-based MT (DBMT) channel this noise is distributed according to the Lévy distribution. Lower and upper bounds on the capacity of the DBMT channel are derived for the case where the delay associated with the propagation of the information particles in the channel is finite, namely, when the information particles dissipate after a finite time interval. For the case where a single particle is released per channel use, these bounds are shown to be tight. When the transmitter simultaneously releases a large number of particles, the detector at the receiver may not be able to precisely detect the arrival time of all the particles. Therefore, two alternative models are considered: detection based on the particle that arrives first, or detection based on the average arrival times. Tight lower and upper bounds are derived for these two models. It is shown that by controlling the maximal delay of the information particles, the capacity can increase poly-logarithmically with the number of released particles. As each particle takes a random independent path, this diversity of paths is analogous to receiver diversity and can be used to considerably increase the achievable data rates.
Complex-demand Scheduling Problem with Application in Smart Grid
Venue: arXiv cs.DS 2018
Year: 2018

We consider the problem of scheduling complex-valued demands over a discretized time horizon. Given a set of users, each user is associated with a set of demands representing different power consumption preferences. A demand is represented by a complex number, a time interval, and a utility value obtained if it is satisfied. At each time slot, the magnitude of the total selected demands should not exceed a given generation capacity. This naturally captures the supply constraints in alternating current (AC) electric systems. In this paper, we consider maximizing the aggregate user utility subject to power supply limits over a time horizon. We present approximation algorithms characterized by the maximum angle $ϕ$ between any two complex-valued demands. More precisely, a PTAS is presented for the case $ϕ\in [0,\tfracπ{2}]$, a bi-criteria FPTAS for $ϕ\in [0,π \mbox{-} \varepsilon]$ for any polynomially small $\varepsilon$, assuming the number of time slots in the discretized time horizon is a constant. Furthermore, if the number of time slots is part of the input, we present a reduction to the real-valued unsplittable flow problem on a path with only a constant approximation ratio. Finally, we present a practical greedy algorithm for the single time slot case with an approximation ratio of $\tfrac{1}{2}\cos \fracϕ{2}$ and a running time complexity of only ${O}(N\log N)$, $N$ standing for the aggregate number of user demands, which can be implemented efficiently in practice.
Topology-Guided Path Integral Approach for Stochastic Optimal Control in Cluttered Environment
Venue: arXiv cs.RO 2018
Year: 2018

This paper addresses planning and control of robot motion under uncertainty that is formulated as a continuous-time, continuous-space stochastic optimal control problem, by developing a topology-guided path integral control method. The path integral control framework, which forms the backbone of the proposed method, re-writes the Hamilton-Jacobi-Bellman equation as a statistical inference problem; the resulting inference problem is solved by a sampling procedure that computes the distribution of controlled trajectories around the trajectory by the passive dynamics. For motion control of robots in a highly cluttered environment, however, this sampling can easily be trapped in a local minimum unless the sample size is very large, since the global optimality of local minima depends on the degree of uncertainty. Thus, a homology-embedded sampling-based planner that identifies many (potentially) local-minimum trajectories in different homology classes is developed to aid the sampling process. In combination with a receding-horizon fashion of the optimal control the proposed method produces a dynamically feasible and collision-free motion plans without being trapped in a local minimum. Numerical examples on a synthetic toy problem and on quadrotor control in a complex obstacle field demonstrate the validity of the proposed method.
Consistently faster and smaller compressed bitmaps with Roaring
Venue: arXiv cs.DB 2018
Year: 2018

Compressed bitmap indexes are used in databases and search engines. Many bitmap compression techniques have been proposed, almost all relying primarily on run-length encoding (RLE). However, on unsorted data, we can get superior performance with a hybrid compression technique that uses both uncompressed bitmaps and packed arrays inside a two-level tree. An instance of this technique, Roaring, has recently been proposed. Due to its good performance, it has been adopted by several production platforms (e.g., Apache Lucene, Apache Spark, Apache Kylin and Druid). Yet there are cases where run-length encoded bitmaps are smaller than the original Roaring bitmaps---typically when the data is sorted so that the bitmaps contain long compressible runs. To better handle these cases, we build a new Roaring hybrid that combines uncompressed bitmaps, packed arrays and RLE compressed segments. The result is a new Roaring format that compresses better. Overall, our new implementation of Roaring can be several times faster (up to two orders of magnitude) than the implementations of traditional RLE-based alternatives (WAH, Concise, EWAH) while compressing better. We review the design choices and optimizations that make these good results possible.
A Stochastic Differential Equation Framework for Guiding Online User Activities in Closed Loop
Venue: arXiv cs.SI 2018
Year: 2018

Recently, there is a surge of interest in using point processes to model continuous-time user activities. This framework has resulted in novel models and improved performance in diverse applications. However, most previous works focus on the "open loop" setting where learned models are used for predictive tasks. Typically, we are interested in the "closed loop" setting where a policy needs to be learned to incorporate user feedbacks and guide user activities to desirable states. Although point processes have good predictive performance, it is not clear how to use them for the challenging closed loop activity guiding task. In this paper, we propose a framework to reformulate point processes into stochastic differential equations, which allows us to extend methods from stochastic optimal control to address the activity guiding problem. We also design an efficient algorithm, and show that our method guides user activities to desired states more effectively than the state of the art.
Fast Computation of Isomorphisms Between Finite Fields Using Elliptic Curves
Venue: arXiv cs.DS 2018
Year: 2018

We propose a randomized algorithm to compute isomorphisms between finite fields using elliptic curves. To compute an isomorphism between two fields of cardinality $q^n$, our algorithm takes $$n^{1+o(1)} \log^{1+o(1)}q + \max_{\ell} \left(\ell^{n_\ell + 1+o(1)} \log^{2+o(1)} q + O(\ell \log^5q)\right)$$ time, where $\ell$ runs through primes dividing $n$ but not $q(q-1)$ and $n_\ell$ denotes the highest power of $\ell$ dividing $n$. Prior to this work, the best known run time dependence on $n$ was quadratic. Our run time dependence on $n$ is at worst quadratic but is subquadratic if $n$ has no large prime factor. In particular, the $n$ for which our run time is nearly linear in $n$ have natural density at least $3/10$. The crux of our approach is finding a point on an elliptic curve of a prescribed prime power order or equivalently finding preimages under the Lang map on elliptic curves over finite fields. We formulate this as an open problem whose resolution would solve the finite field isomorphism problem with run time nearly linear in $n$.
Video Analysis for Body-worn Cameras in Law Enforcement
Venue: arXiv cs.CY 2018
Year: 2018

The social conventions and expectations around the appropriate use of imaging and video has been transformed by the availability of video cameras in our pockets. The impact on law enforcement can easily be seen by watching the nightly news; more and more arrests, interventions, or even routine stops are being caught on cell phones or surveillance video, with both positive and negative consequences. This proliferation of the use of video has led law enforcement to look at the potential benefits of incorporating video capture systematically in their day to day operations. At the same time, recognition of the inevitability of widespread use of video for police operations has caused a rush to deploy all types of cameras, including body worn cameras. However, the vast majority of police agencies have limited experience in utilizing video to its full advantage, and thus do not have the capability to fully realize the value of expanding their video capabilities. In this white paper, we highlight some of the technology needs and challenges of body-worn cameras, and we relate these needs to the relevant state of the art in computer vision and multimedia research. We conclude with a set of recommendations.
A declarative Language for Rapid Business Development
Venue: arXiv cs.SE 2018
Year: 2018

The motivation for ZoomBA are domain specific languages (DSL) like VERILOG, VHDL, Spice. DSL for Software testing is not a new idea, many commercial tools like Silk Suite use them, while Selenese, the DSL for Selenium IDE [6] is open source. ZoomBA is a functionally motivated, embeddable, Turing Complete language. It's philosophy is to expose the existing Java echo system in a declarative fashion for the purpose of System Integration and software validation. By design ZoomBA script size is meagre compared to Python or even to Scala for business automation problems. Bayestree uses ZoomBA for system integration/adapter/data manipulation purposes.
Flexible Fractional Repetition Codes for Distributed Storage Networks
Venue: arXiv cs.IT 2018
Year: 2018

Consider the following fundamental question of distributed storage networks: Given any arbitrary $(n,k,d)$ values, whether there exists an intelligent helper selection scheme (assuming unlimited memory and computing power) that can strictly improve the storage-bandwidth (S-B) tradeoff. Ahmad et al. 18' answered this question by proving that for a subset of $(n,k,d)$ values, no helper selection scheme can ever improve the S-B tradeoff, and for the $(n,k,d)$ not in that subset, a new scheme called family helper selection (FHS) can strictly improve the S-B tradeoff over a blind helper selection scheme. Nonetheless, the analysis of FHS is done by a min-cut analysis with no actual code construction. This work fills this gap between pure min-cut analysis and actual code construction by pairing FHS with a new, generalized version of the existing fractional repetition (FR) codes. Specifically, existing FR codes are exact-repair codes that admit the highly-desirable repair-by-transfer property, but its unique construction limits the application to a restricted set of $(n,k,d)$ values. In contrast, our new construction, termed flexible fractional repetition codes, can be applied to arbitrary $(n,k,d)$ while retaining most of the practical benefits of FR codes, i.e., admitting small repair bandwidth, being exact-repair, and being almost repairable-by-transfer.
Analyzing Timed Systems Using Tree Automata
Venue: arXiv cs.FL 2018
Year: 2018

Timed systems, such as timed automata, are usually analyzed using their operational semantics on timed words. The classical region abstraction for timed automata reduces them to (untimed) finite state automata with the same time-abstract properties, such as state reachability. We propose a new technique to analyze such timed systems using finite tree automata instead of finite word automata. The main idea is to consider timed behaviors as graphs with matching edges capturing timing constraints. When a family of graphs has bounded tree-width, they can be interpreted in trees and MSO-definable properties of such graphs can be checked using tree automata. The technique is quite general and applies to many timed systems. In this paper, as an example, we develop the technique on timed pushdown systems, which have recently received considerable attention. Further, we also demonstrate how we can use it on timed automata and timed multi-stack pushdown systems (with boundedness restrictions).
Unsupervised Total Variation Loss for Semi-supervised Deep Learning of Semantic Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

We introduce a novel unsupervised loss function for learning semantic segmentation with deep convolutional neural nets (ConvNet) when densely labeled training images are not available. More specifically, the proposed loss function penalizes the L1-norm of the gradient of the label probability vector image , i.e. total variation, produced by the ConvNet. This can be seen as a regularization term that promotes piecewise smoothness of the label probability vector image produced by the ConvNet during learning. The unsupervised loss function is combined with a supervised loss in a semi-supervised setting to learn ConvNets that can achieve high semantic segmentation accuracy even when only a tiny percentage of the pixels in the training images are labeled. We demonstrate significant improvements over the purely supervised setting in the Weizmann horse, Stanford background and Sift Flow datasets. Furthermore, we show that using the proposed piecewise smoothness constraint in the learning phase significantly outperforms post-processing results from a purely supervised approach with Markov Random Fields (MRF). Finally, we note that the framework we introduce is general and can be used to learn to label other types of structures such as curvilinear structures by modifying the unsupervised loss function accordingly.
Active Uncertainty Calibration in Bayesian ODE Solvers
Venue: arXiv cs.NA 2018
Year: 2018

There is resurging interest, in statistics and machine learning, in solvers for ordinary differential equations (ODEs) that return probability measures instead of point estimates. Recently, Conrad et al. introduced a sampling-based class of methods that are 'well-calibrated' in a specific sense. But the computational cost of these methods is significantly above that of classic methods. On the other hand, Schober et al. pointed out a precise connection between classic Runge-Kutta ODE solvers and Gaussian filters, which gives only a rough probabilistic calibration, but at negligible cost overhead. By formulating the solution of ODEs as approximate inference in linear Gaussian SDEs, we investigate a range of probabilistic ODE solvers, that bridge the trade-off between computational cost and probabilistic calibration, and identify the inaccurate gradient measurement as the crucial source of uncertainty. We propose the novel filtering-based method Bayesian Quadrature filtering (BQF) which uses Bayesian quadrature to actively learn the imprecision in the gradient measurement by collecting multiple gradient evaluations.
On the Gap Between Separating Words and Separating Their Reversals
Venue: arXiv cs.FL 2018
Year: 2018

A deterministic finite automaton (DFA) separates two strings $w$ and $x$ if it accepts $w$ and rejects $x$. The minimum number of states required for a DFA to separate $w$ and $x$ is denoted by $sep(w,x)$. The present paper shows that the difference $|sep(w,x)-sep(w^R,x^R)|$ is unbounded for a binary alphabet; here $w^R$ stands for the mirror image of $w$. This solves an open problem stated in [Demaine, Eisenstat, Shallit, Wilson: Remarks on separating words. DCFS 2011. LNCS vol. 6808, pp. 147-157.]