Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

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.

Computing inverses

Louis Rowen
Bar Ilan University
February 24, 2015
We compare methods of computing inverses of matrices over division rings. The most direct way is via Cohn's theory of full matrices, which was improved by Malcolmson, Schofield, and Westreich. But it is simpler to work with finite dimensional representations and generic matrices. In this talk, mostly expository, we describe the relevant algebraic techniques, including a description of full matrices, Sylvester rank functions, coproducts, and generic division algebras and its underlying theory of polynomial identities.

Lower bounds for clique vs. independent set

Mika Göös
University of Toronto
February 23, 2015
We prove an $\omega(\log n)$ lower bound on the conondeterministic communication complexity of the Clique vs. Independent Set problem introduced by Yannakakis (STOC 1988, JCSS 1991). As a corollary, this implies superpolynomial lower bounds for the Alon--Saks--Seymour conjecture in graph theory. Our approach is to first exhibit a query complexity separation for the decision tree analogue of the UP vs. coNP question---namely, unambiguous DNF width vs. CNF width---and then "lift" this separation over to communication complexity using a result from prior work.

Eigencurve over the boundary of the weight space

Liang Xiao
University of Connecticut
February 19, 2015
Eigencurve was introduced by Coleman and Mazur to parametrize modular forms varying $p$-adically. It is a rigid analytic curve such that each point corresponds to an overconvegent eigenform. In this talk, we discuss a conjecture on the geometry of the eigencurve: over the boundary annuli of the weight space, the eigencurve breaks up into infinite disjoint union of connected components and the weight map is finite and flat on each component. This was first verified by Buzzard and Kilford by an explicit computation in the case of $p = 2$ and tame level 1.