OpenRaiser/Intern-Atlas huggingface dataset:
Selection Algorithms with Small Groups
Venue: arXiv cs.DS 2019
Year: 2019

We revisit the selection problem, namely that of computing the $i$th order statistic of $n$ given elements, in particular the classic deterministic algorithm by grouping and partition due to Blum, Floyd, Pratt, Rivest, and Tarjan (1973). Whereas the original algorithm uses groups of odd size at least $5$ and runs in linear time, it has been perpetuated in the literature that using smaller group sizes will force the worst-case running time to become superlinear, namely $Ω(n \log{n})$. We first point out that the usual arguments found in the literature justifying the superlinear worst-case running time fall short of proving this claim. We further prove that it is possible to use group size smaller than $5$ while maintaining the worst case linear running time. To this end we introduce three simple variants of the classic algorithm, the repeated step algorithm, the shifting target algorithm, and the hyperpair algorithm, all running in linear time.
Thin Games with Symmetry and Concurrent Hyland-Ong Games
Venue: arXiv cs.LO 2019
Year: 2019

We build a cartesian closed category, called Cho, based on event structures. It allows an interpretation of higher-order stateful concurrent programs that is refined and precise: on the one hand it is conservative with respect to standard Hyland-Ong games when interpreting purely functional programs as innocent strategies, while on the other hand it is much more expressive. The interpretation of programs constructs compositionally a representation of their execution that exhibits causal dependencies and remembers the points of non-deterministic branching.The construction is in two stages. First, we build a compact closed category Tcg. It is a variant of Rideau and Winskel's category CG, with the difference that games and strategies in Tcg are equipped with symmetry to express that certain events are essentially the same. This is analogous to the underlying category of AJM games enriching simple games with an equivalence relations on plays. Building on this category, we construct the cartesian closed category Cho as having as objects the standard arenas of Hyland-Ong games, with strategies, represented by certain events structures, playing on games with symmetry obtained as expanded forms of these arenas.To illustrate and give an operational light on these constructions, we interpret (a close variant of) Idealized Parallel Algol in Cho.
The Timestamp of Timed Automata
Venue: arXiv cs.FL 2019
Year: 2019

Given a member A of the class of non-deterministic timed automata with silent transitions (eNTA), we effectively compute its timestamp: the set of all pairs (time value, action) of all observable timed traces of A, a generalization of the reachability problem. We show that the timestamp is eventually periodic and that one can compute a simple deterministic timed automaton with the same timestamp as that of A. As a consequence, we have a partial method, not bounded by time or number of steps, for the general language non-inclusion problem for eNTA. We also show that the language of A is periodic with respect to suffixes.
New results on classical and quantum counter automata
Venue: arXiv cs.FL 2019
Year: 2019

We show that one-way quantum one-counter automaton with zero-error is more powerful than its probabilistic counterpart on promise problems. Then, we obtain a similar separation result between Las Vegas one-way probabilistic one-counter automaton and one-way deterministic one-counter automaton. We also obtain new results on classical counter automata regarding language recognition. It was conjectured that one-way probabilistic one blind-counter automata cannot recognize Kleene closure of equality language [A. Yakaryilmaz: Superiority of one-way and realtime quantum machines. RAIRO - Theor. Inf. and Applic. 46(4): 615-641 (2012)]. We show that this conjecture is false, and also show several separation results for blind/non-blind counter automata.
Adaptive Estimation of Shannon Entropy
Venue: arXiv cs.IT 2019
Year: 2019

