OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Proofs of Retrievability with Public Verifiability for Dynamic Cloud Storage
Venue: arXiv cs.CR 2018
Year: 2018

Cloud service providers offer various facilities to their clients. The clients with limited resources opt for some of these facilities. They can outsource their bulk data to the cloud server. The cloud server maintains these data in lieu of monetary benefits. However, a malicious cloud server might delete some of these data to save some space and offer this extra amount of storage to another client. Therefore, the client might not retrieve her file (or some portions of it) as often as needed. Proofs of retrievability (POR) provide an assurance to the client that the server is actually storing all of her data appropriately and they can be retrieved at any point of time. In a dynamic POR scheme, the client can update her data after she uploads them to the cloud server. Moreover, in publicly verifiable POR schemes, the client can delegate her auditing task to some third party specialized for this purpose. In this work, we exploit the homomorphic hashing technique to design a publicly verifiable dynamic POR scheme that is more efficient (in terms of bandwidth required between the client and the server) than the "state-of-the-art" publicly verifiable dynamic POR scheme. We also analyze security and performance of our scheme.
High-Dimensional Stochastic Optimal Control using Continuous Tensor Decompositions
Venue: arXiv cs.RO 2018
Year: 2018

Motion planning and control problems are embedded and essential in almost all robotics applications. These problems are often formulated as stochastic optimal control problems and solved using dynamic programming algorithms. Unfortunately, most existing algorithms that guarantee convergence to optimal solutions suffer from the curse of dimensionality: the run time of the algorithm grows exponentially with the dimension of the state space of the system. We propose novel dynamic programming algorithms that alleviate the curse of dimensionality in problems that exhibit certain low-rank structure. The proposed algorithms are based on continuous tensor decompositions recently developed by the authors. Essentially, the algorithms represent high-dimensional functions (e.g., the value function) in a compressed format, and directly perform dynamic programming computations (e.g., value iteration, policy iteration) in this format. Under certain technical assumptions, the new algorithms guarantee convergence towards optimal solutions with arbitrary precision. Furthermore, the run times of the new algorithms scale polynomially with the state dimension and polynomially with the ranks of the value function. This approach realizes substantial computational savings in "compressible" problem instances, where value functions admit low-rank approximations. We demonstrate the new algorithms in a wide range of problems, including a simulated six-dimensional agile quadcopter maneuvering example and a seven-dimensional aircraft perching example. In some of these examples, we estimate computational savings of up to ten orders of magnitude over standard value iteration algorithms. We further demonstrate the algorithms running in real time on board a quadcopter during a flight experiment under motion capture.
Diversity encouraged learning of unsupervised LSTM ensemble for neural activity video prediction
Venue: arXiv cs.CV 2018
Year: 2018

Being able to predict the neural signal in the near future from the current and previous observations has the potential to enable real-time responsive brain stimulation to suppress seizures. We have investigated how to use an auto-encoder model consisting of LSTM cells for such prediction. Recog- nizing that there exist multiple activity pattern clusters, we have further explored to train an ensemble of LSTM mod- els so that each model can specialize in modeling certain neural activities, without explicitly clustering the training data. We train the ensemble using an ensemble-awareness loss, which jointly solves the model assignment problem and the error minimization problem. During training, for each training sequence, only the model that has the lowest recon- struction and prediction error is updated. Intrinsically such a loss function enables each LTSM model to be adapted to a subset of the training sequences that share similar dynamic behavior. We demonstrate this can be trained in an end- to-end manner and achieve significant accuracy in neural activity prediction.
Hilbert Transform, Analytic Signal, and Modulation Analysis for Graph Signal Processing
Venue: arXiv cs.IT 2018
Year: 2018

