Computer Science and Discrete Mathematics (CSDM)

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...

Abstract:
We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. In particular, we show:
(1) The sparsity achieved by [Kane-Nelson, SODA 2012] in the sparse Johnson-Lindenstrauss lemma is optimal...

For a set of polynomials F, we define their bilinear complexity as the smallest k so that F lies in an ideal generated by k bilinear polynomials. The main open problem is to estimate the bilinear complexity of the single polynomial $\sum_{i,j}x_i^2...

We will give an overview of this system, which has been at the center of recent algorithmic and proof complexity developments. We will give the definitions of the system (as a proof system for polynomial inequalities, and as an SDP-based algorithm)...