All reports by Author Kevin Matulef:

__
TR13-187
| 27th December 2013
__

Peyman Afshani, Kevin Matulef, Bryan Wilkinson#### Property Testing on Linked Lists

Revisions: 1

__
TR11-045
| 1st April 2011
__

Eric Blais, Joshua Brody, Kevin Matulef#### Property Testing Lower Bounds via Communication Complexity

Revisions: 1

__
TR07-128
| 10th November 2007
__

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio#### Testing Halfspaces

__
TR07-077
| 7th August 2007
__

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

Peyman Afshani, Kevin Matulef, Bryan Wilkinson

We define a new property testing model for algorithms that do not have arbitrary query access to the input, but must instead traverse it in a manner that respects the underlying data structure in which it is stored. In particular, we consider the case when the underlying data structure is ... more >>>

Eric Blais, Joshua Brody, Kevin Matulef

We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a simple scheme for reducing communication problems to testing problems, thus allowing us to use known lower bounds in communication complexity to prove lower bounds in ... more >>>

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio

This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x)=sgn(w ⋅ x - θ). We consider halfspaces over the continuous domain R^n (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1,1}^n ... 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 >>>