PreviousNext

__
TR19-104
| 6th August 2019
__

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich#### Reconstruction of Depth-$4$ Multilinear Circuits

__
TR19-103
| 7th August 2019
__

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi#### Query-to-Communication Lifting Using Low-Discrepancy Gadgets

__
TR19-102
| 10th August 2019
__

Oded Goldreich#### Testing Isomorphism in the Bounded-Degree Graph Model

Revisions: 1

PreviousNext

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

We present a deterministic algorithm for reconstructing multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuits, i.e. multilinear depth-$4$ circuits with fan-in $k$ at the top $+$ gate. For any fixed $k$, given black-box access to a polynomial $f \in \mathbb{F}[x_{1},x_{2},\ldots ,x_{n}]$ computable by a multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuit of size $s$, the algorithm runs in time ... more >>>

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Lifting theorems are theorems that relate the query complexity of a function $f:\left\{ 0,1 \right\}^n\to \left\{ 0,1 \right\}$ to the communication complexity of the composed function $f\circ g^n$, for some “gadget” $g:\left\{ 0,1 \right\}^b\times \left\{ 0,1 \right\}^b\to \left\{ 0,1 \right\}$. Such theorems allow transferring lower bounds from query complexity to ... more >>>

Oded Goldreich

We consider two versions of the problem of testing graph isomorphism in the bounded-degree graph model: A version in which one graph is fixed, and a version in which the input consists of two graphs.

We essentially determine the query complexity of these testing problems in the special case of ...
more >>>

PreviousNext