We propose Hilbert transform (HT) and analytic signal (AS) construction for signals over graphs. This is motivated by the popularity of HT, AS, and modulation analysis in conventional signal processing, and the observation that complementary insight is often obtained by viewing conventional signals in the graph setting. Our definitions of HT and AS use a conjugate-symmetry-like property exhibited by the graph Fourier transform (GFT). We show that a real graph signal (GS) can be represented using smaller number of GFT coefficients than the signal length. We show that the graph HT (GHT) and graph AS (GAS) operations are linear and shift-invariant over graphs. Using the GAS, we define the amplitude, phase, and frequency modulations for a graph signal (GS). Further, we use convex optimization to develop an alternative definition of envelope for a GS. We illustrate the proposed concepts by showing applications to synthesized and real-world signals. For example, we show that the GHT is suitable for anomaly detection/analysis over networks and that GAS reveals complementary information in speech signals.
A Fast and Provable Method for Estimating Clique Counts Using Turán's Theorem
Venue: arXiv cs.SI 2018
Year: 2018

Clique counts reveal important properties about the structure of massive graphs, especially social networks. The simple setting of just 3-cliques (triangles) has received much attention from the research community. For larger cliques (even, say 6-cliques) the problem quickly becomes intractable because of combinatorial explosion. Most methods used for triangle counting do not scale for large cliques, and existing algorithms require massive parallelism to be feasible. We present a new randomized algorithm that provably approximates the number of k-cliques, for any constant k. The key insight is the use of (strengthenings of) the classic Turán's theorem: this claims that if the edge density of a graph is sufficiently high, the k-clique density must be non-trivial. We define a combinatorial structure called a Turán shadow, the construction of which leads to fast algorithms for clique counting. We design a practical heuristic, called TURÁN-SHADOW, based on this theoretical algorithm, and test it on a large class of test graphs. In all cases,TURÁN-SHADOW has less than 2% error, in a fraction of the time used by well-tuned exact algorithms. We do detailed comparisons with a range of other sampling algorithms, and find that TURÁN-SHADOW is generally much faster and more accurate. For example, TURÁN-SHADOW estimates all cliques numbers up to size 10 in social network with over a hundred million edges. This is done in less than three hours on a single commodity machine.
Extern Objects in P4: an ROHC Header Compression Scheme Case Study
Venue: arXiv cs.NI 2018
Year: 2018

P4 is an emergent packet-processing language with which the user can describe how the packets are to be processed in a switching element. This paper presents a way to implement complex operations that are not natively supported in P4. In this work, we explored two different methods to add extensions to P4: i) using new native primitives and ii) using extern instances. As a case study, an ROHC entity was implemented and invoked in a P4 program. The tests showed similar relative performance in both methods in terms of normalized packet latency. However, extern instances appear to be more suitable for target-specific switching applications, where the manufacturer/vendor can specify its own specific operations without changes in the P4 syntax and semantics. Extern instances only require changes in the target-specific backend compiler while keeping the P4 frontend compiler unchanged. The use of externs also results in a more elegant code solution since they are implemented outside the switch-core, thus reducing side effects risks that can be caused by a modification in a switch pipeline implementation.
Improving the Coverage and Spectral Efficiency of Millimeter-Wave Cellular Networks using Device-to-Device Relays
Venue: arXiv cs.ET 2018
Year: 2018

The susceptibility of millimeter waveform propagation to blockages limits the coverage of millimeter-wave (mmWave) signals. To overcome blockages, we propose to leverage two-hop device-to-device (D2D) relaying. Using stochastic geometry, we derive expressions for the downlink coverage probability of relay-assisted mmWave cellular networks when the D2D links are implemented in either uplink mmWave or uplink microwave bands. We further investigate the spectral efficiency (SE) improvement in the cellular downlink, and the effect of D2D transmissions on the cellular uplink. For mmWave links, we derive the coverage probability using dominant interferer analysis while accounting for both blockages and beamforming gains. For microwave D2D links, we derive the coverage probability considering both line-of-sight (LOS) and non-line-of-sight (NLOS) propagation. Numerical results show that downlink coverage and SE can be improved using two-hop D2D relaying. Specifically, microwave D2D relays achieve better coverage because D2D connections can be established under NLOS conditions. However, mmWave D2D relays achieve better coverage when the density of interferers is large because blockages eliminate interference from NLOS interferers. The SE on the downlink depends on the relay mode selection strategy, and mmWave D2D relays use a significantly smaller fraction of uplink resources than microwave D2D relays.
Why RLC realizations of certain impedances need many more energy storage elements than expected
Venue: arXiv cs.SY 2018
Year: 2018

