OpenRaiser/Intern-Atlas huggingface dataset:
Parameterized Complexity of Upper Edge Domination
Venue: arXiv cs.DS 2022
Year: 2022

In this paper we study a maximization version of the classical Edge Dominating Set (EDS) problem, namely, the Upper EDS problem, in the realm of Parameterized Complexity. In this problem, given an undirected graph $G$, a positive integer $k$, the question is to check whether $G$ has a minimal edge dominating set of size at least $k$. We obtain the following results for Upper EDS. We prove that Upper EDS admits a kernel with at most $4k^2-2$ vertices. We also design a fixed-parameter tractable (FPT) algorithm for Upper EDS running in time $2^{\mathcal{O}(k)} \cdot n^{\mathcal{O}(1)}$.
Report on the software "SemanticModellingFramework"
Venue: arXiv cs.GR 2022
Year: 2022

The evolution of 3D visual content calls for innovative methods for modelling shapes based on their intended usage, function and role in a complex scenario. Even if different attempts have been done in this direction, shape modelling still mainly focuses on geometry. However, 3D models have a structure, given by the arrangement of salient parts, and shape and structure are deeply related to semantics and functionality. Changing geometry without semantic clues may invalidate such functionalities or the meaning of objects or their parts. Here, the problem is approached by considering semantics as the formalised knowledge related to a category of objects; the geometry can vary provided that the semantics is preserved. The semantics and the variable geometry of a class of shapes is represented through the parametric template: an annotated 3D model whose geometry can be deformed provided that some semantic constraints remain satisfied. In this work, the design and development of a framework for the semantics-aware modelling of shapes is presented, offering the user a single application environment where the whole workflow of defining the parametric template and applying semantics-aware deformations can take place. In particular, the system provides tools for the selection and annotation of geometry based on a formalised contextual knowledge; shape analysis methods to derive new knowledge implicitly encoded in the geometry, and possibly enrich the given semantics; a set of constraints that the user can apply to salient parts and a deformation operation that takes into account the semantic constraints and provides an optimal solution. The framework is modular so that new tools can be continuously added.
SOMPT22: A Surveillance Oriented Multi-Pedestrian Tracking Dataset
Venue: arXiv cs.CV 2022
Year: 2022

Multi-object tracking (MOT) has been dominated by the use of track by detection approaches due to the success of convolutional neural networks (CNNs) on detection in the last decade. As the datasets and bench-marking sites are published, research direction has shifted towards yielding best accuracy on generic scenarios including re-identification (reID) of objects while tracking. In this study, we narrow the scope of MOT for surveillance by providing a dedicated dataset of pedestrians and focus on in-depth analyses of well performing multi-object trackers to observe the weak and strong sides of state-of-the-art (SOTA) techniques for real-world applications. For this purpose, we introduce SOMPT22 dataset; a new set for multi person tracking with annotated short videos captured from static cameras located on poles with 6-8 meters in height positioned for city surveillance. This provides a more focused and specific benchmarking of MOT for outdoor surveillance compared to public MOT datasets. We analyze MOT trackers classified as one-shot and two-stage with respect to the way of use of detection and reID networks on this new dataset. The experimental results of our new dataset indicate that SOTA is still far from high efficiency, and single-shot trackers are good candidates to unify fast execution and accuracy with competitive performance. The dataset will be available at: sompt22.github.io
On the Niho type locally-APN power functions and their boomerang spectrum
Venue: arXiv cs.IT 2022
Year: 2022

