OpenRaiser/Intern-Atlas huggingface dataset:
CertLedger: A New PKI Model with Certificate Transparency Based on Blockchain
Venue: arXiv cs.CR 2018
Year: 2018

In conventional PKI, CAs are assumed to be fully trusted. However, in practice, CAs' absolute responsibility for providing trustworthiness caused major security and privacy issues. To prevent such issues, Google introduced the concept of Certificate Transparency (CT) in 2013. Later, several new PKI models (e.g., AKI, ARPKI, and DTKI) are proposed to reduce the level of trust to the CAs. However, all of these proposals are still vulnerable to split-world attacks if the adversary is capable of showing different views of the log to the targeted victims. In this paper, we propose a new PKI architecture with certificate transparency based on blockchain, what we called CertLedger, to eliminate the split-world attacks and to provide an ideal certificate/revocation transparency. All TLS certificates, their revocation status, entire revocation process, and trusted CA management are conducted in the CertLedger. CertLedger provides a unique, efficient, and trustworthy certificate validation process eliminating the conventional inadequate and incompatible certificate validation processes implemented by different software vendors. TLS clients in the CertLedger also do not require to make certificate validation and store the trusted CA certificates anymore. We analyze the security and performance of the CertLedger and provide a comparison with the previous proposals.
Learning Linear Temporal Properties
Venue: arXiv cs.LO 2018
Year: 2018

We present two novel algorithms for learning formulas in Linear Temporal Logic (LTL) from examples. The first learning algorithm reduces the learning task to a series of satisfiability problems in propositional Boolean logic and produces a smallest LTL formula (in terms of the number of subformulas) that is consistent with the given data. Our second learning algorithm, on the other hand, combines the SAT-based learning algorithm with classical algorithms for learning decision trees. The result is a learning algorithm that scales to real-world scenarios with hundreds of examples, but can no longer guarantee to produce minimal consistent LTL formulas. We compare both learning algorithms and demonstrate their performance on a wide range of synthetic benchmarks. Additionally, we illustrate their usefulness on the task of understanding executions of a leader election protocol.
Rotation Equivariant CNNs for Digital Pathology
Venue: arXiv cs.CV 2018
Year: 2018

We propose a new model for digital pathology segmentation, based on the observation that histopathology images are inherently symmetric under rotation and reflection. Utilizing recent findings on rotation equivariant CNNs, the proposed model leverages these symmetries in a principled manner. We present a visual analysis showing improved stability on predictions, and demonstrate that exploiting rotation equivariance significantly improves tumor detection performance on a challenging lymph node metastases dataset. We further present a novel derived dataset to enable principled comparison of machine learning models, in combination with an initial benchmark. Through this dataset, the task of histopathology diagnosis becomes accessible as a challenging benchmark for fundamental machine learning research.
Michael John Caldwell Gordon (FRS 1994), 28 February 1948 -- 22 August 2017
Venue: arXiv cs.GL 2018
Year: 2018

Michael Gordon was a pioneer in the field of interactive theorem proving and hardware verification. In the 1970s, he had the vision of formally verifying system designs, proving their correctness using mathematics and logic. He demonstrated his ideas on real-world computer designs. His students extended the work to such diverse areas as the verification of floating-point algorithms, the verification of probabilistic algorithms and the verified translation of source code to correct machine code. He was elected to the Royal Society in 1994, and he continued to produce outstanding research until retirement. His achievements include his work at Edinburgh University helping to create Edinburgh LCF, the first interactive theorem prover of its kind, and the ML family of functional programming languages. He adopted higher-order logic as a general formalism for verification, showing that it could specify hardware designs from the gate level right up to the processor level. It turned out to be an ideal formalism for many problems in computer science and mathematics. His tools and techniques have exerted a huge influence across the field of formal verification.
PubMed Labs: An experimental platform for improving biomedical literature search
Venue: arXiv cs.DB 2018
Year: 2018

PubMed is a freely accessible system for searching the biomedical literature, with approximately 2.5 million users worldwide on an average workday. We have recently developed PubMed Labs (www.pubmed.gov/labs), an experimental platform for users to test new features/tools and provide feedback, which enables us to make more informed decisions about potential changes to improve the search quality and overall usability of PubMed. In doing so, we hope to better meet our user needs in an era of information overload. Another novel aspect of PubMed Labs lies in its mobile-first and responsive layout, which offers better support for accessing PubMed on the increasingly popular use of mobile and small-screen devices. Currently, PubMed Labs only includes a core subset of PubMed functionalities, e.g. search, facets. We encourage users to test PubMed Labs and share their experience with us, based on which we expect to continuously improve PubMed Labs with more advanced features and better user experience.
Exploiting Mobility in Cache-Assisted D2D Networks: Performance Analysis and Optimization
Venue: arXiv cs.IT 2018
Year: 2018

Caching popular content at mobile devices, accompanied by device-to-device (D2D) communications, is one promising technology for effective mobile content delivery. User mobility is an important factor when investigating such networks, which unfortunately was largely ignored in most previous works. Preliminary studies have been carried out, but the effect of mobility on the caching performance has not been fully understood. In this paper, by explicitly considering users' contact and inter-contact durations via an alternating renewal process, we first investigate the effect of mobility with a given cache placement. A tractable expression of the data offloading ratio, i.e., the proportion of requested data that can be delivered via D2D links, is derived, which is proved to be increasing with the user moving speed. The analytical results are then used to develop an effective mobility-aware caching strategy to maximize the data offloading ratio. Simulation results are provided to confirm the accuracy of the analytical results and also validate the effect of user mobility. Performance gains of the proposed mobility-aware caching strategy are demonstrated with both stochastic models and real-life data sets. It is observed that the information of the contact durations is critical to design cache placement, especially when they are relatively short or comparable to the inter-contact durations.
Overload Control for Scaling WeChat Microservices
Venue: arXiv cs.DC 2018
Year: 2018

Effective overload control for large-scale online service system is crucial for protecting the system backend from overload. Conventionally, the design of overload control is ad-hoc for individual service. However, service-specific overload control could be detrimental to the overall system due to intricate service dependencies or flawed implementation of service. Service developers usually have difficulty to accurately estimate the dynamics of actual workload during the development of service. Therefore, it is essential to decouple the overload control from service logic. In this paper, we propose DAGOR, an overload control scheme designed for the account-oriented microservice architecture. DAGOR is service agnostic and system-centric. It manages overload at the microservice granule such that each microservice monitors its load status in real time and triggers load shedding in a collaborative manner among its relevant services when overload is detected. DAGOR has been used in the WeChat backend for five years. Experimental results show that DAGOR can benefit high success rate of service even when the system is experiencing overload, while ensuring fairness in the overload control.
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy
Venue: arXiv cs.CC 2018
Year: 2018

$ \newcommand{\eps}ε \newcommand{\NP}{\mathsf{NP}} \newcommand{\YES}{\mathsf{YES}} \newcommand{\NO}{\mathsf{NO}} \newcommand{\myminus}{\text{-}}\newcommand{\Bsat}{\mathsf{B}} \newcommand{\threesat}{\rm{3}\myminus\mathsf{SAT}} \newcommand{\gapthreesat}{\mathsf{\forall\exists}\myminus{\rm{3}}\myminus\mathsf{SAT}} $In 1991, Papadimitriou and Yannakakis gave a reduction implying the $\NP$-hardness of approximating the problem $\threesat$ with bounded occurrences. Their reduction is based on expander graphs. We present an analogue of this result for the second level of the polynomial-time hierarchy based on superconcentrator graphs. This resolves an open question of Ko and Lin (1995) and should be useful in deriving inapproximability results in the polynomial-time hierarchy. More precisely, we show that given an instance of $\gapthreesat$ in which every variable occurs at most $\Bsat$ times (for some absolute constant $\Bsat$), it is $Π_2$-hard to distinguish between the following two cases: $\YES$ instances, in which for any assignment to the universal variables there exists an assignment to the existential variables that satisfies all the clauses, and $\NO$ instances in which there exists an assignment to the universal variables such that any assignment to the existential variables satisfies at most a $1-\eps$ fraction of the clauses. We also generalize this result to any level of the polynomial-time hierarchy.
Degree based Classification of Harmful Speech using Twitter Data
Venue: arXiv cs.CL 2018
Year: 2018

