0
$\begingroup$

This is from Justin Thaler's book - Proofs, Arguments & Zero Knowledge

Page 43

For it to make sense to talk about multilinear extensions, we need to view the adjacency matrix $A$ not as a matrix, but rather as a function $f_A$ mapping $\lbrace0,1\rbrace^ {log n} \times \lbrace0,1\rbrace^ {log n}$ to $\lbrace0,1\rbrace$. The natural way to do this is to define $f_A(x,y)$ so that it interprets $x$ and $y$ as the binary representations of some integers $i$ and $j$ between $1$ and $n$, and outputs $A_{i, j}$. See Figure $4.5$ for an example.

This is figure 4.5

enter image description here

(I have shaded in yellow the element which I am going use below as an example).

The 4 parameters of function $f_A$ seem to be the bit representation of the element number of the matrix - i.e if I consider the matrix elements having numbers $0$ to $15$ (Considering element numbers of first row as $0, 1, 2$ & $3$ & so on)

For e.g. if I consider the element $6$ in row number $4$ & column number $2$- it's the $13$th element of the Matrix. The bit pattern of $13$ is $1101$.

So $f_A$ takes 4 parameters same as the bit pattern - i.e. $f_A(1,1,0,1) = 6$

I hope my understanding above is correct.

However, right after, on Page 44, he says counts triangles using the following equation

$\Delta = \frac {1}{6} \sum_{{x,y,z \in \lbrace 0, 1 \rbrace}^{log\space n}} f_A(x,y)\cdot f_A(y,z) \cdot fA(x,z)$

I assume above that the parameters to $f_A$ are row & column numbers.

In figure $4.5$, the parameters of $f_A$ is the bit pattern of the element number of the matrix. However, above it changes to row & column numbers. How does this match with figure $4.5$?

In the particular case of a $4 \times 4$ matrix the element number bit pattern is the same as bit pattern of row number joined with bit pattern of column number. But this isn't true for others - i.e. not true even for $5\times 5$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

In figure 4.5, the parameters of $f_A$ is the bit pattern of the element number of the matrix. However, above it changes to row & column numbers. How does this match with figure 4.5?

The inputs to $f_A$ are always a pair consisting of a row and column. If the book wanted to be extremely precise, they would have used the following notation, for example $$f_A((1,1),(0,1)) = 6.$$ But that can hurt readability.

But this isn't true for others - i.e. not true even for 5×5 ?

True. The example simplifies to make it work nicely. But for the general case, I believe the "fix" is to arbitrarily define the values of $f_A$ at inputs that aren't valid indices. Then, one can use something akin to a selector polynomial in the specific application (that evaluates to zero, for example, in a counting application, etc..).

Improve this answer
$\endgroup$
4
  • $\begingroup$ fA((1,1),(0,1))=6. with such a definition, how exactly would you use Lemma 3.6 (Page 29) to interpolate & find the polynomial which would represent the matrix? $\endgroup$
    – user93353
    Nov 13 at 14:08
  • $\begingroup$ There's a 1-1 mapping from $((w,x),(y,z))$ to $(w, x ,y ,z)$. So you can define an intermediary function that "flattens" the tuple before doing the interpolation. At this point, it's mainly a question of presentation. $\endgroup$
    – Marc Ilunga
    Nov 13 at 14:13
  • $\begingroup$ Thank you. So the sumcheck also instead of $\sum_{{x,y,z \in \lbrace 0, 1 \rbrace}^{log\space n}} f_A(x,y)\cdot f_A(y,z) \cdot fA(x,z)$ would also become something like $\sum_{x_1 \in \lbrace 0, 1 \rbrace} ... \sum_{y_1 \in \lbrace 0, 1 \rbrace} ... \sum_{z_1 \in \lbrace 0, 1 \rbrace}... f_A(x_1, x_2, ..., y_1, y_2, ..., z_1, z_2, ...)$ $\endgroup$
    – user93353
    Nov 14 at 10:40
  • $\begingroup$ You can certainly define things such that the expression you give works. But I suppose the "ultimate" implementation will still be something like $f_A(x_1,\cdots, y_1, \cdots) f_A(y_1,\cdots, z_1, \cdots) f_A(z_1,\cdots, x_1, \cdots) $. The reason being that the running time for the MLE evaluation is basically exponential in the number of variables in $f_A$. But surely, the long expression you can be used either directly or as "syntactic sugar" for the more efficient implementation. $\endgroup$
    – Marc Ilunga
    Nov 14 at 13:34

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.