We present an efficient labeling scheme for answering connectivity queries in graphs subject to a specified number of vertex failures. Our first result is a randomized construction of a labeling function that assigns vertices $O(f^3\log^5 n)$-bit labels, such that given the labels of $F\cup \{s,t\}$ where $|F|\leq f$, we can correctly report, with probability $1-1/\mathrm{poly}(n)$, whether $s$ and $t$ are connected in $G-F$. However, it is possible that over all $n^{O(f)}$ distinct queries, some are answered incorrectly. Our second result is a deterministic labeling function that produces $O(f^7 \log^{13} n)$-bit labels such that all connectivity queries are answered correctly. Both upper bounds are polynomially off from an $\Omega(f)$-bit lower bound. Our labeling schemes are based on a new low degree decomposition that improves the Duan-Pettie decomposition, and facilitates its distributed representation. We make heavy use of randomization to construct hitting sets, fault-tolerant graph sparsifiers, and in constructing linear sketches. Our derandomized labeling scheme combines a variety of techniques: the method of conditional expectations, hit-miss hash families, and $\epsilon$-nets for axis-aligned rectangles. The prior labeling scheme of Parter and Petruschka shows that $f=1$ and $f=2$ vertex faults can be handled with $O(\log n)$- and $O(\log^3 n)$-bit labels, respectively, and for $f>2$ vertex faults, $\tilde{O}(n^{1-1/2^{f-2}})$-bit labels suffice.
相關內容
Qini curves have emerged as an attractive and popular approach for evaluating the benefit of data-driven targeting rules for treatment allocation. We propose a generalization of the Qini curve to multiple costly treatment arms, that quantifies the value of optimally selecting among both units and treatment arms at different budget levels. We develop an efficient algorithm for computing these curves and propose bootstrap-based confidence intervals that are exact in large samples for any point on the curve. These confidence intervals can be used to conduct hypothesis tests comparing the value of treatment targeting using an optimal combination of arms with using just a subset of arms, or with a non-targeting assignment rule ignoring covariates, at different budget levels. We demonstrate the statistical performance in a simulation experiment and an application to treatment targeting for election turnout.
Blockchain technology is developing using in reliable applications which can be designed to achieve decentralization and trustless. Based on the open network innovation theory, this paper proposes a technical intermediary management idea based on blockchain technology to improve the efficiency of technology intermediaries, providing accurate, reliable information and cutting cost for the market. This study demonstrates the advantage of blockchain to technology intermediaries. First, on a specific level, it can provide openness, transparency, decentralization and anonymity services. Second, the current industrial innovation elements are analyzed. blockchain improve the efficiency of technology intermediary, prevent risks and to make up for the shortcomings of traditional intermediaries. It has revolutionized the traditional technology intermediary. As this happens, it can revolutionize traditional technology intermediaries.
The next generation of wireless communication technology is anticipated to address the communication reliability challenges encountered in high-speed mobile communication scenarios. An Orthogonal Time Frequency Space (OTFS) system has been introduced as a solution that effectively mitigates these issues. However, OTFS is associated with relatively high pilot overhead and multiuser multiplexing overhead. In response to these concerns within the OTFS framework, a novel modulation technology known as Affine Frequency Division Multiplexing (AFDM) which is based on the discrete affine Fourier transform has emerged. AFDM effectively resolves the challenges by achieving full diversity through parameter adjustments aligned with the channel's delay-Doppler profile. Consequently, AFDM is capable of achieving performance levels comparable to OTFS. As the research on AFDM detection is currently limited, we present a low-complexity yet efficient message passing (MP) algorithm. This algorithm handles joint interference cancellation and detection while capitalizing on the inherent sparsity of the channel. Based on simulation results, the MP detection algorithm outperforms Minimum Mean Square Error (MMSE) and Maximal Ratio Combining (MRC) detection techniques.
Many theories of scientific and technological progress imagine science as an iterative, developmental process periodically interrupted by innovations which disrupt and restructure the status quo. Due to the immense societal value created by these disruptive scientific and technological innovations, accurately operationalizing this perspective into quantifiable terms represents a key challenge for researchers seeking to understand the history and mechanisms underlying scientific and technological progress. Researchers have recently proposed a number of quantitative measures that seek to quantify the extent to which works in science and technology are disruptive with respect to their scientific context. While these disruption measures show promise in their ability to quantify potentially disruptive works of science and technology, their definitions are bespoke to the science of science and lack a broader theoretical framework, obscuring their interrelationships and limiting their adoption within broader network science paradigms. We propose a mathematical framework for conceptualizing and measuring disruptive scientific contributions within citation networks through the lens of network centrality, and formally relate the CD Index disruption measure and its variants to betweenness centrality. By reinterpreting disruption through the lens of centrality, we unify a number of existing citation-based disruption measures while simultaneously providing natural generalizations which enjoy empirical and computational efficiencies. We validate these theoretical observations by computing a variety of disruption measures on real citation data and find that computing these centrality-based disruption measures over ego networks of increasing radius results in better discernment of award-winning scientific innovations relative to conventional disruption metrics which rely on local citation context alone.
Humans perceive the world by concurrently processing and fusing high-dimensional inputs from multiple modalities such as vision and audio. Machine perception models, in stark contrast, are typically modality-specific and optimised for unimodal benchmarks, and hence late-stage fusion of final representations or predictions from each modality (`late-fusion') is still a dominant paradigm for multimodal video classification. Instead, we introduce a novel transformer based architecture that uses `fusion bottlenecks' for modality fusion at multiple layers. Compared to traditional pairwise self-attention, our model forces information between different modalities to pass through a small number of bottleneck latents, requiring the model to collate and condense the most relevant information in each modality and only share what is necessary. We find that such a strategy improves fusion performance, at the same time reducing computational cost. We conduct thorough ablation studies, and achieve state-of-the-art results on multiple audio-visual classification benchmarks including Audioset, Epic-Kitchens and VGGSound. All code and models will be released.
Recent advances in maximizing mutual information (MI) between the source and target have demonstrated its effectiveness in text generation. However, previous works paid little attention to modeling the backward network of MI (i.e., dependency from the target to the source), which is crucial to the tightness of the variational information maximization lower bound. In this paper, we propose Adversarial Mutual Information (AMI): a text generation framework which is formed as a novel saddle point (min-max) optimization aiming to identify joint interactions between the source and target. Within this framework, the forward and backward networks are able to iteratively promote or demote each other's generated instances by comparing the real and synthetic data distributions. We also develop a latent noise sampling strategy that leverages random variations at the high-level semantic space to enhance the long term dependency in the generation process. Extensive experiments based on different text generation tasks demonstrate that the proposed AMI framework can significantly outperform several strong baselines, and we also show that AMI has potential to lead to a tighter lower bound of maximum mutual information for the variational information maximization problem.
Embedding entities and relations into a continuous multi-dimensional vector space have become the dominant method for knowledge graph embedding in representation learning. However, most existing models ignore to represent hierarchical knowledge, such as the similarities and dissimilarities of entities in one domain. We proposed to learn a Domain Representations over existing knowledge graph embedding models, such that entities that have similar attributes are organized into the same domain. Such hierarchical knowledge of domains can give further evidence in link prediction. Experimental results show that domain embeddings give a significant improvement over the most recent state-of-art baseline knowledge graph embedding models.
Benefit from the quick development of deep learning techniques, salient object detection has achieved remarkable progresses recently. However, there still exists following two major challenges that hinder its application in embedded devices, low resolution output and heavy model weight. To this end, this paper presents an accurate yet compact deep network for efficient salient object detection. More specifically, given a coarse saliency prediction in the deepest layer, we first employ residual learning to learn side-output residual features for saliency refinement, which can be achieved with very limited convolutional parameters while keep accuracy. Secondly, we further propose reverse attention to guide such side-output residual learning in a top-down manner. By erasing the current predicted salient regions from side-output features, the network can eventually explore the missing object parts and details which results in high resolution and accuracy. Experiments on six benchmark datasets demonstrate that the proposed approach compares favorably against state-of-the-art methods, and with advantages in terms of simplicity, efficiency (45 FPS) and model size (81 MB).
Adversarial attacks to image classification systems present challenges to convolutional networks and opportunities for understanding them. This study suggests that adversarial perturbations on images lead to noise in the features constructed by these networks. Motivated by this observation, we develop new network architectures that increase adversarial robustness by performing feature denoising. Specifically, our networks contain blocks that denoise the features using non-local means or other filters; the entire networks are trained end-to-end. When combined with adversarial training, our feature denoising networks substantially improve the state-of-the-art in adversarial robustness in both white-box and black-box attack settings. On ImageNet, under 10-iteration PGD white-box attacks where prior art has 27.9% accuracy, our method achieves 55.7%; even under extreme 2000-iteration PGD white-box attacks, our method secures 42.6% accuracy. A network based on our method was ranked first in Competition on Adversarial Attacks and Defenses (CAAD) 2018 --- it achieved 50.6% classification accuracy on a secret, ImageNet-like test dataset against 48 unknown attackers, surpassing the runner-up approach by ~10%. Code and models will be made publicly available.
Deep neural networks (DNNs) have been found to be vulnerable to adversarial examples resulting from adding small-magnitude perturbations to inputs. Such adversarial examples can mislead DNNs to produce adversary-selected results. Different attack strategies have been proposed to generate adversarial examples, but how to produce them with high perceptual quality and more efficiently requires more research efforts. In this paper, we propose AdvGAN to generate adversarial examples with generative adversarial networks (GANs), which can learn and approximate the distribution of original instances. For AdvGAN, once the generator is trained, it can generate adversarial perturbations efficiently for any instance, so as to potentially accelerate adversarial training as defenses. We apply AdvGAN in both semi-whitebox and black-box attack settings. In semi-whitebox attacks, there is no need to access the original target model after the generator is trained, in contrast to traditional white-box attacks. In black-box attacks, we dynamically train a distilled model for the black-box model and optimize the generator accordingly. Adversarial examples generated by AdvGAN on different target models have high attack success rate under state-of-the-art defenses compared to other attacks. Our attack has placed the first with 92.76% accuracy on a public MNIST black-box attack challenge.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191