OpenRaiser/Intern-Atlas huggingface dataset:
Kernels on Sample Sets via Nonparametric Divergence Estimates
Venue: arXiv cs.LG 2021
Year: 2021

Most machine learning algorithms, such as classification or regression, treat the individual data point as the object of interest. Here we consider extending machine learning algorithms to operate on groups of data points. We suggest treating a group of data points as an i.i.d. sample set from an underlying feature distribution for that group. Our approach employs kernel machines with a kernel on i.i.d. sample sets of vectors. We define certain kernel functions on pairs of distributions, and then use a nonparametric estimator to consistently estimate those functions based on sample sets. The projection of the estimated Gram matrix to the cone of symmetric positive semi-definite matrices enables us to use kernel machines for classification, regression, anomaly detection, and low-dimensional embedding in the space of distributions. We present several numerical experiments both on real and simulated datasets to demonstrate the advantages of our new approach.
Robust Cooperation in the Prisoner's Dilemma: Program Equilibrium via Provability Logic
Venue: arXiv cs.GT 2021
Year: 2021

We consider the one-shot Prisoner's Dilemma between algorithms with read-access to one anothers' source codes, and we use the modal logic of provability to build agents that can achieve mutual cooperation in a manner that is robust, in that cooperation does not require exact equality of the agents' source code, and unexploitable, meaning that such an agent never cooperates when its opponent defects. We construct a general framework for such "modal agents", and study their properties.
Security Analyses of Quantum Communication Protocols
Venue: arXiv cs.LO 2021
Year: 2021

Truly concurrent process algebras are generalizations to the traditional process algebras for true concurrency, CTC to CCS, APTC to ACP,$π_{tc}$ to $π$ calculus, APPTC to probabilistic process algebra.In this book, we utilize truly concurrent process algebras APTC and APPTC to model quantum computing and unify quantum and classical computing.
Foundations of an Alternative Approach to Reification in RDF
Venue: arXiv cs.DB 2021
Year: 2021

This document defines extensions of the RDF data model and of the SPARQL query language that capture an alternative approach to represent statement-level metadata. While this alternative approach is backwards compatible with RDF reification as defined by the RDF standard, the approach aims to address usability and data management shortcomings of RDF reification. One of the great advantages of the proposed approach is that it clarifies a means to (i) understand sparse matrices, the property graph model, hypergraphs, and other data structures with an emphasis on link attributes, (ii) map such data onto RDF, and (iii) query such data using SPARQL. Further, the proposal greatly expands both the freedom that database designers enjoy when creating physical indexing schemes and query plans for graph data annotated with link attributes and the interoperability of those database solutions.
Faster Compressed Quadtrees
Venue: arXiv cs.DS 2021
Year: 2021

Real-world point sets tend to be clustered, so using a machine word for each point is wasteful. In this paper we first show how a compact representation of quadtrees using $\Oh{1}$ bits per node can break this bound on clustered point sets, while offering efficient range searches. We then describe a new compact quadtree representation based on heavy path decompositions, which supports queries faster than previous compact structures. We present experimental evidence showing that our structure is competitive in practice.
A Concurrency-Optimal List-Based Set
Venue: arXiv cs.DC 2021
Year: 2021

Designing an efficient concurrent data structure is an important challenge that is not easy to meet. Intuitively, efficiency of an implementation is defined, in the first place, by its ability to process applied operations in parallel, without using unnecessary synchronization. As we show in this paper, even for a data structure as simple as a linked list used to implement the set type, the most efficient algorithms known so far are not concurrency-optimal: they may reject correct concurrent schedules. We propose a new algorithm for the list-based set based on a value-aware try-lock that we show to achieve optimal concurrency: it only rejects concurrent schedules that violate correctness of the implemented set type. We show empirically that reaching optimality does not induce a significant overhead. In fact, our implementation of the concurrency-optimal algorithm outperforms both the Lazy Linked List and the Harris-Michael state-of-the-art algorithms.
Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow-time problems
Venue: arXiv cs.DS 2021
Year: 2021

