Révision 216 CSL17/preliminaries.tex
| preliminaries.tex (revision 216) | ||
|---|---|---|
| 199 | 199 |
$$ \size{f(\vec u; \vec x)} \leq q(\size{u_1} , \dots , \size{u_k}) + \max_j \size{x_j}.$$
|
| 200 | 200 |
\end{definition}
|
| 201 | 201 |
|
| 202 |
We define the function $\mode$ by $u\mode x:= u \mod 2^{\size{x}}$.
|
|
| 202 |
We define the function $\mode$ by $u\mode x:= u \mod 2^{\size{x}}$. Note that this means that as a binary string $u\mode x$ is the suffix of $u$ of length $\size{x}$.
|
|
| 203 | 203 |
\begin{definition}
|
| 204 | 204 |
A function $f(\vec u; \vec x)$ is a \textit{polynomial checking function} on $\vec u$ if there exists a polynomial $q$
|
| 205 | 205 |
such that, for any $\vec u$, $\vec x$, $y$ and $z$ such that $\size{y} \geq q(\size{\vec u})+ \size{z}$ we have:
|
Formats disponibles : Unified diff