Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.07752 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929683841417216 |
|---|---|
| author | Anand, Emile |
| author_facet | Anand, Emile |
| contents | Expander graphs are among the most useful combinatorial objects in theoretical computer science. A line of work studies random walks on expander graphs for their pseudorandomness against various classes of test functions, including symmetric functions, read-only branching programs, permutation branching programs, and $\mathrm{AC}^0$ circuits. The promising results of pseudorandomness of expander random walks against $\mathrm{AC}^0$ circuits indicate a robustness of expander random walks beyond symmetric functions, motivating the question of whether expander random walks can fool more robust \emph{asymmetric} complexity classes, such as $\mathrm{ACC}^0$. In this work, we make progress towards this question by considering certain two-layered circuit compositions of $\mathrm{MOD}[k]$ gates, where we show that these family of circuits are fooled by expander random walks with total variation distance error $O(λ)$, where $λ$ is the second largest eigenvalue of the underlying expander graph. For $k\geq 3$, these circuits can be highly asymmetric with complicated Fourier characters. In this context, our work takes a step in the direction of fooling more complex asymmetric circuits. Separately, drawing from the learning-theory literature, we construct an explicit threshold circuit in the circuit family $\mathrm{TC}^0$, and show that it is \emph{not} fooled by expander random walk, providing an upper bound on the set of functions fooled by expander random walks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_07752 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Towards the Pseudorandomness of Expander Random Walks for Read-Once ACC0 circuits Anand, Emile Computational Complexity 60E15 F.1.3; G.3 Expander graphs are among the most useful combinatorial objects in theoretical computer science. A line of work studies random walks on expander graphs for their pseudorandomness against various classes of test functions, including symmetric functions, read-only branching programs, permutation branching programs, and $\mathrm{AC}^0$ circuits. The promising results of pseudorandomness of expander random walks against $\mathrm{AC}^0$ circuits indicate a robustness of expander random walks beyond symmetric functions, motivating the question of whether expander random walks can fool more robust \emph{asymmetric} complexity classes, such as $\mathrm{ACC}^0$. In this work, we make progress towards this question by considering certain two-layered circuit compositions of $\mathrm{MOD}[k]$ gates, where we show that these family of circuits are fooled by expander random walks with total variation distance error $O(λ)$, where $λ$ is the second largest eigenvalue of the underlying expander graph. For $k\geq 3$, these circuits can be highly asymmetric with complicated Fourier characters. In this context, our work takes a step in the direction of fooling more complex asymmetric circuits. Separately, drawing from the learning-theory literature, we construct an explicit threshold circuit in the circuit family $\mathrm{TC}^0$, and show that it is \emph{not} fooled by expander random walk, providing an upper bound on the set of functions fooled by expander random walks. |
| title | Towards the Pseudorandomness of Expander Random Walks for Read-Once ACC0 circuits |
| topic | Computational Complexity 60E15 F.1.3; G.3 |
| url | https://arxiv.org/abs/2501.07752 |