It is a significant and longstanding puzzle that the resistor, inductor, capacitor (RLC) networks obtained by the established RLC realization procedures appear highly non-minimal from the perspective of linear systems theory. Specifically, each of these networks contains significantly more energy storage elements than the McMillan degree of its impedance, and possesses a non-minimal state-space representation whose states correspond to the inductor currents and capacitor voltages. Despite this apparent non-minimality, there have been no improved algorithms since the 1950s, with the concurrent discovery by Reza, Pantell, Fialkow and Gerst of a class of networks (the RPFG networks), which are a slight simplification of the Bott-Duffin networks. Each RPFG network contains more than twice as many energy storage elements as the McMillan degree of its impedance, yet it has never been established if all of these energy storage elements are necessary. In this paper, we present some newly discovered alternatives to the RPFG networks. We then prove that the RPFG networks, and these newly discovered networks, contain the least possible number of energy storage elements for realizing certain positive-real functions. In other words, all RLC networks which realize certain impedances contain more than twice the expected number (McMillan degree) of energy storage elements.
PsyPhy: A Psychophysics Driven Evaluation Framework for Visual Recognition
Venue: arXiv cs.CV 2018
Year: 2018

By providing substantial amounts of data and standardized evaluation protocols, datasets in computer vision have helped fuel advances across all areas of visual recognition. But even in light of breakthrough results on recent benchmarks, it is still fair to ask if our recognition algorithms are doing as well as we think they are. The vision sciences at large make use of a very different evaluation regime known as Visual Psychophysics to study visual perception. Psychophysics is the quantitative examination of the relationships between controlled stimuli and the behavioral responses they elicit in experimental test subjects. Instead of using summary statistics to gauge performance, psychophysics directs us to construct item-response curves made up of individual stimulus responses to find perceptual thresholds, thus allowing one to identify the exact point at which a subject can no longer reliably recognize the stimulus class. In this article, we introduce a comprehensive evaluation framework for visual recognition models that is underpinned by this methodology. Over millions of procedurally rendered 3D scenes and 2D images, we compare the performance of well-known convolutional neural networks. Our results bring into question recent claims of human-like performance, and provide a path forward for correcting newly surfaced algorithmic deficiencies.
Risk-Sensitive Learning and Pricing for Demand Response
Venue: arXiv cs.LG 2018
Year: 2018

We consider the setting in which an electric power utility seeks to curtail its peak electricity demand by offering a fixed group of customers a uniform price for reductions in consumption relative to their predetermined baselines. The underlying demand curve, which describes the aggregate reduction in consumption in response to the offered price, is assumed to be affine and subject to unobservable random shocks. Assuming that both the parameters of the demand curve and the distribution of the random shocks are initially unknown to the utility, we investigate the extent to which the utility might dynamically adjust its offered prices to maximize its cumulative risk-sensitive payoff over a finite number of $T$ days. In order to do so effectively, the utility must design its pricing policy to balance the tradeoff between the need to learn the unknown demand model (exploration) and maximize its payoff (exploitation) over time. In this paper, we propose such a pricing policy, which is shown to exhibit an expected payoff loss over $T$ days that is at most $O(\sqrt{T}\log(T))$, relative to an oracle pricing policy that knows the underlying demand model. Moreover, the proposed pricing policy is shown to yield a sequence of prices that converge to the oracle optimal prices in the mean square sense.
Mending Fences with Self-Invalidation and Self-Downgrade
Venue: arXiv cs.LO 2018
Year: 2018

