deletions | additions       diff --git a/documentclass_12pt_article_usepackage_fullpage__.tex b/documentclass_12pt_article_usepackage_fullpage__.tex  deleted file mode 100644  index dac61b3..0000000  --- a/documentclass_12pt_article_usepackage_fullpage__.tex  +++ /dev/null 
...
\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}  instance is a set of lengths $(a_1,\dots,a_n)$ and a capacity $C$, and  a solution is a set of bins $\{B_1, \dots, B_j\}$ where each $B_i  \subseteq [n]$, $B_i \cap B_j = \emptyset$ and $\bigcup_i B_i = [n]$,  such that for all $j$, $\sum_{i \in B_j} a_i \leq C$.  \begin{itemize}  \item[(a)] The \textsc{binpack} decision problem is: given a  \textsc{binpack} instance and a number $k$, is there a solution  using $k$ or fewer bins? Prove, for fun, that the decision version  is \textsf{NP}-complete.    \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}  diff --git a/layout.md b/layout.md  index 4a38da0..09fc807 100644  --- a/layout.md  +++ b/layout.md 
...
untitled.tex  documentclass_12pt_article_usepackage_fullpage__.tex