We study online scheduling problems on a single processor that can be viewed as extensions of the well-studied problem of minimizing total weighted flow time. In particular, we provide a framework of analysis that is derived by duality properties, does not rely on potential functions and is applicable to a variety of scheduling problems. A key ingredient in our approach is bypassing the need for "black-box" rounding of fractional solutions, which yields improved competitive ratios. We begin with an interpretation of Highest-Density-First (HDF) as a primal-dual algorithm, and a corresponding proof that HDF is optimal for total fractional weighted flow time (and thus scalable for the integral objective). Building upon the salient ideas of the proof, we show how to apply and extend this analysis to the more general problem of minimizing $\sum_j w_j g(F_j)$, where $w_j$ is the job weight, $F_j$ is the flow time and $g$ is a non-decreasing cost function. Among other results, we present improved competitive ratios for the setting in which $g$ is a concave function, and the setting of same-density jobs but general cost functions. We further apply our framework of analysis to online weighted completion time with general cost functions as well as scheduling under polyhedral constraints.
Coalitional Permutation Manipulations in the Gale-Shapley Algorithm
Venue: arXiv cs.GT 2021
Year: 2021

In this paper, we consider permutation manipulations by any subset of women in the men-proposing version of the Gale-Shapley algorithm. This paper is motivated by the college admissions process in China. Our results also answer an open problem on what can be achieved by permutation manipulations. We present an efficient algorithm to find a strategy profile such that the induced matching is stable and Pareto-optimal (in the set of all achievable stable matchings) while the strategy profile itself is inconspicuous. Surprisingly, we show that such a strategy profile actually forms a Nash equilibrium of the manipulation game. In the end, we show that it is NP-complete to find a manipulation that is strictly better for all members of the coalition. This result demonstrates a sharp contrast between weakly better off outcomes and strictly better-off outcomes.
Multilingual Open Relation Extraction Using Cross-lingual Projection
Venue: arXiv cs.CL 2021
Year: 2021

Open domain relation extraction systems identify relation and argument phrases in a sentence without relying on any underlying schema. However, current state-of-the-art relation extraction systems are available only for English because of their heavy reliance on linguistic tools such as part-of-speech taggers and dependency parsers. We present a cross-lingual annotation projection method for language independent relation extraction. We evaluate our method on a manually annotated test set and present results on three typologically different languages. We release these manual annotations and extracted relations in 61 languages from Wikipedia.
Sparse Automatic Differentiation for Complex Networks of Differential-Algebraic Equations Using Abstract Elementary Algebra
Venue: arXiv cs.MS 2021
Year: 2021

Most numerical solvers and libraries nowadays are implemented to use mathematical models created with language-specific built-in data types (e.g. real in Fortran or double in C) and their respective elementary algebra implementations. However, the built-in elementary algebra typically has limited functionality and often restricts the flexibility of mathematical models and the analysis types that can be applied to those models. To overcome this limitation, a number of domain-specific languages such as gPROMS or Modelica with more feature-rich built-in data types have been proposed. In this paper, we argue that if numerical libraries and solvers are designed to use abstract elementary algebra rather than the language-specific built-in algebra, modern mainstream languages can be as effective as any domain-specific language. We illustrate our ideas using the example of sparse Jacobian matrix computation. We implement an automatic differentiation method that takes advantage of sparse system structures and is straightforward to parallelize in a distributed memory setting. Furthermore, we show that the computational cost scales linearly with the size of the system.
Performance Analysis and Prediction in Educational Data Mining: A Research Travelogue
Venue: arXiv cs.CY 2021
Year: 2021