In this article, we focus on the concept of locally-APN-ness (``APN" is the abbreviation of the well-known notion of Almost Perfect Nonlinear) introduced by Blondeau, Canteaut, and Charpin, which makes the corpus of S-boxes somehow larger regarding their differential uniformity and, therefore, possibly, more suitable candidates against the differential attack (or their variants). Specifically, given two coprime positive integers $m$ and $k$ such that $\gcd(2^m+1,2^k+1)=1$, we investigate the locally-APN-ness property of an infinite family of Niho type power functions in the form $F(x)=x^{s(2^m-1)+1}$ over the finite field ${\mathbb F}_{2^{2m}}$ for $s=(2^k+1)^{-1}$, where $(2^k+1)^{-1}$ denotes the multiplicative inverse modulo $2^m+1$. By employing finer studies of the number of solutions of certain equations over finite fields (with even characteristic) as well as some subtle manipulations of solving some equations, we prove that $F(x)$ is locally APN and determine its differential spectrum. It is worth noting that computer experiments show that this class of locally-APN power functions covers all Niho type locally-APN power functions for $2\leq m\leq10$. In addition, we also determine the boomerang spectrum of $F(x)$ by using its differential spectrum, which particularly generalizes a recent result by Yan, Zhang, and Li.
Computing Power of Hybrid Models in Synchronous Networks
Venue: arXiv cs.DC 2022
Year: 2022

During the last two decades, a small set of distributed computing models for networks have emerged, among which LOCAL, CONGEST, and Broadcast Congested Clique (BCC) play a prominent role. We consider hybrid models resulting from combining these three models. That is, we analyze the computing power of models allowing to, say, perform a constant number of rounds of CONGEST, then a constant number of rounds of LOCAL, then a constant number of rounds of BCC, possibly repeating this figure a constant number of times. We specifically focus on 2-round models, and we establish the complete picture of the relative powers of these models. That is, for every pair of such models, we determine whether one is (strictly) stronger than the other, or whether the two models are incomparable. The separation results are obtained by approaching communication complexity through an original angle, which may be of independent interest. The two players are not bounded to compute the value of a binary function, but the combined outputs of the two players are constrained by this value. In particular, we introduce the XOR-Index problem, in which Alice is given a binary vector $x\in\{0,1\}^n$ together with an index $i\in[n]$, Bob is given a binary vector $y\in\{0,1\}^n$ together with an index $j\in[n]$, and, after a single round of 2-way communication, Alice must output a boolean $\textrm{out}_A$, and Bob must output a boolean $\textrm{out}_B$, such that $\mbox{out}_A\land\mbox{out}_B = x_j\oplus y_i$. We show that the communication complexity of XOR-Index is $Ω(n)$ bits.
Development of fully intuitionistic fuzzy data envelopment analysis model with missing data: an application to Indian police sector
Venue: arXiv cs.AI 2022
Year: 2022

Data Envelopment Analysis (DEA) is a technique used to measure the efficiency of decision-making units (DMUs). In order to measure the efficiency of DMUs, the essential requirement is input-output data. Data is usually collected by humans, machines, or both. Due to human/machine errors, there are chances of having some missing values or inaccuracy, such as vagueness/uncertainty/hesitation in the collected data. In this situation, it will be difficult to measure the efficiencies of DMUs accurately. To overcome these shortcomings, a method is presented that can deal with missing values and inaccuracy in the data. To measure the performance efficiencies of DMUs, an input minimization BCC (IMBCC) model in a fully intuitionistic fuzzy (IF) environment is proposed. To validate the efficacy of the proposed fully intuitionistic fuzzy input minimization BCC (FIFIMBCC) model and the technique to deal with missing values in the data, a real-life application to measure the performance efficiencies of Indian police stations is presented.
WShEx: A language to describe and validate Wikibase entities
Venue: arXiv cs.DB 2022
Year: 2022

Wikidata is one of the most successful Semantic Web projects. Its underlying Wikibase data model departs from RDF with the inclusion of several features like qualifiers and references, built-in datatypes, etc. Those features are serialized to RDF for content negotiation, RDF dumps and in the SPARQL endpoint. Wikidata adopted the entity schemas namespace using the ShEx language to describe and validate the RDF serialization of Wikidata entities. In this paper we propose WShEx, a language inspired by ShEx that directly supports the Wikibase data model and can be used to describe and validate Wikibase entities. The paper presents a the abstract syntax and semantic of the WShEx language.
Unconventional application of k-means for distributed approximate similarity search
Venue: arXiv cs.IR 2022
Year: 2022

Similarity search based on a distance function in metric spaces is a fundamental problem for many applications. Queries for similar objects lead to the well-known machine learning task of nearest-neighbours identification. Many data indexing strategies, collectively known as Metric Access Methods (MAM), have been proposed to speed up queries for similar elements in this context. Moreover, since exact approaches to solve similarity queries can be complex and time-consuming, alternative options have appeared to reduce query execution time, such as returning approximate results or resorting to distributed computing platforms. In this paper, we introduce MASK (Multilevel Approximate Similarity search with $k$-means), an unconventional application of the $k$-means algorithm as the foundation of a multilevel index structure for approximate similarity search, suitable for metric spaces. We show that inherent properties of $k$-means, like representing high-density data areas with fewer prototypes, can be leveraged for this purpose. An implementation of this new indexing method is evaluated, using a synthetic dataset and a real-world dataset in a high-dimensional and high-sparsity space. Results are promising and underpin the applicability of this novel indexing method in multiple domains.
Decentralized Risk-Aware Tracking of Multiple Targets
Venue: arXiv cs.RO 2022
Year: 2022

We consider the setting where a team of robots is tasked with tracking multiple targets with the following property: approaching the targets enables more accurate target position estimation, but also increases the risk of sensor failures. Therefore, it is essential to address the trade-off between tracking quality maximization and risk minimization. In our previous work, a centralized controller is developed to plan motions for all the robots -- however, this is not a scalable approach. Here, we present a decentralized and risk-aware multi-target tracking framework, in which each robot plans its motion trading off tracking accuracy maximization and aversion to risk, while only relying on its own information and information exchanged with its neighbors. We use the control barrier function to guarantee network connectivity throughout the tracking process. Extensive numerical experiments demonstrate that our system can achieve similar tracking accuracy and risk-awareness to its centralized counterpart.
Semantic Data Augmentation based Distance Metric Learning for Domain Generalization
Venue: arXiv cs.LG 2022
Year: 2022

Domain generalization (DG) aims to learn a model on one or more different but related source domains that could be generalized into an unseen target domain. Existing DG methods try to prompt the diversity of source domains for the model's generalization ability, while they may have to introduce auxiliary networks or striking computational costs. On the contrary, this work applies the implicit semantic augmentation in feature space to capture the diversity of source domains. Concretely, an additional loss function of distance metric learning (DML) is included to optimize the local geometry of data distribution. Besides, the logits from cross entropy loss with infinite augmentations is adopted as input features for the DML loss in lieu of the deep features. We also provide a theoretical analysis to show that the logits can approximate the distances defined on original features well. Further, we provide an in-depth analysis of the mechanism and rational behind our approach, which gives us a better understanding of why leverage logits in lieu of features can help domain generalization. The proposed DML loss with the implicit augmentation is incorporated into a recent DG method, that is, Fourier Augmented Co-Teacher framework (FACT). Meanwhile, our method also can be easily plugged into various DG methods. Extensive experiments on three benchmarks (Digits-DG, PACS and Office-Home) have demonstrated that the proposed method is able to achieve the state-of-the-art performance.
An Empirical Study on Ethereum Private Transactions and the Security Implications
Venue: arXiv cs.CR 2022
Year: 2022

Recently, Decentralized Finance (DeFi) platforms on Ethereum are booming, and numerous traders are trying to capitalize on the opportunity for maximizing their benefits by launching front-running attacks and extracting Miner Extractable Values (MEVs) based on information in the public mempool. To protect end users from being harmed and hide transactions from the mempool, private transactions, a special type of transactions that are sent directly to miners, were invented. Private transactions have a high probability of being packed to the front positions of a block and being added to the blockchain by the target miner, without going through the public mempool, thus reducing the risk of being attacked by malicious entities. Despite the good intention of inventing private transactions, due to their stealthy nature, private transactions have also been used by attackers to launch attacks, which has a negative impact on the Ethereum ecosystem. However, existing works only touch upon private transactions as by-products when studying MEV, while a systematic study on private transactions is still missing. To fill this gap and paint a complete picture of private transactions, we take the first step towards investigating the private transactions on Ethereum. In particular, we collect large-scale private transaction datasets and perform analysis on their characteristics, transaction costs and miner profits, as well as security impacts. This work provides deep insights on different aspects of private transactions.
Latent Multi-Relation Reasoning for GAN-Prior based Image Super-Resolution
Venue: arXiv cs.CV 2022
Year: 2022

Recently, single image super-resolution (SR) under large scaling factors has witnessed impressive progress by introducing pre-trained generative adversarial networks (GANs) as priors. However, most GAN-Priors based SR methods are constrained by an attribute disentanglement problem in inverted latent codes which directly leads to mismatches of visual attributes in the generator layers and further degraded reconstruction. In addition, stochastic noises fed to the generator are employed for unconditional detail generation, which tends to produce unfaithful details that compromise the fidelity of the generated SR image. We design LAREN, a LAtent multi-Relation rEasoNing technique that achieves superb large-factor SR through graph-based multi-relation reasoning in latent space. LAREN consists of two innovative designs. The first is graph-based disentanglement that constructs a superior disentangled latent space via hierarchical multi-relation reasoning. The second is graph-based code generation that produces image-specific codes progressively via recursive relation reasoning which enables prior GANs to generate desirable image details. Extensive experiments show that LAREN achieves superior large-factor image SR and outperforms the state-of-the-art consistently across multiple benchmarks.
A Forward-secure Efficient Two-factor Authentication Protocol
Venue: arXiv cs.CR 2022
Year: 2022

Two-factor authentication (2FA) schemes that rely on a combination of knowledge factors (e.g., PIN) and device possession have gained popularity. Some of these schemes remain secure even against strong adversaries that (a) observe the traffic between a client and server, and (b) have physical access to the client's device, or its PIN, or breach the server. However, these solutions have several shortcomings; namely, they (i) require a client to remember multiple secret values to prove its identity, (ii) involve several modular exponentiations, and (iii) are in the non-standard random oracle model. In this work, we present a 2FA protocol that resists such a strong adversary while addressing the above shortcomings. Our protocol requires a client to remember only a single secret value/PIN, does not involve any modular exponentiations, and is in a standard model. It is the first one that offers these features without using trusted chipsets. This protocol also imposes up to 40% lower communication overhead than the state-of-the-art solutions do.
Improving Fuzzy-Logic based Map-Matching Method with Trajectory Stay-Point Detection
Venue: arXiv cs.LG 2022
Year: 2022

The requirement to trace and process moving objects in the contemporary era gradually increases since numerous applications quickly demand precise moving object locations. The Map-matching method is employed as a preprocessing technique, which matches a moving object point on a corresponding road. However, most of the GPS trajectory datasets include stay-points irregularity, which makes map-matching algorithms mismatch trajectories to irrelevant streets. Therefore, determining the stay-point region in GPS trajectory datasets results in better accurate matching and more rapid approaches. In this work, we cluster stay-points in a trajectory dataset with DBSCAN and eliminate redundant data to improve the efficiency of the map-matching algorithm by lowering processing time. We reckoned our proposed method's performance and exactness with a ground truth dataset compared to a fuzzy-logic based map-matching algorithm. Fortunately, our approach yields 27.39% data size reduction and 8.9% processing time reduction with the same accurate results as the previous fuzzy-logic based map-matching approach.
Can the Government Compel Decryption? Don't Trust -- Verify
Venue: arXiv cs.CY 2022
Year: 2022

If a court knows that a respondent knows the password to a device, can the court compel the respondent to enter that password into the device? In this work, we propose a new approach to the foregone conclusion doctrine from Fisher v US that governs the answer to this question. The Holy Grail of this line of work would be a framework for reasoning about whether the testimony implicit in any action is already known to the government. In this paper we attempt something narrower. We introduce a framework for specifying actions for which all implicit testimony is, constructively, a foregone conclusion. Our approach is centered around placing the burden of proof on the government to demonstrate that it is not "rely[ing] on the truthtelling" of the respondent. Building on original legal analysis and using precise computer science formalisms, we propose demonstrability as a new central concept for describing compelled acts. We additionally provide a language for whether a compelled action meaningfully entails the respondent to perform in a manner that is 'as good as' the government's desired goal. Then, we apply our definitions to analyze the compellability of several cryptographic primitives including decryption, multifactor authentication, commitment schemes, and hash functions. In particular, our framework reaches a novel conclusion about compelled decryption in the setting that the encryption scheme is deniable: the government can compel but the respondent is free to use any password of her choice.
Human Decision Makings on Curriculum Reinforcement Learning with Difficulty Adjustment
Venue: arXiv cs.AI 2022
Year: 2022

Human-centered AI considers human experiences with AI performance. While abundant research has been helping AI achieve superhuman performance either by fully automatic or weak supervision learning, fewer endeavors are experimenting with how AI can tailor to humans' preferred skill level given fine-grained input. In this work, we guide the curriculum reinforcement learning results towards a preferred performance level that is neither too hard nor too easy via learning from the human decision process. To achieve this, we developed a portable, interactive platform that enables the user to interact with agents online via manipulating the task difficulty, observing performance, and providing curriculum feedback. Our system is highly parallelizable, making it possible for a human to train large-scale reinforcement learning applications that require millions of samples without a server. The result demonstrates the effectiveness of an interactive curriculum for reinforcement learning involving human-in-the-loop. It shows reinforcement learning performance can successfully adjust in sync with the human desired difficulty level. We believe this research will open new doors for achieving flow and personalized adaptive difficulties.
A Semantic Alignment System for Multilingual Query-Product Retrieval
Venue: arXiv cs.IR 2022
Year: 2022

This paper mainly describes our winning solution (team name: www) to Amazon ESCI Challenge of KDD CUP 2022, which achieves a NDCG score of 0.9043 and wins the first place on task 1: the query-product ranking track. In this competition, participants are provided with a real-world large-scale multilingual shopping queries data set and it contains query-product pairs in English, Japanese and Spanish. Three different tasks are proposed in this competition, including ranking the results list as task 1, classifying the query/product pairs into Exact, Substitute, Complement, or Irrelevant (ESCI) categories as task 2 and identifying substitute products for a given query as task 3. We mainly focus on task 1 and propose a semantic alignment system for multilingual query-product retrieval. Pre-trained multilingual language models (LM) are adopted to get the semantic representation of queries and products. Our models are all trained with cross-entropy loss to classify the query-product pairs into ESCI 4 categories at first, and then we use weighted sum with the 4-class probabilities to get the score for ranking. To further boost the model, we also do elaborative data preprocessing, data augmentation by translation, specially handling English texts with English LMs, adversarial training with AWP and FGM, self distillation, pseudo labeling, label smoothing and ensemble. Finally, Our solution outperforms others both on public and private leaderboard.