[DMANET] IGAFIT Algorithmic Colloquium - 4pm(!) CEST, Juny 1: 3SUM, All-Pairs Shortest Paths and Monochromatic Problems by Virginia Vassilevska Williams

Dear all,
Please note the unusual time(!) for the next talk on the IGAFIT
Algorithmic Colloquium this Thursday:

July 1, 2021, 16:00 CEST (not the usual 14:00 time)
Virginia Vassilevska Williams, MIT
Title: 3SUM, All-Pairs Shortest Paths and Monochromatic Problems
Abstract: Two of the main hypotheses of Fine-Grained Complexity concern the
3SUM problem from Computational Geometry and the All-Pairs Shortest Paths
(APSP) from Graph Algorithms; both are for the word RAM model of
computation. The 3SUM hypothesis asserts that given a set A of n integers,
any algorithm needs n^{2-o(1)} time to determine whether A contains 3
integers summing to 0. The APSP hypothesis says that given an n node graph
G with integer weights bounded by poly(n), any algorithm needs n^{3-o(1)}
time to compute the shortest path distances between every pair of nodes of
G.
Together with the Strong Exponential Time Hypothesis about the complexity
of Boolean Satisfiability, these two hypotheses explain the best known
running times for a huge variety of problems of interest. However, very
little is known about how 3SUM and APSP relate to each other and whether
their two hypotheses might be equivalent. In this talk we will discuss some
indirect relationships between the two problems. In particular, we will
show that 3SUM is fine-grained equivalent to a problem called Monochromatic
Convolution, while both 3SUM and APSP are fine-grained reducible to a
problem called Monochromatic Triangles. As both monochromatic problems
merely ask about equality of colors (and no summations), these reductions
show that the hardness of 3SUM and APSP is not due to having to sum large
numbers as was originally believed.

We would like to invite you to take part in the event including the
networking session. This new event aims to integrate the European
algorithmic community and keep it connected during the times of the
pandemic. The meeting will be held using the Airmeet platform and to attend
please go to https://www.airmeet.com/e/b50ad4d0-d83e-11eb-b58d-e3a6dfec430b.
You can find more information about the talk on IGAFIT web page:
http://igafit.mimuw.edu.pl/?page_id=483786.

In order to access the Airmeet platform, you will need to register, so that
others know who you are. Then before and after the talk, you will be
located inside a Social Lounge, where discussion tables are visible. Most
of the tables can have up to 8 chairs, and you can join a table by clicking
the "Take a Seat" button on a table. This way you will be able to talk to
people seated currently at the table. When the session starts you will be
automatically switched to see the stage. You can find more instructions on
how to use Airmeet here:
https://www.airmeet.com/hub/step-by-step-guide-use-airmeet-for-attendees/.

We invite you to take part in the event. Please advertise broadly and bring
your students/postdocs as well.

Organization Committee:
Nikhil Bansal
Artur Czumaj
Andreas Feldmann
Danupon Nanongkai
Adi Rosen
Eva Rotenberg
Piotr Sankowski
Christian Sohler

**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************