In this era of computerization, education has also revamped itself and is not limited to old lecture method. The regular quest is on to find out new ways to make it more effective and efficient for students. Nowadays, lots of data is collected in educational databases, but it remains unutilized. In order to get required benefits from such a big data, powerful tools are required. Data mining is an emerging powerful tool for analysis and prediction. It is successfully applied in the area of fraud detection, advertising, marketing, loan assessment and prediction. But, it is in nascent stage in the field of education. Considerable amount of work is done in this direction, but still there are many untouched areas. Moreover, there is no unified approach among these researches. This paper presents a comprehensive survey, a travelogue (2002-2014) towards educational data mining and its scope in future.
Weight Balancing on Boundaries
Venue: arXiv cs.CG 2021
Year: 2021

Given a polygonal region containing a target point (which we assume is the origin), it is not hard to see that there are two points on the perimeter that are antipodal, that is, whose midpoint is the origin. We prove three generalizations of this fact. (1) For any polygon (or any compact planar set) containing the origin, it is possible to place a given set of weights on the boundary so that their barycenter (center of mass) coincides with the origin, provided that the largest weight does not exceed the sum of the other weights. (2) On the boundary of any 3-dimensional compact set containing the origin, there exist three points that form an equilateral triangle centered at the origin. (3) For any $d$-dimensional bounded convex polyhedron containing the origin, there exists a pair of antipodal points consisting of a point on a $\lfloor d/2 \rfloor$-face and a point on a $\lceil d/2\rceil$-face.
Proving Differential Privacy via Probabilistic Couplings
Venue: arXiv cs.LO 2021
Year: 2021

In this paper, we develop compositional methods for formally verifying differential privacy for algorithms whose analysis goes beyond the composition theorem. Our methods are based on the observation that differential privacy has deep connections with a generalization of probabilistic couplings, an established mathematical tool for reasoning about stochastic processes. Even when the composition theorem is not helpful, we can often prove privacy by a coupling argument. We demonstrate our methods on two algorithms: the Exponential mechanism and the Above Threshold algorithm, the critical component of the famous Sparse Vector algorithm. We verify these examples in a relational program logic apRHL+, which can construct approximate couplings. This logic extends the existing apRHL logic with more general rules for the Laplace mechanism and the one-sided Laplace mechanism, and new structural rules enabling pointwise reasoning about privacy; all the rules are inspired by the connection with coupling. While our paper is presented from a formal verification perspective, we believe that its main insight is of independent interest for the differential privacy community.
On New Quantum Codes From Matrix Product Codes
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, by using matrix product codes, several classes of new quantum codes are obtained. Moreover, some of them have better parameters than the previous quantum codes available.
Fully-Convolutional Siamese Networks for Object Tracking
Venue: arXiv cs.CV 2021
Year: 2021

The problem of arbitrary object tracking has traditionally been tackled by learning a model of the object's appearance exclusively online, using as sole training data the video itself. Despite the success of these methods, their online-only approach inherently limits the richness of the model they can learn. Recently, several attempts have been made to exploit the expressive power of deep convolutional networks. However, when the object to track is not known beforehand, it is necessary to perform Stochastic Gradient Descent online to adapt the weights of the network, severely compromising the speed of the system. In this paper we equip a basic tracking algorithm with a novel fully-convolutional Siamese network trained end-to-end on the ILSVRC15 dataset for object detection in video. Our tracker operates at frame-rates beyond real-time and, despite its extreme simplicity, achieves state-of-the-art performance in multiple benchmarks.
Learning the semantic structure of objects from Web supervision
Venue: arXiv cs.CV 2021
Year: 2021

While recent research in image understanding has often focused on recognizing more types of objects, understanding more about the objects is just as important. Recognizing object parts and attributes has been extensively studied before, yet learning large space of such concepts remains elusive due to the high cost of providing detailed object annotations for supervision. The key contribution of this paper is an algorithm to learn the nameable parts of objects automatically, from images obtained by querying Web search engines. The key challenge is the high level of noise in the annotations; to address it, we propose a new unified embedding space where the appearance and geometry of objects and their semantic parts are represented uniformly. Geometric relationships are induced in a soft manner by a rich set of nonsemantic mid-level anchors, bridging the gap between semantic and non-semantic parts. We also show that the resulting embedding provides a visually-intuitive mechanism to navigate the learned concepts and their corresponding images.
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Venue: arXiv cs.DS 2021
Year: 2021

