OpenRaiser/Intern-Atlas huggingface dataset:
Key-dependent Security of Stream Ciphers
Venue: arXiv cs.CR 2020
Year: 2020

The control of the cryptography is more than ever a recurrent issue. As the current international regulation does not apply in the signatory countries, the concept of enforcing backdoors in encryption system is reborn with more strength. This paper deals with a particular class of stream cipher backdoors. This class, under a different form, has been widely used by the industry in the 80s and 90s in the context of the export control rules imposed by the US to the Western countries. We propose here a new system -- called BSEA-2, with a 128-bit secret key -- which is a seemingly minor modification of BSEA-1, a system proposed in \cite{filiol_bsea1}. BSEA-2 illustrates, in a simple and didactic~\textemdash~it has been also designed for a MSc cryptanalysis course~\textemdash~but efficient way the concept of key-dependent cryptographic security. The aim is to keep control on encryption means that a country/provider could provide to another country/client for which the secret key are also provided. With such systems, changing the key class results in downgrading the cryptographic security.
Non-Parametric Learning of Gaifman Models
Venue: arXiv cs.LG 2020
Year: 2020

We consider the problem of structure learning for Gaifman models and learn relational features that can be used to derive feature representations from a knowledge base. These relational features are first-order rules that are then partially grounded and counted over local neighborhoods of a Gaifman model to obtain the feature representations. We propose a method for learning these relational features for a Gaifman model by using relational tree distances. Our empirical evaluation on real data sets demonstrates the superiority of our approach over classical rule-learning.
Toward Optimal Adversarial Policies in the Multiplicative Learning System with a Malicious Expert
Venue: arXiv cs.LG 2020
Year: 2020

We consider a learning system based on the conventional multiplicative weight (MW) rule that combines experts' advice to predict a sequence of true outcomes. It is assumed that one of the experts is malicious and aims to impose the maximum loss on the system. The loss of the system is naturally defined to be the aggregate absolute difference between the sequence of predicted outcomes and the true outcomes. We consider this problem under both offline and online settings. In the offline setting where the malicious expert must choose its entire sequence of decisions a priori, we show somewhat surprisingly that a simple greedy policy of always reporting false prediction is asymptotically optimal with an approximation ratio of $1+O(\sqrt{\frac{\ln N}{N}})$, where $N$ is the total number of prediction stages. In particular, we describe a policy that closely resembles the structure of the optimal offline policy. For the online setting where the malicious expert can adaptively make its decisions, we show that the optimal online policy can be efficiently computed by solving a dynamic program in $O(N^3)$. Our results provide a new direction for vulnerability assessment of commonly used learning algorithms to adversarial attacks where the threat is an integral part of the system.
A Comparative Evaluation of Pitch Modification Techniques
Venue: arXiv cs.SD 2020
Year: 2020

This paper addresses the problem of pitch modification, as an important module for an efficient voice transformation system. The Deterministic plus Stochastic Model of the residual signal we proposed in a previous work is compared to TDPSOLA, HNM and STRAIGHT. The four methods are compared through an important subjective test. The influence of the speaker gender and of the pitch modification ratio is analyzed. Despite its higher compression level, the DSM technique is shown to give similar or better results than other methods, especially for male speakers and important ratios of modification. The DSM turns out to be only outperformed by STRAIGHT for female voices.
Eigenresiduals for improved Parametric Speech Synthesis
Venue: arXiv cs.SD 2020
Year: 2020

Statistical parametric speech synthesizers have recently shown their ability to produce natural-sounding and flexible voices. Unfortunately the delivered quality suffers from a typical buzziness due to the fact that speech is vocoded. This paper proposes a new excitation model in order to reduce this undesirable effect. This model is based on the decomposition of pitch-synchronous residual frames on an orthonormal basis obtained by Principal Component Analysis. This basis contains a limited number of eigenresiduals and is computed on a relatively small speech database. A stream of PCA-based coefficients is added to our HMM-based synthesizer and allows to generate the voiced excitation during the synthesis. An improvement compared to the traditional excitation is reported while the synthesis engine footprint remains under about 1Mb.
Large-scale Gender/Age Prediction of Tumblr Users
Venue: arXiv cs.LG 2020
Year: 2020

