Rightly chastised by Suresh for not blogging while at SODA [1] – enough time has passed for me to completely forget anything I might have wanted to say. But the timing is perfect. I am procrastinating writing a paper that I do not wish to write [2]. So here are six (not necessarily technical) things that I learned at SODA this year.
- The crossing number of K13 is unknown! This gem from Tasos Sidiropoulos’ talk on his work with Julia Chuzhoy and Yury Makarychev studying the approximating the minimum number of crossings required to draw a graph on the plane.
- John Hershberger lives in Portland! Maybe not so exciting to you, but for theory-starved me, it is very exciting to learning that there is an algorithmer nearby.
- It is still possible to give a more efficient, deterministic, optimal algorithm for simple problems in general graphs. Monika Henzinger spoke on her work with Krishnendu Chatterjee on maximal end-components (like strongly connected components, but not). Later in the same session I was delighted by Valerie King’s laugh when a youthful speaker referred to a work of hers as ‘classic’.
- Listening to a talk with the goal of asking one or two questions results in increased attention and a deeper understanding of the material. I learnt this while acting as the MC for 1 ALENEX and 3 SODA sessions – knowing that I’m always left sad after giving a question-less talk, I wanted to make sure that I had a question ready for each of my speakers.
- There are still problems that we don’t know how to solve in bounded treewidth graphs: (a) thin trees (which can be used to solve the asymmetric travelling salesperson problem) as pointed to by Shayan Oveis Gharan in his work with Amin Saberi on the ATSP problem in surface-embedded graphs and (b) prize-collecting Steiner forests which are (among other things) shown to be APX-hard in bounded treewidth graphs in Bateni et. al’s work.
- 40% of Princeton students take first-year computer science and this course has the second-highest enrolment at the university. Okay, this one wasn’t from SODA, but from ANALCO’s keynote talk by Robert Sedgewick. I have dreamt (in my teaching statement) of bringing such a stat to Oregon State University. Now I have ammunition for the people upstairs [3].
[1] I decided to travel without my laptop and thought that painfully poking away at my touch phone would be a bit ridiculous.
[2] But should.
[3] Actually downstairs.
Wrt crossing numbers, there are a ton of things that are not known! Did you know that for complete bipartite graphs there’s a conjectured formula which people have verified up till K_{7,7}… When I was an undergrad I worked on verifying the conjecture for K_{9,9}; we made some progress but the problem is still open!!
Cora: you made it to my “quotes” file with this one:
“Listening to a talk with the goal of asking one or two questions results in increased attention and a deeper understanding of the material.”
– Glencora Borradaile, aka Silent Glen
(http://www.glencora.org/silent-glen-speaks/a-flat-6-pack-of-soda/)
I wish we would teach that to students (and to older professors who mock people “always” asking questions, e.g. myself)!