OpenRaiser/Intern-Atlas huggingface dataset:
OpenHPS: An Open Source Hybrid Positioning System
Venue: arXiv cs.CV 2020
Year: 2020

Positioning systems and frameworks use various techniques to determine the position of an object. Some of the existing solutions combine different sensory data at the time of positioning in order to compute more accurate positions by reducing the error introduced by the used individual positioning techniques. We present OpenHPS, a generic hybrid positioning system implemented in TypeScript, that can not only reduce the error during tracking by fusing different sensory data based on different algorithms, but also also make use of combined tracking techniques when calibrating or training the system. In addition to a detailed discussion of the architecture, features and implementation of the extensible open source OpenHPS framework, we illustrate the use of our solution in a demonstrator application fusing different positioning techniques. While OpenHPS offers a number of positioning techniques, future extensions might integrate new positioning methods or algorithms and support additional levels of abstraction including symbolic locations.
Knowledge Graphs and Natural-Language Processing
Venue: arXiv cs.CY 2020
Year: 2020

Emergency-relevant data comes in many varieties. It can be high volume and high velocity, and reaction times are critical, calling for efficient and powerful techniques for data analysis and management. Knowledge graphs represent data in a rich, flexible, and uniform way that is well matched with the needs of emergency management. They build on existing standards, resources, techniques, and tools for semantic data and computing. This chapter explains the most important semantic technologies and how they support knowledge graphs. We proceed to discuss their benefits and challenges and give examples of relevant semantic data sources and vocabularies. Natural-language texts -- in particular those collected from social media such as Twitter -- is a type of data source that poses particular analysis challenges. We therefore include an overview of techniques for processing natural-language texts.
Computability-logic web: an alternative to deep learning
Venue: arXiv cs.AI 2020
Year: 2020

{\em Computability logic} (CoL) is a powerful, mathematically rigorous computational model. In this paper, we show that CoL-web, a web extension to CoL, naturally supports web programming where database updates are involved. To be specific, we discuss an implementation of the AI ATM based on CoL (CL9 to be exact). More importantly, we argue that CoL-web supports a general AI and, therefore, is a good alternative to neural nets and deep learning. We also discuss how to integrate neural nets into CoL-web.
Black-box Adversarial Attacks on Monocular Depth Estimation Using Evolutionary Multi-objective Optimization
Venue: arXiv cs.CV 2020
Year: 2020

This paper proposes an adversarial attack method to deep neural networks (DNNs) for monocular depth estimation, i.e., estimating the depth from a single image. Single image depth estimation has improved drastically in recent years due to the development of DNNs. However, vulnerabilities of DNNs for image classification have been revealed by adversarial attacks, and DNNs for monocular depth estimation could contain similar vulnerabilities. Therefore, research on vulnerabilities of DNNs for monocular depth estimation has spread rapidly, but many of them assume white-box conditions where inside information of DNNs is available, or are transferability-based black-box attacks that require a substitute DNN model and a training dataset. Utilizing Evolutionary Multi-objective Optimization, the proposed method in this paper analyzes DNNs under the black-box condition where only output depth maps are available. In addition, the proposed method does not require a substitute DNN that has a similar architecture to the target DNN nor any knowledge about training data used to train the target model. Experimental results showed that the proposed method succeeded in attacking two DNN-based methods that were trained with indoor and outdoor scenes respectively.
Machine Learning Coupled Trajectory and Communication Design for UAV-Facilitated Wireless Networks
Venue: arXiv cs.NI 2020
Year: 2020

