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

Given an $n$-vertex $m$-edge digraph $G = (V,E)$ and a set $S \subseteq V$, $|S| = n^{\sigma}$ (for some $0 < \sigma \le 1$) of designated sources, the $S \times V$-direachability problem is to compute for every $s \in S$, the set of all the vertices reachable from $s$ in $G$. Known naive algorithms for this problem either run a BFS/DFS separately from every source, and as a result require $O(m \cdot n^{\sigma})$ time, or compute the transitive closure of $G$ in $\tilde O(n^{\omega})$ time, where $\omega < 2.371552\ldots$ is the matrix multiplication exponent. Hence, the current state-of-the-art bound for the problem on graphs with $m = \Theta(n^{\mu})$ edges in $\tilde O(n^{\min \{\mu + \sigma, \omega \}})$. Our first contribution is an algorithm with running time $\tilde O(n^{1 + \tiny{\frac{2}{3}} \omega(\sigma)})$ for this problem, where $\omega(\sigma)$ is the rectangular matrix multiplication exponent. Using current state-of-the-art estimates on $\omega(\sigma)$, our exponent is better than $\min \{2 + \sigma, \omega \}$ for $\tilde \sigma \le \sigma \le 0.53$, where $1/3 < \tilde \sigma < 0.3336$ is a universal constant. Our second contribution is a sequence of algorithms $\mathcal A_0, \mathcal A_1, \mathcal A_2, \ldots$ for the $S \times V$-direachability problem. We argue that under a certain assumption that we introduce, for every $\tilde \sigma \le \sigma < 1$, there exists a sufficiently large index $k = k(\sigma)$ so that $\mathcal A_k$ improves upon the current state-of-the-art bounds for $S \times V$-direachability with $|S| = n^{\sigma}$, in the densest regime $\mu =2$. We show that to prove this assumption, it is sufficient to devise an algorithm that computes a rectangular max-min matrix product roughly as efficiently as ordinary $(+, \cdot)$ matrix product. Our algorithms heavily exploit recent constructions of directed shortcuts by Kogan and Parter.

This work concerns elementwise-transformations of spiked matrices: $Y_n = n^{-1/2} f( \sqrt{n} X_n + Z_n)$. Here, $f$ is a function applied elementwise, $X_n$ is a low-rank signal matrix, and $Z_n$ is white noise. We find that principal component analysis is powerful for recovering signal under highly nonlinear or discontinuous transformations. Specifically, in the high-dimensional setting where $Y_n$ is of size $n \times p$ with $n,p \rightarrow \infty$ and $p/n \rightarrow \gamma > 0$, we uncover a phase transition: for signal-to-noise ratios above a sharp threshold -- depending on $f$, the distribution of elements of $Z_n$, and the limiting aspect ratio $\gamma$ -- the principal components of $Y_n$ (partially) recover those of $X_n$. Below this threshold, the principal components of $Y_n$ are asymptotically orthogonal to the signal. In contrast, in the standard setting where $X_n + n^{-1/2}Z_n$ is observed directly, the analogous phase transition depends only on $\gamma$. A similar phenomenon occurs with $X_n$ square and symmetric and $Z_n$ a generalized Wigner matrix.

We prove that a polynomial fraction of the set of $k$-component forests in the $m \times n$ grid graph have equal numbers of vertices in each component, for any constant $k$. This resolves a conjecture of Charikar, Liu, Liu, and Vuong, and establishes the first provably polynomial-time algorithm for (exactly or approximately) sampling balanced grid graph partitions according to the spanning tree distribution, which weights each $k$-partition according to the product, across its $k$ pieces, of the number of spanning trees of each piece. Our result follows from a careful analysis of the probability a uniformly random spanning tree of the grid can be cut into balanced pieces. Beyond grids, we show that for a broad family of lattice-like graphs, we achieve balance up to any multiplicative $(1 \pm \varepsilon)$ constant with constant probability, and up to an additive constant with polynomial probability. More generally, we show that, with constant probability, components derived from uniform spanning trees can approximate any given partition of a planar region specified by Jordan curves. These results imply polynomial time algorithms for sampling approximately balanced tree-weighted partitions for lattice-like graphs. Our results have applications to understanding political districtings, where there is an underlying graph of indivisible geographic units that must be partitioned into $k$ population-balanced connected subgraphs. In this setting, tree-weighted partitions have interesting geometric properties, and this has stimulated significant effort to develop methods to sample them.

For a permutation $\pi:[k] \to [k]$, a function $f:[n] \to \mathbb{R}$ contains a $\pi$-appearance if there exists $1 \leq i_1 < i_2 < \dots < i_k \leq n$ such that for all $s,t \in [k]$, $f(i_s) < f(i_t)$ if and only if $\pi(s) < \pi(t)$. The function is $\pi$-free if it has no $\pi$-appearances. In this paper, we investigate the problem of testing whether an input function $f$ is $\pi$-free or whether $f$ differs on at least $\varepsilon n$ values from every $\pi$-free function. This is a generalization of the well-studied monotonicity testing and was first studied by Newman, Rabinovich, Rajendraprasad and Sohler (Random Structures and Algorithms 2019). We show that for all constants $k \in \mathbb{N}$, $\varepsilon \in (0,1)$, and permutation $\pi:[k] \to [k]$, there is a one-sided error $\varepsilon$-testing algorithm for $\pi$-freeness of functions $f:[n] \to \mathbb{R}$ that makes $\tilde{O}(n^{o(1)})$ queries. We improve significantly upon the previous best upper bound $O(n^{1 - 1/(k-1)})$ by Ben-Eliezer and Canonne (SODA 2018). Our algorithm is adaptive, while the earlier best upper bound is known to be tight for nonadaptive algorithms.

