In this talk, we will consider algorithmic problems which follow the following template: given a real-valued multivariate polynomial f(x) of degree d, is it approximately equal to a sum of a few "simple" polynomials, i

Abstract:  The task of manipulating randomness has been a subject of intense investigation in computational complexity with dispersers, extractors, pseudorandom generators, condensers, mergers being just a few of the objects of interest.

Abstract: The classical Ulam’s problem asks about the length of a longest increasing subsequence in a uniform random permutation.

Abstract: The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. Approximate degree is known to be a lower bound on quantum query complexity.

Abstract: Graph partitioning problems are a central topic of research in the study of algorithms and complexity theory.