亚洲男人的天堂2018av,欧美草比,久久久久久免费视频精选,国色天香在线看免费,久久久久亚洲av成人片仓井空

Consider the problem of nonparametric estimation of an unknown $\beta$-H\"older smooth density $p_{XY}$ at a given point, where $X$ and $Y$ are both $d$ dimensional. An infinite sequence of i.i.d.\ samples $(X_i,Y_i)$ are generated according to this distribution, and two terminals observe $(X_i)$ and $(Y_i)$, respectively. They are allowed to exchange $k$ bits either in oneway or interactively in order for Bob to estimate the unknown density. We show that the minimax mean square risk is order $\left(\frac{k}{\log k} \right)^{-\frac{2\beta}{d+2\beta}}$ for one-way protocols and $k^{-\frac{2\beta}{d+2\beta}}$ for interactive protocols. The logarithmic improvement is nonexistent in the parametric counterparts, and therefore can be regarded as a consequence of nonparametric nature of the problem. Moreover, a few rounds of interactions achieve the interactive minimax rate: the number of rounds can grow as slowly as the super-logarithm (i.e., inverse tetration) of $k$. The proof of the upper bound is based on a novel multi-round scheme for estimating the joint distribution of a pair of biased Bernoulli variables.

We consider a non-monotone activation process $(X_t)_{t\in\{ 0,1,2,\ldots\}}$ on a graph $G$, where $X_0\subseteq V(G)$, $X_t=\{ u\in V(G):|N_G(u)\cap X_{t-1}|\geq \tau(u)\}$ for every positive integer $t$, and $\tau:V(G)\to \mathbb{Z}$ is a threshold function. The set $X_0$ is a so-called non-monotone target set for $(G,\tau)$ if there is some $t_0$ such that $X_t=V(G)$ for every $t\geq t_0$. Ben-Zwi, Hermelin, Lokshtanov, and Newman [Discrete Optimization 8 (2011) 87-96] asked whether a target set of minimum order can be determined efficiently if $G$ is a tree. We answer their question in the affirmative for threshold functions $\tau$ satisfying $\tau(u)\in \{ 0,1,d_G(u)\}$ for every vertex $u$. For such restricted threshold functions, we give a characterization of target sets that allows to show that the minimum target set problem remains NP-hard for planar graphs of maximum degree $3$ but is efficiently solvable for graphs of bounded treewidth.

We consider the problem of computing the topology and describing the geometry of a parametric curve in $\mathbb{R}^n$. We present an algorithm, PTOPO, that constructs an abstract graph that is isotopic to the curve in the embedding space. Our method exploits the benefits of the parametric representation and does not resort to implicitization. Most importantly, we perform all computations in the parameter space and not in the implicit space. When the parametrization involves polynomials of degree at most $d$ and maximum bitsize of coefficients $\tau$, then the worst case bit complexity of PTOPO is $ \tilde{\mathcal{O}}_B(nd^6+nd^5\tau+d^4(n^2+n\tau)+d^3(n^2\tau+ n^3)+n^3d^2\tau)$. This bound matches the current record bound $\tilde{\mathcal{O}}_B(d^6+d^5\tau)$ for the problem of computing the topology of a plane algebraic curve given in implicit form. For plane and space curves, if $N = \max\{d, \tau \}$, the complexity of PTOPO becomes $\tilde{\mathcal{O}}_B(N^6)$, which improves the state-of-the-art result, due to Alc\'azar and D\'iaz-Toca [CAGD'10], by a factor of $N^{10}$. In the same time complexity, we obtain a graph whose straight-line embedding is isotopic to the curve. However, visualizing the curve on top of the abstract graph construction, increases the bound to $\tilde{\mathcal{O}}_B(N^7)$. For curves of general dimension, we can also distinguish between ordinary and non-ordinary real singularities and determine their multiplicities in the same expected complexity of PTOPO by employing the algorithm of Blasco and P\'erez-D\'iaz [CAGD'19]. We have implemented PTOPO in Maple for the case of plane and space curves. Our experiments illustrate its practical nature.