Augmenting wireless networks with Unmanned Aerial Vehicles (UAVs), commonly referred to as drones, offers a promising avenue for providing reliable, cost-effective, and on-demand wireless services to desired areas. However, existing UAV communication and trajectory schemes are inefficient as they assume limited drone mobility and static transmission power. Furthermore, they tend to rely upon convex approximations to highly non-linear functions and fail to adopt a combination of heuristic and convex methods. This paper considers a Multi-UAV system where UAV-mounted mobile base stations serve users on the ground. An iterative approach using block gradient descent is used to jointly optimize user scheduling, UAV trajectories, and transmission power for maximizing throughput over all users. Subsequently, an innovative technique for initial trajectory predictions was developed using a K-means clustering algorithm for partitioning users into subgroups and a genetic algorithm for initializing shortest flight paths within clusters. Finally, convex optimization solvers such as MATLAB's Fmincon are used for fine-tuning parameters. Extensive simulation and optimization results demonstrate a 33.57%, 87.4%, and 53.2% increase in system throughput for the 1, 2, and 3 UAV scenarios respectively when compared to existing trajectory and communication design schemes. Furthermore, the K-means and genetic algorithm reveal additional improvements in throughput by around 15%. Our results note diminished increases in throughput for increases in UAV trajectory period as the period approaches higher values. Further research into joint adoption of convex and non-convex schemes as well as consideration of environment-dependent channel models would allow for a faster and more optimal deployment of UAVs.
Application Layer Modeling in Vehicle Networks: Cooperative Maneuver Use Case
Venue: arXiv cs.NI 2020
Year: 2020

In recent years, network function virtualization and a software defined focus has allowed networks to become flexible and extensible in ways not possible previously. Although network modeling tools such as NS-2, NS-3, and OMNet++ have been extended with modules and code to support the absolute latest wireless protocols and medium access standards - there has been a growing gap in simulation of layers above medium access which recent 5G use cases are designed to support. In this thesis, I extend research into the topic of application layer modeling in wireless networks, with focus on upcoming deployments of enhanced vehicle services. In particular, I begin in discussing the evolution of vehicle network standards and use cases, along with the most recent initiative `Project 5GCar`; funded by the European Commission. I go narrower, from the macro trend of vehicular network standards evolution, to compare the state of the art in simulation stacks, designed to support application models in vehicle networks. Within this comparison, simulation environments OVNIS, Veins, iTetris, and VSimRTI are compared for their capabilities. Finally, to measure the qualitative performance of application layer modeling in vehicle networks, I take the cooperative maneuver use case, presented under Project 5GCar; to design an autonomous merge algorithm - completing the steps required to program and model the application in vehicles using the VSimRTI simulation stack.
Correlation Decay up to Uniqueness in Spin Systems
Venue: arXiv cs.DS 2021
Year: 2021

We give a complete characterization of the two-state anti-ferromagnetic spin systems which are of strong spatial mixing on general graphs. We show that a two-state anti-ferromagnetic spin system is of strong spatial mixing on all graphs of maximum degree at most $Δ$ if and only if the system has a unique Gibbs measure on infinite regular trees of degree up to $Δ$, where $Δ$ can be either bounded or unbounded. As a consequence, there exists an FPTAS for the partition function of a two-state anti-ferromagnetic spin system on graphs of maximum degree at most $Δ$ when the uniqueness condition is satisfied on infinite regular trees of degree up to $Δ$. In particular, an FPTAS exists for arbitrary graphs if the uniqueness is satisfied on all infinite regular trees. This covers as special cases all previous algorithmic results for two-state anti-ferromagnetic systems on general-structure graphs. Combining with the FPRAS for two-state ferromagnetic spin systems of Jerrum-Sinclair and Goldberg-Jerrum-Paterson, and the hardness results of Sly-Sun and independently of Galanis-Stefankovic-Vigoda, this gives a complete classification, except at the phase transition boundary, of the approximability of all two-state spin systems, on either degree-bounded families of graphs or family of all graphs.
Enumerable Distributions, Randomness, Dependence
Venue: arXiv cs.CC 2021
Year: 2021

Mutual information I in infinite sequences (and in their finite prefixes) is essential in theoretical analysis of many situations. Yet its right definition has been elusive for a long time. I address it by generalizing Kolmogorov Complexity theory from measures to SEMImeasures i.e, infimums of sets of measures. Being concave rather than linear functionals, semimeasures are quite delicate to handle. Yet, they adequately grasp various theoretical and practical scenaria. A simple lower bound i$(α:β) = \sup\,_{x\in N}\,(K(x) - K(x|α) - K(x|β)) $ for information turns out tight for Martin-Lof random $ α,β$. For all sequences I$(α:β) $ is characterized by the minimum of i$(α':β') $ over random $ α',β' $ with $ U(α')=α, U(β')=β$.
Modal Functional (Dialectica) Interpretation
Venue: arXiv cs.LO 2021
Year: 2021

