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

Given a vector dataset $\mathcal{X}$ and a query vector $\vec{x}_q$, graph-based Approximate Nearest Neighbor Search (ANNS) aims to build a graph index $G$ and approximately return vectors with minimum distances to $\vec{x}_q$ by searching over $G$. The main drawback of graph-based ANNS is that a graph index would be too large to fit into the memory especially for a large-scale $\mathcal{X}$. To solve this, a Product Quantization (PQ)-based hybrid method called DiskANN is proposed to store a low-dimensional PQ index in memory and retain a graph index in SSD, thus reducing memory overhead while ensuring a high search accuracy. However, it suffers from two I/O issues that significantly affect the overall efficiency: (1) long routing path from an entry vertex to the query's neighborhood that results in large number of I/O requests and (2) redundant I/O requests during the routing process. We propose an optimized DiskANN++ to overcome above issues. Specifically, for the first issue, we present a query-sensitive entry vertex selection strategy to replace DiskANN's static graph-central entry vertex by a dynamically determined entry vertex that is close to the query. For the second I/O issue, we present an isomorphic mapping on DiskANN's graph index to optimize the SSD layout and propose an asynchronously optimized Pagesearch based on the optimized SSD layout as an alternative to DiskANN's beamsearch. Comprehensive experimental studies on eight real-world datasets demonstrate our DiskANN++'s superiority on efficiency. We achieve a notable 1.5 X to 2.2 X improvement on QPS compared to DiskANN, given the same accuracy constraint.

We investigate the relation between $\delta$ and $\epsilon$ required for obtaining a $(1+\delta)$-approximation in time $N^{2-\epsilon}$ for closest pair problems under various distance metrics, and for other related problems in fine-grained complexity. Specifically, our main result shows that if it is impossible to (exactly) solve the (bichromatic) inner product (IP) problem for vectors of dimension $c \log N$ in time $N^{2-\epsilon}$, then there is no $(1+\delta)$-approximation algorithm for (bichromatic) Euclidean Closest Pair running in time $N^{2-2\epsilon}$, where $\delta \approx (\epsilon/c)^2$ (where $\approx$ hides $\polylog$ factors). This improves on the prior result due to Chen and Williams (SODA 2019) which gave a smaller polynomial dependence of $\delta$ on $\epsilon$, on the order of $\delta \approx (\epsilon/c)^6$. Our result implies in turn that no $(1+\delta)$-approximation algorithm exists for Euclidean closest pair for $\delta \approx \epsilon^4$, unless an algorithmic improvement for IP is obtained. This in turn is very close to the approximation guarantee of $\delta \approx \epsilon^3$ for Euclidean closest pair, given by the best known algorithm of Almam, Chan, and Williams (FOCS 2016). By known reductions, a similar result follows for a host of other related problems in fine-grained hardness of approximation. Our reduction combines the hardness of approximation framework of Chen and Williams, together with an MA communication protocol for IP over a small alphabet, that is inspired by the MA protocol of Chen (Theory of Computing, 2020).

I propose Ziv-Zakai-type lower bounds on the Bayesian error for estimating a parameter $\beta:\Theta \to \mathbb R$ when the parameter space $\Theta$ is general and $\beta(\theta)$ need not be a linear function of $\theta$.

We explore a notion of bent sequence attached to the data consisting of an Hadamard matrix of order $n$ defined over the complex $q^{th}$ roots of unity, an eigenvalue of that matrix, and a Galois automorphism from the cyclotomic field of order $q.$ In particular we construct self-dual bent sequences for various $q\le 60$ and lengths $n\le 21.$ Computational construction methods comprise the resolution of polynomial systems by Groebner bases and eigenspace computations. Infinite families can be constructed from regular Hadamard matrices, Bush-type Hadamard matrices, and generalized Boolean bent functions.As an application, we estimate the covering radius of the code attached to that matrix over $\Z_q.$ We derive a lower bound on that quantity for the Chinese Euclidean metric when bent sequences exist. We give the Euclidean distance spectrum, and bound above the covering radius of an attached spherical code, depending on its strength as a spherical design.

The polynomial identity lemma (also called the "Schwartz-Zippel lemma") states that any nonzero polynomial $f(x_1,\ldots, x_n)$ of degree at most $s$ will evaluate to a nonzero value at some point on a grid $S^n \subseteq \mathbb{F}^n$ with $|S| > s$. Thus, there is an explicit hitting set for all $n$-variate degree $s$, size $s$ algebraic circuits of size $(s+1)^n$. In this paper, we prove the following results: - Let $\varepsilon > 0$ be a constant. For a sufficiently large constant $n$ and all $s > n$, if we have an explicit hitting set of size $(s+1)^{n-\varepsilon}$ for the class of $n$-variate degree $s$ polynomials that are computable by algebraic circuits of size $s$, then for all $s$, we have an explicit hitting set of size $s^{\exp \circ \exp (O(\log^\ast s))}$ for $s$-variate circuits of degree $s$ and size $s$. That is, if we can obtain a barely non-trivial exponent compared to the trivial $(s+1)^{n}$ sized hitting set even for constant variate circuits, we can get an almost complete derandomization of PIT. - The above result holds when "circuits" are replaced by "formulas" or "algebraic branching programs". This extends a recent surprising result of Agrawal, Ghosh and Saxena (STOC 2018,PNAS 2019) who proved the same conclusion for the class of algebraic circuits, if the hypothesis provided a hitting set of size at most $(s^{n^{0.5 - \delta}})$ (where $\delta>0$ is any constant). Hence, our work significantly weakens the hypothesis of Agrawal, Ghosh and Saxena to only require a slightly non-trivial saving over the trivial hitting set, and also presents the first such result for algebraic branching programs and formulas.

