OpenRaiser/Intern-Atlas huggingface dataset:
The similarity index of scientific publications with equations and formulas, identification of self-plagiarism, and testing of the iThenticate system
Venue: arXiv cs.DL 2021
Year: 2021

The problems of estimating the similarity index of mathematical and other scientific publications containing equations and formulas are discussed for the first time. It is shown that the presence of equations and formulas (as well as figures, drawings, and tables) is a complicating factor that significantly complicates the study of such texts. It is shown that the method for determining the similarity index of publications, based on taking into account individual mathematical symbols and parts of equations and formulas, is ineffective and can lead to erroneous and even completely absurd conclusions. The possibilities of the most popular software system iThenticate, currently used in scientific journals, are investigated for detecting plagiarism and self-plagiarism. The results of processing by the iThenticate system of specific examples and special test problems containing equations (PDEs and ODEs), exact solutions, and some formulas are presented. It has been established that this software system when analyzing inhomogeneous texts, is often unable to distinguish self-plagiarism from pseudo-self-plagiarism (false self-plagiarism). A model complex situation is considered, in which the identification of self-plagiarism requires the involvement of highly qualified specialists of a narrow profile. Various ways to improve the work of software systems for comparing inhomogeneous texts are proposed. This article will be useful to researchers and university teachers in mathematics, physics, and engineering sciences, programmers dealing with problems in image recognition and research topics of digital image processing, as well as a wide range of readers who are interested in issues of plagiarism and self-plagiarism.
Do You See What I See? Capabilities and Limits of Automated Multimedia Content Analysis
Venue: arXiv cs.MM 2021
Year: 2021

The ever-increasing amount of user-generated content online has led, in recent years, to an expansion in research and investment in automated content analysis tools. Scrutiny of automated content analysis has accelerated during the COVID-19 pandemic, as social networking services have placed a greater reliance on these tools due to concerns about health risks to their moderation staff from in-person work. At the same time, there are important policy debates around the world about how to improve content moderation while protecting free expression and privacy. In order to advance these debates, we need to understand the potential role of automated content analysis tools. This paper explains the capabilities and limitations of tools for analyzing online multimedia content and highlights the potential risks of using these tools at scale without accounting for their limitations. It focuses on two main categories of tools: matching models and computer prediction models. Matching models include cryptographic and perceptual hashing, which compare user-generated content with existing and known content. Predictive models (including computer vision and computer audition) are machine learning techniques that aim to identify characteristics of new or previously unknown content.
Maximum Entropy of Random Permutation Set
Venue: arXiv cs.IT 2021
Year: 2021

Recently, a new type of set, named as random permutation set (RPS), is proposed by considering all the permutations of elements in a certain set. For measuring the uncertainty of RPS, the entropy of RPS is presented. However, the maximum entropy principle of RPS entropy has not been discussed. To address this issue, in this paper, the maximum entropy of RPS is presented. The analytical solution for maximum entropy of RPS and its corresponding PMF condition are respectively proofed and discussed. Numerical examples are used to illustrate the maximum entropy RPS. The results show that the maximum entropy RPS is compatible with the maximum Deng entropy and the maximum Shannon entropy. When the order of the element in the permutation event is ignored, the maximum entropy of RPS will degenerate into the maximum Deng entropy. When each permutation event is limited to containing just one element, the maximum entropy of RPS will degenerate into the maximum Shannon entropy.
Post-Processing Hierarchical Community Structures: Quality Improvements and Multi-scale View
Venue: arXiv cs.DS 2021
Year: 2021

Dense sub-graphs of sparse graphs (communities), which appear in most real-world complex networks, play an important role in many contexts. Most existing community detection algorithms produce a hierarchical structure of community and seek a partition into communities that optimizes a given quality function. We propose new methods to improve the results of any of these algorithms. First we show how to optimize a general class of additive quality functions (containing the modularity, the performance, and a new similarity based quality function we propose) over a larger set of partitions than the classical methods. Moreover, we define new multi-scale quality functions which make it possible to detect the different scales at which meaningful community structures appear, while classical approaches find only one partition.
Shannon-Kotel'nikov Mappings for Analog Point-to-Point Communications
Venue: arXiv cs.IT 2022
Year: 2022

