Finding the longest increasing subsequence (LIS) is a classic algorithmic problem. Simple O(n log n) algorithms, based on dynamic programming, are known for solving this problem exactly on arrays of length n.

We consider the following two questions:

The small-set expansion conjecture introduced by Raghavendra and Steuerer is a natural hardness assumption concerning the problem of approximating edge expansion of small sets (of size $\delta n$) in graphs. It was shown to be intimately connected to the well-known Unique Games Conjecture.

Pursuing this line of research further, we obtain the following results:

The Stepanov method is an elementary method for proving bounds on the number of roots of polynomials. At its core is the following idea. To upper bound the number of roots of a polynomial f(x) in a field, one sets up an auxiliary polynomial F(x) , of (magically) low degree, which vanishes at the roots of f with high multiplicity. That appropriate F exits is usually proved by a dimension argument.

An epsilon-biased set X in {0,1}ⁿ is a set so that for every non-empty set T in [n] the following holds. The random bit B(T) obtained by selecting at random a vector x in X, and computing the mod-2 sum of its T-coordinates, has bias at most epsilon. Such sets may be viewed as generating matrices of binary error correcting codes of distance (1/2 - epsilon), as well as pseudorandom sets in the sense that all their nontrivial Fourier coefficients are at most epsilon in absolute value.

A beautiful conjecture of Erd\H{o}s-Simonovits and Sidorenko states that if H is a bipartite graph, then the random graph with edge density p has in expectation asymptotically the minimum number of copies of H over all graphs of the same order and edge density. This conjecture also has an equivalent analytic form and has connections to a broad range of topics, such as matrix theory, Markov chains, graph limits, and quasirandomness.