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

Given a graph $G$ that is modified by a sequence of edge insertions and deletions, we study the Maximum $k$-Edge Coloring problem Having access to $k$ colors, how can we color as many edges of $G$ as possible such that no two adjacent edges share the same color? While this problem is different from simply maintaining a $b$-matching with $b=k$, the two problems are closely related: a maximum $k$-matching always contains a $\frac{k+1}k$-approximate maximum $k$-edge coloring. However, maximum $b$-matching can be solved efficiently in the static setting, whereas the Maximum $k$-Edge Coloring problem is NP-hard and even APX-hard for $k \ge 2$. We present new results on both problems: For $b$-matching, we show a new integrality gap result and for the case where $b$ is a constant, we adapt Wajc's matching sparsification scheme~[STOC20]. Using these as basis, we give three new algorithms for the dynamic Maximum $k$-Edge Coloring problem: Our MatchO algorithm builds on the dynamic $(2+\epsilon)$-approximation algorithm of Bhattacharya, Gupta, and Mohan~[ESA17] for $b$-matching and achieves a $(2+\epsilon)\frac{k+1} k$-approximation in $O(poly(\log n, \epsilon^{-1}))$ update time against an oblivious adversary. Our MatchA algorithm builds on the dynamic $8$-approximation algorithm by Bhattacharya, Henzinger, and Italiano~[SODA15] for fractional $b$-matching and achieves a $(8+\epsilon)\frac{3k+3}{3k-1}$-approximation in $O(poly(\log n, \epsilon^{-1}))$ update time against an adaptive adversary. Moreover, our reductions use the dynamic $b$-matching algorithm as a black box, so any future improvement in the approximation ratio for dynamic $b$-matching will automatically translate into a better approximation ratio for our algorithms. Finally, we present a greedy algorithm that runs in $O(\Delta+k)$ update time, while guaranteeing a $2.16$~approximation factor.

Simplicial complexes are a convenient semantic primitive to reason about processes (agents) communicating with each other in synchronous and asynchronous computation. Impure simplicial complexes distinguish active processes from crashed ones, in other words, agents that are alive from agents that are dead. In order to rule out that dead agents reason about themselves and about other agents, three-valued epistemic semantics have been proposed where, in addition to the usual values true and false, the third value stands for undefined: the knowledge of dead agents is undefined and so are the propositional variables describing their local state. Other semantics for impure complexes are two-valued where a dead agent knows everything. Different choices in designing a semantics produce different three-valued semantics, and also different two-valued semantics. In this work, we categorize the available choices by discounting the bad ones, identifying the equivalent ones, and connecting the non-equivalent ones via a translation. The main result of the paper is identifying the main relevant distinction to be the number of truth values and bridging this difference by means of a novel embedding from three- into two-valued semantics. This translation also enables us to highlight quite fundamental modeling differences underpinning various two- and three-valued approaches in this area of combinatorial topology. In particular, pure complexes can be defined as those invariant under the translation.

The learning with errors problem (LWE) is one of the most important building blocks for post-quantum cryptography. To better understand the quantum hardness of LWE, it is crucial to explore quantum variants of LWE, show quantum algorithms for those variants, or prove they are as hard as standard LWE. To this end, Chen, Liu, and Zhandry [Eurocrypt 2022] define the $\sf{S|LWE\rangle}$ problem, which encodes the error of LWE samples into quantum amplitudes. They then show efficient quantum algorithms for $\sf{S|LWE\rangle}$ with a few interesting amplitudes. However, the hardness of the most interesting amplitude, Gaussian, was not addressed by Chen et al., or only known for some restricted settings (for example, when the number of $\sf{S|LWE\rangle}$ samples is very small, it is well known that $\sf{S|LWE\rangle}$ is as hard as standard LWE). In this paper, we show new hardness and algorithms for $\sf{S|LWE\rangle}$ with Gaussian and other amplitudes. Our main results are 1. There exist quantum reductions from standard LWE or worst-case GapSVP to $\sf{S|LWE\rangle}$ with Gaussian amplitude with unknown phase, and arbitrarily many $\sf{S|LWE\rangle}$ samples. 2. There is a $2^{\widetilde{O}(\sqrt{n})}$-time algorithm for $\sf{S|LWE\rangle}$ with Gaussian amplitude with known phase, given $2^{\widetilde{O}(\sqrt{n})}$ many quantum samples. The algorithm is modified from Kuperberg's sieve, and in fact works for more general amplitudes as long as the amplitudes and phases are completely known. One way of interpreting our result is: to show a sub-exponential time quantum algorithm for standard LWE, all we need is to handle phases in $\sf{S|LWE\rangle}$ amplitudes better, either in the algorithm or the reduction.

The Subset Feedback Vertex Set problem (SFVS), to delete $k$ vertices from a given graph such that any vertex in a vertex subset (called a terminal set) is not in a cycle in the remaining graph, generalizes the famous Feedback Vertex Set problem and Multiway Cut problem. SFVS remains NP-hard even in split and chordal graphs, and SFVS in Chordal Graphs (SFVS-C) can be considered as an implicit 3-Hitting Set problem. However, it is not easy to solve SFVS-C faster than 3-Hitting Set. In 2019, Philip, Rajan, Saurabh, and Tale (Algorithmica 2019) proved that SFVS-C can be solved in $\mathcal{O}^{*}(2^{k})$ time, slightly improving the best result $\mathcal{O}^{*}(2.076^{k})$ for 3-Hitting Set. In this paper, we break the "$2^{k}$-barrier" for SFVS-C by giving an $\mathcal{O}^{*}(1.820^{k})$-time algorithm. Our algorithm uses reduction and branching rules based on the Dulmage-Mendelsohn decomposition and a divide-and-conquer method.

