Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

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.

How to round subspaces: a new spectral clustering algorithm

Ali Kemal Sinop
Simons Institute for the Theory of Computing, Berkeley
February 10, 2015
Given a $k$-dimensional linear subspace, consider the problem of approximating it (with respect to the spectral norm) in terms of another subspace spanned by the indicators of a $k$-partition of the coordinates. This is known as the spectral clustering problem, first introduced by [Kannan, Kumar]. It is a generalization of the standard $k$-means problem, which corresponds to the Frobenius norm. In this talk, I will present a new spectral clustering algorithm.

Quantum computing with noninteracting particles

Alex Arkhipov
Massachusetts Institute of Technology
February 9, 2015
We introduce an abstract model of computation corresponding to an experiment in which identical, non-interacting bosons are sent through a non-adaptive linear circuit before being measured. We show that despite the very limited nature of the model, an exact classical simulation would imply a collapse of the polynomial hierarchy. Moreover, under plausible conjectures, a "noisy" approximate simulation would do the same.

Dimension expanders via rank condensers

Michael Forbes
Member, School of Mathematics
February 3, 2015
Expander graphs are sparse graphs with good connectivity properties and they have become ubiquitous in theoretical computer science. Dimension expanders are a linear-algebraic variant where we ask for a constant number of linear maps that expand subspaces of a vector space (instead of subsets of vertices). After their definition 10 years ago by Barak, Impagliazzo, Shpilka and Wigderson there are now two constructions of constant-degree dimension expanders, both of which suggest dimension expanders are more complicated than expander graphs.

On monotonicity testing and boolean isoperimetric type theorems

Subhash Khot
New York University
February 2, 2015

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\epsilon^2)$ non-adaptive queries to a function $f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function and rejects a function that is $\epsilon$-far from being monotone with constant probability. Joint work with Dor Minzer and Muli Safra. The paper is available on ECCC: