Uncategorized – Weekly Mathematics

Proof of the Sensitivity Conjecture without Cauchy’s Interlacing Theorem

If you aren’t aware, one month ago, the Sensitivity Conjecture, a 30-year old problem, was proven by Hao Hung, an assistant professor at Emory University in just a little more than 2 pages using particularly simple methods albeit cleverly implemented. The proof is very easy to understand and requires nothing more than basic linear algebra. You can find it here.

A few days ago, Donald Knuth simplified the already simple proof of H. Hung and could fit all his arguments in half a page. What really shocked me when I heard the news is that Knuth is still alive. I could have sworn that it was only a few days ago when I was skimming through a textbook on Discrete Mathematics and saw a bio with a black-and-white pic of him in one of the chapters related to computational complexity in the same manner that I’d see pictures and mini-biographies of other 20th century giants such as Grothendieck and Nash relegated to the margins of math textbooks and online articles romantically detailing the course of their fabled lives.

Now that I’ve realized that he’s well and alive, it shocks me equally to learn that at the age of 81, he is still able to contribute to research.

I’m not exactly going to regurgitate Knuth’s proof but what I’ll present certainly uses the same ideas. I must note here than Knuth’s proof itself is inspired by a comment on Scott Aronson’s blog which provided a method to prove the conjecture without using Cauchy’s Interlacing Theorem.

If you don’t know what the Sensitivity Conjecture, I’ll state it below.

If $f:\{0,1\}^{n} \mapsto \{0,1 \}$ is a boolean function where the domain is the graph of the $n-dimensional$ cube denoted by $Q^{n}=\{0,1 \}^{n}$ . So, a particular input $x$ is just a string of 0s and 1s. The local sensitivity of $f$ at an input $x$ is the number of indices in the ‘string’ of $x$ that you can flip and not change the output. The local block sensitivity of $f$ at input $x$ is the number of disjoint subsets of the set of indices $\{0,1,2 \cdots, n \}$ such that the output doesn’t change when every index corresponding to a block flips in the input string of $x$ . The sensitivity and block sensitivity are defined to be the maximum of these corresponding measures over all the inputs.

Continue reading “Proof of the Sensitivity Conjecture without Cauchy’s Interlacing Theorem”

Topological Constraints on the Universal Approximation of Neural Networks

The title may seem like a contradiction given that there is such a thing as the Universal Approximation Theorem which simply states that a neural network with a single hidden layer of finite width(i.e finite number of neurons) can approximate any function on a compact set of $\mathbb{R}^{n}$ given that the activation function is non-constant,bounded and continuous.

Needless to say, I haven’t found any kind of flaws in the existing proofs(see Kolmogrov or Cybenko). However, I thought of something a little simple and scoured the internet for an answer.

What if we allow an arbitrary number of hidden layers and bound the dimension of the hidden layers making them ‘Deep, Skinny Neural Networks’? Would that be a universal approximator?

Continue reading “Topological Constraints on the Universal Approximation of Neural Networks”

The logarithmic spiral

The logarithmic spiral has some very interesting properties and Bernoulli was especially fascinated by it.I’ll prove it’s most important property(the angle between the curve and the radius at every angle is constant) and proceed with an example.

In polar co-ordinates,the equation of the spiral is given by:

$r(\theta)=ae^{k\theta}$ where $a,k$ are constants and $a>0$

Now,to prove that any line from the origin which intersects the curve does so by making a constant angle(say $\phi$ ) with the curve(direction of tangent line),we consider the derivatives of the parameter equations which correspond to $r(\theta)$

Continue reading “The logarithmic spiral”