Harmful speech has various forms and it has been plaguing the social media in different ways. If we need to crackdown different degrees of hate speech and abusive behavior amongst it, the classification needs to be based on complex ramifications which needs to be defined and hold accountable for, other than racist, sexist or against some particular group and community. This paper primarily describes how we created an ontological classification of harmful speech based on degree of hateful intent, and used it to annotate twitter data accordingly. The key contribution of this paper is the new dataset of tweets we created based on ontological classes and degrees of harmful speech found in the text. We also propose supervised classification system for recognizing these respective harmful speech classes in the texts hence.
Perturbation Resilient Clustering for $k$-Center and Related Problems via LP Relaxations
Venue: arXiv cs.DS 2018
Year: 2018

We consider clustering in the perturbation resilience model that has been studied since the work of Bilu and Linial [ICS, 2010] and Awasthi, Blum and Sheffet [Inf. Proc. Lett., 2012]. A clustering instance $I$ is said to be $α$-perturbation resilient if the optimal solution does not change when the pairwise distances are modified by a factor of $α$ and the perturbed distances satisfy the metric property --- this is the metric perturbation resilience property introduced in Angelidakis et. al. [STOC, 2010] and a weaker requirement than prior models. We make two high-level contributions. 1) We show that the natural LP relaxation of $k$-center and asymmetric $k$-center is integral for $2$-perturbation resilient instances. We belive that demonstrating the goodness of standard LP relaxations complements existing results that are based on combinatorial algorithms designed for the perturbation model. 2) We define a simple new model of perturbation resilience for clustering with \emph{outliers}. Using this model we show that the unified MST and dynamic programming based algorithm proposed by Angelidakis et. al. [STOC, 2010] exactly solves the clustering with outliers problem for several common center based objectives (like $k$-center, $k$-means, $k$-median) when the instances is $2$-perturbation resilient. We further show that a natural LP relxation is integral for $2$-perturbation resilient instances of \kcenter with outliers.
A Note about: Local Explanation Methods for Deep Neural Networks lack Sensitivity to Parameter Values
Venue: arXiv cs.LG 2018
Year: 2018

Local explanation methods, also known as attribution methods, attribute a deep network's prediction to its input (cf. Baehrens et al. (2010)). We respond to the claim from Adebayo et al. (2018) that local explanation methods lack sensitivity, i.e., DNNs with randomly-initialized weights produce explanations that are both visually and quantitatively similar to those produced by DNNs with learned weights. Further investigation reveals that their findings are due to two choices in their analysis: (a) ignoring the signs of the attributions; and (b) for integrated gradients (IG), including pixels in their analysis that have zero attributions by choice of the baseline (an auxiliary input relative to which the attributions are computed). When both factors are accounted for, IG attributions for a random network and the actual network are uncorrelated. Our investigation also sheds light on how these issues affect visualizations, although we note that more work is needed to understand how viewers interpret the difference between the random and the actual attributions.
The Potential of the Return Distribution for Exploration in RL
Venue: arXiv cs.LG 2018
Year: 2018

This paper studies the potential of the return distribution for exploration in deterministic reinforcement learning (RL) environments. We study network losses and propagation mechanisms for Gaussian, Categorical and Gaussian mixture distributions. Combined with exploration policies that leverage this return distribution, we solve, for example, a randomized Chain task of length 100, which has not been reported before when learning with neural networks.
Pseudorandom Generators for Width-3 Branching Programs
Venue: arXiv cs.CC 2018
Year: 2018

