I’m reading A note on succinct representations of graphs by Papadimitriou and Yannakakis. Let me quote the following paragraph on page 183:

Formula $ F$ has a highly regular structure. It has $ |x|$ clauses stating that the input to the computation of $ U$ is $ x$ , and a finite number of other types of clauses reflecting the moves of $ U$ , repeated in a regular way an exponential number of times (for each possible time-square combination of the computation of $ U$ on $ x$ ). In particular, it is very easy to see that, given two $ c|x|$ -bit integers, the indices of a literal and a clause, it can be determined in polynomial time whether the literal appears in the clause. Let us call $ B$ the polynomial-time algorithm computing this literal-clause relation.

Though $ B$ is polynomial-time, it’s not polynomial-size because it contains an exponential amount of information, i.e., literal-clause pairs.

Then it continues:

Combining algorithms $ A$ and $ B$ , we obtain an algorithm $ C$ which, given two integers with $ ck|x|$ bits, determines in polynomial time whether the two nodes are adjacent in the graph $ G(F)$ , based only on the bits of $ x$ . For fixed $ x$ this algorithm can be rendered as a polynomial-size circuit $ C_{G(F)}$ with $ 2ck|x|$ inputs, which is therefore a succinct representation of $ G(F)$ . Now, it is easy to see that, given $ x$ , we can construct $ C_{G(F)}$ in polynomial time.

I don’t understand how you can pack an exponential amount of information in “a polynomial-size circuit $ C_{G(F)}$ .” Can you explain? This is the hardest part of the paper, or it is wrong.