If we let a language L in {0,1}* be dyadic if for each x in L, and each index i with xi = 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?

• What do you mean by "use the advice string and the input x to generate a dyadic language"? Commented May 8, 2023 at 0:22

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}}$$.