We adapt our light Dialectica interpretation to usual and light modal formulas (with universal quantification on boolean and natural variables) and prove it sound for a non-standard modal arithmetic based on Goedel's T and classical S4. The range of this light modal Dialectica is the usual (non-modal) classical Arithmetic in all finite types (with booleans); the propositional kernel of its domain is Boolean and not S4. The `heavy' modal Dialectica interpretation is a new technique, as it cannot be simulated within our previous light Dialectica. The synthesized functionals are at least as good as before, while the translation process is improved. Through our modal Dialectica, the existence of a realizer for the defining axiom of classical S5 reduces to the Drinking Principle (cf. Smullyan).
Learning Bayesian Networks: A Unification for Discrete and Gaussian Domains
Venue: arXiv cs.AI 2021
Year: 2021

We examine Bayesian methods for learning Bayesian networks from a combination of prior knowledge and statistical data. In particular, we unify the approaches we presented at last year's conference for discrete and Gaussian domains. We derive a general Bayesian scoring metric, appropriate for both domains. We then use this metric in combination with well-known statistical facts about the Dirichlet and normal--Wishart distributions to derive our metrics for discrete and Gaussian domains.
Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
Venue: arXiv cs.DS 2021
Year: 2021

We prove that any graph excluding $K_r$ as a minor has can be partitioned into clusters of diameter at most $Δ$ while removing at most $O(r/Δ)$ fraction of the edges. This improves over the results of Fakcharoenphol and Talwar, who building on the work of Klein, Plotkin and Rao gave a partitioning that required to remove $O(r^2/Δ)$ fraction of the edges. Our result is obtained by a new approach to relate the topological properties (excluding a minor) of a graph to its geometric properties (the induced shortest path metric). Specifically, we show that techniques used by Andreae in his investigation of the cops-and-robbers game on excluded-minor graphs can be used to construct padded decompositions of the metrics induced by such graphs. In particular, we get probabilistic partitions with padding parameter $O(r)$ and strong-diameter partitions with padding parameter $O(r^2)$ for $K_r$-free graphs, padding $O(k)$ for graphs with treewidth $k$, and padding $O(\log g)$ for graphs with genus $g$.
Analyzing the Dual Space of the Saturated Ideal of a Regular Set and the Local Multiplicities of its Zeros
Venue: arXiv cs.SC 2021
Year: 2021

In this paper, we are concerned with the problem of counting the multiplicities of a zero-dimensional regular set's zeros. We generalize the squarefree decomposition of univariate polynomials to the so-called pseudo squarefree decomposition of multivariate polynomials, and then propose an algorithm for decomposing a regular set into a finite number of simple sets. From the output of this algorithm, the multiplicities of zeros could be directly read out, and the real solution isolation with multiplicity can also be easily produced. As a main theoretical result of this paper, we analyze the structure of dual space of the saturated ideal generated by a simple set as well as a regular set. Experiments with a preliminary implementation show the efficiency of our method.
Local Algorithms for Sparse Spanning Graphs
Venue: arXiv cs.DS 2021
Year: 2021

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider a relaxed version of this problem in the setting of local algorithms. The relaxation is that the constructed subgraph is a sparse spanning subgraph containing at most $(1+ε)n$ edges (where $n$ is the number of vertices and $ε$ is a given approximation/sparsity parameter). In the local setting, the goal is to quickly determine whether a given edge $e$ belongs to such a subgraph, without constructing the whole subgraph, but rather by inspecting (querying) the local neighborhood of $e$. The challenge is to maintain consistency. That is, to provide answers concerning different edges according to the same spanning subgraph. We first show that for general bounded-degree graphs, the query complexity of any such algorithm must be $Ω(\sqrt{n})$. This lower bound holds for constant-degree graphs that have high expansion. Next we design an algorithm for (bounded-degree) graphs with high expansion, obtaining a result that roughly matches the lower bound. We then turn to study graphs that exclude a fixed minor (and are hence non-expanding). We design an algorithm for such graphs, which may have an unbounded maximum degree. The query complexity of this algorithm is $poly(1/ε, h)$ (independent of $n$ and the maximum degree), where $h$ is the number of vertices in the excluded minor. Though our two algorithms are designed for very different types of graphs (and have very different complexities), on a high-level there are several similarities, and we highlight both the similarities and the differences.
The Density of Fan-Planar Graphs
Venue: arXiv cs.DM 2021
Year: 2021

