Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Expanders and Communication-Avoiding Algorithms

Oded Schwartz
Technical University Berlin
January 25, 2010

Algorithms spend time on performing arithmetic computations, but often more on moving data, between the levels of a memory hierarchy and between parallel computing entities. Judging by the hardware evolution of the last few decades, the fraction of running time spent on communication is expected to increase, and with it - the demand for communication-avoiding algorithms. We use geometric, combinatorial, and algebraic ideas and techniques, some of which are known in the context of expander graphs, to construct provably communication-optimal algorithms.

An Algorithmic Proof of Forster's Lower Bound

Moritz Hardt
Princeton University
December 15, 2009

We give an algorithmic proof of Forster's Theorem, a fundamental result in communication complexity. Our proof is based on a geometric notion we call radial isotropic position which is related to the well-known isotropic position of a set of vectors. We point out an efficient algorithm to compute the radial isotropic position of a given set of vectors when it exists.

Algorithmic Dense Model Theorems, Decompositions, and Regularity Theorems

Russell Impagliazzo
Institute for Advanced Study
December 8, 2009

Green and Tao used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Reingold, Trevisan, Tulsiani and Vadhan, and independently, Gowers, give a quantitatively improved characterization of when such dense models exist. An equivalent formulation was obtained earlier by Barak, Shaltiel and Wigderson.

The NOF Communication Complexity of Multiparty Pointer Jumping

Joshua Brody
Dartmouth College
December 7, 2009

We give new results on the number-on-the-forhead (NOF) communication complexity of the multiparty pointer jumping problem.
The origional motivation for this problem comes from circuit complexity. Specifically, there is no explicit function known to lie outside the complexity class ACC0. However, a long line of research in the early 90's showed that a sufficiently strong NOF communication lower bound for a function would place it outside ACC0. Pointer jumping is widely considered to be a strong candidate for such a lower bound.

Arithmetic Progressions in Primes

Madhur Tulsiani
Institute for Advanced Study
November 24, 2009

I will discuss the Green-Tao proof for existence of arbitrarily long arithmetic progressions in the primes. The focus will primarily be on the parts of the proof which are related to notions in complexity theory. In particular, I will try to describe in detail how the proof can be seen as applying Szemeredi's theorem to primes, by arguing that they are indistinguishable from dense subsets of integers, for a suitable family of distinguishers.

Graph and Subgraph Sparsification and its Implications to Linear System Solving and Transforming Graphs into Expanders

Alexandra Kolla
Institute for Advanced Study
November 10, 2009

I will first give an overview of several constructions of graph sparsifiers and their properties. I will then present a method of sparsifying a subgraph W of a graph G with optimal number of edges and talk about the implications of subgraph sparsification in constructing nearly-optimal ultrasparsifiers and optimizing the algebraic connectivity of a graph by adding few edges.

The talk is based on joint work with Makarychev,Saberi,Teng.