Fooling Near-Maximal Decision Trees

William M. Hoza, Zelin Lv

TL;DR

This paper introduces a new concept called "k-wise probable uniformity" and uses it to construct pseudorandom generators (PRGs) that are significantly better at fooling decision trees and Boolean circuits. The key innovation is a PRG with a seed length that is nearly optimal, achieving a seed length of $(1+\alpha) \log m + O(\log(1/\epsilon) + \log \log n)$ for fooling decision trees of size $m$ with error $\epsilon$.

What Problem Does This Paper Address?

The paper tackles the challenge of generating "random-looking" bits that can fool computational models like decision trees and Boolean circuits. Specifically, it addresses the problem of constructing pseudorandom generators (PRGs) that can efficiently simulate truly random bits for these models. Existing PRGs often require a seed length that is too long to be practical for fooling complex circuits or decision trees with many variables. The authors aim to improve the seed length of these PRGs, making them more efficient and useful for theoretical computer science applications, particularly in circuit complexity and derandomization.

Methods

The core of the paper's contribution lies in the introduction and application of a new concept: k-wise probable uniformity. This concept is a strengthening of existing notions like "almost k-wise uniformity" and "k-wise y-biased distributions." The authors provide two equivalent definitions for k-wise probable uniformity, one based on the distribution of projected variables and another based on the expected value of k-junta functions.

They then leverage this new concept to construct an explicit PRG. The construction involves:

  • Pseudorandomly partitioning variables into buckets: This technique, inspired by prior work, aims to ensure that no single bucket receives too many of the "important" variables.
  • Combining pairwise uniform hash functions with k-wise y-biased generators: This is a standard approach, but the authors use it in conjunction with their new k-wise probable uniformity concept to achieve better seed length bounds.
  • A brute-force construction for hitting sets: This is used as a subroutine in constructing hitting sets for systems of linear equations over F2.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The power of "k-wise probable uniformity": This new notion of randomness is shown to be a more powerful tool for fooling decision trees and circuits than previous concepts like k-wise independence or small-bias distributions. It allows for better seed length trade-offs.
  • Near-optimal seed length for fooling decision trees: The authors achieve a seed length that is remarkably close to the theoretical minimum for fooling decision trees of a given size and error. This is a significant improvement over prior constructions.
  • Limitations of existing "small-bias" generators: The paper demonstrates that traditional k-wise y-biased generators, while useful, are inherently too weak to achieve the improved seed lengths they present for fooling circuits. This justifies the need for their new approach.
  • Bridging circuit complexity and PRGs: The work establishes a strong connection between the problem of fooling Boolean circuits and the construction of efficient PRGs, providing new tools for both areas.

Key Results

  • PRG for Fooling Near-Maximal Decision Trees: An explicit PRG is constructed that fools $n$-variate decision trees of size $m$ with error $\epsilon$ and seed length $s = \log m + O(\log^{2/3} m \cdot \log^{1/3} (\log m) + \log(1/\epsilon) + \log \log n)$. This is a significant improvement, especially for trees with near-maximal size.
  • PRG for Fooling U2-circuits: An explicit PRG is developed that fools $U_2$-circuits of size $(3-\alpha) \cdot n$ with error $\eta \cdot 2^{-O(\alpha^2 n)}$ and seed length $s = (1-\Omega(\alpha^2)) \cdot n$. This is the first such PRG with a seed length that is linear in $n$ and sub-linear in the circuit size.
  • Hitting Set for Systems of Equations over F2: A hitting set construction is presented for systems of linear equations over $F_2$. The size of the hitting set is $2^k + O((k \log n \log k)^{2/3} + \log n)$, which improves the exponent of $k$ from 2 to 1 compared to previous methods.
  • Hitting Set for B2-circuits: The hitting set for linear systems is used to construct a hitting set for $B_2$-circuits of size $(2.5-\alpha) \cdot n$, with enumeration time $2^{(1-\Omega(\alpha^2)) \cdot n} + \tilde{O}(n^{2/3})$.

Limitations and Future Work

  • "Black box" nature of hitting sets: While the hitting set construction is efficient, the paper notes that it is crucial for applications where only query access to the circuit is available.
  • Comparison of hitting set constructions: The paper mentions that their hitting set construction for systems of equations over $F_2$ is incomparable to a prior claimed result, being better when $k \approx n$ and worse when $k \ll n$.
  • Future work: The authors suggest that their work extends to the more powerful model of "subcube partitions" and that their new constructions provide tools for tackling problems in circuit complexity. The paper also highlights that their new concept of k-wise probable uniformity is a novel area of study with potential for further research.

Summary updated

BibTeX
@inproceedings{hoza2025fooling,
  author = {William M. Hoza and Zelin Lv},
  title = {{Fooling Near-Maximal Decision Trees}},
  booktitle = {APPROX/RANDOM},
  year = {2025},
  doi = {10.4230/lipics.approx/random.2025.35},
}
Figure