I explain the 3SUM problem, which an O(n^(2-ε)) solution has not been found for a long time. Based on the seminal paper by Gajentaan and Overmars, I give reductions from the 3SUM problem to various problems in computational geometry. This demonstrates the 3SUM-hardness of the problems discussed in this talk.
We investigate the orthogonal range searching problem in multidimensional settings. Given n points in a d-dimensional space, the problem is to preprocess the points so that we can answer axis-parallel hyperrectangular queries asking for all points inside the hyperrectangle in sublinear time. We study data structures called the kd-tree and the range tree, and learn how we can use the data structures to solve the orthogonal range searching problem.
We study the JPEG algorithm, which is a lossy image compressing scheme. We investigate the Discrete Cosine Transform and the Karhunen-Loeve Transform from the information theory perspective, which is essential in understanding the JPEG algorithm.
We study the Rate Distortion Theory, which describes the relation between rate and distortion in a lossy encoding setting. Specifically, we focus on proving that the infimum of all achievable rates given an input distribution and a target distortion is equal to the output of the information rate distortion function. We study algorithms to compute the information rate distortion function.
We study Shor’s algorithm, which allows us to factorize numbers in polynomial time using a quantum computer. The scheme consists of two parts, a quantum circuit for computing the order of an element in a multiplicative group modulo some number, and a non-quantum probabilistic algorithm that uses the quantum circuit as a module.
We focus on auction mechanisms that maximizes the seller’s profit, i.e. “optimal” mechanisms. We study Myerson’s Theorem, which allows us to design such optimal mechanisms through various characterizations.