# 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$

Thank you for Igor's answer.Additional questions are:

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 ?)

• You are trying to compress n bits of information into fewer bits. This is not possible. – Robin Kothari Jun 13 '13 at 13:48
• obviously not all undirected graphs can be represented succinctly (by a pigeonhole argument). and succinct problems are easy on instances for which the smallest representing circuit is of size polynomial in the graph/CNF formula size. however, for the set of instances for which an (N)EXP-complete succinct problem is hard the circuits will much smaller than the graph/formula size. to see how that happens, check out the reduction to succinct SAT i outlined in this answer: cstheory.stackexchange.com/a/10503/4896 – Sasho Nikolov Jun 14 '13 at 5:54

## 1 Answer

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