OpenRaiser/Intern-Atlas huggingface dataset:
Few-Shot Learning via Embedding Adaptation with Set-to-Set Functions
Venue: arXiv cs.LG 2021
Year: 2021

Learning with limited data is a key challenge for visual recognition. Many few-shot learning methods address this challenge by learning an instance embedding function from seen classes and apply the function to instances from unseen classes with limited labels. This style of transfer learning is task-agnostic: the embedding function is not learned optimally discriminative with respect to the unseen classes, where discerning among them leads to the target task. In this paper, we propose a novel approach to adapt the instance embeddings to the target classification task with a set-to-set function, yielding embeddings that are task-specific and are discriminative. We empirically investigated various instantiations of such set-to-set functions and observed the Transformer is most effective -- as it naturally satisfies key properties of our desired model. We denote this model as FEAT (few-shot embedding adaptation w/ Transformer) and validate it on both the standard few-shot classification benchmark and four extended few-shot learning settings with essential use cases, i.e., cross-domain, transductive, generalized few-shot learning, and low-shot learning. It archived consistent improvements over baseline models as well as previous methods and established the new state-of-the-art results on two benchmarks.
Entanglement-assisted quantum error-correcting codes over arbitrary finite fields
Venue: arXiv cs.IT 2021
Year: 2021

We prove that the known formulae for computing the optimal number of maximally entangled pairs required for entanglement-assisted quantum error-correcting codes (EAQECCs) over the binary field hold for codes over arbitrary finite fields as well. We also give a Gilbert-Varshamov bound for EAQECCs and constructions of EAQECCs coming from punctured self-orthogonal linear codes which are valid for any finite field.
ForASec: Formal Analysis of Security Vulnerabilities in Sequential Circuits
Venue: arXiv cs.CR 2021
Year: 2021

Security vulnerability analysis of Integrated Circuits using conventional design-time validation and verification techniques (like simulations, emulations, etc.) is generally a computationally intensive task and incomplete by nature, especially under limited resources and time constraints. To overcome this limitation, we propose a novel methodology based on model checking to formally analyze security vulnerabilities in sequential circuits while considering side-channel parameters like propagation delay, switching power, and leakage power. In particular, we present a novel algorithm to efficiently partition the state-space into corresponding smaller state-spaces to enable distributed security analysis of complex sequential circuits and thereby mitigating the associated state-space explosion due to their feedback loops. We analyze multiple ISCAS89 and trust-hub benchmarks to demonstrate the efficacy of our framework in identifying security vulnerabilities. The experimental results show that ForASec successfully performs the complete analysis of the given complex and large sequential circuits, and provides approximately 11x to 16x speedup in analysis time compared to state-of-the-art model checking-based techniques. Moreover, it also identifies the number of gates required by an HT that can go undetected for a given design and variability conditions.
Testing Stability Properties in Graphical Hedonic Games
Venue: arXiv cs.GT 2021
Year: 2021

