Computer Science/Discrete Mathematics

Efficient verification of computation is fundamental to computer science and is at the heart of the P vs. NP question. Recently it has had growing practical significance, especially with the increasing popularity of blockchain technologies and cloud...

Suppose we are given matchings $M_1,....,M_N$ of size t in some r-uniform hypergraph, and let us think of each matching having a different color. How large does N need to be (in terms of t and r) such that we can always find a rainbow matching of...

Tree decompositions are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”. Exhibiting a particular kind of a tree...

In the minimum cost set cover problem, a set system is given as input, and the goal is to find a collection of sets with minimum cost whose union covers the universe. This NP-hard problem has long been known to admit logarithmic approximations...

Randomness is a vital resource in computation, with many applications in areas such as cryptography, data-structures and algorithm design, sampling, distributed computing, etc. However generating truly random bits is expensive, and most sources in...