Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

The communication complexity of distributed subgraph detection

Rotem Oshman
Tel Aviv University
October 6, 2014
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 charging only for messages sent between the participants; in particular, we usually assume that the computation proceeds in rounds, and in each round each participant can send only a limited number of bits. We are interested in characterizing the number of rounds required to perform various tasks.

Uniform words are primitive (cont'd)

Doron Puder
Member, School of Mathematics
September 30, 2014
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 \(ab\), \(a^2\), or \(aba^{-2}b^{-1}\)? More concretely, do these new random elements have uniform distribution?

In general, a word \(w\) in the free group \(F_k\) is called uniform if it induces the uniform distribution on every finite group \(G\). So which words are uniform?

Breaking \(e^n\) barrier for deterministic poly-time approximation of the permanent and settling Friedland's conjecture on the Monomer-Dimer Entropy

Leonid Gurvits
City University of New York
September 29, 2014
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. Linial, A. Samorodnitsky and A. Wigderson introduced a strongly poly-time deterministic algorithm to approximate the permanent of general non-negative matrices within the multiplicative factor en. Many things happened since them, notably the prize-winning Jerrum, Vigoda, Sinclair FPRAS for the permanent.

Uniform words are primitive

Doron Puder
Member, School of Mathematics
September 23, 2014
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 \(ab\), \(a^2\), or \(aba^{-2}b^{-1}\)? More concretely, do these new random elements have uniform distribution?

In general, a word \(w\) in the free group \(F_k\) is called uniform if it induces the uniform distribution on every finite group \(G\). So which words are uniform?

Colouring graphs with no odd holes

Paul Seymour
Princeton University
September 22, 2014
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 neither \(G\) nor its complement has an odd hole, then \(k(G)=w(G)\). (An ``odd hole" is an induced cycle of odd length at least five.) What happens in between?

A central limit theorem for Gaussian polynomials and deterministic approximate counting for polynomial threshold functions

Anindya De
Institute for Advanced Study; Member, School of Mathematics
May 13, 2014
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 on using techniques from Malliavin calculus. We will also describe a new decomposition lemma for polynomials which says that any polynomial can be written as a function of small number of eigenregular polynomials. The techniques in the lemma are likely to be of independent interest. Based on joint work with Rocco Servedio.

A central limit theorem for Gaussian polynomials and deterministic approximate counting for polynomial threshold functions

Anindya De
Institute for Advanced Study; Member, School of Mathematics
April 29, 2014
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 of the talk will be towards achieving the following goal:
Given a degree-d polynomial threshold function, deterministically approximating the fraction of satisfying assignments up to o(1) error in polynomial time. Along the way, we'll first survey some important existing results in this area.

Search games and Optimal Kakeya Sets

Yuval Peres
Microsoft Research
April 28, 2014
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 theory and probability. A hunter and a rabbit move on an n-vertex cycle without seeing each other until they meet. At each step, the hunter moves to a neighboring vertex or stays in place, while the rabbit is free to jump to any node. Thus they are engaged in a zero sum game, where the payoff is the capture time.

Results and open problems in theory of quantum complexity

Andris Ambainis
University of Latvia; Member, School of Mathematics
April 22, 2014
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. Quantum vs. classical query complexity
2. Quantum vs. classical query complexity for almost all inputs
3. Quantum counterparts of Valiant-Vazirani theorem (reducing NP to unique-NP)

True Randomness: Its Origin and Expansion

Yaoyun Shi
University of Michigan
April 21, 2014
How can we produce randomness of almost perfect quality, in large quantities, and under minimal assumptions? This question is fundamental not only to modern day information processing but also to physics. Yet a satisfactory answer is still elusive to both the practice and the theory of randomness extraction. Here we propose a solution through a new paradigm of extracting randomness from physical systems and basing security on the validity of physical theories, such as quantum mechanics and special relativity.