In this paper an approach to joint source-channel coding (JSCC) named Shannon-Kotel'nikov mappings (S-K mappings) is presented. S-K mappings are continuous, or piecewise continuous direct source-to-channel mappings operating directly on amplitude continuous and discrete time signals. Such mappings include several existing JSCC schemes as special cases. Many existing approaches to analog- or hybrid discrete analog JSCC provide both excellent performance as well as robustness to variations in noise level. This at low delay and relatively low complexity. However, a theory explaining their performance and behaviour on a general basis, as well as guidelines on how to construct close to optimal mappings in general, does not currently exist. Therefore, such mappings are often found based on educated guesses inspired of configurations that are known in advance to produce good solutions, combination of already existing mappings, numerical optimization or machine learning methods. The objective of this paper is to introduce a theoretical framework for analysis of analog- or hybrid discrete analog S-K mappings. This framework will enable calculation of distortion when applying such schemes on point-to-point links, reveal more about their fundamental nature, and provide guidelines on how they should be constructed in order to perform well at both low and arbitrary complexity and delay. Such guidelines will likely help constrain solutions to numerical approaches and help explain why machine learning approaches finds the solutions they do. This task is difficult and we do not provide a complete framework at this stage: We focus on high SNR and memoryless sources with an arbitrary continuous unimodal density function and memoryless Gaussian channels. We also provide example of mappings based on surfaces which are chosen based on the provided theory.
An NP-Complete Problem in Grid Coloring
Venue: arXiv cs.CC 2022
Year: 2022

A c-coloring of G(n,m)=n x m is a mapping of G(n,m) into {1,...,c} such that no four corners forming a rectangle have the same color. In 2009 a challenge was proposed via the internet to find a 4-coloring of G(17,17). This attracted considerable attention from the popular mathematics community. A coloring was produced; however, finding it proved to be difficult. The question arises: is the problem of grid coloring is difficult in general? We show that the problem of, given a partial coloring of a grid, can it be extended to a full (proper) coloring, is NP-complete.
Diabetes prediction using Machine Learning algorithms and ontology
Venue: arXiv cs.DB 2022
Year: 2022

Diabetes is one of the chronic diseases, which is increasing from year to year. The problems begin when diabetes is not detected at an early phase and diagnosed properly at the appropriate time. Different machine learning techniques, as well as ontology-based ML techniques, have recently played an important role in medical science by developing an automated system that can detect diabetes patients. This paper provides a comparative study and review of the most popular machine learning techniques and ontology-based Machine Learning classification. Various types of classification algorithms were considered namely: SVM, KNN, ANN, Naive Bayes, Logistic regression, and Decision Tree. The results are evaluated based on performance metrics like Recall, Accuracy, Precision, and F-Measure that are derived from the confusion matrix. The experimental results showed that the best accuracy goes for ontology classifiers and SVM.
Online Stochastic Bin Packing
Venue: arXiv cs.DS 2022
Year: 2022