We consider estimating the Shannon entropy of a discrete distribution $P$ from $n$ i.i.d. samples. Recently, Jiao, Venkat, Han, and Weissman, and Wu and Yang constructed approximation theoretic estimators that achieve the minimax $L_2$ rates in estimating entropy. Their estimators are consistent given $n \gg \frac{S}{\ln S}$ samples, where $S$ is the alphabet size, and it is the best possible sample complexity. In contrast, the Maximum Likelihood Estimator (MLE), which is the empirical entropy, requires $n\gg S$ samples. In the present paper we significantly refine the minimax results of existing work. To alleviate the pessimism of minimaxity, we adopt the adaptive estimation framework, and show that the minimax rate-optimal estimator in Jiao, Venkat, Han, and Weissman achieves the minimax rates simultaneously over a nested sequence of subsets of distributions $P$, without knowing the alphabet size $S$ or which subset $P$ lies in. In other words, their estimator is adaptive with respect to this nested sequence of the parameter space, which is characterized by the entropy of the distribution. We also characterize the maximum risk of the MLE over this nested sequence, and show, for every subset in the sequence, that the performance of the minimax rate-optimal estimator with $n$ samples is essentially that of the MLE with $n\ln n$ samples, thereby further substantiating the generality of the phenomenon identified by Jiao, Venkat, Han, and Weissman.
Leader Election in Multi-Hop Radio Networks
Venue: arXiv cs.DC 2019
Year: 2019

In this paper we present a framework for leader election in multi-hop radio networks which yield randomized leader election algorithms taking $O(\text{broadcasting time})$ in expectation, and another which yields algorithms taking fixed $O(\sqrt{\log n})$-times broadcasting time. Both succeed with high probability. We show how to implement these frameworks in radio networks without collision detection, and in networks with collision detection (in fact in the strictly weaker beep model). In doing so, we obtain the first optimal expected-time leader election algorithms in both settings, and also improve the worst-case running time in directed networks without collision detection by an $O(\sqrt {\log n})$ factor.
Modeling meaning: computational interpreting and understanding of natural language fragments
Venue: arXiv cs.CL 2019
Year: 2019

In this introductory article we present the basics of an approach to implementing computational interpreting of natural language aiming to model the meanings of words and phrases. Unlike other approaches, we attempt to define the meanings of text fragments in a composable and computer interpretable way. We discuss models and ideas for detecting different types of semantic incomprehension and choosing the interpretation that makes most sense in a given context. Knowledge representation is designed for handling context-sensitive and uncertain / imprecise knowledge, and for easy accommodation of new information. It stores quantitative information capturing the essence of the concepts, because it is crucial for working with natural language understanding and reasoning. Still, the representation is general enough to allow for new knowledge to be learned, and even generated by the system. The article concludes by discussing some reasoning-related topics: possible approaches to generation of new abstract concepts, and describing situations and concepts in words (e.g. for specifying interpretation difficulties).
Quasi-Concavity for Gaussian Multicast Relay Channels
Venue: arXiv cs.IT 2019
Year: 2019

Standard upper and lower bounds on the capacity of relay channels are cut-set (CS), decode-forward (DF), and quantize-forward (QF) rates. For real additive white Gaussian noise (AWGN) multicast relay channels with one source node and one relay node, these bounds are shown to be quasi-concave in the receiver signal-to-noise ratios and the squared source-relay correlation coefficient. Furthermore, the CS rates are shown to be quasi-concave in the relay position for a fixed correlation coefficient, and the DF rates are shown to be quasi-concave in the relay position. The latter property characterizes the optimal relay position when using DF.
Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs
Venue: arXiv cs.DS 2019
Year: 2019

A colouring of a graph $G=(V,E)$ is a function $c: V\rightarrow\{1,2,\ldots \}$ such that $c(u)\neq c(v)$ for every $uv\in E$. A $k$-regular list assignment of $G$ is a function $L$ with domain $V$ such that for every $u\in V$, $L(u)$ is a subset of $\{1, 2, \dots\}$ of size $k$. A colouring $c$ of $G$ respects a $k$-regular list assignment $L$ of $G$ if $c(u)\in L(u)$ for every $u\in V$. A graph $G$ is $k$-choosable if for every $k$-regular list assignment $L$ of $G$, there exists a colouring of $G$ that respects $L$. We may also ask if for a given $k$-regular list assignment $L$ of a given graph $G$, there exists a colouring of $G$ that respects $L$. This yields the $k$-Regular List Colouring problem. For $k\in \{3,4\}$ we determine a family of classes ${\cal G}$ of planar graphs, such that either $k$-Regular List Colouring is NP-complete for instances $(G,L)$ with $G\in {\cal G}$, or every $G\in {\cal G}$ is $k$-choosable. By using known examples of non-$3$-choosable and non-$4$-choosable graphs, this enables us to classify the complexity of $k$-Regular List Colouring restricted to planar graphs, planar bipartite graphs, planar triangle-free graphs and to planar graphs with no $4$-cycles and no $5$-cycles. We also classify the complexity of $k$-Regular List Colouring and a number of related colouring problems for graphs with bounded maximum degree.
Perfect Secrecy under Deep Random assumption
Venue: arXiv cs.CR 2019
Year: 2019

