OpenRaiser/Intern-Atlas huggingface dataset:
Clustering as an Evaluation Protocol for Knowledge Embedding Representation of Categorised Multi-relational Data in the Clinical Domain
Venue: arXiv cs.AI 2019
Year: 2019

Learning knowledge representation is an increasingly important technology applicable in many domain-specific machine learning problems. We discuss the effectiveness of traditional Link Prediction or Knowledge Graph Completion evaluation protocol when embedding knowledge representation for categorised multi-relational data in the clinical domain. Link prediction uses to split the data into training and evaluation subsets, leading to loss of information along training and harming the knowledge representation model accuracy. We propose a Clustering Evaluation Protocol as a replacement alternative to the traditionally used evaluation tasks. We used embedding models trained by a knowledge embedding approach which has been evaluated with clinical datasets. Experimental results with Pearson and Spearman correlations show strong evidence that the novel proposed evaluation protocol is pottentially able to replace link prediction.
Incremental Deployment of Network Monitors Based on Group Betweenness Centrality
Venue: arXiv cs.DS 2020
Year: 2020

In many applications we are required to increase the deployment of a distributed monitoring system on an evolving network. In this paper we present a new method for finding candidate locations for additional deployment in the network. This method is based on the Group Betweenness Centrality (GBC) measure that is used to estimate the influence of a group of nodes over the information flow in the network. The new method assists in finding the location of k additional monitors in the evolving network, such that the portion of additional traffic covered is at least (1-1/e) of the optimal.
Von Neumann Normalisation of a Quantum Random Number Generator
Venue: arXiv cs.IT 2020
Year: 2020

In this paper we study von Neumann un-biasing normalisation for ideal and real quantum random number generators, operating on finite strings or infinite bit sequences. In the ideal cases one can obtain the desired un-biasing. This relies critically on the independence of the source, a notion we rigorously define for our model. In real cases, affected by imperfections in measurement and hardware, one cannot achieve a true un-biasing, but, if the bias "drifts sufficiently slowly", the result can be arbitrarily close to un-biasing. For infinite sequences, normalisation can both increase or decrease the (algorithmic) randomness of the generated sequences. A successful application of von Neumann normalisation---in fact, any un-biasing transformation---does exactly what it promises, un-biasing, one (among infinitely many) symptoms of randomness; it will not produce "true" randomness.
A short proof that all linear codes are weakly algebraic-geometric using Bertini theorems of B. Poonen
Venue: arXiv cs.IT 2020
Year: 2020

In this paper we give a simpler proof of a deep theorem proved by Pellikan, Shen and van Wee that all linear codes are weakly algebraic-geometric using a theorem of B.Poonen.
Polynomiality for Bin Packing with a Constant Number of Item Types
Venue: arXiv cs.DS 2020
Year: 2020

We consider the bin packing problem with d different item sizes s_i and item multiplicities a_i, where all numbers are given in binary encoding. This problem formulation is also known as the 1-dimensional cutting stock problem. In this work, we provide an algorithm which, for constant d, solves bin packing in polynomial time. This was an open problem for all d >= 3. In fact, for constant d our algorithm solves the following problem in polynomial time: given two d-dimensional polytopes P and Q, find the smallest number of integer points in P whose sum lies in Q. Our approach also applies to high multiplicity scheduling problems in which the number of copies of each job type is given in binary encoding and each type comes with certain parameters such as release dates, processing times and deadlines. We show that a variety of high multiplicity scheduling problems can be solved in polynomial time if the number of job types is constant.
A Construction of New Quantum MDS Codes
Venue: arXiv cs.IT 2020
Year: 2020