Given a graph $G=(V,E)$ on $n$ vertices and an assignment of colours to its edges, a set of edges $S \subseteq E$ is said to be rainbow if edges from $S$ have pairwise different colours assigned to them. In this paper, we investigate rainbow spanning trees in randomly coloured random $G_{k-out}$ graphs.

We introduce, motivate and study $\varepsilon$-almost collision-flat (ACFU) universal hash functions $f:\mathcal X\times\mathcal S\to\mathcal A$. Their main property is that the number of collisions in any given value is bounded. Each $\varepsilon$-ACFU hash function is an $\varepsilon$-almost universal (AU) hash function, and every $\varepsilon$-almost strongly universal (ASU) hash function is an $\varepsilon$-ACFU hash function. We study how the size of the seed set $\mathcal S$ depends on $\varepsilon,|\mathcal X|$ and $|\mathcal A|$. Depending on how these parameters are interrelated, seed-minimizing ACFU hash functions are equivalent to mosaics of balanced incomplete block designs (BIBDs) or to duals of mosaics of quasi-symmetric block designs; in a third case, mosaics of transversal designs and nets yield seed-optimal ACFU hash functions, but a full characterization is missing. By either extending $\mathcal S$ or $\mathcal X$, it is possible to obtain an $\varepsilon$-ACFU hash function from an $\varepsilon$-AU hash function or an $\varepsilon$-ASU hash function, generalizing the construction of mosaics of designs from a given resolvable design (Gnilke, Greferath, Pav{\v c}evi\'c, Des. Codes Cryptogr. 86(1)). The concatenation of an ASU and an ACFU hash function again yields an ACFU hash function. Finally, we motivate ACFU hash functions by their applicability in privacy amplification.

In the Maximum Independent Set of Objects problem, we are given an $n$-vertex planar graph $G$ and a family $\mathcal{D}$ of $N$ objects, where each object is a connected subgraph of $G$. The task is to find a subfamily $\mathcal{F} \subseteq \mathcal{D}$ of maximum cardinality that consists of pairwise disjoint objects. This problem is $\mathsf{NP}$-hard and is equivalent to the problem of finding the maximum number of pairwise disjoint polygons in a given family of polygons in the plane. As shown by Adamaszek et al. (J. ACM '19), the problem admits a \emph{quasi-polynomial time approximation scheme} (QPTAS): a $(1-\varepsilon)$-approximation algorithm whose running time is bounded by $2^{\mathrm{poly}(\log(N),1/\epsilon)} \cdot n^{\mathcal{O}(1)}$. Nevertheless, to the best of our knowledge, in the polynomial-time regime only the trivial $\mathcal{O}(N)$-approximation is known for the problem in full generality. In the restricted setting where the objects are pseudolines in the plane, Fox and Pach (SODA '11) gave an $N^{\varepsilon}$-approximation algorithm with running time $N^{2^{\tilde{\mathcal{O}}(1/\varepsilon)}}$, for any $\varepsilon>0$. In this work, we present an $\text{OPT}^{\varepsilon}$-approximation algorithm for the problem that runs in time $N^{\tilde{\mathcal{O}}(1/\varepsilon^2)} n^{\mathcal{O}(1)}$, for any $\varepsilon>0$, thus improving upon the result of Fox and Pach both in terms of generality and in terms of the running time. Our approach combines the methodology of Voronoi separators, introduced by Marx and Pilipczuk (TALG '22), with a new analysis of the approximation factor.

We give a simple and computationally efficient algorithm that, for any constant $\varepsilon>0$, obtains $\varepsilon T$-swap regret within only $T = \mathsf{polylog}(n)$ rounds; this is an exponential improvement compared to the super-linear number of rounds required by the state-of-the-art algorithm, and resolves the main open problem of [Blum and Mansour 2007]. Our algorithm has an exponential dependence on $\varepsilon$, but we prove a new, matching lower bound. Our algorithm for swap regret implies faster convergence to $\varepsilon$-Correlated Equilibrium ($\varepsilon$-CE) in several regimes: For normal form two-player games with $n$ actions, it implies the first uncoupled dynamics that converges to the set of $\varepsilon$-CE in polylogarithmic rounds; a $\mathsf{polylog}(n)$-bit communication protocol for $\varepsilon$-CE in two-player games (resolving an open problem mentioned by [Babichenko-Rubinstein'2017, Goos-Rubinstein'2018, Ganor-CS'2018]; and an $\tilde{O}(n)$-query algorithm for $\varepsilon$-CE (resolving an open problem of [Babichenko'2020] and obtaining the first separation between $\varepsilon$-CE and $\varepsilon$-Nash equilibrium in the query complexity model). For extensive-form games, our algorithm implies a PTAS for $\mathit{normal}$ $\mathit{form}$ $\mathit{correlated}$ $\mathit{equilibria}$, a solution concept often conjectured to be computationally intractable (e.g. [Stengel-Forges'08, Fujii'23]).

We construct a graph with $n$ vertices where the smoothed runtime of the 3-FLIP algorithm for the 3-Opt Local Max-Cut problem can be as large as $2^{\Omega(\sqrt{n})}$. This provides the first example where a local search algorithm for the Max-Cut problem can fail to be efficient in the framework of smoothed analysis. We also give a new construction of graphs where the runtime of the FLIP algorithm for the Local Max-Cut problem is $2^{\Omega(n)}$ for any pivot rule. This graph is much smaller and has a simpler structure than previous constructions.