this is for holding javascript data
Sean Geronimo Anderson edited untitled.tex
over 8 years ago
Commit id: ffb6e97b91ed6d9141c8b67f494c2f016b7cebcf
deletions | additions
diff --git a/untitled.tex b/untitled.tex
index bd20bc1..fe32b2b 100644
--- a/untitled.tex
+++ b/untitled.tex
...
untitled.tex
\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{amsfonts}
\newcounter{qnum}
\newcommand{\question}[1]{\stepcounter{qnum}\bigskip\noindent{\bf \arabic{qnum}. #1}}
\newcommand{\rand}{\textsf{R}}
\newcommand{\E}{\mathop{\textrm{E}}}
\newcommand{\np}{\textsf{NP}}
\begin{document}
\begin{center}
{\Large \bf CSci 5403, Fall 2015}
\end{center}
{\bf Homework 6} \hfill {\bf due: December 7, 2015}
\medskip
\hrule
\medskip
\noindent
\newcommand{\bpnp}{\textsf{BP}\cdot\textsf{NP}}
\question{Where you bin?} Bin packing is an optimization problem that
models the situation of someone packing items into bins, with the goal
of minimizing the number of bins used. Formally, a \textsc{binpack}
...
\item[(b)] Give a very simple algorithm that yields a
$2$-approximation, e.g. it uses at most twice as many bins as the
optimal solution.
\end{itemize}
\question{Adopting adaptiveness.} One property of an $(r,q)$-verifier
that was not explicitly mentioned in Lecture 21 is whether its oracle
queries are {\em adaptive}, e.g., whether the value of the
$i^{\text{th}}$ query depends on the results of the first $i-1$
queries. Our proof that the PCP theorem is equivalent to the
existence of a gap-producing reduction from \textsc{3sat} to
\textsc{max-3sat} actually relies on a non-adaptive verifier (e.g. the
proof locations that it queries are a fixed function of the input $x$
and random string $s$). Prove that when $q(n)=O(1)$ this distinction
is not very important: every adaptive $(r,q)$-verifier can be
simulated by a nonadaptive $(r,2^q)$ verifier.
\question{Linearity Testing.} Suppose that the function $f : \{0,1\}^n
\to \{0,1\}$ satisfies the linearity test over $GF(2)$ with
probability $1-\epsilon$, i.e. $\Pr_{x,y}[f(x)+f(y)=f(x+y)] \geq
1-\epsilon$.
\begin{itemize}
\item[(a)] Prove that for any fixed $z$,
$\Pr[f(z+r_1)+f(r_1)=f(z+r_2)+f(r_2)] \geq 1 - 2\epsilon$. (Hint:
suppose $f(r_1)+f(r_2) = f(r_1+r_2)$; what is the relationship
between $f(z+r_1)$ and $f(z+r_2)$?)
\item[(b)] Show that for every $z \in \{0,1\}^n$, there exists a
value $f'(z)$ such that $\Pr_r[f(z+r)+f(r)=f'(z)] \geq \frac{1}{2} +
\sqrt{\frac{1}{4}-\epsilon}$. (so the probability tends to 1 as
$\epsilon$ approaches zero)
\end{itemize}
\question{Fool me once\dots} Define the function $f_{\textsf{MAJ}} :
\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ to return $1$ iff at least
$n+1$ bits of its input are 1. Give a fooling set of size $n$ for
$f_{\textsf{MAJ}}$.
\vfill
\end{document}