Cache coherence protocols based on self-invalidation and self-downgrade have recently seen increased popularity due to their simplicity, potential performance efficiency, and low energy consumption. However, such protocols result in memory instruction reordering, thus causing extra program behaviors that are often not intended by the programmers. We propose a novel formal model that captures the semantics of programs running under such protocols, and features a set of fences that interact with the coherence layer. Using the model, we design an algorithm to analyze the reachability and check whether a program satisfies a given safety property with the current set of fences. We describe a method for insertion of optimal sets of fences that ensure correctness of the program under such protocols. The method relies on a counter-example guided fence insertion procedure. One feature of our method is that it can handle a variety of fences (with different costs). This diversity makes optimization more difficult since one has to optimize the total cost of the inserted fences, rather than just their number. To demonstrate the strength of our approach, we have implemented a prototype and run it on a wide range of examples and benchmarks. We have also, using simulation, evaluated the performance of the resulting fenced programs.
Perpetually Dominating Large Grids
Venue: arXiv cs.DM 2018
Year: 2018

In the m-\emph{Eternal Domination} game, a team of guard tokens initially occupies a dominating set on a graph $G$. An attacker then picks a vertex without a guard on it and attacks it. The guards defend against the attack: one of them has to move to the attacked vertex, while each remaining one can choose to move to one of his neighboring vertices. The new guards' placement must again be dominating. This attack-defend procedure continues eternally. The guards win if they can eternally maintain a dominating set against any sequence of attacks, otherwise, the attacker wins. The m-\emph{eternal domination number} for a graph $G$ is the minimum amount of guards such that they win against any attacker strategy in $G$ (all guards move model). We study rectangular grids and provide the first known general upper bound on the m-eternal domination number for these graphs. Our novel strategy implements a square rotation principle and eternally dominates $m \times n$ grids by using approximately $\frac{mn}{5}$ guards, which is asymptotically optimal even for ordinary domination.
The problem of Pi_2-cut-introduction
Venue: arXiv cs.LO 2018
Year: 2018

We describe an algorithmic method of proof compression based on the introduction of Pi_2-cuts into a cut-free LK-proof. The current approach is based on an inversion of Gentzen s cut-elimination method and extends former methods for introducing Pi_1-cuts. The Herbrand instances of a cut-free proof pi of a sequent S are described by a grammar G which encodes substitutions defined in the elimination of quantified cuts. We present an algorithm which, given a grammar G, constructs a Pi_2-cut formula A and a proof phi of S with one cut on A. It is shown that, by this algorithm, we can achieve an exponential proof compression.
Finite-Length Analysis of Spatially-Coupled Regular LDPC Ensembles on Burst-Erasure Channels
Venue: arXiv cs.IT 2018
Year: 2018

Regular spatially-Coupled LDPC (SC-LDPC) ensembles have gained significant interest since they were shown to universally achieve the capacity of binary memoryless channels under low-complexity belief-propagation decoding. In this work, we focus primarily on the performance of these ensembles over binary channels affected by bursts of erasures. We first develop an analysis of the finite length performance for a single burst per codeword and no errors otherwise. We first assume that the burst erases a complete spatial position, modeling for instance node failures in distributed storage. We provide new tight lower bounds for the block erasure probability ($P_{\mathrm{B}}$) at finite block length and bounds on the coupling parameter for being asymptotically able to recover the burst. We further show that expurgating the ensemble can improve the block erasure probability by several orders of magnitude. Later we extend our methodology to more general channel models. In a first extension, we consider bursts that can start at a random position in the codeword and span across multiple spatial positions. Besides the finite length analysis, we determine by means of density evolution the maximnum correctable burst length. In a second extension, we consider the case where in addition to a single burst, random bit erasures may occur. Finally, we consider a block erasure channel model which erases each spatial position independently with some probability $p$, potentially introducing multiple bursts simultaneously. All results are verified using Monte-Carlo simulations.
On Sub-Propositional Fragments of Modal Logic
Venue: arXiv cs.LO 2018
Year: 2018

