Posts

A Mathematical Theory of Communication In 1948, Claude E. Shannon, while working in Bell Labs published his paper “A Mathematical Theory of Communication”. Shannon was interested in modeling the English language. In his paper, he assumed that the English language has a 27-symbol alphabet of 26 letters and a space. He tried to model it using stochastic processes. The simplest stochastic process to model English is a process where each symbol is sampled equiprobably and independently....

Introduction Suppose you want to model the dynamics of a gas inside a box. We model the gas as a bunch of molecules, which can hit each other and the box they are enclosed in. We consider the situation in which there is no loss of energy (elastic collisions, friction, heat, etc.). We can write physical equations of motions to model this gas. The problem is that the number of balls is enormous, and we cannot describe the position and momentum of each particle....

Lower Bounds Computer scientists are interested in proving lower bounds for their algorithms. Lower bounds are important because they give algorithm designers some metric about how efficient their algorithms can be. Computer scientists are usually interested in showing lower bounds for the running time of Turing Machines, which are computational models that emulate how our computers work (with some “small” overhead). Non-Uniform Circuits As is the usual motif in theoretical computer science, showing lower bounds for Turing Machines is considered difficult, and computer scientists have found it easier to analyse lower bounds in the setting of non-uniform circuits....