We present a method for solving the transshipment problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of $1 + \varepsilon$ in undirected graphs with non-negative edge weights using a tailored gradient descent algorithm. Using $\tilde{O}(\cdot)$ to hide polylogarithmic factors in $n$ (the number of nodes in the graph), our gradient descent algorithm takes $\tilde O(\varepsilon^{-2})$ iterations, and in each iteration it solves an instance of the transshipment problem up to a multiplicative error of $\operatorname{polylog} n$. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. Using a randomized rounding scheme, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve upon prior work by obtaining the following results: (1) Broadcast CONGEST model: $(1 + \varepsilon)$-approximate SSSP using $\tilde{O}((\sqrt{n} + D)\varepsilon^{-3})$ rounds, where $ D $ is the (hop) diameter of the network. (2) Broadcast congested clique model: $(1 + \varepsilon)$-approximate transshipment and SSSP using $\tilde{O}(\varepsilon^{-2})$ rounds. (3) Multipass streaming model: $(1 + \varepsilon)$-approximate transshipment and SSSP using $\tilde{O}(n)$ space and $\tilde{O}(\varepsilon^{-2})$ passes. The previously fastest SSSP algorithms for these models leverage sparse hop sets. We bypass the hop set construction; computing a spanner is sufficient with our method. The above bounds assume non-negative edge weights that are polynomially bounded in $n$; for general non-negative weights, running times scale with the logarithm of the maximum ratio between non-zero weights.
On $H$-Topological Intersection Graphs
Venue: arXiv cs.DM 2021
Year: 2021

Biró et al. (1992) introduced $H$-graphs, intersection graphs of connected subgraphs of a subdivision of a graph $H$. They are related to many classes of geometric intersection graphs, e.g., interval graphs, circular-arc graphs, split graphs, and chordal graphs. We negatively answer the 25-year-old question of Biró et al. which asks if $H$-graphs can be recognized in polynomial time, for a fixed graph $H$. We prove that it is NP-complete if $H$ contains the diamond graph as a minor. We provide a polynomial-time algorithm recognizing $T$-graphs, for each fixed tree $T$. When $T$ is a star $S_d$ of degree $d$, we have an $O(n^{3.5})$-time algorithm. We give FPT- and XP-time algorithms solving the minimum dominating set problem on $S_d$-graphs and $H$-graphs parametrized by $d$ and the size of $H$, respectively. The algorithm for $H$-graphs adapts to an XP-time algorithm for the independent set and the independent dominating set problems on $H$-graphs. If $H$ contains the double-triangle as a minor, we prove that $H$-graphs are GI-complete and that the clique problem is APX-hard. The clique problem can be solved in polynomial time if $H$ is a cactus graph. When a graph $G$ has a Helly $H$-representation, the clique problem can be solved in polynomial time. We show that both the $k$-clique and the list $k$-coloring problems are solvable in FPT-time on $H$-graphs (parameterized by $k$ and the treewidth of $H$). In fact, these results apply to classes of graphs with treewidth bounded by a function of the clique number. We observe that $H$-graphs have at most $n^{O(\|H\|)}$ minimal separators which allows us to apply the meta-algorithmic framework of Fomin et al. (2015) to show that for each fixed $t$, finding a maximum induced subgraph of treewidth $t$ can be done in polynomial time. When $H$ is a cactus, we improve the bound to $O(\|H\|n^2)$.
Datatype defining rewrite systems for naturals and integers
Venue: arXiv cs.LO 2021
Year: 2021

