Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with One-Sided Error vs Two-Sided Error:
TR13-067 | 2nd May 2013
Oded Goldreich

On Multiple Input Problems in Property Testing

Revisions: 1

We consider three types of multiple input problems in the context of property testing.
Specifically, for a property $\Pi\subseteq\{0,1\}^n$, a proximity parameter $\epsilon$, and an integer $m$, we consider the following problems:

\item Direct $m$-Sum Problem for $\Pi$ and $\epsilon$:
Given a sequence of $m$ inputs, output a sequence ... more >>>

TR18-171 | 10th October 2018
Oded Goldreich

Testing Graphs in Vertex-Distribution-Free Models

Revisions: 1

Prior studies of testing graph properties presume that the tester can obtain uniformly distributed vertices in the tested graph (in addition to obtaining answers to the some type of graph-queries).
Here we envision settings in which it is only feasible to obtain random vertices drawn according to an arbitrary distribution ... more >>>

TR20-068 | 3rd May 2020
Oded Goldreich, Dana Ron

One-Sided Error Testing of Monomials and Affine Subspaces

Revisions: 1

We consider the query complexity of three versions of the problem of testing monomials and affine (and linear) subspaces with one-sided error, and obtain the following results:
\item The general problem, in which the arity of the monomial (resp., co-dimension of the subspace) is not specified, has ... more >>>

ISSN 1433-8092 | Imprint