In this paper, we consider the well-known modal logics $\mathbf{K}$, $\mathbf{T}$, $\mathbf{K4}$, and $\mathbf{S4}$, and we study some of their sub-propositional fragments, namely the classical Horn fragment, the Krom fragment, the so-called core fragment, defined as the intersection of the Horn and the Krom fragments, plus their sub-fragments obtained by limiting the use of boxes and diamonds in clauses. We focus, first, on the relative expressive power of such languages: we introduce a suitable measure of expressive power, and we obtain a complex hierarchy that encompasses all fragments of the considered logics. Then, after observing the low expressive power, in particular, of the Horn fragments without diamonds, we study the computational complexity of their satisfiability problem, proving that, in general, it becomes polynomial.
Combining Data-driven and Model-driven Methods for Robust Facial Landmark Detection
Venue: arXiv cs.CV 2018
Year: 2018

Facial landmark detection is an important yet challenging task for real-world computer vision applications. This paper proposes an effective and robust approach for facial landmark detection by combining data- and model-driven methods. Firstly, a Fully Convolutional Network (FCN) is trained to compute response maps of all facial landmark points. Such a data-driven method could make full use of holistic information in a facial image for global estimation of facial landmarks. After that, the maximum points in the response maps are fitted with a pre-trained Point Distribution Model (PDM) to generate the initial facial shape. This model-driven method is able to correct the inaccurate locations of outliers by considering the shape prior information. Finally, a weighted version of Regularized Landmark Mean-Shift (RLMS) is employed to fine-tune the facial shape iteratively. This Estimation-Correction-Tuning process perfectly combines the advantages of the global robustness of data-driven method (FCN), outlier correction capability of model-driven method (PDM) and non-parametric optimization of RLMS. Results of extensive experiments demonstrate that our approach achieves state-of-the-art performances on challenging datasets including 300W, AFLW, AFW and COFW. The proposed method is able to produce satisfying detection results on face images with exaggerated expressions, large head poses, and partial occlusions.
On Equivalence of Binary Asymmetric Channels regarding the Maximum Likelihood Decoding
Venue: arXiv cs.IT 2018
Year: 2018

We study the problem of characterizing when two memoryless binary asymmetric channels, described by their transition probabilities $(p,q)$ and $(p',q')$, are equivalent from the point of view of maximum likelihood decoding (MLD) when restricted to $n$-block binary codes. This equivalence of channels induces a partition (depending on $n$) on the space of parameters $(p,q)$ into regions associated with the equivalence classes. Explicit expressions for describing these regions, their number and areas are derived. Some perspectives of applications of our results to decoding problems are also presented.
Anchored Correlation Explanation: Topic Modeling with Minimal Domain Knowledge
Venue: arXiv cs.CL 2018
Year: 2018

While generative models such as Latent Dirichlet Allocation (LDA) have proven fruitful in topic modeling, they often require detailed assumptions and careful specification of hyperparameters. Such model complexity issues only compound when trying to generalize generative models to incorporate human input. We introduce Correlation Explanation (CorEx), an alternative approach to topic modeling that does not assume an underlying generative model, and instead learns maximally informative topics through an information-theoretic framework. This framework naturally generalizes to hierarchical and semi-supervised extensions with no additional modeling assumptions. In particular, word-level domain knowledge can be flexibly incorporated within CorEx through anchor words, allowing topic separability and representation to be promoted with minimal human intervention. Across a variety of datasets, metrics, and experiments, we demonstrate that CorEx produces topics that are comparable in quality to those produced by unsupervised and semi-supervised variants of LDA.