Computer Science and Discrete Mathematics (CSDM)

Monotone submodular maximization over a matroid (MSMM) is a fundamental optimization problem generalizing Maximum Coverage and MAX-SAT. Maximum Coverage is NP-hard to approximate better than \(1-1/e\), an approximation ratio obtained by the greedy...

In distributed systems, communication between the participants in the computation is usually the most expensive part of the computation. Theoretical models of distributed systems usually reflect this by neglecting the cost of local computation, and...

Let \(G\) be a finite group, and let \(a\), \(b\), \(c\),... be independent random elements of \(G\), chosen at uniform distribution. What is the distribution of the element obtained by a fixed word in the letters \(a\), \(b\), \(c\),..., such as \...

Two important breakthroughs on the permanent had been accomplished in 1998: A. Schrijver proved Schrijver-Valiant Conjecture on the minimal exponential growth of the number of perfect matchings in k-regular bipartite graphs with multiple edges; N...

Let \(G\) be a finite group, and let \(a\), \(b\), \(c\),... be independent random elements of \(G\), chosen at uniform distribution. What is the distribution of the element obtained by a fixed word in the letters \(a\), \(b\), \(c\),..., such as \...

The chromatic number \(k(G)\) of a graph \(G\) is always at least the size of its largest clique (denoted by \(w(G)\)), and there are graphs with \(w(G)=2\) and \(k(G)\) arbitrarily large. On the other hand, the perfect graph theorem asserts that if...

In this talk, we will continue, the proof of the Central Limit theorem from my last talk. We will show that that the law of "eigenregular" Gaussian polynomials is close to a Gaussian. The proof will be based on Stein's method and will be dependent...

In the last few years, there has been a lot of activity in the area of structural analysis and derandomization of polynomial threshold functions. Tools from analysis and probability have played a significant role in many of these works. The focus...

A planar set that contains a unit segment in every direction is called a Kakeya set. These sets have been studied intensively in geometric measure theory and harmonic analysis since the work of Besicovich (1919); we find a new connection to game...

I will survey recent results and open problems in several areas of quantum complexity theory, with emphasis on open problems which can be phrased in terms of classical complexity theory or mathematics but have implications for quantum computing: 1...