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

CC BY-SA 3.0
2013-06-13T10:32:19.600Z
2013-06-13T10:32:19.600Z
Igor Shinkar
<p>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 <em>indices</em> of $i,j$ is assigned in the input wires, the hardness of P-complete  , NP-complete problems is <em>amplified</em> to EXP complete and NEXP-complete problems respectively .</p>

<p>My question is about relationship between communication complexity  and succinct representation. </p>

<p>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 ?</p>

<p>Protocol:</p>

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

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

<p>Thank you for Igor's answer.Additional questions are:</p>

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

CC BY-SA 3.0
2013-06-13T13:48:37.213Z
You are trying to compress n bits of information into fewer bits. This is not possible.
Robin Kothari
CC BY-SA 3.0
2013-06-14T05:54:35.090Z
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: http://cstheory.stackexchange.com/a/10503/4896
Sasho Nikolov
<cc.complexity-theory><circuit-complexity><boolean-functions><communication-complexity><succinct>
Succinct Representation and Communication complexity
poul
# Succinct Representation and Communication complexity

(Asked by: username_0 on 2013-06-13)

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

**Tags:** cc.complexity-theory, circuit-complexity, boolean-functions, communication-complexity, succinct

> **Comments:**
> **username_1**: You are trying to compress n bits of information into fewer bits. This is not possible.  
> **username_2**: 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: http://cstheory.stackexchange.com/a/10503/4896  

---

## 1 answers

### Answer by username_3 on 2013-06-13. Score: 2

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


---