Tumblr, as a leading content provider and social media, attracts 371 million monthly visits, 280 million blogs and 53.3 million daily posts. The popularity of Tumblr provides great opportunities for advertisers to promote their products through sponsored posts. However, it is a challenging task to target specific demographic groups for ads, since Tumblr does not require user information like gender and ages during their registration. Hence, to promote ad targeting, it is essential to predict user's demography using rich content such as posts, images and social connections. In this paper, we propose graph based and deep learning models for age and gender predictions, which take into account user activities and content features. For graph based models, we come up with two approaches, network embedding and label propagation, to generate connection features as well as directly infer user's demography. For deep learning models, we leverage convolutional neural network (CNN) and multilayer perceptron (MLP) to prediction users' age and gender. Experimental results on real Tumblr daily dataset, with hundreds of millions of active users and billions of following relations, demonstrate that our approaches significantly outperform the baseline model, by improving the accuracy relatively by 81% for age, and the AUC and accuracy by 5\% for gender.
Efficient Information Reconciliation for Energy-Time Entanglement Quantum Key Distribution
Venue: arXiv cs.IT 2020
Year: 2020

Graph based codes such as low density parity check (LDPC) codes have been shown promising for the information reconciliation phase in quantum key distribution (QKD). However, existing graph coding schemes have not fully utilized the properties of the QKD channel. In this work, we first investigate the channel statistics for discrete variable (DV) QKD based on energy-time entangled photons. We then establish a so-called balanced modulation scheme that is promising for this channel. Based on the modulation, we propose a joint local-global graph coding scheme that is expected to achieve good error-correction performance.
Mining Disinformation and Fake News: Concepts, Methods, and Recent Advancements
Venue: arXiv cs.SI 2020
Year: 2020

In recent years, disinformation including fake news, has became a global phenomenon due to its explosive growth, particularly on social media. The wide spread of disinformation and fake news can cause detrimental societal effects. Despite the recent progress in detecting disinformation and fake news, it is still non-trivial due to its complexity, diversity, multi-modality, and costs of fact-checking or annotation. The goal of this chapter is to pave the way for appreciating the challenges and advancements via: (1) introducing the types of information disorder on social media and examine their differences and connections; (2) describing important and emerging tasks to combat disinformation for characterization, detection and attribution; and (3) discussing a weak supervision approach to detect disinformation with limited labeled data. We then provide an overview of the chapters in this book that represent the recent advancements in three related parts: (1) user engagements in the dissemination of information disorder; (2) techniques on detecting and mitigating disinformation; and (3) trending issues such as ethics, blockchain, clickbaits, etc. We hope this book to be a convenient entry point for researchers, practitioners, and students to understand the problems and challenges, learn state-of-the-art solutions for their specific needs, and quickly identify new research problems in their domains.
Bayesian task embedding for few-shot Bayesian optimization
Venue: arXiv cs.LG 2020
Year: 2020

We describe a method for Bayesian optimization by which one may incorporate data from multiple systems whose quantitative interrelationships are unknown a priori. All general (nonreal-valued) features of the systems are associated with continuous latent variables that enter as inputs into a single metamodel that simultaneously learns the response surfaces of all of the systems. Bayesian inference is used to determine appropriate beliefs regarding the latent variables. We explain how the resulting probabilistic metamodel may be used for Bayesian optimization tasks and demonstrate its implementation on a variety of synthetic and real-world examples, comparing its performance under zero-, one-, and few-shot settings against traditional Bayesian optimization, which usually requires substantially more data from the system of interest.
Statistical Detection of Collective Data Fraud
Venue: arXiv cs.DB 2020
Year: 2020