It has been a great challenge to construct new quantum MDS codes. In particular, it is very hard to construct quantum MDS codes with relatively large minimum distance. So far, except for some sparse lengths, all known $q$-ary quantum MDS codes have minimum distance less than or equal to $q/2+1$. In the present paper, we provide a construction of quantum MDS codes with minimum distance bigger than $q/2+1$. In particular, we show existence of $q$-ary quantum MDS codes with length $n=q^2+1$ and minimum distance $d$ for any $d\le q-1$ and $d= q+1$(this result extends those given in \cite{Gu11,Jin1,KZ12}); and with length $(q^2+2)/3$ and minimum distance $d$ for any $d\le (2q+2)/3$ if $3|(q+1)$. Our method is through Hermitian self-orthogonal codes. The main idea of constructing Hermitian self-orthogonal codes is based on the solvability in $\F_q$ of a system of homogenous equations over $\F_{q^2}$.
Information-theoretic interpretation of quantum formalism
Venue: arXiv cs.IT 2020
Year: 2020

We present an information-theoretic interpretation of quantum formalism based on a Bayesian framework and devoid of any extra axiom or principle. Quantum information is construed as a technique for analyzing a logical system subject to classical constraints, based on a question-and-answer procedure. The problem is posed from a particular batch of queries while the constraints are represented by the truth table of a set of Boolean functions. The Bayesian inference technique consists in assigning a probability distribution within a real-valued probability space to the joint set of queries in order to satisfy the constraints. The initial query batch is not unique and alternative batches can be considered at will. They are enabled mechanically from the initial batch, quite simply by transcribing the probability space into a Hilbert space. It turns out that this sole procedure leads to exactly recover the standard quantum information theory and thus provides an information-theoretic rationale to its technical rules. In this framework, the great challenges of quantum mechanics become simple platitudes: Why is the theory probabilistic? Why is the theory linear? Where does the Hilbert space come from? In addition, most of the paradoxes, such as uncertainty principle, entanglement, contextuality, nonsignaling correlation, measurement problem, etc., become straightforwards features. In the end, our major conclusion is that quantum information is nothing but classical information processed by a mature form of Bayesian inference technique and, as such, consubstantial with Aristotelian logic.
Essentially optimal interactive certificates in linear algebra
Venue: arXiv cs.SC 2020
Year: 2020

Certificates to a linear algebra computation are additional data structures for each output, which can be used by a---possibly randomized---verification algorithm that proves the correctness of each output. The certificates are essentially optimal if the time (and space) complexity of verification is essentially linear in the input size $N$, meaning $N$ times a factor $N^{o(1)}$, i.e., a factor $N^{η(N)}$ with $\lim\_{N\to \infty} η(N)$ $=$ $0$. We give algorithms that compute essentially optimal certificates for the positive semidefiniteness, Frobenius form, characteristic and minimal polynomial of an $n\times n$ dense integer matrix $A$. Our certificates can be verified in Monte-Carlo bit complexity $(n^2 \log\|A\|)^{1+o(1)}$, where $\log\|A\|$ is the bit size of the integer entries, solving an open problem in [Kaltofen, Nehring, Saunders, Proc.\ ISSAC 2011] subject to computational hardness assumptions. Second, we give algorithms that compute certificates for the rank of sparse or structured $n\times n$ matrices over an abstract field, whose Monte Carlo verification complexity is $2$ matrix-times-vector products $+$ $n^{1+o(1)}$ arithmetic operations in the field. For example, if the $n\times n$ input matrix is sparse with $n^{1+o(1)}$ non-zero entries, our rank certificate can be verified in $n^{1+o(1)}$ field operations. This extends also to integer matrices with only an extra $\|A\|^{1+o(1)}$ factor. All our certificates are based on interactive verification protocols with the interaction removed by a Fiat-Shamir identification heuristic. The validity of our verification procedure is subject to standard computational hardness assumptions from cryptography.
Vertex Cover Reconfiguration and Beyond
Venue: arXiv cs.CC 2020
Year: 2020

In the Vertex Cover Reconfiguration (VCR) problem, given a graph $G$, positive integers $k$ and $\ell$ and two vertex covers $S$ and $T$ of $G$ of size at most $k$, we determine whether $S$ can be transformed into $T$ by a sequence of at most $\ell$ vertex additions or removals such that every operation results in a vertex cover of size at most $k$. Motivated by results establishing the W[1]-hardness of VCR when parameterized by $\ell$, we delineate the complexity of the problem restricted to various graph classes. In particular, we show that VCR remains W[1]-hard on bipartite graphs, is NP-hard, but fixed-parameter tractable on (regular) graphs of bounded degree and more generally on nowhere dense graphs and is solvable in polynomial time on trees and (with some additional restrictions) on cactus graphs.
Kolmogorov structure functions for automatic complexity
Venue: arXiv cs.FL 2020
Year: 2020