We present a new idea to design perfectly secure information exchange protocol, based on so called Deep Randomness, which means randomness relying on hidden probability distribution. Such idea drives us to introduce a new axiom in probability theory, thanks to which we can design a protocol, beyond Shannon limit, enabling two legitimate partners, sharing originally no common private information, to exchange secret information with accuracy as close as desired from perfection, and knowledge as close as desired from zero by any unlimitedly powered opponent.
MultiView Diffusion Maps
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we address the challenging task of achieving multi-view dimensionality reduction. The goal is to effectively use the availability of multiple views for extracting a coherent low-dimensional representation of the data. The proposed method exploits the intrinsic relation within each view, as well as the mutual relations between views. The multi-view dimensionality reduction is achieved by defining a cross-view model in which an implied random walk process is restrained to hop between objects in the different views. The method is robust to scaling and insensitive to small structural changes in the data. We define new diffusion distances and analyze the spectra of the proposed kernel. We show that the proposed framework is useful for various machine learning applications such as clustering, classification, and manifold learning. Finally, by fusing multi-sensor seismic data we present a method for automatic identification of seismic events.
Combining Privileged Information to Improve Context-Aware Recommender Systems
Venue: arXiv cs.IR 2019
Year: 2019

A recommender system is an information filtering technology which can be used to predict preference ratings of items (products, services, movies, etc) and/or to output a ranking of items that are likely to be of interest to the user. Context-aware recommender systems (CARS) learn and predict the tastes and preferences of users by incorporating available contextual information in the recommendation process. One of the major challenges in context-aware recommender systems research is the lack of automatic methods to obtain contextual information for these systems. Considering this scenario, in this paper, we propose to use contextual information from topic hierarchies of the items (web pages) to improve the performance of context-aware recommender systems. The topic hierarchies are constructed by an extension of the LUPI-based Incremental Hierarchical Clustering method that considers three types of information: traditional bag-of-words (technical information), and the combination of named entities (privileged information I) with domain terms (privileged information II). We evaluated the contextual information in four context-aware recommender systems. Different weights were assigned to each type of information. The empirical results demonstrated that topic hierarchies with the combination of the two kinds of privileged information can provide better recommendations.
The minimum volume of subspace trades
Venue: arXiv cs.DM 2019
Year: 2019

A subspace bitrade of type $T_q(t,k,v)$ is a pair $(T_0,T_1)$ of two disjoint nonempty collections of $k$-dimensional subspaces of a $v$-dimensional space $V$ over the finite field of order $q$ such that every $t$-dimensional subspace of $V$ is covered by the same number of subspaces from $T_0$ and $T_1$. In a previous paper, the minimum cardinality of a subspace $T_q(t,t+1,v)$ bitrade was established. We generalize that result by showing that for admissible $v$, $t$, and $k$, the minimum cardinality of a subspace $T_q(t,k,v)$ bitrade does not depend on $k$. An example of a minimum bitrade is represented using generator matrices in the reduced echelon form. For $t=1$, the uniqueness of a minimum bitrade is proved.
On perfect codes that do not contain Preparata-like codes
Venue: arXiv cs.IT 2019
Year: 2019

We show that for every length of form $4^k-1$, there exists a binary $1$-perfect code that does not include any Preparata-like code.
Co-Clustering Under the Maximum Norm
Venue: arXiv cs.DM 2019
Year: 2019

