Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Composition Theorems:
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 >>>

TR24-016 | 27th January 2024
Swagato Sanyal

Randomized query composition and product distributions

Let R_eps denote randomized query complexity for error probability eps, and R:=R_{1/3}. In this work we investigate whether a perfect composition theorem R(f o g^n)=Omega(R(f).R(g)) holds for a relation f in {0,1}^n * S and a total inner function g:{0,1}^m \to {0, 1}.

Let D^(prod) denote the maximum distributional query ... more >>>

ISSN 1433-8092 | Imprint