In hedonic games, players form coalitions based on individual preferences over the group of players they could belong to. Several concepts to describe the stability of coalition structures in a game have been proposed and analysed in the literature. However, prior research focuses on algorithms with time complexity that is at least linear in the input size. In the light of very large games that arise from, e.g., social networks and advertising, we initiate the study of sublinear time property testing algorithms for existence and verification problems under several notions of coalition stability in a model of hedonic games represented by graphs with bounded degree. In graph property testing, one shall decide whether a given input has a property (e.g., a game admits a stable coalition structure) or is far from it, i.e., one has to modify at least an $ε$-fraction of the input (e.g., the game's preferences) to make it have the property. In particular, we consider verification of perfection, individual rationality, Nash stability, (contractual) individual stability, and core stability. While there is always a Nash-stable coalition structure (which also implies individually stable coalitions), we show that the existence of a perfect coalition structure is not tautological but can be tested. All our testers have one-sided error and time complexity that is independent of the input size.
Application-driven Privacy-preserving Data Publishing with Correlated Attributes
Venue: arXiv cs.LG 2021
Year: 2021

Recent advances in computing have allowed for the possibility to collect large amounts of data on personal activities and private living spaces. To address the privacy concerns of users in this environment, we propose a novel framework called PR-GAN that offers privacy-preserving mechanism using generative adversarial networks. Given a target application, PR-GAN automatically modifies the data to hide sensitive attributes -- which may be hidden and can be inferred by machine learning algorithms -- while preserving the data utility in the target application. Unlike prior works, the public's possible knowledge of the correlation between the target application and sensitive attributes is built into our modeling. We formulate our problem as an optimization problem, show that an optimal solution exists and use generative adversarial networks (GAN) to create perturbations. We further show that our method provides privacy guarantees under the Pufferfish framework, an elegant generalization of the differential privacy that allows for the modeling of prior knowledge on data and correlations. Through experiments, we show that our method outperforms conventional methods in effectively hiding the sensitive attributes while guaranteeing high performance in the target application, for both property inference and training purposes. Finally, we demonstrate through further experiments that once our model learns a privacy-preserving task, such as hiding subjects' identity, on a group of individuals, it can perform the same task on a separate group with minimal performance drops.
Improving Face Anti-Spoofing by 3D Virtual Synthesis
Venue: arXiv cs.CV 2021
Year: 2021

Face anti-spoofing is crucial for the security of face recognition systems. Learning based methods especially deep learning based methods need large-scale training samples to reduce overfitting. However, acquiring spoof data is very expensive since the live faces should be re-printed and re-captured in many views. In this paper, we present a method to synthesize virtual spoof data in 3D space to alleviate this problem. Specifically, we consider a printed photo as a flat surface and mesh it into a 3D object, which is then randomly bent and rotated in 3D space. Afterward, the transformed 3D photo is rendered through perspective projection as a virtual sample. The synthetic virtual samples can significantly boost the anti-spoofing performance when combined with a proposed data balancing strategy. Our promising results open up new possibilities for advancing face anti-spoofing using cheap and large-scale synthetic data.
IDStack -- The Common Protocol for Document Verification built on Digital Signatures
Venue: arXiv cs.CR 2021
Year: 2021

The use of physical documents is inconvenient and inefficient in today's world, which motivates us to move towards the use of digital documents. Digital documents can solve many problems of inefficiency of data management but proving their authenticity and verifying them is still a problem. This paper presents a solution for this problem using text extraction, digital signatures and a correlation score for a set of documents. The paper discusses the impacts and advantages of the proposed technologies against other possible technologies that could serve the same purpose.
Lower bounds for maximal matchings and maximal independent sets
Venue: arXiv cs.DC 2021
Year: 2021

There are distributed graph algorithms for finding maximal matchings and maximal independent sets in $O(Δ+ \log^* n)$ communication rounds; here $n$ is the number of nodes and $Δ$ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on $n$ is optimal: these problems cannot be solved in $o(\log^* n)$ rounds even if $Δ= 2$. However, the dependency on $Δ$ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that any algorithm that finds a maximal matching or maximal independent set with probability at least $1-1/n$ requires $Ω(\min\{Δ,\log \log n / \log \log \log n\})$ rounds in the LOCAL model of distributed computing. As a corollary, it follows that any deterministic algorithm that finds a maximal matching or maximal independent set requires $Ω(\min\{Δ, \log n / \log \log n\})$ rounds; this is an improvement over prior lower bounds also as a function of $n$.
DUNEuro -- A software toolbox for forward modeling in bioelectromagnetism
Venue: arXiv cs.MS 2021
Year: 2021

Accurate and efficient source analysis in electro- and magnetoencephalography using sophisticated realistic head geometries requires advanced numerical approaches. This paper presents DUNEuro, a free and open source C++ software toolbox for forward modeling in bioelectromagnetism. Building upon the DUNE framework, it provides implementations of modern fitted and unfitted finite element methods to efficiently solve the forward problems in electro- and magnetoencephalography. The user can choose between a variety of different source models that are implemented. The software's aim is to provide interfaces that are extendible and easy-to-use. In order to enable a closer integration into existing analysis pipelines, interfaces to Python and Matlab are provided. The practical use is demonstrated by a source analysis example of somatosensory evoked potentials using a realistic six compartment head model.
Skeletonisation Algorithms with Theoretical Guarantees for Unorganised Point Clouds with High Levels of Noise
Venue: arXiv cs.CG 2021
Year: 2021

Data Science aims to extract meaningful knowledge from unorganised data. Real datasets usually come in the form of a cloud of points with only pairwise distances. Numerous applications require to visualise an overall shape of a noisy cloud of points sampled from a non-linear object that is more complicated than a union of disjoint clusters. The skeletonisation problem in its hardest form is to find a 1-dimensional skeleton that correctly represents a shape of the cloud. This paper compares several algorithms that solve the above skeletonisation problem for any point cloud and guarantee a successful reconstruction. For example, given a highly noisy point sample of an unknown underlying graph, a reconstructed skeleton should be geometrically close and homotopy equivalent to (has the same number of independent cycles as) the underlying graph. One of these algorithm produces a Homologically Persistent Skeleton (HoPeS) for any cloud without extra parameters. This universal skeleton contains sub-graphs that provably represent the 1-dimensional shape of the cloud at any scale. Other subgraphs of HoPeS reconstruct an unknown graph from its noisy point sample with a correct homotopy type and within a small offset of the sample. The extensive experiments on synthetic and real data reveal for the first time the maximum level of noise that allows successful graph reconstructions.
Selfish Mining in Ethereum
Venue: arXiv cs.CR 2021
Year: 2021

As the second largest cryptocurrency by market capitalization and today's biggest decentralized platform that runs smart contracts, Ethereum has received much attention from both industry and academia. Nevertheless, there exist very few studies about the security of its mining strategies, especially from the selfish mining perspective. In this paper, we aim to fill this research gap by analyzing selfish mining in Ethereum and understanding its potential threat. First, we introduce a 2-dimensional Markov process to model the behavior of a selfish mining strategy inspired by a Bitcoin mining strategy proposed by Eyal and Sirer. Second, we derive the stationary distribution of our Markov model and compute long-term average mining rewards. This allows us to determine the threshold of computational power that makes selfish mining profitable in Ethereum. We find that this threshold is lower than that in Bitcoin mining (which is 25% as discovered by Eyal and Sirer), suggesting that Ethereum is more vulnerable to selfish mining than Bitcoin.
TaDA Live: Compositional Reasoning for Termination of Fine-grained Concurrent Programs
Venue: arXiv cs.PL 2021
Year: 2021

We present TaDA Live, a concurrent separation logic for reasoning compositionally about the termination of blocking fine-grained concurrent programs. The crucial challenge is how to deal with abstract atomic blocking: that is, abstract atomic operations that have blocking behaviour arising from busy-waiting patterns as found in, for example, fine-grained spin locks. Our fundamental innovation is with the design of abstract specifications that capture this blocking behaviour as liveness assumptions on the environment. We design a logic that can reason about the termination of clients which use such operations without breaking their abstraction boundaries, and the correctness of the implementations of the operations with respect to their abstract specifications. We introduce a novel semantic model using layered subjective obligations to express liveness invariants, and a proof system that is sound with respect to the model. The subtlety of our specifications and reasoning is illustrated using several case studies.
Computing large market equilibria using abstractions
Venue: arXiv cs.GT 2021
Year: 2021

Computing market equilibria is an important practical problem for market design, for example in fair division of items. However, computing equilibria requires large amounts of information (typically the valuation of every buyer for every item) and computing power. We consider ameliorating these issues by applying a method used for solving complex games: constructing a coarsened abstraction of a given market, solving for the equilibrium in the abstraction, and lifting the prices and allocations back to the original market. We show how to bound important quantities such as regret, envy, Nash social welfare, Pareto optimality, and maximin share/proportionality when the abstracted prices and allocations are used in place of the real equilibrium. We then study two abstraction methods of interest for practitioners: (1) filling in unknown valuations using techniques from matrix completion, (2) reducing the problem size by aggregating groups of buyers/items into smaller numbers of representative buyers/items and solving for equilibrium in this coarsened market. We find that in real data allocations/prices that are relatively close to equilibria can be computed from even very coarse abstractions.
Disturbed YouTube for Kids: Characterizing and Detecting Inappropriate Videos Targeting Young Children
Venue: arXiv cs.SI 2021
Year: 2021

A large number of the most-subscribed YouTube channels target children of a very young age. Hundreds of toddler-oriented channels on YouTube feature inoffensive, well-produced, and educational videos. Unfortunately, inappropriate content that targets this demographic is also common. YouTube's algorithmic recommendation system regrettably suggests inappropriate content because some of it mimics or is derived from otherwise appropriate content. Considering the risk for early childhood development, and an increasing trend in toddler's consumption of YouTube media, this is a worrisome problem. In this work, we build a classifier able to discern inappropriate content that targets toddlers on YouTube with 84.3% accuracy, and leverage it to perform a first-of-its-kind, large-scale, quantitative characterization that reveals some of the risks of YouTube media consumption by young children. Our analysis reveals that YouTube is still plagued by such disturbing videos and its currently deployed counter-measures are ineffective in terms of detecting them in a timely manner. Alarmingly, using our classifier we show that young children are not only able, but likely to encounter disturbing videos when they randomly browse the platform starting from benign videos.
SecureBoost: A Lossless Federated Learning Framework
Venue: arXiv cs.LG 2021
Year: 2021

The protection of user privacy is an important concern in machine learning, as evidenced by the rolling out of the General Data Protection Regulation (GDPR) in the European Union (EU) in May 2018. The GDPR is designed to give users more control over their personal data, which motivates us to explore machine learning frameworks for data sharing that do not violate user privacy. To meet this goal, in this paper, we propose a novel lossless privacy-preserving tree-boosting system known as SecureBoost in the setting of federated learning. SecureBoost first conducts entity alignment under a privacy-preserving protocol and then constructs boosting trees across multiple parties with a carefully designed encryption strategy. This federated learning system allows the learning process to be jointly conducted over multiple parties with common user samples but different feature sets, which corresponds to a vertically partitioned data set. An advantage of SecureBoost is that it provides the same level of accuracy as the non-privacy-preserving approach while at the same time, reveals no information of each private data provider. We show that the SecureBoost framework is as accurate as other non-federated gradient tree-boosting algorithms that require centralized data and thus it is highly scalable and practical for industrial applications such as credit risk analysis. To this end, we discuss information leakage during the protocol execution and propose ways to provably reduce it.
Strong Equivalence and Program Structure in Arguing Essential Equivalence between Logic Programs
Venue: arXiv cs.AI 2021
Year: 2021

Answer set programming is a prominent declarative programming paradigm used in formulating combinatorial search problems and implementing different knowledge representation formalisms. Frequently, several related and yet substantially different answer set programs exist for a given problem. Sometimes these encodings may display significantly different performance. Uncovering precise formal links between these programs is often important and yet far from trivial. This paper presents formal results carefully relating a number of interesting program rewritings. It also provides the proof of correctness of system Projector concerned with automatic program rewritings for the sake of efficiency. Under consideration in Theory and Practice of Logic Programming (TPLP).
Computing longest palindromic substring after single-character or block-wise edits
Venue: arXiv cs.DS 2021
Year: 2021

Palindromes are important objects in strings which have been extensively studied from combinatorial, algorithmic, and bioinformatics points of views. It is known that the length of the longest palindromic substrings (LPSs) of a given string T of length n can be computed in O(n) time by Manacher's algorithm [J. ACM '75]. In this paper, we consider the problem of finding the LPS after the string is edited. We present an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LPSs in O(\log (\min \{σ, \log n\})) time after a single character substitution, insertion, or deletion, where σdenotes the number of distinct characters appearing in T. We also propose an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LPSs in O(\ell + \log \log n) time, after an existing substring in T is replaced by a string of arbitrary length \ell.
How to Write High-quality News on Social Network? Predicting News Quality by Mining Writing Style
Venue: arXiv cs.CL 2021
Year: 2021

