This post also appears on the ICE-TCS blog.
On Friday, 3 May, ICE-TCS hosted its 15th annual Theory Day. The event consisted of two 45-minute presentations by Ravi
Boppana (Department of Mathematics, MIT) and Exequiel Rivas
(Inria Paris - Rocquencourt, France), and three ten-minute
presentations by ICE-TCS researchers highlighting some of the recent
research directions pursued by members of the centre.
Boppana kicked off the Theory Day with a wonderfully paced talk on his work with Ron Holzman on Tomaszewski’s problem on randomly signed sums. The problem is as follows. Let , , ..., be real numbers whose squares add up to 1. Consider the signed sums of the form . Can there be more signed sums whose value is greater than 1 then those whose value is at most 1? Holzman and Kleitman (1992) proved that at least 3/8 of these sums satisfy . In his talk, Ravi showed us the main ideas Holzman and he used to improve the bound to 13/32.
Computational effects model the interaction of computer programs with
their environment. In his talk, Exequiel Rivas
taught us how monads
can be used to capture computational effects (a research programme that started with Moggi's award-winning work), and then, discussed some
attempts to incorporate merging operations in the monadic picture.
Two of the short talks were given by Henning A. Úlfarsson and Elli
Anastasiadi. Henning described the work of his group on a tool, called
the CombSpecSearcher, that automates the methods used by
combinatorialists to prove some of their theorems, The tool is able to
prove results featured
in dozens of research papers. Watch this space for updates on its
development and for its successes!
Elli Anastasiadi, a PhD student who is already playing an important role
for the centre, gave a clear seven-minute introduction to fine-grained complexity and to the notion of fine-grained reduction.
The 2019 Theory Day was well attended, at least by the standards of a
TCS event in Iceland. If all goes well, we'll be back next year.