{"id":614,"date":"2011-02-11T22:30:27","date_gmt":"2011-02-12T05:30:27","guid":{"rendered":"http:\/\/www.glencora.org\/?p=614"},"modified":"2011-02-11T22:30:27","modified_gmt":"2011-02-12T05:30:27","slug":"a-flat-6-pack-of-soda","status":"publish","type":"post","link":"https:\/\/blogs.oregonstate.edu\/glencora\/2011\/02\/11\/a-flat-6-pack-of-soda\/","title":{"rendered":"A flat 6-pack of SODA"},"content":{"rendered":"

Rightly chastised by Suresh<\/a> 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.<\/p>\n

    \n
  1. The crossing number of K13 is unknown! This gem from\u00a0Tasos Sidiropoulos’ talk on his work with Julia Chuzhoy and Yury Makarychev<\/a> studying the approximating the minimum number of crossings required to draw a graph on the plane.<\/li>\n
  2. John Hershberger<\/a> lives in Portland! \u00a0Maybe not so exciting to you, but for theory-starved<\/a> me, it is very exciting to learning that there is an algorithmer nearby.<\/li>\n
  3. 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<\/a> 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’.<\/li>\n
  4. 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.<\/li>\n
  5. There are still problems that we don’t know how to solve in bounded treewidth graphs: (a)\u00a0thin 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<\/a> 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\u00a0et. al’s work<\/a>.<\/li>\n
  6. 40% of Princeton students take first-year computer science and this course has the second-highest enrolment at the university. \u00a0Okay, this one wasn’t from SODA, but from ANALCO’s\u00a0keynote talk by Robert Sedgewick<\/a>. I have dreamt (in my teaching statement) of bringing such a stat to Oregon State University. \u00a0Now I have ammunition for the people upstairs [3].<\/li>\n<\/ol>\n

    [1] I decided to travel without my laptop and thought that painfully poking away at my touch phone would be a bit ridiculous.
    \n[2] But should.
    \n[3] Actually downstairs.<\/p>\n","protected":false},"excerpt":{"rendered":"

    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 […]<\/p>\n","protected":false},"author":3747,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[2690,106188,106190],"class_list":["post-614","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-conference","tag-soda","tag-tcs"],"_links":{"self":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/614","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/users\/3747"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/comments?post=614"}],"version-history":[{"count":0,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/614\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/media?parent=614"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/categories?post=614"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/tags?post=614"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}