June notes
02 Jul 2019Some notes for June.
Saint Laurent de la Cabrerisse where the Algotel conference took place.
Recorded talks and collaborating virtually
Continuing on the topic of video conferences (e.g. to avoid plane travel), an important question is: can virtual conferences, and more generally communication via video-conference, be really efficient?
I have to admit that, although I really like the idea of video conference, for talks or for work, I have difficulties following recorded talks, and I’m not very comfortable with video calls. Here are the reasons I could find for why video talks and calls are not as good as their physical analogues:
- in a recorded talk, you can escape, take a coffee, answer an email, that is you can “escape the room”, thus you are less focused.
- videos are less immersive: the sound is bad, what you watch occupies a very small part of your visual field, and in a talk you don’t feel that you are part of a crowd participating in something.
- A consequence of the previous bullet is that the experience is socially less comfortable: in a real meeting, there can be a long silence and it’s fine, but during a video call, it’s often awkward.
- Also video conferences are very static. This is especially true for talks: the main part of the screen is taken by the slide, which moves once every minute on average, and even if you see the speaker, you just see a face, no body movements.
- Related to the previous point: I don’t know good ways to have a shared whiteboard when working through video, which reduces a lot the efficiency of the conversation.
Some of these problems are kind of solved by some frameworks. For example TCS+ is an online seminar where the speaker does not record a video alone: it is more like a large video conference with a dozen of labs connected, and one person giving the talk. (The talks are actually recorded so you can watch them offline, but it is not the main goal.) This means that there is a crowd, and that you cannot escape. Also if you have a good video/sound system, then it might be quite immersive. I never had the opportunity to test this so I can’t tell.
Note that some people think the exact opposite of me: they actually prefer watching a recorded talk, because it’s offline: you can stop, rethink what was said, check a reference, jump to the next section etc. Also note that attending a live talk can also be boring, so it also depends a lot on the speaker.
If you know good alternatives to skype (ideally open-source, with a possibility of drawing, and multi-users), send me an email. This will be useful not only to me but also to other people: I timidly signed to be part of a pool of people thinking about such technical topics, in the Labo 1.5 collective I talked about last month.
Terence Tao on the radius of the Earth
Terence Tao has a blog, What’s new. Most of the content is way too complicated for me, but once in a while he writes excellent posts about simpler things. A very recent one is about the radius of the Earth and determinants. An older one is about sailing.
Basic and advanced tools in combinatorics
I have heard that some people tend to despise combinatorics as being “very basic”. To some extent, my research is very basic: most of the time I consider very simple objects, a few edges and a few nodes in a graph. I almost never use complicated tools which have been improved over the centuries and which need time to master. Sometimes it is a bit unsettling: one can feel like playing child games, compared to what one was taught at the university.
On the other hand of course, it is very annoying when people boast about using complicated stuff, and it is always very nice to find a basic proof of a theorem.
Something I like is when you have a basic proof that is a bit of a mess, with many cases for example, and using the point of view of a more general theory you suddenly understand things better. I had this experience with some matroid structure in this paper (although it does not appear at all in the final write-up).
I was reminded of this by this post on David Eppstein’s blog, where he describes a new point of view he has on a matching problem thanks to a more advanced notion of matroid (yes matroids, again).
John ellipsoid and the “‘s”
This arxiv preprint made me discover John ellipsoid. Given a polytope in $n$ dimensions, John ellipsoid is the largest-volume ellipsoid included in the polytope. On the picture below it is the red ellipse (more or less).
An interesting property is that if you take the ellipsoid and dilate it by a factor $n$, then this new ellipsoid contains the polytope (more or less the blue ellipsoid on the picture). At first I thought that dimension 3 should not require more dilatation than dimension 2, but if you think about an equilateral triangle in the plane, and a tetrahedron in a 3D space, you see that the inner ball of the tetrahedron has to be smaller than the inner disk of the equilateral triangle, and that the outer ball has to be larger.
The arxiv preprint presents an algorithm to approximate John ellipsoid.
By the way, why is it “John ellipsoid” and, say, “Dijktra’s algorithm”, why is there a “‘s” sometimes but not always?
Eppstein’s SOCG report and robust statistics
Eppstein wrote a nice report of SOCG, with a selection of talks that caught his interest.
He refers to Tukey depth, which is related to Tukey median, which is a generalization of the median in higher dimension. I discovered this notion in a great talk by Ankur Moitra about the computational aspects of robust statistics, at HALG 2018. The basic story is the following. Suppose you have data, and you want to summarize it by one point. You want to use the average, but because your data has some adversarial noise, the average of the noisy data might be far from the average of the “real data”. If you are in 1D then you can take the median, which is robust to such noise. But if you are in $d$ dimension, then there are several generalizations of the median, and either they are not robust to noise or they are NP-hard to compute, and then you have to think.
Two references on robust statistics : here and there.
Other notes
-
The paper I talked about in a series of posts in February, by the Aalto distributed computing people has been accepted to FOCS 2019.
-
The 128th bulletin of the EATCS is out, with a chapter on matching with preference lists, and a chapter on leader election in directed dynamic graphs.