Parity-SAT is the problem of determining whether a given CNF formula has an odd number of satisfying assignments. As a canonical ⊕P-complete problem, it represents a fundamental variant of the exact model counting problem (#SAT). Under the Strong Exponential Time Hypothesis (SETH), Parity-SAT admits no O^*((2-ε)ⁿ)-time or O^*((2-ε)^m)-time algorithm for any constant ε > 0, where n and m denote the numbers of variables and clauses, respectively. Thus, breaking the 2ⁿ or 2^m barrier appears impossible in full generality. In this work, we revisit this barrier through structural restrictions and a refined exploitation of parity. We study Parity-d-occ-SAT, where each variable appears in at most d clauses, and obtain three main results. First, we design {a randomized} O^*(2^{m(1-1/O(d))})-time algorithm, thereby breaking the 2^m barrier for every fixed d. Second, for the special case d = 2, we develop a significantly sharper branching algorithm running in O^*(1.1193ⁿ) time or O^*(1.3248^m) time. Third, leveraging the structural insights underlying the d = 2 case, we obtain an O^*(1.1052^L)-time algorithm for general Parity-SAT, where L denotes the formula length. All algorithms use only polynomial space. Notably, our running-time bounds are better than the best known bounds for the corresponding exact counting counterparts, highlighting a genuine algorithmic advantage of parity over counting. Conceptually, our results demonstrate that parity admits finer structural reductions and more efficient branching than exact model counting, and that bounded occurrence can be systematically leveraged to circumvent classical exponential barriers.

In this era of exploding data volumes, more and more complex data analysis tasks are now accomplished by machine learning (ML) or deep learning (DL). Despite the powerful and flexible task processing capability, it also brings challenges such as how to reasonably design the optimal hyperparameters configuration and the huge consumption of time for a single validation. Existing Hyperrarameter Optimization (HPO) methods are gradually facing performance bottlenecks. However, in an era where progressively data-centric big data analytics methods are prevalent, such efficiency issues need to be urgently addressed in the design of intelligent DBMS. In this paper, we propose ShrinkHPO, an efficient and explainable-designed HPO approach with a major focus on ($a$) efficient hyperparameter configuration search strategy, (b) asynchronous executing intervention, and (c) XAI (eXplainable AI) design. ShrinkHPO employs a hyperparameter weight estimation strategy named Shrink-search together with an asynchronous execution design to improve HPO efficiency. To the best of our knowledge, ShrinkHPO is the first HPO method that introduces explainable analysis and verification to ensure the judgment of “high significance” hyperparameters. We also conduct a series of experiments on data analysis tasks in the database domain (classification, regression, time series classification, CASH [1], etc.), collecting HPO results on the usual ML or DL models in each task. Compared to SOTA asynchronous and sequential HPO baselines, ShrinkHPO achieves top performance on both accuracy (RMSE for regression tasks) and time cost, accelerating from 20% to a maximum of 2.2 x.

The increasing complexity of data analysis tasks makes it dependent on human expertise and challenging for non-experts. One of the major challenges faced in data analysis is the selection of the proper algorithm for given tasks and data sets. Motivated by this, we develop Assassin, aiming at helping users without enough expertise to automatically select optimal algorithms for classification tasks. By embedding meta-learning techniques and reinforced policy, our system can automatically extract experiences from previous tasks and train a meta-classifier to implement algorithm recommendations. Then we apply genetic search to explore hyperparameter configuration for the selected algorithm. We demonstrate Assassin with classification tasks from OpenML. The system chooses an appropriate algorithm and optimal hyperparameter configuration for them to achieve a high-level performance target. The Assassin has a user-friendly interface that allows users to customize the parameters during the search process.