Co-clustering, that is, partitioning a numerical matrix into homogeneous submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting variants of co-clustering are NP-hard. We focus on the basic variant of co-clustering where the homogeneity of a submatrix is defined in terms of minimizing the maximum distance between two entries. In this context, we spot several NP-hard as well as a number of relevant polynomial-time solvable special cases, thus charting the border of tractability for this challenging data clustering problem. For instance, we provide polynomial-time solvability when having to partition the rows and columns into two subsets each (meaning that one obtains four submatrices). When partitioning rows and columns into three subsets each, however, we encounter NP-hardness even for input matrices containing only values from {0, 1, 2}.
Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix
Venue: arXiv cs.SC 2019
Year: 2019

Computational problem certificates are additional data structures for each output, which can be used by a-possibly randomized-verification algorithm that proves the correctness of each output. In this paper, we give an algorithm that computes a certificate for the minimal polynomial of sparse or structured nxn matrices over an abstract field, of sufficiently large cardinality, whose Monte Carlo verification complexity requires a single matrix-vector multiplication and a linear number of extra field operations. We also propose a novel preconditioner that ensures irreducibility of the characteristic polynomial of the generically preconditioned matrix. This preconditioner takes linear time to be applied and uses only two random entries. We then combine these two techniques to give algorithms that compute certificates for the determinant, and thus for the characteristic polynomial, whose Monte Carlo verification complexity is therefore also linear.
Dynamic Matching and Allocation of Tasks
Venue: arXiv cs.GT 2019
Year: 2019

In many two-sided markets, the parties to be matched have incomplete information about their characteristics. We consider the settings where the parties engaged are extremely patient and are interested in long-term partnerships. Hence, once the final matches are determined, they persist for a long time. Each side has an opportunity to learn (some) relevant information about the other before final matches are made. For instance, clients seeking workers to perform tasks often conduct interviews that require the workers to perform some tasks and thereby provide information to both sides. The performance of a worker in such an interview- and hence the information revealed - depends both on the inherent characteristics of the worker and the task and also on the actions taken by the worker (e.g. the effort expended), which are not observed by the client. Thus there is moral hazard. Our goal is to derive a dynamic matching mechanism that facilitates learning on both sides before final matches are achieved and ensures that the worker side does not have incentive to obscure learning of their characteristics through their actions. We derive such a mechanism that leads to final matching that achieve optimal performance (revenue) in equilibrium. We show that the equilibrium strategy is long-run coalitionally stable, which means there is no subset of workers and clients that can gain by deviating from the equilibrium strategy. We derive all the results under the modeling assumption that the utilities of the agents are defined as limit of means of the utility obtained in each interaction.
Polynomial Depth, Highness and Lowness for E
Venue: arXiv cs.CC 2019
Year: 2019

We study the relations between the notions of highness, lowness and logical depth in the setting of complexity theory. We introduce a new notion of polylog depth based on time bounded Kolmogorov complexity. We show polylog depth satisfies all basic logical depth properties, namely sets in P are not polylog deep, sets with (time bounded)-Kolmogorov complexity greater than polylog are not polylog deep, and only polylog deep sets can polynomially Turing compute a polylog deep set. We prove that if NP does not have p-measure zero, then NP contains polylog deep sets. We show that every high set for E contains a polylog deep set in its polynomial Turing degree, and that there exist low(E,EXP) polylog deep sets. Keywords: algorithmic information theory; Kolmogorov complexity; Bennett logical depth.
Principal Component Projection Without Principal Component Analysis
Venue: arXiv cs.DS 2019
Year: 2019

