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

The dichromatic number $\vec{\chi}(D)$ of a digraph $D$ is the least integer $k$ for which $D$ has a coloring with $k$ colors such that there is no monochromatic directed cycle in $D$. The digraphs considered here are finite and may have antiparallel arcs, but no parallel arcs. A digraph $D$ is called $k$-critical if each proper subdigraph $D'$ of $D$ satisfies $\vec{\chi}(D')<\vec{\chi}(D)=k$. For integers $k$ and $n$, let $\overrightarrow{\mathrm{ext}}(k,n)$ denote the minimum number of arcs possible in a $k$-critical digraph of order $n$. It is easy to show that $\overrightarrow{\mathrm{ext}}(2,n)=n$ for all $n\geq 2$, and $\overrightarrow{\mathrm{ext}}(3,n)\geq 2n$ for all possible $n$, where equality holds if and only if $n$ is odd and $n\geq 3$. As a main result we prove that if $n, k$ and $p$ are integers with $n=k+p$ and $2\leq p \leq k-1$, then $\overrightarrow{\mathrm{ext}}(k,n)=2({\binom{n}{2}} - (p^2+1))$, and we give an exact characterisation of $k$-critical digraphs for which equality holds. This generalizes a result about critical graphs obtained in 1963 by Tibor Gallai.

A new representation is proposed for functions in a Sobolev space with dominating mixed smoothness on an $N$-dimensional hyperrectangle. In particular, it is shown that these functions can be expressed in terms of their highest-order mixed derivative, as well as their lower-order derivatives evaluated along suitable boundaries of the domain. The proposed expansion is proven to be invertible, uniquely identifying any function in the Sobolev space with its derivatives and boundary values. Since these boundary values are either finite-dimensional, or exist in the space of square-integrable functions, this offers a bijective relation between the Sobolev space and $L_{2}$. Using this bijection, it is shown how approximation of functions in Sobolev space can be performed in the less restrictive space $L_{2}$, reconstructing such an approximation of the function from an $L_{2}$-optimal projection of its boundary values and highest-order derivative. This approximation method is presented using a basis of Legendre polynomials and a basis of step functions, and results using both bases are demonstrated to exhibit better convergence behavior than a direct projection approach for two numerical examples.

