Computer Science and Discrete Mathematics (CSDM)

Since the foundational results of Thomason and Chung-Graham-Wilson on quasirandom graphs over 20 years ago, there has been a lot of effort by many researchers to extend the theory to hypergraphs. I will present some of this history, and then...

I will survey some of the basic approaches to derandomizing Probabilistic Logspace computations, including the "classical" Nisan, Impagliazzo-Nisan-Widgerson and Reingold-Raz generators, the Saks-Zhou algorithm and some more recent approaches. We'll...

Polar codes have recently emerged as a new class of low-complexity codes achieving Shannon capacity. This talk introduces polar codes with emphasis on the probabilistic phenomenon underlying the code construction. New results and connections to...

I will describe the very recent breakthrough result by Gupta, Kamath, Kayal and Saptharishi which shows that every polynomial P in n variables, of degree d which is polynomial in n, and which can be computed by a polynomial sized arithmetic circuit...

Expander graphs, in general, and Ramanujan graphs, in particular, have been objects of intensive research in the last four decades. Many application came out, initially to computer science and combinatorics and more recently also to pure mathematics...

With the notion of interaction with oracles as a unifying theme of much of my dissertation work, I discuss novel models and results for property testing and computational learning, with the use of Fourier analytic and probabilistic methods.
One...

https://www.ias.edu/math/files/seminars/MendelAbst.pdf

I will describe some recent results and problems regarding influence of sets of variables on Boolean functions: In 1989 Benny Chor conjectured that a balanced Boolean function with n variables has a subset S of size 0.4n with influence (1-c^n) where...

A linear property of Banach spaces is called "local" if it depends on finite number of vectors and is invariant under renorming (i.e., distorting the norm by a finite factor). A famous theorem of Ribe states that local properties are invariant under...

We study the problem of constructing extractors for independent weak random sources. The probabilistic method shows that such an extractor exists for two sources on n bits with min-entropy k >= 2 log n. On the other hand, explicit constructions are...