Search

We study the wake-up problem in distributed networks, where an adversary awakens a subset of nodes at arbitrary times, and the goal is to wake up all other nodes as quickly as possible by sending only few messages. We prove the following lower bounds: * We first consider the setting where each node receives advice from an oracle who can observe the entire network, but does not know which nodes are awake initially. More specifically, we consider the $KT_0$ $LOCAL$ model with advice, where the nodes have no prior knowledge of their neighbors. We prove that any randomized algorithm must send $\Omega( \frac{n^{2}}{2^{\beta}\log n} )$ messages if nodes receive only $O(\beta)$ bits of advice on average. * For the $KT_1$ assumption, where each node knows its neighbors' IDs from the start, we show that any $(k+1)$-time algorithm requires $\Omega( n^{1+1/k} )$ messages. Our result is the first super-linear (in $n$) lower bound, for a problem that does not require individual nodes to learn a large amount of information about the network topology, which may be of independent interest. To complement our lower bound results, we present several new algorithms: * We give an asynchronous $KT_1$ $LOCAL$ algorithm that solves the wake-up problem with a time and message complexity of $O( n\log n )$ with high probability. * We introduce the notion of \emph{awake distance} $\rho_{\text{awk}}$, which is upper-bounded by the network diameter, and present a synchronous $KT_1$ $LOCAL$ algorithm that takes $O( \rho_{\text{awk}} )$ rounds and sends $O( n^{3/2}\sqrt{\log n} )$ messages with high probability. * We give deterministic advising schemes in the asynchronous $KT_0$ $CONGEST$ model (with advice). In particular, we obtain an $O( \rho_{\text{awk}}\log^2n )$-time advising scheme that sends $O( n\log^2n )$ messages, while requiring $O( \log^2n )$ bits of advice per node., Comment: Added Theorem 4

Quantum computational fluid dynamics (QCFD) offers a promising alternative to classical computational fluid dynamics (CFD) by leveraging quantum algorithms for higher efficiency. This paper introduces a comprehensive QCFD method, including an iterative method "Iterative-QLS" that suppresses error in quantum linear solver, and a subspace method to scale the solution to a larger size. We implement our method on a superconducting quantum computer, demonstrating successful simulations of steady Poiseuille flow and unsteady acoustic wave propagation. The Poiseuille flow simulation achieved a relative error of less than $0.2\%$, and the unsteady acoustic wave simulation solved a 5043-dimensional matrix. We emphasize the utilization of the quantum-classical hybrid approach in applications of near-term quantum computers. By adapting to quantum hardware constraints and offering scalable solutions for large-scale CFD problems, our method paves the way for practical applications of near-term quantum computers in computational science., Comment: 31 pages, 10 figures

Recent studies have shown that code language models at scale demonstrate significant performance gains on downstream tasks, i.e., code generation. However, most of the existing works on code representation learning train models at a hundred million parameter scale using very limited pretraining corpora. In this work, we fuel code representation learning with a vast amount of code data via a two-stage pretraining scheme. We first train the encoders via a mix that leverages both randomness in masking language modeling and the structure aspect of programming language. We then enhance the representations via contrastive learning with hard negative and hard positive constructed in an unsupervised manner. We establish an off-the-shelf encoder model that persistently outperforms the existing models on a wide variety of downstream tasks by large margins. To comprehend the factors contributing to successful code representation learning, we conduct detailed ablations and share our findings on (i) a customized and effective token-level denoising scheme for source code; (ii) the importance of hard negatives and hard positives; (iii) how the proposed bimodal contrastive learning boost the cross-lingual semantic search performance; and (iv) how the pretraining schemes decide the downstream task performance scales with the model size., Comment: 10 pages

We consider the message complexity of verifying whether a given subgraph of the communication network forms a tree with specific properties both in the KT-$\rho$ (nodes know their $\rho$-hop neighborhood, including node IDs) and the KT-$0$ (nodes do not have this knowledge) models. We develop a rather general framework that helps in establishing tight lower bounds for various tree verification problems. We also consider two different verification requirements: namely that every node detects in the case the input is incorrect, as well as the requirement that at least one node detects. The results are stronger than previous ones in the sense that we assume that each node knows the number $n$ of nodes in the graph (in some cases) or an $\alpha$ approximation of $n$ (in other cases). For spanning tree verification, we show that the message complexity inherently depends on the quality of the given approximation of $n$: We show a tight lower bound of $\Omega(n^2)$ for the case $\alpha \ge \sqrt{2}$ and a much better upper bound (i.e., $O(n \log n)$) when nodes are given a tighter approximation. On the other hand, our framework also yields an $\Omega(n^2)$ lower bound on the message complexity of verifying a minimum spanning tree (MST), which reveals a polynomial separation between ST verification and MST verification. This result holds for randomized algorithms with perfect knowledge of the network size, and even when just one node detects illegal inputs, thus improving over the work of Kor, Korman, and Peleg (2013). For verifying a $d$-approximate BFS tree, we show that the same lower bound holds even if nodes know $n$ exactly, however, the lower bound is sensitive to $d$, which is the stretch parameter., Comment: Appeared at OPODIS 2023