Succinct circuit representation of graphs

Question

The complexity class PPAD (e.g. computing various Nash equilibria) can be defined as the set of total search problems polytime reducible to END OF THE LINE:

END OF THE LINE: Given circuits S and P with n input bits and n output bits such that P(0ⁿ) = 0ⁿ != S(0ⁿ), find an input x in {0,1}ⁿ such that P(S(x)) != x or S(P(x)) != x != 0ⁿ.

Circuits or algorithms such as S and P implicitly define an exponentially large graph that is only revealed on a query-by-query basis (to keep the problem in PSPACE!), e.g. Papadimitrou's paper.

However, I don't understand how one would design a circuit that enables arbitrary graphs (if there is a systematic structure to the graph, it appears much easier to find the circuit). For instance, how would one design a polynomially-sized circuit that represents an exponentially-long directed line, with an all-0 label for the source vertex and randomly assigned binary labels to all other vertices? This seems to be implicit in the PPAD-related papers.

The closest I've come from a search online is Galperin/Widgerson's paper, but the circuit described there takes two vertex labels and returns a Boolean answer to "Are these vertices adjacent?"

So, how would you design a polynomially-sized circuit of an exponentially-sized graph that takes an n-bit input and outputs the n-bit label of its predecessor or successor, respectively? Or even, does someone know of a resource that explains this well?

Answer 1

Your question seems to be asking: how does one represent arbitrary graphs (or even arbitrary path graphs) as a circuit of polynomial size? The answer is, you don't. The number of different path graphs with 2ⁿ vertices is (2ⁿ)!, far more than the number of different circuits with n^c gates (exponential in n^c log n). So almost all graphs with this many vertices cannot be represented by a succinct circuit.

Therefore, as you hint, in some sense only graphs that have a high degree of structure can be represented in this way. That's what makes complexity classes like PPAD interesting: despite the structure that we know the input graphs to the EOL problem must have, we don't seem to know how to take advantage of the structure to solve the problem efficiently.

If I'm misunderstanding your question and you're really asking: how does one make a circuit that even meets the input requirements for EOL, for even a very highly structured graph: try the path graph that connects vertex x (considered as a number in binary) to x-1 and x+1, with ends at zero and at 2^n-1. Or if you want something less trivial that seems more difficult to solve EOL for: let E and D be the encryption and decryption functions for a fixed key in your favorite cryptosystem, let the neighbors of x in the graph be E(x) and D(x), and let the ends of the line be 0 and D(0).

Answer 2

Since most graphs on n vertices are Kolmogorov-random, they cannot be described by a circuit (or any other program) that is significantly smaller than the graph itself. (If you don't know what Kolmogorov-random means, you can basically take the conclusion of the previous sentence as its definition. Then rely on the fact that almost all strings are Kolmogorov-random.)

Although I'm not intimately familiar with the works you cited, my guess is that they are always talking about graphs-described-by-circuits. In other words, by focusing on the circuits, they are essentially restricting their attention to the class of graphs that do have succinct circuits (whose size is logarithmic in the size of the graph).