A topological drawing of a graph is fan-planar if for each edge $e$ the edges crossing $e$ form a star and no endpoint of $e$ is enclosed by $e$ and its crossing edges. A fan-planar graph is a graph admitting such a drawing. Equivalently, this can be formulated by three forbidden patterns, one of which is the configuration where $e$ is crossed by two independent edges and the other two where $e$ is crossed by two incident edges in a way that encloses some endpoint of $e$. A topological drawing is simple if any two edges have at most one point in common. Fan-planar graphs are a new member in the ever-growing list of topological graphs defined by forbidden intersection patterns, such as planar graphs and their generalizations, Turán-graphs and Conway's thrackle conjecture. Hence fan-planar graphs fall into an important field in combinatorial geometry with applications in various areas of discrete mathematics. As every $1$-planar graph is fan-planar and every fan-planar graph is $3$-quasiplanar, they also fit perfectly in a recent series of work on nearly-planar graphs from the area of graph drawing and combinatorial embeddings. In this paper we show that every fan-planar graph on $n$ vertices has at most $5n-10$ edges, even though a fan-planar drawing may have a quadratic number of crossings. Our bound, which is tight for every $n \geq 20$, indicates how nicely fan-planar graphs fit in the row with planar graphs ($3n-6$ edges) and $1$-planar graphs ($4n-8$ edges). With this, fan-planar graphs form the largest non-trivial class of topological graphs defined by forbidden patterns, for which the maximum number of edges on $n$ vertices is known exactly.
The Sample Complexity of Learning Linear Predictors with the Squared Loss
Venue: arXiv cs.LG 2021
Year: 2021

In this short note, we provide a sample complexity lower bound for learning linear predictors with respect to the squared loss. Our focus is on an agnostic setting, where no assumptions are made on the data distribution. This contrasts with standard results in the literature, which either make distributional assumptions, refer to specific parameter settings, or use other performance measures.
Tractability Frontier of Data Complexity in Team Semantics
Venue: arXiv cs.LO 2021
Year: 2021

We study the data complexity of model-checking for logics with team semantics. We focus on dependence, inclusion, and independence logic formulas under both strict and lax team semantics. Our results delineate a clear tractability/intractability frontiers in data complexity of both quantifier-free and quantified formulas for each of the logics. For inclusion logic under the lax semantics, we reduce the model-checking problem to the satisfiability problem of so-called dual-Horn Boolean formulas. Via this reduction, we give an alternative proof for the known result that the data complexity of inclusion logic is in PTIME.
On Temporal Graph Exploration
Venue: arXiv cs.DS 2021
Year: 2021

A temporal graph is a graph in which the edge set can change from one time step to the next. The temporal graph exploration problem TEXP is the problem of computing a foremost exploration schedule for a temporal graph, i.e., a temporal walk that starts at a given start node, visits all nodes of the graph, and has the smallest arrival time. In the first part of the paper, we consider only undirected temporal graphs that are connected at each time step. For such temporal graphs with $n$ nodes, we show that it is \NP-hard to approximate TEXP with ratio $O(n^{1-\varepsilon})$ for every $\varepsilon>0$. We also provide an explicit construction of temporal graphs that require $Θ(n^2)$ time steps to be explored. In the second part of the paper, we still consider temporal graphs that are connected in each time step, but we assume that the underlying graph (i.e. the graph that contains all edges that are present in the temporal graph in at least one time step) belongs to a specific class of graphs. Among other results, we show that temporal graphs can be explored in $O(n^{1.5}k^{1.5}\log n)$ time steps if the underlying graph has treewidth $k$, in $O(n^{1.8}\log n)$ time steps if the underlying graph is planar, and in $O(n\log^3 n)$ time steps if the underlying graph is a $2\times n$ grid. In the third part of the paper, we consider settings where the graphs in future time steps are not known and the exploration schedule is constructed online. We replace the connectedness assumption by a weaker assumption and show that $m$-edge temporal graphs with regularly present edges and with probabilistically present edges can be explored online in $O(m)$ time steps and $O(m \log n)$ time steps with high probability, respectively. We finally show that the latter result can be used to obtain a distributed algorithm for the gossiping problem in random temporal graphs.
Very Sparse Additive Spanners and Emulators
Venue: arXiv cs.DS 2021
Year: 2021

