Probabilistically Checkable Proofs

Every statement that has a polynomial time checkable proof has such a proof where the verifier only reads \(O(1)\) (constant) bits of the proof such hat…

• perfect completeness: correct statements will be accepted with probability 1
• soundness: false statements will be rejected with probability 0.99 (with epsilon as the reading constant increases)

PCP Theorem

For some constant \(\alpha > 0\), and for ever language \(L \in NP\), there exists a polynomial-time that makes every input \(x\) into a \(f(x)\) such that…

If we take entangled qubits, and separate them real far away, their behavior would be the same even despite it will take longer for light to travel.

Background

In the 60s, economists that the pricing of options were independent of pricing of underlying assets. Nowadays, we can see that, if the underlying assets were obeying of a Brownian Motion, there is no additional degree of freedom that options can bring: that knowing the stocks will tell you exactly through a DiffEQ how the option will evolve.

The idea, then, is that you can replicate options: by dynamically buying and selling pairs of securities in the same way as the option, your new portfolio can track the option exactly.

function that returns the input that maximizes the expression.

finding argmax

direct optimization

Typical maximization system. Take derivative, set it to 0, solve, plug in, solve. THis is pretty bad during times are not differentiable.

gradient ascent

We take steps following the direction

\begin{equation} \theta_{1j} = \theta_{0j} + \eta \pdv{LL(\theta_{0})}{\theta_{0j}} \end{equation}

additional information

argmax of log

see argmax of log