Bin packing is an algorithmic problem that arises in diverse applications such as remnant inventory systems, shipping logistics, and appointment scheduling. In its simplest variant, a sequence of $T$ items (e.g., orders for raw material, packages for delivery) is revealed one at a time, and each item must be packed on arrival in an available bin (e.g., remnant pieces of raw material in inventory, shipping containers). The sizes of items are i.i.d. samples from an unknown distribution, but the sizes are known when the items arrive. The goal is to minimize the number of non-empty bins (equivalently waste, defined to be the total unused space in non-empty bins). This problem has been extensively studied in the Operations Research and Theoretical Computer Science communities, yet all existing heuristics either rely on learning the distribution or exhibit $o(T)$ additive suboptimality compared to the optimal offline algorithm only for certain classes of distributions (those with sublinear optimal expected waste). In this paper, we propose a family of algorithms which are the first truly distribution-oblivious algorithms for stochastic bin packing, and achieve $\mathcal{O}(\sqrt{T})$ additive suboptimality for all item size distributions. Our algorithms are inspired by approximate interior-point algorithms for convex optimization. In addition to regret guarantees for discrete i.i.d. sequences, we extend our results to continuous item size distribution with bounded density, and also prove a family of novel regret bounds for non-i.i.d. input sequences. To the best of our knowledge these are the first such results for non-i.i.d. and non-random-permutation input sequences for online stochastic packing.
All Sampling Methods Produce Outliers
Venue: arXiv cs.CC 2022
Year: 2022

Given a computable probability measure P over natural numbers or infinite binary sequences, there is no computable, randomized method that can produce an arbitrarily large sample such that none of its members are outliers of P.
Termination Analysis by Learning Terminating Programs
Venue: arXiv cs.LO 2022
Year: 2022

We present a novel approach to termination analysis. In a first step, the analysis uses a program as a black-box which exhibits only a finite set of sample traces. Each sample trace is infinite but can be represented by a finite lasso. The analysis can "learn" a program from a termination proof for the lasso, a program that is terminating by construction. In a second step, the analysis checks that the set of sample traces is representative in a sense that we can make formal. An experimental evaluation indicates that the approach is a potentially useful addition to the portfolio of existing approaches to termination analysis.
Bounds on the Size of Permutation Codes with the Kendall $τ$-Metric
Venue: arXiv cs.IT 2022
Year: 2022

The rank modulation scheme has been proposed for efficient writing and storing data in non-volatile memory storage. Error-correction in the rank modulation scheme is done by considering permutation codes. In this paper we consider codes in the set of all permutations on $n$ elements, $S_n$, using the Kendall $τ$-metric. The main goal of this paper is to derive new bounds on the size of such codes. For this purpose we also consider perfect codes, diameter perfect codes, and the size of optimal anticodes in the Kendall $τ$-metric, structures which have their own considerable interest. We prove that there are no perfect single-error-correcting codes in $S_n$, where $n>4$ is a prime or $4\leq n\leq 10$. We present lower bounds on the size of optimal anticodes with odd diameter. As a consequence we obtain a new upper bound on the size of codes in $S_n$ with even minimum Kendall $τ$-distance. We present larger single-error-correcting codes than the known ones in $S_5$ and $S_7$.
Tight Hardness of the Non-commutative Grothendieck Problem
Venue: arXiv cs.CC 2022
Year: 2022