Statistical divergence is widely applied in multimedia processing, basically due to regularity and interpretable features displayed in data. However, in a broader range of data realm, these advantages may no longer be feasible, and therefore a more general approach is required. In data detection, statistical divergence can be used as a similarity measurement based on collective features. In this paper, we present a collective detection technique based on statistical divergence. The technique extracts distribution similarities among data collections, and then uses the statistical divergence to detect collective anomalies. Evaluation shows that it is applicable in the real world.
Differentially Private Combinatorial Cloud Auction
Venue: arXiv cs.CR 2020
Year: 2020

Cloud service providers typically provide different types of virtual machines (VMs) to cloud users with various requirements. Thanks to its effectiveness and fairness, auction has been widely applied in this heterogeneous resource allocation. Recently, several strategy-proof combinatorial cloud auction mechanisms have been proposed. However, they fail to protect the bid privacy of users from being inferred from the auction results. In this paper, we design a differentially private combinatorial cloud auction mechanism (DPCA) to address this privacy issue. Technically, we employ the exponential mechanism to compute a clearing unit price vector with a probability proportional to the corresponding revenue. We further improve the mechanism to reduce the running time while maintaining high revenues, by computing a single clearing unit price, or a subgroup of clearing unit prices at a time, resulting in the improved mechanisms DPCA-S and its generalized version DPCA-M, respectively. We theoretically prove that our mechanisms can guarantee differential privacy, approximate truthfulness and high revenue. Extensive experimental results demonstrate that DPCA can generate near-optimal revenues at the price of relatively high time complexity, while the improved mechanisms achieve a tunable trade-off between auction revenue and running time.
Fair Auction and Trade Framework for Cloud VM Allocation based on Blockchain
Venue: arXiv cs.CR 2020
Year: 2020

Cloud auctions provide cost-effective strategies for cloud VM allocation. Most existing cloud auctions simply assume that the auctioneer is trustable, and thus the fairness of auctions can be easily achieved. However, in fact, such a trustable auctioneer may not exist, and the fairness is non-trivial to guarantee. In this work, for the first time, we propose a decentralized cloud VM auction and trade framework based on blockchain. We realize both auction fairness and trade fairness among participants (e.g., cloud provider and cloud users) in this system, which guarantees the interest of each party will not suffer any loss as long as it follows the protocol. Furthermore, we implement our system through the local blockchain and Ethereum official test blockchain, carry out experimental simulations, and demonstrate the feasibility of our system.
Bounds on the size of PC and URC formulas
Venue: arXiv cs.LO 2020
Year: 2020

In this paper we investigate CNF formulas, for which the unit propagation is strong enough to derive a contradiction if the formula together with a partial assignment of the variables is unsatisfiable (unit refutation complete or URC formulas) or additionally to derive all implied literals if the formula is satisfiable (propagation complete or PC formulas). If a formula represents a function using existentially quantified auxiliary variables, it is called an encoding of the function. We prove several results on the sizes of PC and URC formulas and encodings. One of them are separations between the sizes of formulas of different types. Namely, we prove an exponential separation between the size of URC formulas and PC formulas and between the size of PC encodings using auxiliary variables and URC formulas. Besides of this, we prove that the sizes of any two irredundant PC formulas for the same function differ at most by a factor polynomial in the number of the variables and present an example of a function demonstrating that a similar statement is not true for URC formulas. One of the separations above implies that a q-Horn formula may require an exponential number of additional clauses to become a URC formula. On the other hand, for every q-Horn formula, we present a polynomial size URC encoding of the same function using auxiliary variables. This encoding is not q-Horn in general.
A cutting-plane algorithm for the Steiner team orienteering problem
Venue: arXiv cs.DS 2020
Year: 2020

