OpenRaiser/Intern-Atlas huggingface dataset:
Rational Threshold Cryptosystems
Venue: arXiv cs.CR 2019
Year: 2019

We propose a framework for threshold cryptosystems under a permissionless-economic model in which the participants are rational profit-maximizing entities. To date, threshold cryptosystems have been considered under permissioned settings with a limited adversary. Our framework relies on an escrow service that slashes and redistributes deposits to incentivize participants to adhere desired behaviors. Today, more than ever, sophisticated escrow services can be implemented over public blockchains like Ethereum, without additional trust assumptions. The key threat to rational threshold cryptosystems is collusion---by cooperating `illegally', a subset of participants can reveal the cryptosystem's secret, which, in turn is translated to unfair profit. Our countermeasure to collusion is framing. If the escrow is notified of collusion, it rewards the framer and slashes the deposits of all other participants. We show that colluding parties find themselves in the prisoner's dilemma, where the dominant strategy is framing.
Demystifying Multi-Faceted Video Summarization: Tradeoff Between Diversity,Representation, Coverage and Importance
Venue: arXiv cs.CV 2019
Year: 2019

This paper addresses automatic summarization of videos in a unified manner. In particular, we propose a framework for multi-faceted summarization for extractive, query base and entity summarization (summarization at the level of entities like objects, scenes, humans and faces in the video). We investigate several summarization models which capture notions of diversity, coverage, representation and importance, and argue the utility of these different models depending on the application. While most of the prior work on submodular summarization approaches has focused oncombining several models and learning weighted mixtures, we focus on the explainability of different models and featurizations, and how they apply to different domains. We also provide implementation details on summarization systems and the different modalities involved. We hope that the study from this paper will give insights into practitioners to appropriately choose the right summarization models for the problems at hand.
Faster and Smaller Two-Level Index for Network-based Trajectories
Venue: arXiv cs.DS 2019
Year: 2019

Two-level indexes have been widely used to handle trajectories of moving objects that are constrained to a network. The top-level of these indexes handles the spatial dimension, whereas the bottom level handles the temporal dimension. The latter turns out to be an instance of the interval-intersection problem, but it has been tackled by non-specialized spatial indexes. In this work, we propose the use of a compact data structure on the bottom level of these indexes. Our experimental evaluation shows that our approach is both faster and smaller than existing solutions.
VeriSolid: Correct-by-Design Smart Contracts for Ethereum
Venue: arXiv cs.CR 2019
Year: 2019

The adoption of blockchain based distributed ledgers is growing fast due to their ability to provide reliability, integrity, and auditability without trusted entities. One of the key capabilities of these emerging platforms is the ability to create self-enforcing smart contracts. However, the development of smart contracts has proven to be error-prone in practice, and as a result, contracts deployed on public platforms are often riddled with security vulnerabilities. This issue is exacerbated by the design of these platforms, which forbids updating contract code and rolling back malicious transactions. In light of this, it is crucial to ensure that a smart contract is secure before deploying it and trusting it with significant amounts of cryptocurrency. To this end, we introduce the VeriSolid framework for the formal verification of contracts that are specified using a transition-system based model with rigorous operational semantics. Our model-based approach allows developers to reason about and verify contract behavior at a high level of abstraction. VeriSolid allows the generation of Solidity code from the verified models, which enables the correct-by-design development of smart contracts.
AVA-ActiveSpeaker: An Audio-Visual Dataset for Active Speaker Detection
Venue: arXiv cs.CV 2019
Year: 2019

Active speaker detection is an important component in video analysis algorithms for applications such as speaker diarization, video re-targeting for meetings, speech enhancement, and human-robot interaction. The absence of a large, carefully labeled audio-visual dataset for this task has constrained algorithm evaluations with respect to data diversity, environments, and accuracy. This has made comparisons and improvements difficult. In this paper, we present the AVA Active Speaker detection dataset (AVA-ActiveSpeaker) that will be released publicly to facilitate algorithm development and enable comparisons. The dataset contains temporally labeled face tracks in video, where each face instance is labeled as speaking or not, and whether the speech is audible. This dataset contains about 3.65 million human labeled frames or about 38.5 hours of face tracks, and the corresponding audio. We also present a new audio-visual approach for active speaker detection, and analyze its performance, demonstrating both its strength and the contributions of the dataset.
The Oxford Multimotion Dataset: Multiple SE(3) Motions with Ground Truth
Venue: arXiv cs.RO 2019
Year: 2019

Datasets advance research by posing challenging new problems and providing standardized methods of algorithm comparison. High-quality datasets exist for many important problems in robotics and computer vision, including egomotion estimation and motion/scene segmentation, but not for techniques that estimate every motion in a scene. Metric evaluation of these multimotion estimation techniques requires datasets consisting of multiple, complex motions that also contain ground truth for every moving body. The Oxford Multimotion Dataset provides a number of multimotion estimation problems of varying complexity. It includes both complex problems that challenge existing algorithms as well as a number of simpler problems to support development. These include observations from both static and dynamic sensors, a varying number of moving bodies, and a variety of different 3D motions. It also provides a number of experiments designed to isolate specific challenges of the multimotion problem, including rotation about the optical axis and occlusion. In total, the Oxford Multimotion Dataset contains over 110 minutes of multimotion data consisting of stereo and RGB-D camera images, IMU data, and Vicon ground-truth trajectories. The dataset culminates in a complex toy car segment representative of many challenging real-world scenarios. This paper describes each experiment with a focus on its relevance to the multimotion estimation problem.
Bandwidth Reduction using Importance Weighted Pruning on Ring AllReduce
Venue: arXiv cs.LG 2019
Year: 2019

It is inevitable to train large deep learning models on a large-scale cluster equipped with accelerators system. Deep gradient compression would highly increase the bandwidth utilization and speed up the training process but hard to implement on ring structure. In this paper, we find that redundant gradient and gradient staleness has negative effect on training. We have observed that in different epoch and different steps, the neural networks focus on updating different layers and different parameters. In order to save more communication bandwidth and preserve the accuracy on ring structure, which break the restrict as the node increase, we propose a new algorithm to measure the importance of gradients on large-scale cluster implementing ring all-reduce based on the size of the ratio of parameter calculation gradient to parameter value. Our importance weighted pruning approach achieved 64X and 58.8X of gradient compression ratio on AlexNet and ResNet50 on ImageNet. Meanwhile, in order to maintain the sparseness of the gradient propagation, we randomly broadcast the index of important gradients on each node. While the remaining nodes are ready for the index gradient and perform all-reduce update. This would speed up the convergence of the model and preserve the training accuracy.
Segmentation Guided Image-to-Image Translation with Adversarial Networks
Venue: arXiv cs.CV 2019
Year: 2019

Recently image-to-image translation has received increasing attention, which aims to map images in one domain to another specific one. Existing methods mainly solve this task via a deep generative model, and focus on exploring the relationship between different domains. However, these methods neglect to utilize higher-level and instance-specific information to guide the training process, leading to a great deal of unrealistic generated images of low quality. Existing methods also lack of spatial controllability during translation. To address these challenge, we propose a novel Segmentation Guided Generative Adversarial Networks (SGGAN), which leverages semantic segmentation to further boost the generation performance and provide spatial mapping. In particular, a segmentor network is designed to impose semantic information on the generated images. Experimental results on multi-domain face image translation task empirically demonstrate our ability of the spatial modification and our superiority in image quality over several state-of-the-art methods.
Toward a Theory of Cyber Attacks
Venue: arXiv cs.CR 2019
Year: 2019

We provide a general methodology for analyzing defender-attacker based "games" in which we model such games as Markov models and introduce a capacity region to analyze how defensive and adversarial strategies impact security. Such a framework allows us to analyze under what kind of conditions we can prove statements (about an attack objective $k$) of the form "if the attacker has a time budget $T_{bud}$, then the probability that the attacker can reach an attack objective $\geq k$ is at most $poly(T_{bud})negl(k)$". We are interested in such rigorous cryptographic security guarantees (that describe worst-case guarantees) as these shed light on the requirements of a defender's strategy for preventing more and more the progress of an attack, in terms of the "learning rate" of a defender's strategy. We explain the damage an attacker can achieve by a "containment parameter" describing the maximally reached attack objective within a specific time window.
Bounds on the Length of Functional PIR and Batch codes
Venue: arXiv cs.IT 2019
Year: 2019

A functional $k$-PIR code of dimension $s$ consists of $n$ servers storing linear combinations of $s$ linearly independent information symbols. Any linear combination of the $s$ information symbols can be recovered by $k$ disjoint subsets of servers. The goal is to find the smallest number of servers for given $k$ and $s$. We provide lower bounds on the number of servers and constructions which yield upper bounds on this number. For $k \leq 4$, exact bounds on the number of servers are proved. Furthermore, we provide some asymptotic bounds. The problem coincides with the well known private information retrieval problem based on a coded database to reduce the storage overhead, when each linear combination contains exactly one information symbol. If any multiset of size $k$ of linear combinations from the linearly independent information symbols can be recovered by $k$ disjoint subset of servers, then the servers form a functional $k$-batch code. A~functional $k$-batch code is a functional $k$-PIR code, where all the $k$ linear combinations in the multiset are equal. We provide some bounds on the number of servers for functional $k$-batch codes. In particular we present a random construction and a construction based on simplex codes, WOM codes, and RIO codes.
A conversation around the analysis of the SiP effort estimation dataset
Venue: arXiv cs.SE 2019
Year: 2019

The analysis of over ten years of commercial development using Agile (10,100 unique task estimates made by 22 developers, under 20 project codes) is documented via a conversation involving the data analyst and a director of the company that created the SiP dataset. Factors found to influence task implementation effort estimation accuracy include the person making the estimate, the project involved, and the propensity to use round numbers. Any improvement in estimation accuracy, with practice, did not noticeably improve regression models fitted.
Tooth morphometry using quasi-conformal theory
Venue: arXiv cs.CV 2019
Year: 2019

Shape analysis is important in anthropology, bioarchaeology and forensic science for interpreting useful information from human remains. In particular, teeth are morphologically stable and hence well-suited for shape analysis. In this work, we propose a framework for tooth morphometry using quasi-conformal theory. Landmark-matching Teichmüller maps are used for establishing a 1-1 correspondence between tooth surfaces with prescribed anatomical landmarks. Then, a quasi-conformal statistical shape analysis model based on the Teichmüller mapping results is proposed for building a tooth classification scheme. We deploy our framework on a dataset of human premolars to analyze the tooth shape variation among genders and ancestries. Experimental results show that our method achieves much higher classification accuracy with respect to both gender and ancestry when compared to the existing methods. Furthermore, our model reveals the underlying tooth shape difference between different genders and ancestries in terms of the local geometric distortion and curvatures.
Variational bridge constructs for approximate Gaussian process regression
Venue: arXiv cs.LG 2019
Year: 2019

This paper introduces a method to approximate Gaussian process regression by representing the problem as a stochastic differential equation and using variational inference to approximate solutions. The approximations are compared with full GP regression and generated paths are demonstrated to be indistinguishable from GP samples. We show that the approach extends easily to non-linear dynamics and discuss extensions to which the approach can be easily applied.
Approximate Discontinuous Trajectory Hotspots
Venue: arXiv cs.CG 2019
Year: 2019

A hotspot is an axis-aligned square of fixed side length $s$, the duration of the presence of an entity moving in the plane in which is maximised. An exact hotspot of a polygonal trajectory with $n$ edges can be found in $O(n^2)$. Defining a $c$-approximate hotspot as an axis-aligned square of side length $cs$, in which the duration of the entity's presence is no less than that of an exact hotspot, in this paper we present an algorithm to find a $(1 + ε)$-approximate hotspot of a polygonal trajectory with the time complexity $O({nϕ\over ε} \log {nϕ\over ε})$, where $ϕ$ is the ratio of average trajectory edge length to $s$.
Baker game and polynomial-time approximation schemes
Venue: arXiv cs.DM 2019
Year: 2019

Baker devised a technique to obtain approximation schemes for many optimization problems restricted to planar graphs; her technique was later extended to more general graph classes. In particular, using the Baker's technique and the minor structure theorem, Dawar et al. gave Polynomial-Time Approximation Schemes (PTAS) for all monotone optimization problems expressible in the first-order logic when restricted to a proper minor-closed class of graphs. We define a Baker game formalizing the notion of repeated application of Baker's technique interspersed with vertex removal, prove that monotone optimization problems expressible in the first-order logic admit PTAS when restricted to graph classes in which the Baker game can be won in a constant number of rounds, and prove without use of the minor structure theorem that all proper minor-closed classes of graphs have this property.
Fusing Body Posture with Facial Expressions for Joint Recognition of Affect in Child-Robot Interaction
Venue: arXiv cs.CV 2019
Year: 2019

In this paper we address the problem of multi-cue affect recognition in challenging scenarios such as child-robot interaction. Towards this goal we propose a method for automatic recognition of affect that leverages body expressions alongside facial ones, as opposed to traditional methods that typically focus only on the latter. Our deep-learning based method uses hierarchical multi-label annotations and multi-stage losses, can be trained both jointly and separately, and offers us computational models for both individual modalities, as well as for the whole body emotion. We evaluate our method on a challenging child-robot interaction database of emotional expressions collected by us, as well as on the GEMEP public database of acted emotions by adults, and show that the proposed method achieves significantly better results than facial-only expression baselines.
Keeping CALM: When Distributed Consistency is Easy
Venue: arXiv cs.DC 2019
Year: 2019

A key concern in modern distributed systems is to avoid the cost of coordination while maintaining consistent semantics. Until recently, there was no answer to the question of when coordination is actually required. In this paper we present an informal introduction to the CALM Theorem, which answers this question precisely by moving up from traditional storage consistency to consider properties of programs. CALM is an acronym for "consistency as logical monotonicity". The CALM Theorem shows that the programs that have consistent, coordination-free distributed implementations are exactly the programs that can be expressed in monotonic logic. This theoretical result has practical implications for developers of distributed applications. We show how CALM provides a constructive application-level counterpart to conventional "systems" wisdom, such as the apparently negative results of the CAP Theorem. We also discuss ways that monotonic thinking can influence distributed systems design, and how new programming language designs and tools can help developers write consistent, coordination-free code.
Distributed Learning with Adversarial Agents Under Relaxed Network Condition
Venue: arXiv cs.DC 2019
Year: 2019

This work studies the problem of non-Bayesian learning over multi-agent network when there are some adversarial (faulty) agents in the network. At each time step, each non-faulty agent collects partial information about an unknown state of the world and tries to estimate true state of the world by iteratively sharing information with its neighbors. Existing algorithms in this setting require that all non-faulty agents in the network should be able to achieve consensus via local information exchange. In this work, we present an analysis of a distributed algorithm which does not require the network to achieve consensus. We show that if every non-faulty agent can receive enough information (via iteratively communicating with neighbors) to differentiate the true state of the world from other possible states then it can indeed learn the true state.
A Compact Representation of Raster Time Series
Venue: arXiv cs.DS 2019
Year: 2019

The raster model is widely used in Geographic Information Systems to represent data that vary continuously in space, such as temperatures, precipitations, elevation, among other spatial attributes. In applications like weather forecast systems, not just a single raster, but a sequence of rasters covering the same region at different timestamps, known as a raster time series, needs to be stored and queried. Compact data structures have proven successful to provide space-efficient representations of rasters with query capabilities. Hence, a naive approach to save space is to use such a representation for each raster in a time series. However, in this paper we show that it is possible to take advantage of the temporal locality that exists in a raster time series to reduce the space necessary to store it while keeping competitive query times for several types of queries.
Efficient Winograd Convolution via Integer Arithmetic
Venue: arXiv cs.NE 2019
Year: 2019

Convolution is the core operation for many deep neural networks. The Winograd convolution algorithms have been shown to accelerate the widely-used small convolution sizes. Quantized neural networks can effectively reduce model sizes and improve inference speed, which leads to a wide variety of kernels and hardware accelerators that work with integer data. The state-of-the-art Winograd algorithms pose challenges for efficient implementation and execution by the integer kernels and accelerators. We introduce a new class of Winograd algorithms by extending the construction to the field of complex and propose optimizations that reduce the number of general multiplications. The new algorithm achieves an arithmetic complexity reduction of $3.13$x over the direct method and an efficiency gain up to $17.37\%$ over the rational algorithms. Furthermore, we design and implement an integer-based filter scaling scheme to effectively reduce the filter bit width by $30.77\%$ without any significant accuracy loss.
Graph- and finite element-based total variation models for the inverse problem in diffuse optical tomography
Venue: arXiv cs.CV 2019
Year: 2019

Total variation (TV) is a powerful regularization method that has been widely applied in different imaging applications, but is difficult to apply to diffuse optical tomography (DOT) image reconstruction (inverse problem) due to complex and unstructured geometries, non-linearity of the data fitting and regularization terms, and non-differentiability of the regularization term. We develop several approaches to overcome these difficulties by: i) defining discrete differential operators for unstructured geometries using both finite element and graph representations; ii) developing an optimization algorithm based on the alternating direction method of multipliers (ADMM) for the non-differentiable and non-linear minimization problem; iii) investigating isotropic and anisotropic variants of TV regularization, and comparing their finite element- and graph-based implementations. These approaches are evaluated on experiments on simulated data and real data acquired from a tissue phantom. Our results show that both FEM and graph-based TV regularization is able to accurately reconstruct both sparse and non-sparse distributions without the over-smoothing effect of Tikhonov regularization and the over-sparsifying effect of L$_1$ regularization. The graph representation was found to out-perform the FEM method for low-resolution meshes, and the FEM method was found to be more accurate for high-resolution meshes.
Decision-making and Fuzzy Temporal Logic
Venue: arXiv cs.AI 2019
Year: 2019

This paper shows that the fuzzy temporal logic can model figures of thought to describe decision-making behaviors. In order to exemplify, some economic behaviors observed experimentally were modeled from problems of choice containing time, uncertainty and fuzziness. Related to time preference, it is noted that the subadditive discounting is mandatory in positive rewards situations and, consequently, results in the magnitude effect and time effect, where the last has a stronger discounting for earlier delay periods (as in, one hour, one day), but a weaker discounting for longer delay periods (for instance, six months, one year, ten years). In addition, it is possible to explain the preference reversal (change of preference when two rewards proposed on different dates are shifted in the time). Related to the Prospect Theory, it is shown that the risk seeking and the risk aversion are magnitude dependents, where the risk seeking may disappear when the values to be lost are very high.