2
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ You are trying to compress n bits of information into fewer bits. This is not possible. $\endgroup$ – Robin Kothari Jun 13 '13 at 13:48
  • $\begingroup$ 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 $\endgroup$ – Sasho Nikolov Jun 14 '13 at 5:54
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.