For a finite word $w$ we define and study the Kolmogorov structure function $h_w$ for nondeterministic automatic complexity. We prove upper bounds on $h_w$ that appear to be quite sharp, based on numerical evidence.
DAG-width is PSPACE-complete
Venue: arXiv cs.DM 2020
Year: 2020

Berwanger et al. show that for every graph $G$ of size $n$ and DAG-width $k$ there is a DAG decomposition of width $k$ and size $n^{O(k)}$. This gives a polynomial time algorithm for determining the DAG-width of a graph for any fixed $k$. However, if the DAG-width of the graphs from a class is not bounded, such algorithms become exponential. This raises the question whether we can always find a DAG decomposition of size polynomial in $n$ as it is the case for tree width and all generalisations of tree width similar to DAG-width. We show that there is an infinite class of graphs such that every DAG decomposition of optimal width has size super-polynomial in $n$ and, moreover, there is no polynomial size DAG decomposition which would approximate an optimal decomposition up to an additive constant. In the second part we use our construction to prove that deciding whether the DAG-width of a given graph is at most a given constant is PSPACE-complete.
Bernays-Schoenfinkel-Ramsey with Simple Bounds is NEXPTIME-complete
Venue: arXiv cs.LO 2020
Year: 2020

First-order predicate logic extended with linear arithmetic is undecidable, in general. We show that the Bernays-Schönfinkel-Ramsey (BSR) fragment extended with linear arithmetic restricted to simple bounds (SB) is decidable through finite ground instantiation. The identified ground instances can be employed to restrict the search space of existing automated reasoning procedures for BSR(SB). Satisfiability of BSR(SB) compared to BSR remains NEXPTIME-complete. The decidability result is almost tight because BSR is undecidable if extended with linear difference inequations, simple additive inequations, quotient inequations and multiplicative inequations.
A Hybrid Systems Model for Simple Manipulation and Self-Manipulation Systems
Venue: arXiv cs.RO 2020
Year: 2020

Rigid bodies, plastic impact, persistent contact, Coulomb friction, and massless limbs are ubiquitous simplifications introduced to reduce the complexity of mechanics models despite the obvious physical inaccuracies that each incurs individually. In concert, it is well known that the interaction of such idealized approximations can lead to conflicting and even paradoxical results. As robotics modeling moves from the consideration of isolated behaviors to the analysis of tasks requiring their composition, a mathematically tractable framework for building models that combine these simple approximations yet achieve reliable results is overdue. In this paper we present a formal hybrid dynamical system model that introduces suitably restricted compositions of these familiar abstractions with the guarantee of consistency analogous to global existence and uniqueness in classical dynamical systems. The hybrid system developed here provides a discontinuous but self-consistent approximation to the continuous (though possibly very stiff and fast) dynamics of a physical robot undergoing intermittent impacts. The modeling choices sacrifice some quantitative numerical efficiencies while maintaining qualitatively correct and analytically tractable results with consistency guarantees promoting their use in formal reasoning about mechanism, feedback control, and behavior design in robots that make and break contact with their environment.
Bag of Genres for Video Retrieval
Venue: arXiv cs.CV 2020
Year: 2020

Often, videos are composed of multiple concepts or even genres. For instance, news videos may contain sports, action, nature, etc. Therefore, encoding the distribution of such concepts/genres in a compact and effective representation is a challenging task. In this sense, we propose the Bag of Genres representation, which is based on a visual dictionary defined by a genre classifier. Each visual word corresponds to a region in the classification space. The Bag of Genres video vector contains a summary of the activations of each genre in the video content. We evaluate the proposed method for video genre retrieval using the dataset of MediaEval Tagging Task of 2012 and for video event retrieval using the EVVE dataset. Results show that the proposed method achieves results comparable or superior to state-of-the-art methods, with the advantage of providing a much more compact representation than existing features.
Attend, Adapt and Transfer: Attentive Deep Architecture for Adaptive Transfer from multiple sources in the same domain
Venue: arXiv cs.AI 2020
Year: 2020