The Team Orienteering Problem (TOP) is an NP-hard routing problem in which a fleet of identical vehicles aims at collecting rewards (prizes) available at given locations, while satisfying restrictions on the travel times. In TOP, each location can be visited by at most one vehicle, and the goal is to maximize the total sum of rewards collected by the vehicles within a given time limit. In this paper, we propose a generalization of TOP, namely the Steiner Team Orienteering Problem (STOP). In STOP, we provide, additionally, a subset of mandatory locations. In this sense, STOP also aims at maximizing the total sum of rewards collected within the time limit, but, now, every mandatory location must be visited. In this work, we propose a new commodity-based formulation for STOP and use it within a cutting-plane scheme. The algorithm benefits from the compactness and strength of the proposed formulation and works by separating three families of valid inequalities, which consist of some general connectivity constraints, classical lifted cover inequalities based on dual bounds and a class of conflict cuts. To our knowledge, the last class of inequalities is also introduced in this work. A state-of-the-art branch-and-cut algorithm from the literature of TOP is adapted to STOP and used as baseline to evaluate the performance of the cutting-plane. Extensive computational experiments show the competitiveness of the new algorithm while solving several STOP and TOP instances. In particular, it is able to solve, in total, 14 more TOP instances than any other previous exact algorithm and finds eight new optimality certificates. With respect to the new STOP instances introduced in this work, our algorithm solves 30 more instances than the baseline.
Novel Wake-up Scheme for Energy-Efficient Low-Latency Mobile Devices in 5G Networks
Venue: arXiv cs.IT 2020
Year: 2020

Improved mobile device battery lifetime and latency mini-mization are critical requirements for enhancing the mobile broadband services and user experience. Long-term evolution (LTE) networks have adopted discontinuous reception (DRX) as the baseline solution for prolonged battery lifetime. However, in every DRX cycle, the mobile device baseband processing unit monitors and decodes the control signaling, and thus all instances without any actual data allocation leads to unnecessary energy consumption. This fact together with the long start-up and power-down times can prevent adopting frequent wake-up instants, which in turn leads to considerable latency. In this work,a novel wake-up scheme is described and studied, to tackle the trade-off between latency and battery lifetime in future 5G networks, seeking thus to facilitate an always-available experience, rather than always-on. Analytical and simulation-based results show that the proposed scheme is a promising approach to control the user plane latency and energy consumption, when the device is operating in the power saving mode. The aim of this article is to describe the overall wake-up system operating principle and the associated signaling methods,receiver processing solutions and essential implementation aspects. Additionally, the advantages compared to DRX-based systems are shown and demonstrated, through the analysis of the system energy-efficiency and latency characteristics, with special emphasis on future 5G-grade mobile devices
The Radial Point Interpolation Mixed Collocation (RPIMC) Method for the Solution of Transient Diffusion Problems
Venue: arXiv cs.CE 2020
Year: 2020

The Radial Point Interpolation Mixed Collocation (RPIMC) method is proposed in this paper for transient analysis of diffusion problems. RPIMC is an efficient purely meshless method where the solution of the field variable is obtained through collocation. The field function and its gradient are both interpolated (mixed collocation approach) leading to reduced $C$-continuity requirement compared to strong-form collocation schemes. The method's accuracy is evaluated in heat conduction benchmark problems. The RPIMC convergence is compared against the Meshless Local Petrov-Galerkin Mixed Collocation (MLPG-MC) method and the Finite Element Method (FEM). Due to the delta Kronecker property of RPIMC, improved accuracy can be achieved as compared to MLPG-MC. RPIMC is proven to be a promising meshless alternative to FEM for transient diffusion problems.
Grab: Fast and Accurate Sensor Processing for Cashier-Free Shopping
Venue: arXiv cs.CV 2020
Year: 2020

Cashier-free shopping systems like Amazon Go improve shopping experience, but can require significant store redesign. In this paper, we propose Grab, a practical system that leverages existing infrastructure and devices to enable cashier-free shopping. Grab needs to accurately identify and track customers, and associate each shopper with items he or she retrieves from shelves. To do this, it uses a keypoint-based pose tracker as a building block for identification and tracking, develops robust feature-based face trackers, and algorithms for associating and tracking arm movements. It also uses a probabilistic framework to fuse readings from camera, weight and RFID sensors in order to accurately assess which shopper picks up which item. In experiments from a pilot deployment in a retail store, Grab can achieve over 90% precision and recall even when 40% of shopping actions are designed to confuse the system. Moreover, Grab has optimizations that help reduce investment in computing infrastructure four-fold.
Computing Euclidean k-Center over Sliding Windows
Venue: arXiv cs.CG 2020
Year: 2020

