Watrous conjectured that the randomized and quantum query complexities of symmetric functions are polynomially equivalent, which was resolved by Aaronson & Ambainis (2014) and was later improved by Chailloux (2019) and Ben-David et al. (2020). This paper explores a fine-grained version of the Watrous conjecture, including the randomized and quantum algorithms with success probabilities arbitrarily close to $$1/2$$ 1 / 2 . Our contributions include the following: 1. We analyze the optimal success probabilities of quantum and randomized query algorithms of two fundamental partial symmetric Boolean functions given a fixed number of queries. 2. We establish that for any total symmetric Boolean function $$f$$ f , if a quantum algorithm uses $$T$$ T queries to compute $$f$$ f with success probability $$1/2+\beta$$ 1 / 2 + β , then there exists a randomized algorithm using $$O(T^2)$$ O ( T 2 ) queries to compute $$f$$ f with success probability $$1/2+\Omega{\delta\beta^2}$$ 1 / 2 + Ω δ β 2 on a $$1-\delta$$ 1 - δ fraction of inputs, where $$\beta,\delta$$ β , δ can be arbitrarily small positive values. Moreover, we prove a randomized version of Aaronson-Ambainis Conjecture (Aaronson & Ambainis 2014) for symmetric Boolean functions in the regime where the success probability of algorithms can be arbitrarily close to 1/2. 3. We present tight polynomial equivalence for several fundamental complexity measures of partial symmetric Boolean functions.

Rapid increase of storage and network bandwidth incurs higher CPU consumption in modern data systems. This phenomenon is particularly evident for log-structured merged key-value stores (LSM-KVS), which rely on resource-intensive background operations to flush and compact disk data. While extensive research has been conducted to reduce the CPU overhead of background compaction, less attention has been paid to background flushing, which can also consume a significant amount of valuable CPU cycles and disrupt CPU caches, ultimately impacting overall performance. In this paper, we propose DFlush, a novel solution that uses DPUs to offload background flush operations to reduce its CPU cost. DPUs are an appealing choice for this goal due to their cost-effectiveness, ease of programming, and widespread deployment. However, their complex hardware architecture requires careful design of both the data and control planes. To fully harness the DPU's capabilities, DFlush decomposes a flush job into fine-grained steps, mapped them to DPU hardware units, and accelerates them through pipeline, data, and channel parallelism, ensuring data-plane efficiency. It also introduces an adaptive control plane that dynamically schedules flush jobs from different LSM-KVS instances based on their priority, reducing write stall and tail latency. Our experiments on a real DPU platform with an industrial-grade LSM-KVS show that DFlush delivers higher throughput, significantly lower tail latency, and saves up to dozens of CPU cores per LSM-KVS server while reducing energy consumption.

This paper gives a nearly tight characterization of the quantum communication complexity of permutation-invariant Boolean functions. With such a characterization, we show that the quantum and randomized communication complexity of permutation-invariant Boolean functions are quadratically equivalent (up to a polylogarithmic factor of the input size). Our results extend a recent line of research regarding query complexity to communication complexity, showing symmetry prevents exponential quantum speedups. Furthermore, we show that the Log-rank Conjecture holds for any non-trivial total permutation-invariant Boolean function. Moreover, we establish a relationship between the quantum/classical communication complexity and the approximate rank of permutation-invariant Boolean functions. This implies the correctness of the Log-approximate-rank Conjecture for permutation-invariant Boolean functions in both randomized and quantum settings (up to a polylogarithmic factor of the input size).

Visual graph query interfaces (VQI) facilitate non-programmers to query graph data effortlessly. The construction of these interfaces for large networks is typically not data-driven. That is, they do not exploit the underlying networks to automatically generate the contents of various panels of a VQI. Such data-driven construction has several benefits such as facilitating efficient top-down and bottom-up query formulation and portability of an interface across different application domains and sources. In this demonstration, we present a novel plug-and-play visual subgraph query interface construction engine called PLAYPEN that can be plugged on any large network G with a plug specification b to automatically generate the VQI for G that satisfies b by populating various components of the interface.

Canned patterns ( i.e. , small subgraph patterns) in visual graph query interfaces (a.k.a GUI) facilitate efficient query formulation by enabling pattern-at-a-time construction mode. However, existing GUIS for querying large networks either do not expose any canned patterns or if they do then they are typically selected manually based on domain knowledge. Unfortunately, manual generation of canned patterns is not only labor intensive but may also lack diversity for supporting efficient visual formulation of a wide range of subgraph queries. In this paper, we present a novel, generic, and extensible framework called TATTOO that takes a data-driven approach to automatically select canned patterns for a GUI from large networks. Specifically, it first decomposes the underlying network into truss-infested and truss-oblivious regions. Then candidate canned patterns capturing different real-world query topologies are generated from these regions. Canned patterns based on a user-specified plug are then selected for the GUI from these candidates by maximizing coverage and diversity , and by minimizing the cognitive load of the pattern set. Experimental studies with real-world datasets demonstrate the benefits of TATTOO. Importantly, this work takes a concrete step towards realizing plug-and-play visual graph query interfaces for large networks.

Considering the drawbacks of existing reversion based on-line portfolio selection (PS) strategies, we propose a new on-line learning and reversion based strategy that is called Gaussian Weighting Reversion (GWR in short). On the one hand, to exploit the "time validity" of historical market data, which means that the more recent market data are more valuable to market prediction than the less recent market data, we use the Gaussian function to weight data in a moving window. On the other hand, for each time point we average two predictions to alleviate the impact of noise and outliers. We conduct extensive evaluation on six real market datasets and compare our strategy with nine existing methods, including the state of the art ones. Experimental results show that our method outperforms the existing methods.