Suppose you have a set S of integers from {1 , 2 , … , N} that
contains at least N / C elements. Then for large enough N , must S
contain three equally spaced numbers (i.e., a 3-term arithmetic
progression)?
A central goal of physics is to understand the low-energy
solutions of quantum interactions between particles. This talk will
focus on the complexity of describing low-energy solutions; I will
show that we can construct quantum systems for which the...
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...
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...