A datatype defining rewrite system (DDRS) is an algebraic (equational) specification intended to specify a datatype. When interpreting the equations from left-to-right, a DDRS defines a term rewriting system that must be ground-complete. First we define two DDRSs for the ring of integers, each comprising twelve rewrite rules, and prove their ground-completeness. Then we introduce natural number and integer arithmetic specified according to unary view, that is, arithmetic based on a postfix unary append constructor (a form of tallying). Next we specify arithmetic based on two other views: binary and decimal notation. The binary and decimal view have as their characteristic that each normal form resembles common number notation, that is, either a digit, or a string of digits without leading zero, or the negated versions of the latter. Integer arithmetic in binary and decimal notation is based on (postfix) digit append functions. For each view we define a DDRS, and in each case the resulting datatype is a canonical term algebra that extends a corresponding canonical term algebra for natural numbers. Then, for each view, we consider an alternative DDRS based on tree constructors that yields comparable normal forms, which for that view admits expressions that are algorithmically more involved. For all DDRSs considered, ground-completeness is proven.
Pricing and Optimization in Shared Vehicle Systems: An Approximation Framework
Venue: arXiv cs.GT 2021
Year: 2021

Optimizing shared vehicle systems (bike/scooter/car/ride-sharing) is more challenging compared to traditional resource allocation settings due to the presence of \emph{complex network externalities} -- changes in the demand/supply at any location affect future supply throughout the system within short timescales. These externalities are well captured by steady-state Markovian models, which are therefore widely used to analyze such systems. However, using such models to design pricing and other control policies is computationally difficult since the resulting optimization problems are high-dimensional and non-convex. To this end, we develop a \emph{rigorous approximation framework} for shared vehicle systems, providing a unified approach for a wide range of controls (pricing, matching, rebalancing), objective functions (throughput, revenue, welfare), and system constraints (travel-times, welfare benchmarks, posted-price constraints). Our approach is based on the analysis of natural convex relaxations, and obtains as special cases existing approximate-optimal policies for limited settings, asymptotic-optimality results, and heuristic policies. The resulting guarantees are non-asymptotic and parametric, and provide operational insights into the design of real-world systems. In particular, for any shared vehicle system with $n$ stations and $m$ vehicles, our framework obtains an approximation ratio of $1+(n-1)/m$, which is particularly meaningful when $m/n$, the average number of vehicles per station, is large, as is often the case in practice.
Class Invariants: Concepts, Problems, Solutions
Venue: arXiv cs.SE 2021
Year: 2021

Class invariants are both a core concept of object-oriented programming and the source of the two key open OO verification problems: furtive access (from callbacks) and reference leak. Existing approaches force on programmers an unacceptable annotation burden. This article explains invariants and solves both problems modularly through the O-rule, defining fundamental OO semantics, and the inhibition rule, using information hiding to remove harmful reference leaks. It also introduces the concept of "object tribe" as a basis for other possible approaches. For all readers: this article is long because it includes a tutorial, covers many examples and dispels misconceptions. To understand the key ideas and results, however, the first two pages suffice. For non-experts in verification: all concepts are explained; anyone with a basic understanding of object-oriented programming can understand the discussion. For experts: the main limitation of this work is that it is a paper proposal (no soundness proof, no implementation). It addresses, however, the known problems with class invariants, solving such examples as linked lists and Observer, through a simple theory and without any of the following: ownership; separation logic; universe types; object wrapping and unwrapping; semantic collaboration, observer specifications; history invariants; "inc" and "coop" constructs; friendship construct; non-modular reasoning. More generally, it involves no new language construct and no new programmer annotations.
Cognitive Indoor Positioning and Tracking using Multipath Channel Information
Venue: arXiv cs.RO 2021
Year: 2021

This paper presents a robust and accurate positioning system that adapts its behavior to the surrounding environment, mimicking the capability of the visual brain to filtering out clutter and focusing attention on activity and relevant information. Especially in indoor environments, which are characterized by harsh multipath propagation, robust positioning is still hard to achieve under the constraint of reasonable infrastructural needs. In such environments it is essential to separate relevant from irrelevant information and attain an appropriate uncertainty model for measurements that are used for positioning.