Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Non-constructive combinatorics

Noga Alon
Tel Aviv University; Visiting Professor, School of Mathematics
October 13, 2015
I will describe several old and new applications of topological and algebraic methods in the derivation of combinatorial results. In all of them the proofs provide no efficient solutions for the corresponding algorithmic problems. Finding such solutions is an intriguing challenge.

Factors of polynomials of low individual degree

Rafael Oliveira
Princeton University
October 12, 2015
In [kal89], Kaltofen proved the remarkable fact that multivariate polynomial factorization can be done efficiently, in randomized polynomial time. Still, more than twenty years after Kaltofen's work, many questions remain unanswered regarding the complexity aspects of polynomial factorization, such as the question of whether factors of polynomials efficiently computed by arithmetic formulas also have small arithmetic formulas, asked in [KSS14], and the question of bounding the depth of the circuits computing the factors of a polynomial.

Invariants of random knots

Chaim Even Zohar
Hebrew University of Jerusalem
October 6, 2015
A knot is a closed curve embedded in the three-dimensional space, like a rope whose two ends are joined together. As usual in Topology, two knots are equivalent if one can be deformed into the other by continuous moves, where stretching and squeezing are allowed but with no cutting and pasting. Random curves in space and how they are knotted give an insight into the behavior of "typical" knots and links. They have been studied by biologists and physicists in the context of the structure of random polymers.

Ramsey numbers of degenerate graphs

Choongbum Lee
Massachusetts Institute of Technology
September 28, 2015
The Ramsey number of a graph $G$ is the minimum integer $n$ for which every edge-coloring of the complete graph on $n$ vertices with two colors contains a monochromatic copy of $G$. A graph is $d$-degenerate if all its subgraphs have a vertex of degree at most $d$. In this talk, we prove that for all $d$, there exists a constant $c$ such that every $d$-degenerate graph $G$ has Ramsey number at most $c|V(G)|$. This solves a conjecture of Burr and Erdős from 1973.

Explicit two-source extractors and resilient functions II

Eshan Chattopadhyay
University of Texas at Austin
September 22, 2015
We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant $C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain, required each source to have min-entropy $.499n$. A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on n bits that is resilient to coalitions of size $n^{1-\delta}$, for any $\delta > 0$.

Explicit two-source extractors and resilient functions I

Eshan Chattopadhyay
University of Texas at Austin
September 21, 2015
We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant $C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain, required each source to have min-entropy $.499n$. A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on n bits that is resilient to coalitions of size $n^{1-\delta}$, for any $\delta > 0$.

Chernoff bounds for expander walks

Christopher Beck
Member, School of Mathematics
March 10, 2015
Expander walk sampling is an important tool for derandomization. For any bounded function, sampling inputs from a random walk on an expander graph yields a sample average which is quite close to the true mean, and moreover the deviations obtained are qualitatively similar to those obtained from statistically independent samples. The "Chernoff Bound for Expander Walks" was first described by Ajtai, Komlos, and Szemeredi in 1987, and analyzed in a general form by Gilman in 1988.

Strong contraction and influences in tail spaces

Elchanan Mossel
University of Pennsylvania
March 9, 2015
Various motivations recently led Mendel and Naor, Hatami and Kalai to study functions in tail spaces - i.e. function all of whose low level Fourier coefficients vanish. I will discuss the questions and conjectures that they posed and our recent work which resolves some of these questions and conjectures. Based on a joint work with Steven Heilman and Krzysztof Oleszkiewicz.

Whitney numbers via measure concentration in representation varieties

Karim Adiprasito
Member, School of Mathematics
March 3, 2015
We provide a simple proof of the Rota--Heron--Welsh conjecture for matroids realizable as c-arrangements in the sense of Goresky--MacPherson: we prove that the coefficients of the characteristic polynomial of the associated matroids form log-concave sequences, proving the conjecture for a family of matroids out of reach for all previous methods. To this end, we study the Lévy--Milman measure concentration phenomenon on natural pushforwards of uniform measures on the Grassmannian to realization spaces of arrangements under a certain extension procedure on matroids.