We consider the performance of a least-squares regression model, as judged by out-of-sample $R^2$. Shapley values give a fair attribution of the performance of a model to its input features, taking into account interdependencies between features. Evaluating the Shapley values exactly requires solving a number of regression problems that is exponential in the number of features, so a Monte Carlo-type approximation is typically used. We focus on the special case of least-squares regression models, where several tricks can be used to compute and evaluate regression models efficiently. These tricks give a substantial speed up, allowing many more Monte Carlo samples to be evaluated, achieving better accuracy. We refer to our method as least-squares Shapley performance attribution (LS-SPA), and describe our open-source implementation.

Standard multidimensional scaling takes as input a dissimilarity matrix of general term $\delta _{ij}$ which is a numerical value. In this paper we input $\delta _{ij}=[\underline{\delta _{ij}},\overline{\delta _{ij}}]$ where $\underline{\delta _{ij}}$ and $\overline{\delta _{ij}}$ are the lower bound and the upper bound of the ``dissimilarity'' between the stimulus/object $S_i$ and the stimulus/object $S_j$ respectively. As output instead of representing each stimulus/object on a factorial plane by a point, as in other multidimensional scaling methods, in the proposed method each stimulus/object is visualized by a rectangle, in order to represent dissimilarity variation. We generalize the classical scaling method looking for a method that produces results similar to those obtained by Tops Principal Components Analysis. Two examples are presented to illustrate the effectiveness of the proposed method.

Minimum sum vertex cover of an $n$-vertex graph $G$ is a bijection $\phi : V(G) \to [n]$ that minimizes the cost $\sum_{\{u,v\} \in E(G)} \min \{\phi(u), \phi(v) \}$. Finding a minimum sum vertex cover of a graph (the MSVC problem) is NP-hard. MSVC is studied well in the realm of approximation algorithms. The best-known approximation factor in polynomial time for the problem is $16/9$ [Bansal, Batra, Farhadi, and Tetali, SODA 2021]. Recently, Stankovic [APPROX/RANDOM 2022] proved that achieving an approximation ratio better than $1.014$ for MSVC is NP-hard, assuming the Unique Games Conjecture. We study the MSVC problem from the perspective of parameterized algorithms. The parameters we consider are the size of a minimum vertex cover and the size of a minimum clique modulator of the input graph. We obtain the following results. 1. MSVC can be solved in $2^{2^{O(k)}} n^{O(1)}$ time, where $k$ is the size of a minimum vertex cover. 2. MSVC can be solved in $f(k)\cdot n^{O(1)}$ time for some computable function $f$, where $k$ is the size of a minimum clique modulator.

This work considers a discrete-time Poisson noise channel with an input amplitude constraint $\mathsf{A}$ and a dark current parameter $\lambda$. It is known that the capacity-achieving distribution for this channel is discrete with finitely many points. Recently, for $\lambda=0$, a lower bound of order $\sqrt{\mathsf{A}}$ and an upper bound of order $\mathsf{A} \log^2(\mathsf{A})$ have been demonstrated on the cardinality of the support of the optimal input distribution. In this work, we improve these results in several ways. First, we provide upper and lower bounds that hold for non-zero dark current. Second, we produce a sharper upper bound with a far simpler technique. In particular, for $\lambda=0$, we sharpen the upper bound from the order of $\mathsf{A} \log^2(\mathsf{A})$ to the order of $\mathsf{A}$. Finally, some other additional information about the location of the support is provided.

We propose and analyze a class of meshfree, super-algebraically convergent methods for partial differential equations (PDEs) on surfaces using Fourier extensions minimizing a measure of non-smoothness (such as a Sobolev norm). Current spectral methods for surface PDEs are primarily limited to a small class of surfaces, such as subdomains of spheres. Other high order methods for surface PDEs typically use radial basis functions (RBFs). Many of these methods are not well-understood analytically for surface PDEs and are highly ill-conditioned. Our methods work by extending a surface PDE into a box-shaped domain so that differential operators of the extended function agree with the surface differential operators, as in the Closest Point Method. The methods can be proven to converge super-algebraically for certain well-posed linear PDEs, and spectral convergence to machine error has been observed numerically for a variety of problems. Our approach works on arbitrary smooth surfaces (closed or non-closed) defined by point clouds with minimal conditions.

Dynamic programming (DP) solves a variety of structured combinatorial problems by iteratively breaking them down into smaller subproblems. In spite of their versatility, DP algorithms are usually non-differentiable, which hampers their use as a layer in neural networks trained by backpropagation. To address this issue, we propose to smooth the max operator in the dynamic programming recursion, using a strongly convex regularizer. This allows to relax both the optimal value and solution of the original combinatorial problem, and turns a broad class of DP algorithms into differentiable operators. Theoretically, we provide a new probabilistic perspective on backpropagating through these DP operators, and relate them to inference in graphical models. We derive two particular instantiations of our framework, a smoothed Viterbi algorithm for sequence prediction and a smoothed DTW algorithm for time-series alignment. We showcase these instantiations on two structured prediction tasks and on structured and sparse attention for neural machine translation.