Computer scientists devise randomized algorithms when they cannot find good deterministic ones. Then they try to decrease the randomness used and still try to prove that the algorithm answers correctly with high probability.
In a landmark paper, Papadimitriou introduced several syntactic subclasses of the search class TFNP (Total Function Nondeterministic Polynomial) based on proof styles that (unlike TFNP) admit complete problems.
We will discuss a lower bound (due to Noga Alon) on the rank of any real matrix in which all the diagonal entries are significantly larger (in absolute value) than all the other entries.
We will see the definition of Probably Approximately CORRECT Learning. Then we will prove that its easy to learn about Rectangles and Conjunctions but hard to learn about 3-Term Disjunctions.
In a short span in the 1940's Claude Shannon established the fields of information theory and modern cryptography which lie at the foundation of the digital era.
