P/poly and dyadic oracle

Question

If we let a language L in {0,1}^* be dyadic if for each x in L, and each index i with x_i = 1, i is a power of 2, then consider the class of languages recognized by a polynomial time oracle machine with a dyadic oracle. Is this the same as the class P/poly? If we start with some language L in P/poly, then we can use the advice string and the input x to generate a dyadic language, and then check various strings for each input x on the oracle to see if they are in our language to determine if x is in L. Is this the right idea? I also don't know how to approach the other direction. Do you need to create a circuit based on the queries to the oracle?

Answer 1

Let $D \subseteq \{0,1\}^*$ be the class of all dyadic languages. Then by $P^D$, we denote the class of languages decidable in polynomial time by a Turing machine with an oracle for a Dyadic language.

Given a dyadic string $x \in \{0,1\}^m$, denote by $B(x)$ the string $y$ such that $y_i = x_{2^i}$. Intuitively, you can think of $B(x)$ as "compressing" $x$ by removing all the $0$ indices in between the indices which are powers of $2$. Now given a dyadic language $L$, let $B(L) := \{B(x) : x \in L\}$.

Claim: $D \subseteq P_{\text{poly}}$

Proof Let $L \in D$, and we describe a polynomial size circuit family $\{C_n\}$ which computes $L$. Let $L_n := \{x \in L : |x| = n\}$. Note that $B(L_n) \subseteq \{0,1\}^{\log n}$, so the naive DNF circuit which computes it has size $\log n \cdot 2^{\log n} = n \log n$. Our circuit $C_n$ simply wires $x_i$ for which $i$ is a power of $2$ into the $i$th input for this naive DNF circuit for $B(L_n)$.

It then follows that $P^D \subseteq P_{\text{poly}}$.