We show how to efficiently project a vector onto the top principal components of a matrix, without explicitly computing these components. Specifically, we introduce an iterative algorithm that provably computes the projection using few calls to any black-box routine for ridge regression. By avoiding explicit principal component analysis (PCA), our algorithm is the first with no runtime dependence on the number of top principal components. We show that it can be used to give a fast iterative method for the popular principal component regression problem, giving the first major runtime improvement over the naive method of combining PCA with regression. To achieve our results, we first observe that ridge regression can be used to obtain a "smooth projection" onto the top principal components. We then sharpen this approximation to true projection using a low-degree polynomial approximation to the matrix step function. Step function approximation is a topic of long-term interest in scientific computing. We extend prior theory by constructing polynomials with simple iterative structure and rigorously analyzing their behavior under limited precision.
Stable Marriage with Covering Constraints: A Complete Computational Trichotomy
Venue: arXiv cs.DS 2019
Year: 2019

We consider Stable Marriage with Covering Constraints (SMC): in this variant of Stable Marriage, we distinguish a subset of women as well as a subset of men, and we seek a matching with fewest number of blocking pairs that matches all of the distinguished people. We investigate how a set of natural parameters, namely the maximum length of preference lists for men and women, the number of distinguished men and women, and the number of blocking pairs allowed determine the computational tractability of this problem. Our main result is a complete complexity trichotomy that, for each choice of the studied parameters, classifies SMC as polynomial-time solvable, NP-hard and fixed-parameter tractable, or NP-hard and W[1]-hard. We also classify all cases of one-sided constraints where only women may be distinguished.
Shortest Paths and Convex Hulls in 2D Complexes with Non-Positive Curvature
Venue: arXiv cs.CG 2019
Year: 2019

Globally non-positively curved, or CAT(0), polyhedral complexes arise in a number of applications, including evolutionary biology and robotics. These spaces have unique shortest paths and are composed of Euclidean polyhedra, yet many algorithms and properties of shortest paths and convex hulls in Euclidean space fail to transfer over. We give an algorithm, using linear programming, to compute the convex hull of a set of points in a 2-dimensional CAT(0) polyhedral complex with a single vertex. We explore the use of shortest path maps to answer single-source shortest path queries in 2-dimensional CAT(0) polyhedral complexes, and we unify efficient solutions for 2-manifold and rectangular cases.
The Complexity of Computing (Almost) Unitary Matrices With $\eps$-Copies of the Fourier Transform
Venue: arXiv cs.CC 2019
Year: 2019

The complexity of computing the Fourier transform is a longstanding open problem. Very recently, Ailon (2013, 2014, 2015) showed in a collection of papers that, roughly speaking, a speedup of the Fourier transform computation implies numerical ill-condition. The papers also quantify this tradeoff. The main method for proving these results is via a potential function called quasi-entropy, reminiscent of Shannon entropy. The quasi-entropy method opens new doors to understanding the computational complexity of the important Fourier transformation. However, it suffers from various obvious limitations. This paper, motivated by one such limitation, partly overcomes it, while at the same time sheds llight on new interesting, and problems on the intersection of computational complexity and group theory. The paper also explains why this research direction, if fruitful, has a chance of solving much bigger questions about the complexity of the Fourier transform.
Strategyproof Peer Selection using Randomization, Partitioning, and Apportionment
Venue: arXiv cs.GT 2019
Year: 2019

Peer reviews, evaluations, and selections are a fundamental aspect of modern science. Funding bodies the world over employ experts to review and select the best proposals from those submitted for funding. The problem of peer selection, however, is much more general: a professional society may want to give a subset of its members awards based on the opinions of all members; an instructor for a Massive Open Online Course (MOOC) or an online course may want to crowdsource grading; or a marketing company may select ideas from group brainstorming sessions based on peer evaluation. We make three fundamental contributions to the study of peer selection, a specific type of group decision-making problem, studied in computer science, economics, and political science. First, we propose a novel mechanism that is strategyproof, i.e., agents cannot benefit by reporting insincere valuations. Second, we demonstrate the effectiveness of our mechanism by a comprehensive simulation-based comparison with a suite of mechanisms found in the literature. Finally, our mechanism employs a randomized rounding technique that is of independent interest, as it solves the apportionment problem that arises in various settings where discrete resources such as parliamentary representation slots need to be divided proportionally.