Search

A temporal graph G is a pair (G , λ) where G is a graph and λ is a function on the edges of G describing when each edge is active. Temporal connectivity then concerns only paths that respect the flow of time. In this context, it is known that Menger's Theorem does not hold. In a seminal paper, Kempe, Kleinberg and Kumar (STOC'2000) defined a graph to be Mengerian if equality holds for every time-function. They then proved that, if each edge is allowed to be active only once in (G , λ) , then G is Mengerian if and only if G has no gem as topological minor. In this paper, we generalize their result by allowing edges to be active more than once, giving a characterization also in terms of forbidden structures. We additionally provide a polynomial time recognition algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of PAC learning halfspaces in the non-interactive local differential privacy model (NLDP). To breach the barrier of exponential sample complexity, previous results studied a relaxed setting where the server has access to some additional public but unlabeled data. We continue in this direction. Specifically, we consider the problem under the standard setting instead of the large margin setting studied before. Under different mild assumptions on the underlying data distribution, we propose two approaches that are based on the Massart noise model and self-supervised learning and show that it is possible to achieve sample complexities that are only linear in the dimension and polynomial in other terms for both private and public data, which significantly improve the previous results. Our methods could also be used for other private PAC learning problems. [ABSTRACT FROM AUTHOR]

The maximum parsimony distance d MP (T 1 , T 2) and the bounded-state maximum parsimony distance d MP t (T 1 , T 2) measure the difference between two phylogenetic trees T 1 , T 2 in terms of the maximum difference between their parsimony scores for any character (with t a bound on the number of states in the character, in the case of d MP t (T 1 , T 2)). While computing d MP (T 1 , T 2) was previously shown to be fixed-parameter tractable with a linear kernel, no such result was known for d MP t (T 1 , T 2). In this paper, we prove that computing d MP t (T 1 , T 2) is fixed-parameter tractable for all t. Specifically, we prove that this problem has a kernel of size O (k lg ⁡ k) , where k = d MP t (T 1 , T 2). As the primary analysis tool, we introduce the concept of leg-disjoint incompatible quartets, which may be of independent interest. [ABSTRACT FROM AUTHOR]

In their 2006 seminal paper in Distributed Computing, Angluin et al. present a construction that, given any Presburger predicate, outputs a leaderless population protocol that decides the predicate. The protocol for a predicate of size m runs in O (m ⋅ n 2 log ⁡ n) expected number of interactions, which is almost optimal in n , the number of interacting agents. However, the number of states is exponential in m. Blondin et al. presented at STACS 2020 another construction that produces protocols with a polynomial number of states, but exponential expected number of interactions. We present a construction that produces protocols with O (m) states that run in expected O (m 7 ⋅ n 2) interactions, optimal in n , for all inputs of size Ω (m). For this, we introduce population computers, a generalization of population protocols, and show that our computers for Presburger predicates can be translated into fast and succinct population protocols. [ABSTRACT FROM AUTHOR]

This paper studies the relationship between undirected (unrooted) and directed (rooted) phylogenetic networks. We describe a polynomial-time algorithm for deciding whether an undirected nonbinary phylogenetic network, given the locations of the root and reticulation vertices, can be oriented as a directed nonbinary phylogenetic network. Moreover, we characterize when this is possible and show that, in such instances, the resulting directed nonbinary phylogenetic network is unique. In addition, without being given the location of the root and the reticulation vertices, we describe an algorithm for deciding whether an undirected binary phylogenetic network N can be oriented as a directed binary phylogenetic network of a certain class. The algorithm is fixed-parameter tractable (FPT) when the parameter is the level of N and is applicable to classes of directed phylogenetic networks that satisfy certain conditions. As an example, we show that the well-studied class of binary tree-child networks satisfies these conditions. [ABSTRACT FROM AUTHOR]