A preview of the talks for this coming ARC Day

ARC is our Algorithms & Randomness Center at Tech. It was created by Santosh Vempala, and this Monday ARC is holding a special theory day. The organizers are Santosh with Richard Peng and Dana Randall.

Tomorrow, Monday April 11th, is the day for the talks, and I only have time to highlight just two of them.

All of the talks look great—see this for details on the other two by Rocco Servedio on “Circuit Lower Bounds via Random Projections” and Aaron Sidford on “ Recent Advances in the Theory of Interior Point Methods.” We previewed a related joint paper by Servedio last May. Sidford’s talk will include the first ${\tilde{O}(n)}$-time algorithm for finding the geometric median, that is a point that minimizes the sum of distances to ${m}$ given points in Euclidean space. This is a nice contrast to recent results where having any sub-quadratic algorithm would break conjectures about the hardness of SAT.

Two ARC Talks

Virginia Vassilevska-Williams will speak on Fine-Grained Algorithms and Complexity. Virginia key point is simple:

If a problem is computable in polynomial time, then the classic reductions used to study the ${\mathsf{P = NP}}$ question are useless.

They are useless since they cannot distinguish the fine structure of polynomial time: linear time and time ${n^{100}}$ all look the same.

This simple insight leads one to study the topic now called “fine-grained reductions,” which focuses on exact running times. She explains that the key point of fine-grained is to allow one to compare problems that run in polynomial time. Yet the reductions also “float” so that they are not just: the algorithms run in essentially the same time. There is a ${\epsilon>0}$ lurking here. She states:

This approach has led to the discovery of many meaningful relationships between problems, and even sometimes equivalence classes.

She plans to discuss current progress and highlight some new exciting developments.

$\displaystyle \S$

Luca Trevisan of Berkeley will speak on Ramanujan Graphs. These are graphs that are of course name after the extraordinary mathematician Srinivasa Ramanujan. Luca plans on reviewing what is known about existence and constructions of Ramanujan graphs, which are the best possible expander graphs from the point of view of spectral expansion—see this for precise definitions.

He will talk about Joel Friedman’s result that random graphs are nearly Ramanujan, and recent simplifications of Friedman’s proof, which was around 100 pages long. Luca will also talk about connections between Ramanujan graphs and the Ihara zeta function, and also about recent non-constructive existence results.

The Ihara zeta-function, named for Yasutaka Ihara, can be defined by a formula analogous to the Euler product for the usual Riemann zeta function:

$\displaystyle \frac{1}{\zeta_G(u)} = \prod_{p} ({1 - u^{L(p)}}]$

This product is taken over all prime walks “p” of the graph ${ G = (V, E) }$ that is, closed cycles. See this for the rest of the formal definition, and also this 2001 survey on zeta functions of graphs. Toshikazu Sunada made the key connection between Ramanujan graphs and this function that was first defined in the 1966, in a totally different context.

It seems amazing that graph problems can be coded into zeta like functions. One wonders what another problems yield to similar ideas.

Open Problems

We hope the talks have a nice turnout and are looking forward to a banner day.