👋 Welcome to Theoreticles

Consider the following problem: If $A$ is any language, let $\sqrt{A}$ denote the set of first halves of strings in $A$, where both the first and second halves are identical $$\sqrt{A} = {x \mid \mbox{$xx \in A$}}$$ Show that if $A$ is regular, then so is $\sqrt{A}$. Proof Sketch Before trying to come up with a solution to this problem, let us understand what we can deduce simply from the problem statement:...

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....

Introduction In many areas of theoretical computer science, we come across various problems where we can exploit structures in the problem to obtain quantum speedups over known classical algorithms. Examples of this include the famous Shor’s algorithm (Shor95 1) which allows us to compute discrete log or factor integers efficiently, while there are no known classical algorithms that do the same. In this vein, the central question addressed by CMP22 2 is as follows:...

This post assumes basic familiarity with Turing machines, P, NP, NP-completeness, decidability, and undecidability. Don’t hesitate to contact me via email if you need further clarification. Without further ado, let’s dive in. Introduction Why do we need 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!’ at a time. Romantic as these anecdotes may be, for mathematics, we can hardly look to Mother Nature for providing us the key insight to our proofs....