$\newcommand{\eps}{\varepsilon} $We prove that for any $\eps > 0$ it is $\textsf{NP}$-hard to approximate the non-commutative Grothendieck problem to within a factor $1/2 + \eps$, which matches the approximation ratio of the algorithm of Naor, Regev, and Vidick (STOC'13). Our proof uses an embedding of $\ell_2$ into the space of matrices endowed with the trace norm with the property that the image of standard basis vectors is longer than that of unit vectors with no large coordinates. We also observe that one can obtain a tight $\textsf{NP}$-hardness result for the commutative Little Grothendieck problem; previously, this was only known based on the Unique Games Conjecture (Khot and Naor, Mathematika 2009).
Extract an essential skeleton of a character as a graph from a character image
Venue: arXiv cs.CV 2022
Year: 2022

This paper aims to make a graph representing an essential skeleton of a character from an image that includes a machine printed or a handwritten character using growing neural gas (GNG) method and relative network graph (RNG) algorithm. The visual system in our brain can recognize printed characters and handwritten characters easily, robustly, and precisely. How does our brain robustly recognize characters? The visual processing in our brain uses the essential features of an object, such as crosses and corners. These features will be helpful for character recognition by a computer. However, extraction of the features is difficult. If the skeleton of a character is represented as a graph, we can more easily extract the features. To extract the skeleton of a character as a graph from an image, this paper proposes the new approach using GNG and RNG algorithm. I achieved to extract skeleton graphs from images including distorted, noisy, and handwritten characters.
Efficient Globally Optimal 2D-to-3D Deformable Shape Matching
Venue: arXiv cs.CV 2022
Year: 2022

We propose the first algorithm for non-rigid 2D-to-3D shape matching, where the input is a 2D shape represented as a planar curve and a 3D shape represented as a surface; the output is a continuous curve on the surface. We cast the problem as finding the shortest circular path on the product 3-manifold of the surface and the curve. We prove that the optimal matching can be computed in polynomial time with a (worst-case) complexity of $O(mn^2\log(n))$, where $m$ and $n$ denote the number of vertices on the template curve and the 3D shape respectively. We also demonstrate that in practice the runtime is essentially linear in $m\!\cdot\! n$ making it an efficient method for shape analysis and shape retrieval. Quantitative evaluation confirms that the method provides excellent results for sketch-based deformable 3D shape retrieval.
Constant factor Approximation Algorithms for Uniform Hard Capacitated Facility Location Problems: Natural LP is not too bad
Venue: arXiv cs.DS 2022
Year: 2022

In this paper, we give first constant factor approximation for capacitated knapsack median problem (CKM) for hard uniform capacities, violating the budget only by an additive factor of $f_{max}$ where $f_{max}$ is the maximum cost of a facility opened by the optimal and violating capacities by $(2+ε)$ factor. Natural LP for the problem is known to have an unbounded integrality gap when any one of the two constraints is allowed to be violated by a factor less than $2$. Thus, we present a result which is very close to the best achievable from the natural LP. To the best of our knowledge, the problem has not been studied earlier. For capacitated facility location problem with uniform capacities, a constant factor approximation algorithm is presented violating the capacities a little ($1 + ε$). Though constant factor results are known for the problem without violating the capacities, the result is interesting as it is obtained by rounding the solution to the natural LP, which is known to have an unbounded integrality gap without violating the capacities. Thus, we achieve the best possible from the natural LP for the problem. The result shows that natural LP is not too bad. Finally, we raise some issues with the proofs of the results presented in \cite{capkmByrkaFRS2013} for capacitated $k$-facility location problem (C$k$FLP). \cite{capkmByrkaFRS2013} presents $O(1/ε^2)$ approximation violating the capacities by a factor of $(2 + ε)$ using dependent rounding. We first fix these issues using our techniques. Also, it can be argued that (deterministic) pipage rounding cannot be used to open the facilities instead of dependent rounding. Our techniques for CKM provide a constant factor approximation for CkFLP violating the capacities by $(2 + ε)$.
An algebra of synchronous atomic steps
Venue: arXiv cs.LO 2022
Year: 2022

This research started with an algebra for reasoning about rely/guarantee concurrency for a shared memory model. The approach taken led to a more abstract algebra of atomic steps, in which atomic steps synchronise (rather than interleave) when composed in parallel. The algebra of rely/guarantee concurrency then becomes an interpretation of the more abstract algebra. Many of the core properties needed for rely/guarantee reasoning can be shown to hold in the abstract algebra where their proofs are simpler and hence allow a higher degree of automation. Moreover, the realisation that the synchronisation mechanisms of standard process algebras, such as CSP and CCS/SCCS, can be interpreted in our abstract algebra gives evidence of its unifying power. The algebra has been encoded in Isabelle/HOL to provide a basis for tool support.
Implementations and the independent set polynomial below the Shearer threshold
Venue: arXiv cs.CC 2022
Year: 2022

The independent set polynomial is important in many areas. For every integer $Δ\geq 2$, the Shearer threshold is the value $λ^*(Δ)=(Δ-1)^{Δ-1}/Δ^Δ$ . It is known that for $λ< - λ^*(Δ)$, there are graphs~$G$ with maximum degree~$Δ$ whose independent set polynomial, evaluated at~$λ$, is at most~$0$. Also, there are no such graphs for any $λ> -λ^*(Δ)$. This paper is motivated by the computational problem of approximating the independent set polynomial when $λ< - λ^*(Δ)$. The key issue in complexity bounds for this problem is "implementation". Informally, an implementation of a real number $λ'$ is a graph whose hard-core partition function, evaluated at~$λ$, simulates a vertex-weight of~$λ'$ in the sense that $λ'$ is the ratio between the contribution to the partition function from independent sets containing a certain vertex and the contribution from independent sets that do not contain that vertex. Implementations are the cornerstone of intractability results for the problem of approximately evaluating the independent set polynomial. Our main result is that, for any $λ< - λ^*(Δ)$, it is possible to implement a set of values that is dense over the reals. The result is tight in the sense that it is not possible to implement a set of values that is dense over the reals for any $λ> λ^*(Δ)$. Our result has already been used in a paper with \bezakova{} (STOC 2018) to show that it is \#P-hard to approximate the evaluation of the independent set polynomial on graphs of degree at most~$Δ$ at any value $λ<-λ^*(Δ)$. In the appendix, we give an additional incomparable inapproximability result (strengthening the inapproximability bound to an exponential factor, but weakening the hardness to NP-hardness).
Sorting Networks On Restricted Topologies
Venue: arXiv cs.DS 2022
Year: 2022

The sorting number of a graph with $n$ vertices is the minimum depth of a sorting network with $n$ inputs and outputs that uses only the edges of the graph to perform comparisons. Many known results on sorting networks can be stated in terms of sorting numbers of different classes of graphs. In this paper we show the following general results about the sorting number of graphs. Any $n$-vertex graph that contains a simple path of length $d$ has a sorting network of depth $O(n \log(n/d))$. Any $n$-vertex graph with maximal degree $Δ$ has a sorting network of depth $O(Δn)$. We also provide several results that relate the sorting number of a graph with its routing number, size of its maximal matching, and other well known graph properties. Additionally, we give some new bounds on the sorting number for some typical graphs.
LEPOR: An Augmented Machine Translation Evaluation Metric
Venue: arXiv cs.CL 2022
Year: 2022

Machine translation (MT) was developed as one of the hottest research topics in the natural language processing (NLP) literature. One important issue in MT is that how to evaluate the MT system reasonably and tell us whether the translation system makes an improvement or not. The traditional manual judgment methods are expensive, time-consuming, unrepeatable, and sometimes with low agreement. On the other hand, the popular automatic MT evaluation methods have some weaknesses. Firstly, they tend to perform well on the language pairs with English as the target language, but weak when English is used as source. Secondly, some methods rely on many additional linguistic features to achieve good performance, which makes the metric unable to replicate and apply to other language pairs easily. Thirdly, some popular metrics utilize incomprehensive factors, which result in low performance on some practical tasks. In this thesis, to address the existing problems, we design novel MT evaluation methods and investigate their performances on different languages. Firstly, we design augmented factors to yield highly accurate evaluation. Secondly, we design a tunable evaluation model where weighting of factors can be optimized according to the characteristics of languages. Thirdly, in the enhanced version of our methods, we design concise linguistic feature using part-of-speech (POS) to show that our methods can yield even higher performance when using some external linguistic resources. Finally, we introduce the practical performance of our metrics in the ACL-WMT workshop shared tasks, which show that the proposed methods are robust across different languages. In addition, we also present some novel work on quality estimation of MT without using reference translations including the usage of probability models of Naïve Bayes (NB), support vector machine (SVM) classification algorithms, and CRFs.