The conference that shares its namesake with this blog has announced their accepted papers. The 27th Conference on Computational Complexity itself will be held in Porto, Portugal June 26-29. If you go, stop by England on the way and celebrate the 100th anniversary of Turing's birth (June 23) in either Cambridge or Manchester.
Lots of great papers accepted to the conference. For biased reasons I like Limits on Alternation-Trading Proofs for Time-Space Lower Bounds by Sam Buss and Ryan Williams. They give some compelling logical reasons why we've hit the limit of current techniques in proving time-space tradeoffs for Satisfiability. Alon, Shpilka and Umans found connections between Sunflowers and Matrix Mulitplication. Finally a plug for my student Josh Grochow's first Complexity paper Matrix Lie Algebra Isomorphism.
Pedantry: it will be the 99th anniversary of Turing's birth; he was born in 1912.
ReplyDeleteAnonymous at 8:02: no, it will be the 100th anniversary (2012-1912). If he was born in 2011, it would be the 1st anniversary (2012-2011), etc.
ReplyDeleteAnon#1 I don't see how you get 99. Assuming he was born as you say in 1912 Turing would be 100 years old on June 23rd 2012, it would be his 100th birthday. Am I missing something here?
ReplyDelete"Pedantry: it will be the 99th anniversary of Turing's birth; he was born in 1912."
ReplyDeleteAn off-by-1 error. A common occurrence in CS.
In the paper 'Sunflowers and Matrix Multiplication' it is stated that "The best known result is due to Coppersmith and Winograd that gave an O(n^2.376) time algorithm for multiplying two nxn matrices". Aren't the authors aware of Stothers and Williams breakthru?
ReplyDeleteThe Jug of Punch
ReplyDeleteBein' on the twenty-third of June,
As I sat weaving all at my loom,
Bein' on the twenty-third of June,
As I sat weaving all at my loom,
I heard a thrush, singing on yon bush,
And the song she sang was The Jug of Punch.
What more pleasure can a boy desire,
Than sitting down beside the fire?
What more pleasure can a boy desire,
Than sitting down beside the fire?
And in his hand a jug of punch,
And on his knee a tidy wench.
When I am dead and left in my mould,
At my head and feet place a flowing bowl,
When I am dead and left in my mould,
At my head and feet place a flowing bowl,
And every young man that passes by,
He can have a drink and remember I.
• Ostensibly Recursive Texts
I listened to Josh's talk and found it quite interesting.
ReplyDeleteThe off by one error seems not to be special for computer science: Note that the day of birth is not the 1st birthday.
ReplyDelete