All reports by Author Krzysztof Onak:

__
TR13-002
| 31st December 2012
__

Venkatesan Guruswami, Krzysztof Onak#### Superlinear lower bounds for multipass graph processing

Revisions: 3

__
TR07-077
| 7th August 2007
__

Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan#### Testing for Concise Representations

Venkatesan Guruswami, Krzysztof Onak

We prove $n^{1+\Omega(1/p)}/p^{O(1)}$ lower bounds for the space complexity of $p$-pass streaming algorithms solving the following problems on $n$-vertex graphs:

* testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size),

* testing if two ... more >>>

Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. with ideas from learning theory, and yields property testers that make poly(s/epsilon) queries (independent of n) for Boolean function classes ... more >>>