What is the "right" topological invariant of a large point cloud X? Prior research has focused on estimating the full persistence diagram of X, a quantity that is very expensive to compute, unstable to outliers, and far from a sufficient statistic. We therefore propose that the correct invariant is not the persistence diagram of X, but rather the collection of persistence diagrams of many small subsets. This invariant, which we call "distributed persistence," is perfectly parallelizable, more stable to outliers, and has a rich inverse theory. The map from the space of point clouds (with the quasi-isometry metric) to the space of distributed persistence invariants (with the Hausdorff-Bottleneck distance) is a global quasi-isometry. This is a much stronger property than simply being injective, as it implies that the inverse of a small neighborhood is a small neighborhood, and is to our knowledge the only result of its kind in the TDA literature. Moreover, the quasi-isometry bounds depend on the size of the subsets taken, so that as the size of these subsets goes from small to large, the invariant interpolates between a purely geometric one and a topological one. Lastly, we note that our inverse results do not actually require considering all subsets of a fixed size (an enormous collection), but a relatively small collection satisfying certain covering properties that arise with high probability when randomly sampling subsets. These theoretical results are complemented by two synthetic experiments demonstrating the use of distributed persistence in practice.

Map labeling is a classical problem in cartography and geographic information systems (GIS) that asks to place labels for area, line, and point features, with the goal to select and place the maximum number of independent, i.e., overlap-free, labels. A practically interesting case is point labeling with axis-parallel rectangular labels of common size. In a fully dynamic setting, at each time step, either a new label appears or an existing label disappears. Then, the challenge is to maintain a maximum cardinality subset of pairwise independent labels with sub-linear update time. Motivated by this, we study the maximal independent set ((MIS)) and maximum independent set (Max-IS) problems on fully dynamic (insertion/deletion model) sets of axis-parallel rectangles of two types -- (i) uniform height and width and (ii) uniform height and arbitrary width; both settings can be modeled as rectangle intersection graphs. We present the first deterministic algorithm for maintaining an MIS (and thus a 4-approximate Max-IS) of a dynamic set of uniform rectangles with polylogarithmic update time. This breaks the natural barrier of $\Omega(\Delta)$ update time (where $\Delta$ is the maximum degree in the graph) for \emph{vertex updates} presented by Assadi et al. (STOC 2018). We continue by investigating Max-IS and provide a series of deterministic dynamic approximation schemes with approximation factors between 2 and 4 and corresponding running-time trade-offs. We have implemented our algorithms and reported the results of an experimental comparison exploring the trade-off between solution quality and update time for synthetic and real-world map labeling instances.

We introduce the problem of finding a set $B$ of $k$ points in $[0,1]^n$ such that the expected cost of the cheapest point in $B$ that dominates a random point from $[0,1]^n$ is minimized. We study the case where the coordinates of the random points are independently distributed and the cost function is linear. This problem arises naturally in various application areas where customers' requests are satisfied based on predefined products, each corresponding to a subset of features. We show that the problem is NP-hard already for $k=2$ when each coordinate is drawn from $\{0,1\}$, and obtain an FPTAS for general fixed $k$ under mild assumptions on the distributions.

A cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of $(1\pm\epsilon)$. This paper considers computing cut sparsifiers of weighted graphs of size $O(n\log (n)/\epsilon^2)$. Our algorithm computes such a sparsifier in time $O(m\cdot\min(\alpha(n)\log(m/n),\log (n)))$, both for graphs with polynomially bounded and unbounded integer weights, where $\alpha(\cdot)$ is the functional inverse of Ackermann's function. This improves upon the state of the art by Bencz\'ur and Karger (SICOMP 2015), which takes $O(m\log^2 (n))$ time. For unbounded weights, this directly gives the best known result for cut sparsification. Together with preprocessing by an algorithm of Fung et al. (SICOMP 2019), this also gives the best known result for polynomially-weighted graphs. Consequently, this implies the fastest approximate min-cut algorithm, both for graphs with polynomial and unbounded weights. In particular, we show that it is possible to adapt the state of the art algorithm of Fung et al. for unweighted graphs to weighted graphs, by letting the partial maximum spanning forest (MSF) packing take the place of the Nagamochi-Ibaraki (NI) forest packing. MSF packings have previously been used by Abraham at al. (FOCS 2016) in the dynamic setting, and are defined as follows: an $M$-partial MSF packing of $G$ is a set $\mathcal{F}=\{F_1, \dots, F_M\}$, where $F_i$ is a maximum spanning forest in $G\setminus \bigcup_{j=1}^{i-1}F_j$. Our method for computing (a sufficient estimation of) the MSF packing is the bottleneck in the running time of our sparsification algorithm.

Recently geometric hypergraphs that can be defined by intersections of pseudohalfplanes with a finite point set were defined in a purely combinatorial way. This led to extensions of earlier results about points and halfplanes to pseudohalfplanes, including polychromatic colorings and discrete Helly-type theorems about pseudohalfplanes. Here we continue this line of research and introduce the notion of convex sets of such pseudohalfplane hypergraphs. In this context we prove several results corresponding to classical results about convexity, namely Helly Theorem, Carath\'eodory's Theorem, Kirchberger's Theorem, Separation Theorem, Radon's Theorem and the Cup-Cap Theorem. These results imply the respective results about pseudoconvex sets in the plane defined using pseudohalfplanes. It turns out that most of our results can be also proved using oriented matroids and topological affine planes (TAPs) but our approach is different from both of them. Compared to oriented matroids, our theory is based on a linear ordering of the vertex set which makes our definitions and proofs quite different and perhaps more elementary. Compared to TAPs, which are continuous objects, our proofs are purely combinatorial and again quite different in flavor. Altogether, we believe that our new approach can further our understanding of these fundamental convexity results.

In this work, we consider the distributed optimization of non-smooth convex functions using a network of computing units. We investigate this problem under two regularity assumptions: (1) the Lipschitz continuity of the global objective function, and (2) the Lipschitz continuity of local individual functions. Under the local regularity assumption, we provide the first optimal first-order decentralized algorithm called multi-step primal-dual (MSPD) and its corresponding optimal convergence rate. A notable aspect of this result is that, for non-smooth functions, while the dominant term of the error is in $O(1/\sqrt{t})$, the structure of the communication network only impacts a second-order term in $O(1/t)$, where $t$ is time. In other words, the error due to limits in communication resources decreases at a fast rate even in the case of non-strongly-convex objective functions. Under the global regularity assumption, we provide a simple yet efficient algorithm called distributed randomized smoothing (DRS) based on a local smoothing of the objective function, and show that DRS is within a $d^{1/4}$ multiplicative factor of the optimal convergence rate, where $d$ is the underlying dimension.

Driven by successes in deep learning, computer vision research has begun to move beyond object detection and image classification to more sophisticated tasks like image captioning or visual question answering. Motivating such endeavors is the desire for models to capture not only objects present in an image, but more fine-grained aspects of a scene such as relationships between objects and their attributes. Scene graphs provide a formal construct for capturing these aspects of an image. Despite this, there have been only a few recent efforts to generate scene graphs from imagery. Previous works limit themselves to settings where bounding box information is available at train time and do not attempt to generate scene graphs with attributes. In this paper we propose a method, based on recent advancements in Generative Adversarial Networks, to overcome these deficiencies. We take the approach of first generating small subgraphs, each describing a single statement about a scene from a specific region of the input image chosen using an attention mechanism. By doing so, our method is able to produce portions of the scene graphs with attribute information without the need for bounding box labels. Then, the complete scene graph is constructed from these subgraphs. We show that our model improves upon prior work in scene graph generation on state-of-the-art data sets and accepted metrics. Further, we demonstrate that our model is capable of handling a larger vocabulary size than prior work has attempted.