A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the value corresponding to the first rule whose term is satisfied by the input. Decision lists generalize both CNFs and DNFs and have been studied both in complexity theory and in learning theory. The size of a decision list is the number of rules, and its width is the maximal number of variables in a term. We prove that decision lists of small width can always be approximated by decision lists of small size, where we obtain sharp bounds for such approximation. This also resolves a conjecture of Gopalan, Meka, and Reingold (Computational Complexity, 2013) on DNF sparsification. An ingredient in our proof is a new random restriction lemma, which allows to analyze how DNFs (and more generally, decision lists) simplify if a small fraction of the variables are fixed. This is in contrast to the more commonly used switching lemma, which requires most of the variables to be fixed.

Spurred by the influential work of Viola (Journal of Computing 2012), the past decade has witnessed an active line of research into the complexity of (approximately) sampling distributions, in contrast to the traditional focus on the complexity of computing functions. We build upon and make explicit earlier implicit results of Viola to provide superconstant lower bounds on the locality of Boolean functions approximately sampling the uniform distribution over binary strings of particular Hamming weights, both exactly and modulo an integer, answering questions of Viola (Journal of Computing 2012) and Filmus, Leigh, Riazanov, and Sokolov (RANDOM 2023). Applications to data structure lower bounds and quantum-classical separations are discussed. This is an extended abstract. The full paper can be found at https://arxiv.org/abs/2402.14278.

Reversible Boolean function (RBF) is a one-to-one function which maps n-bit input to n-bit output. Reversible logic synthesis has been widely studied due to its connection with low-energy computation as well as quantum computation. In this paper, we give a structured decomposition for even RBFs. Specifically, for n≥q 6, any even n-bit RBF can be decomposed to 7 blocks of (n-1)-bit RBF, where 7 is a constant independent of n and the positions of these blocks have a large degree of freedom. Moreover, if the (n-1)-bit RBFs are required to be even as well, we show for n≥q 10, even n-bit RBF can be decomposed to 10 even (n-1)-bit RBFs. In short, our decomposition has block depth 7 and even block depth 10. Our result improves Selinger's work in block depth model, by reducing the constant from 9 to 7 and from 13 to 10, when the blocks are limited to be even. We emphasize that our setting is a bit different from Selinger's work. In Selinger's constructive proof, each block is placed in one of two specific positions and thus the decomposition has an alternating structure. We relax this restriction and allow each block to act on arbitrary (n-1) bits. This relaxation keeps the block structure and provides more candidates when choosing the positions of blocks.