skip to main content


Title: Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE
Award ID(s):
1740850
NSF-PAR ID:
10181169
Author(s) / Creator(s):
;
Date Published:
Journal Name:
ACM Web Search and Data Mining Conference (WSDM)
Page Range / eLocation ID:
447 to 455
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. The vertex function (Γ) within the Green’s function formalism encapsulates information about all higher-order electron–electron interaction beyond those mediated by density fluctuations. Herein, we present an efficient approach that embeds vertex corrections in the one-shot GW correlation self-energy for isolated and periodic systems. The vertex-corrected self-energy is constructed through the proposed separation–propagation–recombination procedure: the electronic Hilbert space is separated into an active space and its orthogonal complement denoted as the “rest;” the active component is propagated by a space-specific effective Hamiltonian different from the rest. The vertex corrections are introduced by a rescaled time-dependent nonlocal exchange interaction. The direct Γ correction to the self-energy is further updated by adjusting the rescaling factor in a self-consistent post-processing cycle. Our embedding method is tested mainly on donor–acceptor charge-transfer systems. The embedded vertex effects consistently and significantly correct the quasiparticle energies of the gap-edge states. The fundamental gap is generally improved by 1–3 eV upon the one-shot GW approximation. Furthermore, we provide an outlook for applications of (embedded) vertex corrections in calculations of extended solids.

     
    more » « less
  2. We study the stochastic vertex cover problem. In this problem, G = (V, E) is an arbitrary known graph, and G⋆ is an unknown random subgraph of G where each edge e is realized independently with probability p. Edges of G⋆ can only be verified using edge queries. The goal in this problem is to find a minimum vertex cover of G⋆ using a small number of queries. Our main result is designing an algorithm that returns a vertex cover of G⋆ with size at most (3/2+є) times the expected size of the minimum vertex cover, using only O(n/є p) non-adaptive queries. This improves over the best-known 2-approximation algorithm by Behnezhad, Blum and Derakhshan [SODA’22] who also show that Ω(n/p) queries are necessary to achieve any constant approximation. Our guarantees also extend to instances where edge realizations are not fully independent. We complement this upperbound with a tight 3/2-approximation lower bound for stochastic graphs whose edges realizations demonstrate mild correlations. 
    more » « less