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

This is a simplification of a previous version of this ArXiv note. We present an example of a function $f$ from $\{-1,1\}^n$ to the unit sphere in $\mathbb{C}$ with influence bounded by $1$ and entropy of $|\hat f|^2$ larger than $\frac12\log n$.

The Cayley distance between two permutations $\pi, \sigma \in S_n$ is the minimum number of \textit{transpositions} required to obtain the permutation $\sigma$ from $\pi$. When we only allow adjacent transpositions, the minimum number of such transpositions to obtain $\sigma$ from $\pi$ is referred to the Kendall $\tau$-distance. A set $C$ of permutation words of length $n$ is called a $t$-Cayley permutation code if every pair of distinct permutations in $C$ has Cayley distance greater than $t$. A $t$-Kendall permutation code is defined similarly. Let $C(n,t)$ and $K(n,t)$ be the maximum size of a $t$-Cayley and a $t$-Kendall permutation code of length $n$, respectively. In this paper, we improve the Gilbert-Varshamov bound asymptotically by a factor $\log(n)$, namely \[ C(n,t) \geq \Omega_t\left(\frac{n!\log n}{n^{2t}}\right) \text{ and } K(n,t) \geq \Omega_t\left(\frac{n! \log n}{n^t}\right).\] Our proof is based on graph theory techniques.

We investigate inexact proximity operators for weakly convex functions. To this aim, we derive sum rules for proximal {\epsilon}-subdifferentials, by incorporating the moduli of weak convexity of the functions into the respective formulas. This allows us to investigate inexact proximity operators for weakly convex functions in terms of proximal {\epsilon}-subdifferentials.

We derive eigenvalue bounds for the $t$-distance chromatic number of a graph, which is a generalization of the classical chromatic number. We apply such bounds to hypercube graphs, providing alternative spectral proofs for results by Ngo, Du and Graham [Inf. Process. Lett., 2002], and improving their bound for several instances. We also apply the eigenvalue bounds to Lee graphs, extending results by Kim and Kim [Discrete Appl. Math., 2011]. Finally, we provide a complete characterization for the existence of perfect Lee codes of minimum distance $3$. In order to prove our results, we use a mix of spectral and number theory tools. Our results, which provide the first application of spectral methods to Lee codes, illustrate that such methods succeed to capture the nature of the Lee metric.

Consider a connected graph $G$ and let $T$ be a spanning tree of $G$. Every edge $e \in G-T$ induces a cycle in $T \cup \{e\}$. The intersection of two distinct such cycles is the set of edges of $T$ that belong to both cycles. The MSTCI problem consists in finding a spanning tree that has the least number of such non-empty intersections and the instersection number is the number of non-empty intersections of a solution. In this article we consider three aspects of the problem in a general context (i.e. for arbitrary connected graphs). The first presents two lower bounds of the intersection number. The second compares the intersection number of graphs that differ in one edge. The last is an attempt to generalize a recent result for graphs with a universal vertex.

At STOC 2002, Eiter, Gottlob, and Makino presented a technique called ordered generation that yields an $n^{O(d)}$-delay algorithm listing all minimal transversals of an $n$-vertex hypergraph of degeneracy $d$. Recently at IWOCA 2019, Conte, Kant\'e, Marino, and Uno asked whether this XP-delay algorithm parameterized by $d$ could be made FPT-delay for a weaker notion of degeneracy, or even parameterized by the maximum degree $\Delta$, i.e., whether it can be turned into an algorithm with delay $f(\Delta)\cdot n^{O(1)}$ for some computable function $f$. Moreover, and as a first step toward answering that question, they note that they could not achieve these time bounds even for the particular case of minimal dominating sets enumeration. In this paper, using ordered generation, we show that an FPT-delay algorithm can be devised for minimal transversals enumeration parameterized by the degeneracy and dimension, giving a positive and more general answer to the latter question.

This paper presents new upper bounds on the rate of linear $k$-hash codes in $\mathbb{F}_q^n$, $q\geq k$, that is, codes with the property that any $k$ distinct codewords are all simultaneously distinct in at least one coordinate.

We consider an observed subcritical Galton Watson process $\{Y_n,\ n\in \mathbb{Z} \}$ with correlated stationary immigration process $\{\epsilon_n,\ n\in \mathbb{Z} \}$. Two situations are presented. The first one is when $\mbox{Cov}(\epsilon_0,\epsilon_k)=0$ for $k$ larger than some $k_0$: a consistent estimator for the reproduction and mean immigration rates is given, and a central limit theorem is proved. The second one is when $\{\epsilon_n,\ n\in \mathbb{Z} \}$ has general correlation structure: under mixing assumptions, we exhibit an estimator for the the logarithm of the reproduction rate and we prove that it converges in quadratic mean with explicit speed. In addition, when the mixing coefficients decrease fast enough, we provide and prove a two terms expansion for the estimator. Numerical illustrations are provided.

We describe a new dependent-rounding algorithmic framework for bipartite graphs. Given a fractional assignment $\vec x$ of values to edges of graph $G = (U \cup V, E)$, the algorithms return an integral solution $\vec X$ such that each right-node $v \in V$ has at most one neighboring edge $f$ with $X_f = 1$, and where the variables $X_e$ also satisfy broad nonpositive-correlation properties. In particular, for any edges $e_1, e_2$ sharing a left-node $u \in U$, the variables $X_{e_1}, X_{e_2}$ have strong negative-correlation properties, i.e. the expectation of $X_{e_1} X_{e_2}$ is significantly below $x_{e_1} x_{e_2}$. This algorithm is based on generating negatively-correlated Exponential random variables and using them in a contention-resolution scheme inspired by an algorithm Im & Shadloo (2020). Our algorithm gives stronger and much more flexible negative correlation properties. Dependent rounding schemes with negative correlation properties have been used for approximation algorithms for job-scheduling on unrelated machines to minimize weighted completion times (Bansal, Srinivasan, & Svensson (2021), Im & Shadloo (2020), Im & Li (2023)). Using our new dependent-rounding algorithm, among other improvements, we obtain a $1.398$-approximation for this problem. This significantly improves over the prior $1.45$-approximation ratio of Im & Li (2023).

We consider the problem of counting 4-cycles ($C_4$) in an undirected graph $G$ of $n$ vertices and $m$ edges (in bipartite graphs, 4-cycles are also often referred to as $\textit{butterflies}$). There have been a number of previous algorithms for this problem based on sorting the graph by degree and using randomized hash tables. These are appealing in theory due to compact storage and fast access on average. But, the performance of hash tables can degrade unpredictably and are also vulnerable to adversarial input. We develop a new simpler algorithm for counting $C_4$ requiring $O(m\bar\delta(G))$ time and $O(n)$ space, where $\bar \delta(G) \leq O(\sqrt{m})$ is the $\textit{average degeneracy}$ parameter introduced by Burkhardt, Faber & Harris (2020). It has several practical improvements over previous algorithms; for example, it is fully deterministic, does not require any sorting of the input graph, and uses only addition and array access in its inner loops. To the best of our knowledge, all previous efficient algorithms for $C_4$ counting have required $\Omega(m)$ space in addition to storing the input graph. Our algorithm is very simple and easily adapted to count 4-cycles incident to each vertex and edge. Empirical tests demonstrate that our array-based approach is $4\times$ -- $7\times$ faster on average compared to popular hash table implementations.