3
$\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$
2
  • 5
    $\begingroup$ You are trying to compress n bits of information into fewer bits. This is not possible. $\endgroup$ Jun 13, 2013 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$ Jun 14, 2013 at 5:54

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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