In 1982 Linial and Berge conjectured that there is some form of
duality between partitioning the vertices of a directed graph to
disjoint paths and finding a big set of vertices in it with a small
chromatic number. In the talk I will discuss the...
Pseudo-random generators that are secure against constant depth
polynomial size circuits have been known since the seminal paper by
Ajtai and Wigderson (1985). All available constructions of such
generators, however, appear to be somewhat special...