We construct pseudorandom generators of seed length $\tilde{O}(\log(n)\cdot \log(1/ε))$ that $ε$-fool ordered read-once branching programs (ROBPs) of width $3$ and length $n$. For unordered ROBPs, we construct pseudorandom generators with seed length $\tilde{O}(\log(n) \cdot \mathrm{poly}(1/ε))$. This is the first improvement for pseudorandom generators fooling width $3$ ROBPs since the work of Nisan [Combinatorica, 1992]. Our constructions are based on the `iterated milder restrictions' approach of Gopalan et al. [FOCS, 2012] (which further extends the Ajtai-Wigderson framework [FOCS, 1985]), combined with the INW-generator [STOC, 1994] at the last step (as analyzed by Braverman et al. [SICOMP, 2014]). For the unordered case, we combine iterated milder restrictions with the generator of Chattopadhyay et al. [CCC, 2018]. Two conceptual ideas that play an important role in our analysis are: (1) A relabeling technique allowing us to analyze a relabeled version of the given branching program, which turns out to be much easier. (2) Treating the number of colliding layers in a branching program as a progress measure and showing that it reduces significantly under pseudorandom restrictions. In addition, we achieve nearly optimal seed-length $\tilde{O}(\log(n/ε))$ for the classes of: (1) read-once polynomials on $n$ variables, (2) locally-monotone ROBPs of length $n$ and width $3$ (generalizing read-once CNFs and DNFs), and (3) constant-width ROBPs of length $n$ having a layer of width $2$ in every consecutive $\mathrm{poly}\log(n)$ layers.
3D Pose Estimation for Fine-Grained Object Categories
Venue: arXiv cs.CV 2018
Year: 2018

Existing object pose estimation datasets are related to generic object types and there is so far no dataset for fine-grained object categories. In this work, we introduce a new large dataset to benchmark pose estimation for fine-grained objects, thanks to the availability of both 2D and 3D fine-grained data recently. Specifically, we augment two popular fine-grained recognition datasets (StanfordCars and CompCars) by finding a fine-grained 3D CAD model for each sub-category and manually annotating each object in images with 3D pose. We show that, with enough training data, a full perspective model with continuous parameters can be estimated using 2D appearance information alone. We achieve this via a framework based on Faster/Mask R-CNN. This goes beyond previous works on category-level pose estimation, which only estimate discrete/continuous viewpoint angles or recover rotation matrices often with the help of key points. Furthermore, with fine-grained 3D models available, we incorporate a dense 3D representation named as location field into the CNN-based pose estimation framework to further improve the performance. The new dataset is available at www.umiacs.umd.edu/~wym/3dpose.html
Downlink Analysis in Unmanned Aerial Vehicle (UAV) Assisted Cellular Networks with Clustered Users
Venue: arXiv cs.IT 2018
Year: 2018

The use of unmanned aerial vehicles (UAVs) operating as aerial base stations (BSs) has emerged as a promising solution especially in scenarios requiring rapid deployments (e.g., in the cases of crowded hotspots, sporting events, emergencies, natural disasters) in order to assist the ground BSs. In this paper, an analytical framework is provided to analyze the signal-to-interference-plus-noise ratio (SINR) coverage probability of unmanned aerial vehicle (UAV) assisted cellular networks with clustered user equipments (UEs). Locations of UAVs and ground BSs are modeled as Poison point processes (PPPs), and UEs are assumed to be distributed according to a Poisson cluster process (PCP) around the projections of UAVs on the ground. Initially, the complementary cumulative distribution function (CCDF) and probability density function (PDF) of path losses for both UAV and ground BS tiers are derived. Subsequently, association probabilities with each tier are obtained. SINR coverage probability is derived for the entire network using tools from stochastic geometry. Finally, area spectral efficiency (ASE) of the entire network is determined, and SINR coverage probability expression for a more general model is presented by considering that UAVs are located at different heights. Via numerical results, we have shown that UAV height and path-loss exponents play important roles on the coverage performance. Moreover, coverage probability can be improved with smaller number of UAVs, while better area spectral efficiency is achieved by employing more UAVs and having UEs more compactly clustered around the UAVs.
Qiniu Submission to ActivityNet Challenge 2018
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we introduce our submissions for the tasks of trimmed activity recognition (Kinetics) and trimmed event recognition (Moments in Time) for Activitynet Challenge 2018. In the two tasks, non-local neural networks and temporal segment networks are implemented as our base models. Multi-modal cues such as RGB image, optical flow and acoustic signal have also been used in our method. We also propose new non-local-based models for further improvement on the recognition accuracy. The final submissions after ensembling the models achieve 83.5% top-1 accuracy and 96.8% top-5 accuracy on the Kinetics validation set, 35.81% top-1 accuracy and 62.59% top-5 accuracy on the MIT validation set.
Using Chaos in Grey Wolf Optimizer and Application to Prime Factorization
Venue: arXiv cs.NE 2018
Year: 2018

The Grey Wolf Optimizer (GWO) is a swarm intelligence meta-heuristic algorithm inspired by the hunting behaviour and social hierarchy of grey wolves in nature. This paper analyses the use of chaos theory in this algorithm to improve its ability to escape local optima by replacing the key parameters by chaotic variables. The optimal choice of chaotic maps is then used to apply the Chaotic Grey Wolf Optimizer (CGWO) to the problem of factoring a large semi prime into its prime factors. Assuming the number of digits of the factors to be equal, this is a computationally difficult task upon which the RSA-cryptosystem relies. This work proposes the use of a new objective function to solve the problem and uses the CGWO to optimize it and compute the factors. It is shown that this function performs better than its predecessor for large semi primes and CGWO is an efficient algorithm to optimize it.
Erasure Coding for Distributed Storage: An Overview
Venue: arXiv cs.IT 2018
Year: 2018

In a distributed storage system, code symbols are dispersed across space in nodes or storage units as opposed to time. In settings such as that of a large data center, an important consideration is the efficient repair of a failed node. Efficient repair calls for erasure codes that in the face of node failure, are efficient in terms of minimizing the amount of repair data transferred over the network, the amount of data accessed at a helper node as well as the number of helper nodes contacted. Coding theory has evolved to handle these challenges by introducing two new classes of erasure codes, namely regenerating codes and locally recoverable codes as well as by coming up with novel ways to repair the ubiquitous Reed-Solomon code. This survey provides an overview of the efforts in this direction that have taken place over the past decade.
Techniques for Efficiently Handling Power Surges in Fuel Cell Powered Data Centers: Modeling, Analysis, Results
Venue: arXiv cs.DC 2018
Year: 2018

Fuel cells are a promising power source for future data centers, offering high energy efficiency, low greenhouse gas emissions, and high reliability. However, due to mechanical limitations related to fuel delivery, fuel cells are slow to adjust to sudden increases in data center power demands, which can result in temporary power shortfalls. To mitigate the impact of power shortfalls, prior work has proposed to either perform power capping by throttling the servers, or to leverage energy storage devices (ESDs) that can temporarily provide enough power to make up for the shortfall while the fuel cells ramp up power generation. Both approaches have disadvantages: power capping conservatively limits server performance and can lead to service level agreement (SLA) violations, while ESD-only solutions must significantly overprovision the energy storage device capacity to tolerate the shortfalls caused by the worst-case (i.e., largest) power surges, which greatly increases the total cost of ownership (TCO). We propose SizeCap, the first ESD sizing framework for fuel cell powered data centers, which coordinates ESD sizing with power capping to enable a cost-effective solution to power shortfalls in data centers. SizeCap sizes the ESD just large enough to cover the majority of power surges, but not the worst-case surges that occur infrequently, to greatly reduce TCO. It then uses the smaller capacity ESD in conjunction with power capping to cover the power shortfalls caused by the worst-case power surges. As part of our new flexible framework, we propose multiple power capping policies with different degrees of awareness of fuel cell and workload behavior, and evaluate their impact on workload performance and ESD size. Using traces from Microsoft's production data center systems, we demonstrate that SizeCap significantly reduces the ESD size without violating any SLAs.
Learning to Automatically Generate Fill-In-The-Blank Quizzes
Venue: arXiv cs.CL 2018
Year: 2018

In this paper we formalize the problem automatic fill-in-the-blank question generation using two standard NLP machine learning schemes, proposing concrete deep learning models for each. We present an empirical study based on data obtained from a language learning platform showing that both of our proposed settings offer promising results.