Transferring knowledge from prior source tasks in solving a new target task can be useful in several learning applications. The application of transfer poses two serious challenges which have not been adequately addressed. First, the agent should be able to avoid negative transfer, which happens when the transfer hampers or slows down the learning instead of helping it. Second, the agent should be able to selectively transfer, which is the ability to select and transfer from different and multiple source tasks for different parts of the state space of the target task. We propose A2T (Attend, Adapt and Transfer), an attentive deep architecture which adapts and transfers from these source tasks. Our model is generic enough to effect transfer of either policies or value functions. Empirical evaluations on different learning algorithms show that A2T is an effective architecture for transfer by being able to avoid negative transfer while transferring selectively from multiple source tasks in the same domain.
Mathematical Foundations for Designing and Development of Intelligent Systems of Information Analysis
Venue: arXiv cs.AI 2020
Year: 2020

This article is an attempt to combine different ways of working with sets of objects and their classes for designing and development of artificial intelligent systems (AIS) of analysis information, using object-oriented programming (OOP). This paper contains analysis of basic concepts of OOP and their relation with set theory and artificial intelligence (AI). Process of sets and multisets creation from different sides, in particular mathematical set theory, OOP and AI is considered. Definition of object and its properties, homogeneous and inhomogeneous classes of objects, set of objects, multiset of objects and constructive methods of their creation and classification are proposed. In addition, necessity of some extension of existing OOP tools for the purpose of practical implementation AIS of analysis information, using proposed approach, is shown.
The 4/3 Additive Spanner Exponent is Tight
Venue: arXiv cs.DS 2020
Year: 2020

A spanner is a sparse subgraph that approximately preserves the pairwise distances of the original graph. It is well known that there is a smooth tradeoff between the sparsity of a spanner and the quality of its approximation, so long as distance error is measured multiplicatively. A central open question in the field is to prove or disprove whether such a tradeoff exists also in the regime of \emph{additive} error. That is, is it true that for all $\varepsilon>0$, there is a constant $k_{\varepsilon}$ such that every graph has a spanner on $O(n^{1+\varepsilon})$ edges that preserves its pairwise distances up to $+k_{\varepsilon}$? Previous lower bounds are consistent with a positive resolution to this question, while previous upper bounds exhibit the beginning of a tradeoff curve: all graphs have $+2$ spanners on $O(n^{3/2})$ edges, $+4$ spanners on $\tilde{O}(n^{7/5})$ edges, and $+6$ spanners on $O(n^{4/3})$ edges. However, progress has mysteriously halted at the $n^{4/3}$ bound, and despite significant effort from the community, the question has remained open for all $0 < \varepsilon < 1/3$. Our main result is a surprising negative resolution of the open question, even in a highly generalized setting. We show a new information theoretic incompressibility bound: there is no function that compresses graphs into $O(n^{4/3 - \varepsilon})$ bits so that distance information can be recovered within $+n^{o(1)}$ error. As a special case of our theorem, we get a tight lower bound on the sparsity of additive spanners: the $+6$ spanner on $O(n^{4/3})$ edges cannot be improved in the exponent, even if any subpolynomial amount of additive error is allowed. Our theorem implies new lower bounds for related objects as well; for example, the twenty-year-old $+4$ emulator on $O(n^{4/3})$ edges also cannot be improved in the exponent unless the error allowance is polynomial.
On links of vertices in simplicial $d$-complexes embeddable in the euclidean $2d$-space
Venue: arXiv cs.CG 2020
Year: 2020

We consider $d$-dimensional simplicial complexes which can be PL embedded in the $2d$-dimensional euclidean space. In short, we show that in any such complex, for any three vertices, the intersection of the link-complexes of the vertices is linklessly embeddable in the $(2d-1)$-dimensional euclidean space. These considerations lead us to a new upper bound on the total number of $d$-simplices in an embeddable complex in $2d$-space with $n$ vertices, improving known upper bounds, for all $d \geq 2$. Moreover, the bound is also true for the size of $d$-complexes linklessly embeddable in the $(2d+1)$-dimensional space.
Three-coloring triangle-free graphs on surfaces VII. A linear-time algorithm
Venue: arXiv cs.DM 2020
Year: 2020