Omnidirectional camera is a cost-effective and information-rich sensor highly suitable for many marine applications and the ocean scientific community, encompassing several domains such as augmented reality, mapping, motion estimation, visual surveillance, and simultaneous localization and mapping. However, designing and constructing such a high-quality 360$^{\circ}$ real-time streaming camera system for underwater applications is a challenging problem due to the technical complexity in several aspects including sensor resolution, wide field of view, power supply, optical design, system calibration, and overheating management. This paper presents a novel and comprehensive system that addresses the complexities associated with the design, construction, and implementation of a fully functional 360$^{\circ}$ real-time streaming camera system specifically tailored for underwater environments. Our proposed system, UWA360CAM, can stream video in real time, operate in 24/7, and capture 360$^{\circ}$ underwater panorama images. Notably, our work is the pioneering effort in providing a detailed and replicable account of this system. The experiments provide a comprehensive analysis of our proposed system.

An important family of quantum codes is the quantum maximum-distance-separable (MDS) codes. In this paper, we construct some new classes of quantum MDS codes by generalized Reed-Solomon (GRS) codes and Hermitian construction. In addition, the length $n$ of most of the quantum MDS codes we constructed satisfies $n\equiv 0,1($mod$\,\frac{q\pm1}{2})$, which is different from previously known code lengths. At the same time, the quantum MDS codes we construct have large minimum distances that are greater than $q/2+1$.

We present a simple yet accurate method to compute the adjoint double layer potential, which is used to solve the Neumann boundary value problem for Laplace's equation in three dimensions. An expansion in curvilinear coordinates leads us to modify the expression for the adjoint double layer so that the singularity is reduced when evaluating the integral on the surface. We then regularize the Green's function, with a radial parameter $\delta$. We show that a natural regularization has error $O(\delta^3)$, and a simple modification improves the error to $O(\delta^5)$. The integral is evaluated numerically without the need of special coordinates. We use this treatment of the adjoint double layer to solve the classical integral equation for the interior Neumann problem and evaluate the solution on the boundary. Choosing $\delta = ch^{4/5}$, we find about $O(h^4)$ convergence in our examples, where $h$ is the spacing in a background grid.

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.

Generalization to out-of-distribution (OOD) data is a critical challenge in machine learning. Ensemble-based methods, like weight space ensembles that interpolate model parameters, have been shown to achieve superior OOD performance. However, the underlying mechanism for their effectiveness remains unclear. In this study, we closely examine WiSE-FT, a popular weight space ensemble method that interpolates between a pre-trained and a fine-tuned model. We observe an unexpected phenomenon, in which WiSE-FT successfully corrects many cases where each individual model makes incorrect predictions, which contributes significantly to its OOD effectiveness. To gain further insights, we conduct theoretical analysis in a multi-class setting with a large number of spurious features. Our analysis predicts the above phenomenon and it further shows that ensemble-based models reduce prediction errors in the OOD settings by utilizing a more diverse set of spurious features. Contrary to the conventional wisdom that focuses on learning invariant features for better OOD performance, our findings suggest that incorporating a large number of diverse spurious features weakens their individual contributions, leading to improved overall OOD generalization performance. Empirically we demonstrate the effectiveness of utilizing diverse spurious features on a MultiColorMNIST dataset, and our experimental results are consistent with the theoretical analysis. Building upon the new theoretical insights into the efficacy of ensemble methods, we further identify an issue of WiSE-FT caused by the overconfidence of fine-tuned models in OOD situations. This overconfidence magnifies the fine-tuned model's incorrect prediction, leading to deteriorated OOD ensemble performance. To remedy this problem, we propose a novel method called BAlaNced averaGing (BANG), which significantly enhances the OOD performance of WiSE-FT.

Graph convolution networks (GCN) are increasingly popular in many applications, yet remain notoriously hard to train over large graph datasets. They need to compute node representations recursively from their neighbors. Current GCN training algorithms suffer from either high computational costs that grow exponentially with the number of layers, or high memory usage for loading the entire graph and node embeddings. In this paper, we propose a novel efficient layer-wise training framework for GCN (L-GCN), that disentangles feature aggregation and feature transformation during training, hence greatly reducing time and memory complexities. We present theoretical analysis for L-GCN under the graph isomorphism framework, that L-GCN leads to as powerful GCNs as the more costly conventional training algorithm does, under mild conditions. We further propose L^2-GCN, which learns a controller for each layer that can automatically adjust the training epochs per layer in L-GCN. Experiments show that L-GCN is faster than state-of-the-arts by at least an order of magnitude, with a consistent of memory usage not dependent on dataset size, while maintaining comparable prediction performance. With the learned controller, L^2-GCN can further cut the training time in half. Our codes are available at //github.com/Shen-Lab/L2-GCN.