William He

collaborators

2 papers

cs.CC2024

More Efficient $k$ -wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities

Lucas Gretta, William He, Angelos Pelecanos

We prove that the permutation computed by a reversible circuit with $O ~ (nk \cdot lo g (1/ ε))$ random $3$ -bit gates is $ε$ -approximately $k$ -wise independen…

cs.CC2022

Symmetric Formulas for Products of Permutations

William He, Benjamin Rossman

We study the formula complexity of the word problem $Word_{S_{n}, k} : {0, 1}^{k n^{2}} \to {0, 1}$ : given $n$ -by- $n$ permutation matrices $M_{1}, \dots, M_{k}$ , compute the $(1, 1)$ …

More Efficient k-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities

Symmetric Formulas for Products of Permutations

More Efficient $k$ -wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities