# Succinct Representation and Communication complexity

Succinct representation is often used to define NEXP or EXP complete problems. For example, when a graph is given as a circuit to compute the existence of edge between vertex $i,j$ for indices of $i,j$ is assigned in the input wires, the hardness of P-complete , NP-complete problems is amplified to EXP complete and NEXP-complete problems respectively .

My question is about relationship between communication complexity and succinct representation.

For example, can Alice and Bob that have $A,B \subseteq \{1,...,n\}$ compute the disjointedness function with $O(\log n)$ bits to construct the following protocol ? However, disjointedness has a lower bound $\Omega (n)$. The answer of this question must be $NO$. Why ?

Protocol:

1.Alice make a succinct representation of her input $A$ : this circuit output $1$ iff $i\in A$ for given index of $i \in \{1,...,n\}$.

2.Bob gets $A$ from the succinct circuit by executing brute force evaluation of all assignments, and check whether $A \cap B =\emptyset$

What are examples of $nice$ $structures$ you mention ?(Why arbitrary undirected graphs, boolean circuits, or formulae have $nice$ $structures$ in the sence of your answer ? Why messages Alice sent do not have ? If $A,B\subseteq \{1,...,{n \choose 2}\}$ then can we consider their inputs as undirected graphs ?)
The circuit computed by Alice gets $\log(n)$ bits representing $i \in [n]$, and outputs $1$ iff $i \in A$. Note that if $A$ does not have a particularly nice structure, the size of this circuit will be exponential in the length of the input, that is $2^{\log(n)}$.