👋 Welcome to Theoretickles

A Prelude to this post I was introduced to the notion of the trace of a square matrix as early as the eleventh grade, but never fully appreciated the nuances attached to this seemingly innocuous concept until I took a second course in Linear algebra! Funnily, the reason I even took the second course was because I was struggling the intuition behind certain concepts such as density matrices and measurements in basic quantum computing and quantum information theory!...

In this post, we discuss an important class of algebraic structures known as $q$-ary lattices that are central to lattice-based cryptographic primitives. Hardness of problems Computational hardness usually revolves around problems with worst-case hardness guarantees since we want to design algorithms that run efficiently even on the worst possible input. On the other hand, cryptographic schemes require security guarantees for random keys. Therefore, cryptographic applications require problems with average-case hardness guarantees....

This post assumes basic familiarity with Turing machines, P, NP, NP-completeness, decidability, and undecidability. The reader is referred to the book by Sipser, or the book by Arora and Barak for any formal definitions that have been skipped in this post. Without further ado, let’s dive in. This is the second part of an earlier post on Self Reductions . Since the two posts are meant to be perused in order, please check out the earlier post for any definitions/concepts not covered in this post....

This post assumes basic familiarity with Turing machines, P, NP, NP-completeness, decidability, and undecidability. The reader is referred to the book by Sipser, or the book by Arora and Barak for any formal definitions that have been skipped in this post. Without further ado, let’s dive in. Introduction Preliminaries: Search and Decision Problems In an earlier post, we familiarised ourselves with the notion of reductions . Towards the end, we introduced the notion of self-reducibility which is our main topic of focus today....

This post assumes basic familiarity with Turing machines, P, NP, NP-completeness, decidability, and undecidability. The reader is referred to the book by Sipser, or the book by Arora and Barak for any formal definitions that have been skipped in this post. Without further ado, let’s dive in. Introduction The What and Why of reductions? From Archimedes terrorizing the good folk of ancient Syracuse to Newton watching apples fall during a medieval plague, science has always progressed one ‘Eureka!...