Computer Science and Discrete Mathematics (CSDM)
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.
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:
*It is not from the benevolence of the butcher, the brewer, or the baker, that we expect our dinner, but from their regard for their own interest. Each participant in a competitive economy is led by an invisible hand to promote an end which was no part of his intention.*
Adam Smith, 1776
The cover time of a graph is one of the most basic and well-studied properties of the simple random walk, and yet a number of fundamental questions concerning cover times have remained open. We show that there is a deep connection between cover times of graphs and Talagrand's majorizing measure theory. In particular, we prove that the cover time can be characterized, up to universal constants, by the majorizing measure value of a certain metric space on the underlying graph.