In the Euclidean $k$-center problem in sliding window model, input points are given in a data stream and the goal is to find the $k$ smallest congruent balls whose union covers the $N$ most recent points of the stream. In this model, input points are allowed to be examined only once and the amount of space that can be used to store relative information is limited. Cohen-Addad et al.~\cite{cohen-2016} gave a $(6+ε)$-approximation for the metric $k$-center problem using O($k/ε\log α$) points, where $α$ is the ratio of the largest and smallest distance and is assumed to be known in advance. In this paper, we present a $(3+ε)$-approximation algorithm for the Euclidean $1$-center problem using O($1/ε\log α$) points. We present an algorithm for the Euclidean $k$-center problem that maintains a coreset of size $O(k)$. Our algorithm gives a $(c+2\sqrt{3} + ε)$-approximation for the Euclidean $k$-center problem using O($k/ε\log α$) points by using any given $c$-approximation for the coreset where $c$ is a positive real number. For example, by using the $2$-approximation~\cite{feder-greene-1988} of the coreset, our algorithm gives a $(2+2\sqrt{3} + ε)$-approximation ($\approx 5.465$) using $O(k\log k)$ time. This is an improvement over the approximation factor of $(6+ε)$ by Cohen-Addad et al.~\cite{cohen-2016} with the same space complexity and smaller update time per point. Moreover we remove the assumption that $α$ is known in advance. Our idea can be adapted to the metric diameter problem and the metric $k$-center problem to remove the assumption. For low dimensional Euclidean space, we give an approximation algorithm that guarantees an even better approximation.
Adapting Deep Learning for Sentiment Classification of Code-Switched Informal Short Text
Venue: arXiv cs.CL 2020
Year: 2020

Nowadays, an abundance of short text is being generated that uses nonstandard writing styles influenced by regional languages. Such informal and code-switched content are under-resourced in terms of labeled datasets and language models even for popular tasks like sentiment classification. In this work, we (1) present a labeled dataset called MultiSenti for sentiment classification of code-switched informal short text, (2) explore the feasibility of adapting resources from a resource-rich language for an informal one, and (3) propose a deep learning-based model for sentiment classification of code-switched informal short text. We aim to achieve this without any lexical normalization, language translation, or code-switching indication. The performance of the proposed models is compared with three existing multilingual sentiment classification models. The results show that the proposed model performs better in general and adapting character-based embeddings yield equivalent performance while being computationally more efficient than training word-based domain-specific embeddings.
selp: A Single-Shot Epistemic Logic Program Solver
Venue: arXiv cs.LO 2020
Year: 2020

Epistemic Logic Programs (ELPs) are an extension of Answer Set Programming (ASP) with epistemic operators that allow for a form of meta-reasoning, that is, reasoning over multiple possible worlds. Existing ELP solving approaches generally rely on making multiple calls to an ASP solver in order to evaluate the ELP. However, in this paper, we show that there also exists a direct translation from ELPs into non-ground ASP with bounded arity. The resulting ASP program can thus be solved in a single shot. We then implement this encoding method, using recently proposed techniques to handle large, non-ground ASP rules, into the prototype ELP solving system "selp", which we present in this paper. This solver exhibits competitive performance on a set of ELP benchmark instances. Under consideration in Theory and Practice of Logic Programming (TPLP).
Transformer-based language modeling and decoding for conversational speech recognition
Venue: arXiv cs.CL 2020
Year: 2020

We propose a way to use a transformer-based language model in conversational speech recognition. Specifically, we focus on decoding efficiently in a weighted finite-state transducer framework. We showcase an approach to lattice re-scoring that allows for longer range history captured by a transfomer-based language model and takes advantage of a transformer's ability to avoid computing sequentially.