We study two popular ways to sketch the shortest path distances of an input graph. The first is distance preservers, which are sparse subgraphs that agree with the distances of the original graph on a given set of demand pairs. Prior work on distance preservers has exploited only a simple structural property of shortest paths, called consistency, stating that one can break shortest path ties such that no two paths intersect, split apart, and then intersect again later. We prove that consistency alone is not enough to understand distance preservers, by showing both a lower bound on the power of consistency and a new general upper bound that polynomially surpasses it. Specifically, our new upper bound is that any $p$ demand pairs in an $n$-node undirected unweighted graph have a distance preserver on $O(n^{2/3}p^{2/3} + np^{1/3})$ edges. We leave a conjecture that the right bound is $O(n^{2/3}p^{2/3} + n)$ or better. The second part of this paper leverages these distance preservers in a new construction of additive spanners, which are subgraphs that preserve all pairwise distances up to an additive error function. We give improved error bounds for spanners with relatively few edges; for example, we prove that all graphs have spanners on $O(n)$ edges with $+O(n^{3/7 + \varepsilon})$ error. Our construction can be viewed as an extension of the popular path-buying framework to clusters of larger radii.
Polynomial Fixed-Parameter Algorithms: A Case Study for Longest Path on Interval Graphs
Venue: arXiv cs.CC 2021
Year: 2021

We study the design of fixed-parameter algorithms for problems already known to be solvable in polynomial time. The main motivation is to get more efficient algorithms for problems with unattractive polynomial running times. Here, we focus on a fundamental graph problem: Longest Path, that is, given an undirected graph, find a maximum-length path in $G$. Longest Path is NP-hard in general but known to be solvable in $O(n^{4})$ time on $n$-vertex interval graphs. We show how to solve Longest Path on Interval Graphs, parameterized by vertex deletion number $k$ to proper interval graphs, in $O(k^{9}n)$ time. Notably, Longest Path is trivially solvable in linear time on proper interval graphs, and the parameter value $k$ can be approximated up to a factor of 4 in linear time. From a more general perspective, we believe that using parameterized complexity analysis may enable a refined understanding of efficiency aspects for polynomial-time solvable problems similarly to what classical parameterized complexity analysis does for NP-hard problems.
Structural Generalizability: The Case of Similarity Search
Venue: arXiv cs.DB 2021
Year: 2021

Graph similarity search algorithms usually leverage the structural properties of a database. Hence, these algorithms are effective only on some structural variations of the data and are ineffective on other forms, which makes them hard to use. Ideally, one would like to design a data analytics algorithm that is structurally robust, i.e., it returns essentially the same accurate results over all possible structural variations of a dataset. We propose a novel approach to create a structurally robust similarity search algorithm over graph databases. We leverage the classic insight in the database literature that schematic variations are caused by having constraints in the database. We then present RelSim algorithm which is provably structurally robust under these variations. Our empirical studies show that our proposed algorithms are structurally robust while being efficient and as effective as or more effective than the state-of-the-art similarity search algorithms.
On a new fast public key cryptosystem
Venue: arXiv cs.CR 2021
Year: 2021

This paper presents a new fast public key cryptosystem namel : a key exchange algorithm, a public key encryption algorithm and a digital signature algorithm, based on the difficulty to invert the following function: $$F(x) =(a\times x)Mod(2^p)Div(2^q).$$ Mod is modulo operation , Div is integer division operation , a , p and q are integers where $( p > q )$. We define p and q values for which ModDiv2Inv can be the hardest. We then present ModDiv2Kex, a new fast key exchange algorithm based on ModDiv2Inv. In this paper we also evaluate the hardness of this problem by reducing it to SAT .