We show a fully dynamic algorithm for maintaining $(1+\epsilon)$-approximate \emph{size} of maximum matching of the graph with $n$ vertices and $m$ edges using $m^{0.5-\Omega_{\epsilon}(1)}$ update time. This is the first polynomial improvement over the long-standing $O(n)$ update time, which can be trivially obtained by periodic recomputation. Thus, we resolve the value version of a major open question of the dynamic graph algorithms literature (see, e.g., [Gupta and Peng FOCS'13], [Bernstein and Stein SODA'16],[Behnezhad and Khanna SODA'22]). Our key technical component is the first sublinear algorithm for $(1,\epsilon n)$-approximate maximum matching with sublinear running time on dense graphs. All previous algorithms suffered a multiplicative approximation factor of at least $1.499$ or assumed that the graph has a very small maximum degree.

We study the problem of testing $C_k$-freeness ($k$-cycle-freeness) for fixed constant $k > 3$ in graphs with bounded arboricity (but unbounded degrees). In particular, we are interested in one-sided error algorithms, so that they must detect a copy of $C_k$ with high constant probability when the graph is $\epsilon$-far from $C_k$-free. We next state our results for constant arboricity and constant $\epsilon$ with a focus on the dependence on the number of graph vertices, $n$. The query complexity of all our algorithms grows polynomially with $1/\epsilon$. (1) As opposed to the case of $k=3$, where the complexity of testing $C_3$-freeness grows with the arboricity of the graph but not with the size of the graph (Levi, ICALP 2021) this is no longer the case already for $k=4$. We show that $\Omega(n^{1/4})$ queries are necessary for testing $C_4$-freeness, and that $\widetilde{O}(n^{1/4})$ are sufficient. The same bounds hold for $C_5$. (2) For every fixed $k \geq 6$, any one-sided error algorithm for testing $C_k$-freeness must perform $\Omega(n^{1/3})$ queries. (3) For $k=6$ we give a testing algorithm whose query complexity is $\widetilde{O}(n^{1/2})$. (4) For any fixed $k$, the query complexity of testing $C_k$-freeness is upper bounded by ${O}(n^{1-1/\lfloor k/2\rfloor})$. Our $\Omega(n^{1/4})$ lower bound for testing $C_4$-freeness in constant arboricity graphs provides a negative answer to an open problem posed by (Goldreich, 2021).

The random $k$-XORSAT problem is a random constraint satisfaction problem of $n$ Boolean variables and $m=rn$ clauses, which a random instance can be expressed as a $G\mathbb{F}(2)$ linear system of the form $Ax=b$, where $A$ is a random $m \times n$ matrix with $k$ ones per row, and $b$ is a random vector. It is known that there exist two distinct thresholds $r_{core}(k) < r_{sat}(k)$ such that as $n \rightarrow \infty$ for $r < r_{sat}(k)$ the random instance has solutions with high probability, while for $r_{core} < r < r_{sat}(k)$ the solution space shatters into an exponential number of clusters. Sequential local algorithms are a natural class of algorithms which assign values to variables one by one iteratively. In each iteration, the algorithm runs some heuristics, called local rules, to decide the value assigned, based on the local neighborhood of the selected variables under the factor graph representation of the instance. We prove that for any $r > r_{core}(k)$ the sequential local algorithms with certain local rules fail to solve the random $k$-XORSAT with high probability. They include (1) the algorithm using the Unit Clause Propagation as local rule for $k \ge 9$, and (2) the algorithms using any local rule that can calculate the exact marginal probabilities of variables in instances with factor graphs that are trees, for $k\ge 13$. The well-known Belief Propagation and Survey Propagation are included in (2). Meanwhile, the best known linear-time algorithm succeeds with high probability for $r < r_{core}(k)$. Our results support the intuition that $r_{core}(k)$ is the sharp threshold for the existence of a linear-time algorithm for random $k$-XORSAT.

We present polylogarithmic approximation algorithms for variants of the Shortest Path, Group Steiner Tree, and Group ATSP problems with vector costs. In these problems, each edge e has a non-negative vector cost $c_e \in \mathbb{R}^{\ell}_{\ge 0}$. For a feasible solution - a path, subtree, or tour (respectively) - we find the total vector cost of all the edges in the solution and then compute the $\ell_p$-norm of the obtained cost vector (we assume that $p \ge 1$ is an integer). Our algorithms for series-parallel graphs run in polynomial time and those for arbitrary graphs run in quasi-polynomial time. To obtain our results, we introduce and use new flow-based Sum-of-Squares relaxations. We also obtain a number of hardness results.

The class of $\mathsf{Ga}$lled-$\mathsf{T}$ree $\mathsf{Ex}$plainable ($\mathsf{GaTEx}$) graphs has recently been discovered as a natural generalization of cographs. Cographs are precisely those graphs that can be uniquely represented by a rooted tree where the leaves correspond to the vertices of the graph. As a generalization, $\mathsf{GaTEx}$ graphs are precisely those that can be uniquely represented by a particular rooted acyclic network, called a galled-tree. This paper explores the use of galled-trees to solve combinatorial problems on $\mathsf{GaTEx}$ graphs that are, in general, NP-hard. We demonstrate that finding a maximum clique, an optimal vertex coloring, a perfect order, as well as a maximum independent set in $\mathsf{GaTEx}$ graphs can be efficiently done in linear time. The key idea behind the linear-time algorithms is to utilize the galled-trees that explain the $\mathsf{GaTEx}$ graphs as a guide for computing the respective cliques, colorings, perfect orders, or independent sets.

We investigate the statistical behavior of gradient descent iterates with dropout in the linear regression model. In particular, non-asymptotic bounds for the convergence of expectations and covariance matrices of the iterates are derived. The results shed more light on the widely cited connection between dropout and l2-regularization in the linear model. We indicate a more subtle relationship, owing to interactions between the gradient descent dynamics and the additional randomness induced by dropout. Further, we study a simplified variant of dropout which does not have a regularizing effect and converges to the least squares estimator

We give a poly-time algorithm for the $k$-edge-connected spanning subgraph ($k$-ECSS) problem that returns a solution of cost no greater than the cheapest $(k+10)$-ECSS on the same graph. Our approach enhances the iterative relaxation framework with a new ingredient, which we call ghost values, that allows for high sparsity in intermediate problems. Our guarantees improve upon the best-known approximation factor of $2$ for $k$-ECSS whenever the optimal value of $(k+10)$-ECSS is close to that of $k$-ECSS. This is a property that holds for the closely related problem $k$-edge-connected spanning multi-subgraph ($k$-ECSM), which is identical to $k$-ECSS except edges can be selected multiple times at the same cost. As a consequence, we obtain a $\left(1+O\left(\frac{1}{k}\right)\right)$-approximation algorithm for $k$-ECSM, which resolves a conjecture of Pritchard and improves upon a recent $\left(1+O\left(\frac{1}{\sqrt{k}}\right)\right)$-approximation algorithm of Karlin, Klein, Oveis Gharan, and Zhang. Moreover, we present a matching lower bound for $k$-ECSM, showing that our approximation ratio is tight up to the constant factor in $O\left(\frac{1}{k}\right)$, unless $P=NP$.

We consider the distributed complexity of the (degree+1)-list coloring problem, in which each node $u$ of degree $d(u)$ is assigned a palette of $d(u)+1$ colors, and the goal is to find a proper coloring using these color palettes. The (degree+1)-list coloring problem is a natural generalization of the classical $(\Delta+1)$-coloring and $(\Delta+1)$-list coloring problems, both being benchmark problems extensively studied in distributed and parallel computing. In this paper we settle the complexity of the (degree+1)-list coloring problem in the Congested Clique model by showing that it can be solved deterministically in a constant number of rounds.