Computer Science and Discrete Mathematics (CSDM)

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

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

Robust sublinear expansion represents a fairly weak notion of graph expansion which still retains a number of useful properties of the classical notion. The general idea behind it has been introduced by Komlós and Szemerédi around 25 years ago and...

Suppose we are given matchings M1,....,MN 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 size t...

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

In this talk, I'll first give a broad overview of the history of combinatorial auctions within TCS, and then discuss some recent results.

Combinatorial auctions center around the following problem: There is a set M of m items, and N of n bidders...

et K be a convex body in Rn. In some cases (say when K is a cube), we can tile Rn using translates of K. However, in general (say when K is a ball) this is impossible. Nevertheless, we show that one can always cover space "smoothly" using translates...

Graph Crossing Number is a fundamental and extensively studied problem with wide ranging applications. In this problem, the goal is to draw an input graph G in the plane so as to minimize the number of crossings between the images of its edges. The...

Determining the complexity of matrix multiplication is a fundamental problem of theoretical computer science. It is popularly conjectured that matrices can be multiplied in nearly-linear time. If true, this conjecture would yield similarly-fast...

A Locally Decodable Codes (LDC) is an error correcting code which allows the decoding of a single message symbol from a few queries to a possibly corrupted encoding.  LDCs can be constructed, for example, from low degree polynomials over a finite...