Rapid development of Internet technologies promotes traditional newspapers to report news on social networks. However, people on social networks may have different needs which naturally arises the question: whether can we analyze the influence of writing style on news quality automatically and assist writers in improving news quality? It's challenging due to writing style and 'quality' are hard to measure. First, we use 'popularity' as the measure of 'quality'. It is natural on social networks but brings new problems: popularity are also influenced by event and publisher. So we design two methods to alleviate their influence. Then, we proposed eight types of linguistic features (53 features in all) according eight writing guidelines and analyze their relationship with news quality. The experimental results show these linguistic features influence greatly on news quality. Based on it, we design a news quality assessment model on social network (SNQAM). SNQAM performs excellently on predicting quality, presenting interpretable quality score and giving accessible suggestions on how to improve it according to writing guidelines we referred to.
A Unified Dissertation on Bearing Rigidity Theory
Venue: arXiv cs.SY 2021
Year: 2021

This work focuses on the bearing rigidity theory, namely the branch of knowledge investigating the structural properties necessary for multi-element systems to preserve the inter-units bearings when exposed to deformations. The original contributions are twofold. The first one consists in the definition of a general framework for the statement of the principal definitions and results that are then particularized by evaluating the most studied metric spaces, providing a complete overview of the existing literature about the bearing rigidity theory. The second one rests on the determination of a necessary and sufficient condition guaranteeing the rigidity properties of a given multi-element system, independently of its metric space.
Unpriortized Autoencoder For Image Generation
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we treat the image generation task using an autoencoder, a representative latent model. Unlike many studies regularizing the latent variable's distribution by assuming a manually specified prior, we approach the image generation task using an autoencoder by directly estimating the latent distribution. To this end, we introduce 'latent density estimator' which captures latent distribution explicitly and propose its structure. Through experiments, we show that our generative model generates images with the improved visual quality compared to previous autoencoder-based generative models.