Next

__
TR21-088
| 23rd June 2021
__

Oded Goldreich#### Open Problems in Property Testing of Graphs

__
TR21-087
| 22nd June 2021
__

Uma Girish, Ran Raz#### Eliminating Intermediate Measurements using Pseudorandom Generators

__
TR21-086
| 22nd June 2021
__

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy#### Linear Space Streaming Lower Bounds for Approximating CSPs

Next

Oded Goldreich

We briefly discuss a few open problems in the study of various models of testing graph properties, focusing on the query complexity of the various tasks. In the dense graph model, we discuss several open problems, including:

* Determining the complexity of testing triangle-freeness.

* Characterizing the class of properties ...
more >>>

Uma Girish, Ran Raz

We show that quantum algorithms of time T and space $S \ge \log T$ with intermediate measurements can be simulated by quantum algorithms of time $T\cdot \mathrm{poly}(S)$ and space $O(S\cdot \log T)$ without intermediate measurements. The best simulations prior to this work required either $\Omega(T)$ space (by the deferred measurement ... more >>>

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy

We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on $n$ variables taking values in $\{0,\ldots,q-1\}$, we prove that improving over the trivial approximability by a factor of $q$ requires $\Omega(n)$ space even on instances with $O(n)$ constraints. We also identify ... more >>>

Next