Impagliazzo’s Hardcore Lemma and Computational Hardness

We wish to compute boolean functions by circuits, or more generally, compositions of simple boolean functions (gates). Suppose we are given a function which is hard to approximate by any small-size circuit. That is, any small-size circuit fails to compute the given function on certain fraction (say 1/10) of the inputs. There could be two possibilities:

  1. There is a subset of the inputs (say 1/5 fraction of the inputs) such that, when the function is restricted to these inputs, any small-size circuit fails to compute on almost 1/2 of these inputs.
  2. Different circuits fails to computes the function on different subsets of the inputs.

Impagliazzo Hardcore Lemma says that every hard function has the first case. That is, every hard function has a hardcore subset such that the restricted function becomes extremely hard to compute.

Definition. We say a function \(f\colon\{0,1\}^n\to\{0,1\}\) is \(\delta\)-hard for circuits of size \(s\) if, for any circuit \(C\) of size at most \(s\), it fails to compute \(f\) on at least \(\delta\) fraction of the inputs. That is, for \(x\sim \{0,1\}^n\),
\[
Pr [C(x) \neq f(x)] \geq \delta.
\]

Definition. We say a distribution \(D\) over \(\{0,1\}^n\) is has density \(\delta\) if for every \(x\in \{0,1\}^n\), we have \(Pr[D = x] \leq 1/ \delta 2^{n}\).

For example, a uniform (flat) distribution over a subset of size \(2^n/10\) has density \(1/10\). It is easy to see that, a convex combination of \(\delta\)-density distributions is also a \(\delta\)-density distribution.

Hardcore Lemma (Distribution Format). Let \(f\) be a \(\delta\)-hard function for circuits of size \(s\). Then there exists a \(\delta\)-density distribution such that, for any circuit of size \(s’ \leq \epsilon^2 s/100n\),
\[
Pr [C(x) \neq f(x)] \geq 1/2 – \epsilon.
\]

Proof.
Let \(f\) be a \(\delta\)-hard function. Consider a two-player game where in each round:

  • Player A chooses a \(\delta\)-density distributions \(D\).
  • Player B chooses a size-\(s’\) circuit \(C\).

The payoff from Player A to Player B is \(Pr [C(x) = f(x)]\) where \(x\sim D\). Player A tries to come up with a distribution that is hard to approximate by size-\(s’\) circuits. Player B tries to maximize the payoff by giving a circuit computing \(f\) well with respect to the distribution from Player A.

For contradiction, we assume that

  • for every \(\delta\)-density distribution \(D\) (chosen by Player A),
  • there exists a circuit \(C\) (found by Player B), such that

\[
Pr [C(x) \neq f(x)] < 1/2 - \epsilon.
\]
We wish to construct a circuit which computes \(f\) well, contradicting the \(\delta\)-hardness of \(f\).

Since this is a zero-sum game, we can apply von Neumann’s Min-Max Theorem and get the following:

  • there exists a distribution \(\mathcal{C}\) over \(s’\)-size circuits, such that
  • for every distribution \(\mathcal{D}\) over \(\delta\)-density distributions,

\(Pr [C(x) \neq f(x)] < 1/2 - \epsilon\), where \(x \sim D \sim \mathcal{D}\) and \(C\sim \mathcal{C}\).

Since a distribution over \(\delta\)-density distributions also gives a \(\delta\)-density distribution, it is equivalent to say that,

  • there exists a distribution \(\mathcal{C}\) over \(s’\)-size circuits, such that
  • for every \(\delta\)-density distribution \(D\),

\(Pr [C(x) \neq f(x)] < 1/2 - \epsilon\) where \(x \sim D\) and \(C\sim \mathcal{C}\).

Note that, the distribution \(\mathcal{C}\) works for any \(\delta\)-density distribution.

To construct a circuit approximating \(f\) well, we just need to sample a sequence of circuits from \(\mathcal{C}\) independently, and take the majority.

……

Tagged with: ,
Posted in Theory

Searching and Replacing with grep and sed

Unix commands grep and sed can be used to efficiently search and replace strings in a file, a directory, or files acrose multiple directories. Specifically, grep is used to search for a certain string, and sed is used to replace the strings.

Search using grep

grep -l somematchstring somefile.txt

This command searches somematchstring in the file somefile.txt. The option -l means it will print names of files containing matches.

grep -rl somematchstring somedir/

This command searches somematchstring in all files under the directory somedir. The option -l again means it will print names of files containing matches. The option -r means it will go recursively into all subdirectories.

grep -l somematchstring somedir/*.java

This searches somematchstring in all .java files under the directory somedir.

Search and Replace using sed

grep -rl somematchstring somedir/ | xargs sed -i 's/somematchstring/somereplacestring/g'

The grep command will list all files under the directory somedir/ containing somematchstring. The file names are passed on through the pipe ‘|’ delimiter. Then the sed command will replace somematchstring by somereplacestring.

Note that the grep command will pipe only files matching somematchstring to sed. The pipe ‘|’ delimiter is efficient when searching through a lot of files.

The following is another example.

grep -rl 'Windows' ./ | xargs sed -i 's/Windows/Linux/g'

This will search for ‘Windows’ in all files under the current directory, and replace ‘Windows’ by ‘Linux’ for each occurrence ‘Windows’ in each file.

Tagged with: ,
Posted in DevTool

Turn Off Voice Assistant on Apple Mac

VoiceOver, as a voice assistant, provides spoken description of items on the screen. The following are two ways of turning on/off VoiceOver.

Toggle VoiceOver

Use ⌘ Cmd + F5 to toggle on/off VoiceOver.

Enable/disable VoiceOver from the menu

Open System Preferences > Accessibility > VoiceOver. Click to turn if on/off.

Tagged with: ,
Posted in HowTo

A Double Sum of Binomials

Prove the following summation of binomial coefficients.
\[
\sum_{i=0}^n \sum_{j=0}^m {i+j \choose j} = {n + m +2 \choose n+1} - 1.
\]

First, by Pascal’s rule that \({i+j \choose j} = {i+j-1 \choose j} + {i+j-1 \choose j-1} \), the inner summation
\[
\sum_{j=0}^m {i+j \choose j} = {i+m+1 \choose m}.
\]

Similarly,
\[
\sum_{i=0}^n {i+m+1 \choose m} = \sum_{i=0}^n {i+m+1 \choose i+1}
= \sum_{i=0}^{n+1} {i+m+1 \choose i} - 1
= {n+m+2 \choose n+1} - 1.
\]

Tagged with:
Posted in Combinatorics