We give a linear-time algorithm to decide 3-colorability of a triangle-free graph embedded in a fixed surface, and a quadratic-time algorithm to output a 3-coloring in the affirmative case. The algorithms also allow to prescribe the coloring of a bounded number of vertices.
Characterizing Polynomial Ramsey Quantifiers
Venue: arXiv cs.LO 2020
Year: 2020

Ramsey quantifiers are a natural object of study not only for logic and computer science, but also for the formal semantics of natural language. Restricting attention to finite models leads to the natural question whether all Ramsey quantifiers are either polynomial-time computable or NP-hard, and whether we can give a natural characterization of the polynomial-time computable quantifiers. In this paper, we first show that there exist intermediate Ramsey quantifiers and then we prove a dichotomy result for a large and natural class of Ramsey quantifiers, based on a reasonable and widely-believed complexity assumption. We show that the polynomial-time computable quantifiers in this class are exactly the constant-log-bounded Ramsey quantifiers.
Two Cumulative Distributions For Scale-freeness of Dynamic Networks
Venue: arXiv cs.SI 2020
Year: 2020

It is well-known that the scale-free networks are ubiquitous in nature and society and have been one of the hotspot topic in complex networks. Recently, scholars presented a large quantity of scale-free networks by calculating cumulative distribution. The purpose of this paper is to discuss the relationship between two cumulative distributions, namely, cumulative distribution, edge-cumulative distribution. Here, firstly, we introduce a relationship between degree distribution and cumulative distribution. Secondly, we introduce the definition of cumulative distribution and edge-cumulative distribution, and compare the relationship between them. Thirdly, we apply algorithmic techniques to construct three deterministic networks, calculate their cumulative distribution and edge-cumulative distribution, and analyze the relationship between cumulative distribution and edge-cumulative distribution. Finally, we offer some open problems for future research in order to understand the interplay between the degree distribution, cumulative distribution and edge-cumulative distribution.
Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Robotics
Venue: arXiv cs.RO 2020
Year: 2020

Robotic algorithms typically depend on various parameters, the choice of which significantly affects the robot's performance. While an initial guess for the parameters may be obtained from dynamic models of the robot, parameters are usually tuned manually on the real system to achieve the best performance. Optimization algorithms, such as Bayesian optimization, have been used to automate this process. However, these methods may evaluate unsafe parameters during the optimization process that lead to safety-critical system failures. Recently, a safe Bayesian optimization algorithm, called SafeOpt, has been developed, which guarantees that the performance of the system never falls below a critical value; that is, safety is defined based on the performance function. However, coupling performance and safety is often not desirable in robotics. For example, high-gain controllers might achieve low average tracking error (performance), but can overshoot and violate input constraints. In this paper, we present a generalized algorithm that allows for multiple safety constraints separate from the objective. Given an initial set of safe parameters, the algorithm maximizes performance but only evaluates parameters that satisfy safety for all constraints with high probability. To this end, it carefully explores the parameter space by exploiting regularity assumptions in terms of a Gaussian process prior. Moreover, we show how context variables can be used to safely transfer knowledge to new situations and tasks. We provide a theoretical analysis and demonstrate that the proposed algorithm enables fast, automatic, and safe optimization of tuning parameters in experiments on a quadrotor vehicle.
Dual-Context Calculi for Modal Logic
Venue: arXiv cs.LO 2020
Year: 2020

We present natural deduction systems and associated modal lambda calculi for the necessity fragments of the normal modal logics K, T, K4, GL and S4. These systems are in the dual-context style: they feature two distinct zones of assumptions, one of which can be thought as modal, and the other as intuitionistic. We show that these calculi have their roots in in sequent calculi. We then investigate their metatheory, equip them with a confluent and strongly normalizing notion of reduction, and show that they coincide with the usual Hilbert systems up to provability. Finally, we investigate a categorical semantics which interprets the modality as a product-preserving functor.