Kevin Matulef

SODA Conference 2009 Conference Paper

Testing halfspaces

• Kevin Matulef
• Ryan O'Donnell
• Ronitt Rubinfeld
• Rocco A. Servedio

FOCS Conference 2007 Conference Paper

Testing for Concise Representations

• Ilias Diakonikolas
• Homin K. Lee
• Kevin Matulef
• Krzysztof Onak
• Ronitt Rubinfeld
• Rocco A. 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. 16 with ideas from learning theory, and yields property testers that make po! y(s/epsiv) queries (independent of n) for Boolean function classes such as s-term DNF formulas (answering a question posed by Parnas et al. [12]), sizes. decision trees, sizes Boolean formulas, and sizes Boolean circuits. The method can be applied to non-Boolean valued function classes as well. This is achieved via a generalization of the notion of van at ion/row Fischer et al. to non-Boolean functions. Using this generalization we extend the original junta test of Fischer et al. to work for non-Boolean functions, and give poly(s/e)-query testing algorithms for non-Boolean valued function classes such as sizes algebraic circuits and s-sparse polynomials over finite fields. We also prove an Omega(radic(s)) query lower bound for nonadaptively testing s-sparse polynomials over finite fields of constant size. This shows that in some instances, our general method yields a property tester with query complexity that is optimal (for nonadaptive algorithms) up to a polynomial factor.

STOC Conference 2007 Conference Paper

Testing k-wise and almost k-wise independence

• Noga Alon
• Alexandr Andoni
• Tali Kaufman
• Kevin Matulef
• Ronitt Rubinfeld
• Ning Xie 0002

In this work, we consider the problems of testing whether adistribution over (0,1 n ) is k -wise (resp. (ε,k)-wise) independentusing samples drawn from that distribution. For the problem of distinguishing k -wise independent distributions from those that are δ-far from k -wise independence in statistical distance, we upper bound the number ofrequired samples by Õ(n k /δ 2 ) and lower bound it by Ω(n k-1/2 /δ) (these bounds hold for constant k , and essentially the same bounds hold for general k ). Toachieve these bounds, we use Fourier analysis to relate adistribution's distance from k -wise independence to its biases, a measure of the parity imbalance it induces on a setof variables. The relationships we derive are tighter than previouslyknown, and may be of independent interest. To distinguish (ε,k)-wise independent distributions from thosethat are δ-far from (ε,k)-wise independence in statistical distance, we upper bound thenumber of required samples by O(k log n / δ 2 ε 2 ) and lower bound it by Ω(√ k log n / 2 k (ε+δ)√ log 1/2 k (ε+δ)). Although these bounds are anexponential improvement (in terms of n and k ) over thecorresponding bounds for testing k -wise independence, we give evidence thatthe time complexity of testing (ε,k)-wise independence isunlikely to be poly(n,1/ε,1/δ) for k=Θ(log n),since this would disprove a plausible conjecture concerning the hardness offinding hidden cliques in random graphs. Under the conjecture, ourresult implies that for, say, k = log n and ε = 1 / n 0.99 ,there is a set of (ε,k)-wise independent distributions, and a set of distributions at distance δ=1/n 0.51 from (ε,k)-wiseindependence, which are indistinguishable by polynomial time algorithms.