tag:blogger.com,1999:blog-27705661Mon, 24 Nov 2014 11:12:58 +0000Process Algebra DiaryPapers I find interesting---mostly, but not solely, in Process Algebra---, and some fun stuff in Mathematics and Computer Science at large and on general issues related to research, teaching and academic life.http://processalgebra.blogspot.com/noreply@blogger.com (Luca Aceto)Blogger509125tag:blogger.com,1999:blog-27705661.post-767731521649299355Tue, 11 Nov 2014 09:34:00 +00002014-11-14T09:02:03.093ZEATCS Fellows 2015: Call for Nominations<i>In case you have not seen it before, here is the call for nominations for EATCS Fellows 2015. </i><i>Do nominate strong candidates for this accolade! </i> <br /><pre> <span class="il"> </span></pre><pre><b><span class="il">CALL</span> FOR <span class="il">NOMINATIONS</span> FOR <span class="il">EATCS</span> <span class="il">FELLOWS</span> 2015</b><br /> <br /> <br />INSTRUCTIONS:<br />Please note: all nominees and nominators must be <span class="il">EATCS</span> Members<br /><br />Submit by December 31 of the current year for Fellow consideration by<br />email to the <span class="il">EATCS</span> Secretary (<a href="mailto:secretary@eatcs.org" target="_blank">secretary@<span class="il">eatcs</span>.org</a>). The subject line<br />of the email should read "<span class="il">EATCS</span> Fellow Nomination - <surname candidate="" of="">".<br /><br />REQUIREMENTS FOR <span class="il">EATCS</span> NOMINATION:<br /><br />The <span class="il">EATCS</span> <span class="il">Fellows</span> Program is established by the Association to<br />recognize outstanding <span class="il">EATCS</span> Members for their scientific achievements<br />in the field of Theoretical Computer Science. The Fellow status is<br />conferred by the <span class="il">EATCS</span> <span class="il">Fellows</span>-Selection Committee upon a person<br />having a track record of intellectual and organizational leadership<br />within the <span class="il">EATCS</span> community. <span class="il">Fellows</span> are expected to be “model<br />citizens” of the TCS community, helping to develop the standing of TCS<br />beyond the frontiers of the community.<br /><br />In order to be considered by the <span class="il">EATCS</span> <span class="il">Fellows</span>-Selection Committee,<br />candidates must be nominated by at least four <span class="il">EATCS</span> Members. <br />Please verify your membership at <a href="http://www.eatcs.org/" target="_blank">http://www.<span class="il">eatcs</span>.org/</a>.<br /><br />The <span class="il">EATCS</span> <span class="il">Fellows</span>-Selection Committee consists of <br /><br />- Rocco De Nicola (IMT Lucca, Italy) <br />- Paul Goldberg (Oxford, UK)<br />- Anca Muscholl (Bordeaux, France)<br />- Dorothea Wagner (Karlsruhe, Germany, chair)<br />- Roger Wattenhofer (ETH Zurich, CH)<br /><br />INSTRUCTIONS:<br /><br />A nomination should consist of answers to the questions below. It can<br />be co-signed by several <span class="il">EATCS</span> members. At least two nomination letters <br />per candidate are recommended. If you are supporting the<br />nomination from within the candidate's field of<br />expertise, it is expected that you will be specific about the<br />individual's technical contributions.<br /><br />To be considered, <span class="il">nominations</span> for 2015 must be received by December 31, 2014.<br /><br />1. Name of candidate<br />Candidate's current affiliation and position<br />Candidate's email address, postal address and phone number<br />Nominator(s) relationship to the candidate<br /><br />2. Short summary of candidate's accomplishments (citation -- 25 words or less)<br /><br />3. Candidate's accomplishments: Identify the most important<br />contributions that qualify the candidate for the rank of <span class="il">EATCS</span> Fellow<br />according to the following two categories: <br /><br />A) Technical achievements<br />B) Outstanding service to the TCS community<br /><br />Please limit your comments to at most three pages.<br /><br />4. Nominator(s):<br />Name(s)<br />Affiliation(s), email and postal address(es), phone number(s)</surname></pre>http://processalgebra.blogspot.com/2014/11/eatcs-fellows-2015-call-for-nominations.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-3085365133126245507Fri, 31 Oct 2014 09:05:00 +00002014-10-31T09:05:57.732ZOctober 2014 issue of the Bulletin of the EATCS The October issue of the EATCS <span class="il">Bulletin</span> is now available online at <a href="http://bulletin.eatcs.org/index.php/beatcs/issue/view/16" target="_blank">http://<span class="il">bulletin</span>.eatcs.org/<wbr></wbr>index.php/beatcs/issue/view/16</a> from where you can access the individual contributions separately. <br /><br />You can download a pdf with the printed version of the whole issue <span class="il"></span>from <a href="http://www.eatcs.org/images/bulletin/beatcs114.pdf" target="_blank">http://www.eatcs.org/images/<wbr></wbr><span class="il">bulletin</span>/beatcs114.pdf</a>.<br /><br />The Bulletin of the EATCS is open access, so people who are not members of the EATCS can read it. Let me thank the members of the association who make this service of the community possible with their support. (EATCS members have access to the member area, which contains news and related articles and provides access to the Springer Reading Room. Young researchers can find announcements of open positions, news and related articles.)<br /><br />This issue of the bulletin is brimming with interesting content, with five EATCS Columns and a piece by David Woodruff surveying the work for which he had received the EATCS Presburger Award 2014 amongst others. You might also enjoy reading the transcript of a <a href="http://bulletin.eatcs.org/index.php/beatcs/article/view/306/288" target="_blank">dialogue</a> between <a href="https://www.cs.auckland.ac.nz/~cristian/" target="_blank">Christian Calude</a> and <a href="http://www.mpi-inf.mpg.de/~mehlhorn" target="_blank">Kurt Mehlhorn</a> about theory, LEDA and Algorithm Engineering. I find it inspiring to read Christian's dialogues with famous members of our community and I always learn something useful from them. (Unfortunately, the lessons I think I learn do not make it often into my work practices. That's the theory-practice divide, I guess :-))<br /><br />Here are a couple of excerpts to whet your appetite.<br /><ul><li>Kurt's motto, even definition, for Algorithm Engineering is: "Treat programs as first class citizens in algorithms research and not as an afterthought." He also adds that "Algorithm engineering is not only a sub-discipline of algorithms research. More importantly, it is a mind set."</li><li>CC: How do you manage to juggle between so many jobs in di fferent countries?<br />KM: I try to follow some simple principles.<br />I avoid multi-tasking. I set aside time for particular tasks and then concentrate on them. For example, when I was writing my 1984 books and the LEDA book, I would work on the book every work day from 8:00 am to 12:00 pm. I would not accept phone calls or interruptions by students during this time. Now, the 8am to 12pm slot is reserved for reading, thinking and writing. The no-interruption rule still holds.<br />I clean my desk completely every evening when I leave my o ffice, so that I can start with an empty desk the next morning.<br />When I accept a new responsibility, I decide, what I am going to give up for<br />it. For example, when I became vice-president of the Max Planck Society in 2002 (for a 6 year term), I resigned as editor of Algorithmica, Information and Computation, SIAM Journal of Computing, Journal of Discrete and Computational Geometry, International Journal of Computational Geometry and Applications, and Computing.<br />And most importantly, I am supported by many people in what I do, in particular, my co-workers, my students, and then administrative staff in the institute and the department. Cooperation and delegation are very important.</li></ul>Enjoy the issue and consider contributing to future ones!http://processalgebra.blogspot.com/2014/10/october-2014-issue-of-bulletin-of-eatcs.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-8777143857353717279Fri, 17 Oct 2014 10:37:00 +00002014-10-19T21:49:06.815ZFirst CFP for ICALP 2015The first call for papers for ICALP 2015, which will be held in Kyoto in the period 6-10 July 2015, is available <a href="http://www-kb.is.s.u-tokyo.ac.jp/~koba/icalp2015/cfp.txt" target="_blank">here</a>. <br /><br />I hope that you will consider submitting your best work to the conference. The event will be rich of scientific events and will be co-located with <a href="http://lics.rwth-aachen.de/lics15/" target="_blank">LICS 2015</a>. To whet your appetite, here is the list of invited speakers and invited tutorials:<br /><br /><b>Invited Speakers</b><br /><br />Ken Kawarabayashi, NII, Japan<br />Valerie King, University of Victoria, Canada<br />Thomas Moscibroda, MSR Asia, China<br />Anca Muscholl, University of Bordeaux, France (Joint with LICS)<br />Peter O'Hearn, Facebook, UK (Joint with LICS)<br /><br /><b>Invited Tutorial Speakers (Joint with LICS) </b><br /><br />Piotr Indyk, MIT, USA<br />Andrew Pitts, University of Cambridge, UK<br />Geoffrey Smith, Florida International University, USA<br /><br /><b>Masterclass speaker </b><br /><br />Ryuhei Uehara, JAIST, Japan http://processalgebra.blogspot.com/2014/10/first-cfp-for-icalp-2015.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-6959874356776974611Wed, 08 Oct 2014 15:28:00 +00002014-10-08T16:31:05.709ZCFP for CCC'15 postedDieter van Melkebeek has informed me that the CFP for CCC'15 has just been posted. The direct link is <a href="http://computationalcomplexity.org/Archive/2015/cfp.html" target="_blank">http://<wbr></wbr>computationalcomplexity.org/<wbr></wbr>Archive/2015/cfp.html</a>.<br /><br />The deadline for submissions is <b>November 26, 2014</b>.<br /><br />I hope that members of the CCC community will submit some of their best work to the first edition of the conference with open-access proceedings published in <a href="http://www.dagstuhl.de/en/publications/lipics" target="_blank">LIPIcs</a>. http://processalgebra.blogspot.com/2014/10/dieter-van-melkebeek-has-informed-me.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-7380087381962535507Sat, 04 Oct 2014 22:00:00 +00002014-10-04T22:00:39.947ZCall for nominations: EATCS Award 2015<div style="text-align: left;"><i>Please consider nominating outstanding theoretical computer scientists for the EATCS Award 2015. </i></div><div style="text-align: center;"> </div><div style="text-align: center;">The EATCS Award 2015<br /><br />Call for Nominations<br /><br /><b>Deadline: December 31st, 2014</b></div><br />The European Association for Theoretical Computer Science (EATCS) annually honours a respected scientist from our community with the prestigious EATCS Distinguished Achievement Award. The award is given<br />to acknowledge extensive and widely recognized contributions to theoretical computer science over a life long scientific career. For the EATCS Award 2015, candidates may be nominated to the Award Committee consisting of <br /><ul><li>Fedor Fomin (University of Bergen),</li><li>Kim Guldstrand Larsen (Aalborg University) and </li><li>Vladimiro Sassone (University of Southampton). </li></ul>Nominations will be kept strictly confidential. They should include supporting justification and be sent by e-mail to the chair of the EATCS Award Committee:<br /><br />Vladimiro Sassone<br />Email: <a href="mailto:vsassone@soton.ac.uk" target="_blank">vsassone@soton.ac.uk</a><br /><br />The list of previous recipients of the EATCS Award is at <br /><br /><a href="http://eatcs.org/index.php/eatcs-award" target="_blank">http://eatcs.org/index.php/<wbr></wbr>eatcs-award</a><br /><br />The next award will be presented during ICALP 2015 in Kyoto, Japan.http://processalgebra.blogspot.com/2014/10/call-for-nominations-eatcs-award-2015.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-7452695907734464476Fri, 03 Oct 2014 16:31:00 +00002014-10-03T16:31:00.936ZLetter from the President of the EATCS for the October issue of the Bulletin<i>In case any of my two readers is interested in having a look, here is the letter from the president that will appear in the October issue of the Bulletin of the EATCS. </i><br /><br />Dear colleagues, <br /><br />First of all, I hope that you had a good summer break and that you have recharged your batteries for whatever challenges await you in the new academic year. <br /><br />For many of us, the start of each academic year is accompanied by teaching courses to new cohorts of students. Computer Science enrollments seem to be increasing all over the world and several institutions, including mine, will have to decide how to handle the large number of students who are eager to enter our degree courses. I encourage you to have a look at the slides available <a href="http://lazowska.cs.washington.edu/Snowbird.pdf" target="_blank">here</a> for an American perspective on computer science enrollments. Look also at this <a href="http://www.thecrimson.com/article/2014/9/11/cs50-breaks-enrollment-records/" target="_blank">Harvard Crimson article</a>. <a href="https://cs50.harvard.edu/" target="_blank">Course CS 50 at Harvard</a> has over 800 undergraduates (and over 850 total) signed up, making it now the largest class at Harvard.<br /><br />Having many students is, of course, a substantial amount of work, but the popularity of computer science also gives us a very good opportunity to entice some of these students to study the theory of computing; let's make the most of it!<br /><br />I enjoyed meeting several of you at <a href="http://icalp2014.itu.dk/" target="_blank">ICALP 2014</a> in Copenhagen. It was a pleasure to see many young researchers and students at the conference, and I really appreciated the good attendance we had at the event. Thanks to all of you who made the trip to Copenhagen!<br /><br />The 41st ICALP was an excellent conference, both scientifically and socially. The organizers did their very best to make it a memorable event, and I like to think that all the participants felt welcome and enjoyed the conference. On behalf of the EATCS, I warmly thank Thore Husfeldt and his team for doing an outstanding job.<br /><br />You can read my report on ICALP 2014 in this issue of the Bulletin. The <a href="http://icalp2014.itu.dk/en/Events-and-Attractions/Video" target="_blank">recordings of the invited talks and of the award session</a> are available from the conference web page. I hope that you will watch them.<br /><br />ICALP 2015 will be held in Kyoto, Japan, and will be co-located with LICS 2015. Kazuo Iwama is the ICALP 2015 general chair. After 42 years, this will be the first ever ICALP outside Europe and I am very excited at the prospect of holding ICALP in Japan. I hope that you will make plans to submit your best papers to the conference. The call for papers for the conference will be ready for distribution soon.<br /><br />The general assembly of the EATCS decided that ICALP 2016 will be held in Rome, Italy. I thank Tiziana Calamoneri and her collaborators for their willingness to host us in Rome.<br /><br />One of the important decisions that the Council of the EATCS will have to make over the next few months is related to the future publication outlet for the proceedings of ICALP from 2016. Our current contract with Springer will expire at the end of 2015, but we only have until March 2015 to negotiate any changes to it or to decide whether to move to a different publication outlet. I look forward to hearing any opinion you might have on this matter. <br /><br />Regarding publications, I strongly encourage all the members of the EATCS to make all their publications freely accessible on line. It is our duty, as well as being in the interests of our science and in our own interest, to make access to our scientific work free of financial barriers for any researcher. This is possible even for papers that have appeared in journals and conference proceedings published by commercial publishers.<br /><br />As usual at this time of the year, the EATCS issues calls for nominations for the EATCS Award, EATCS Fellows and the Presburger Award. (The call for the Gödel Prize will be published at a later time, when ACM SIGACT has named its representatives in the prize committee.) You can read the calls in this issue of the Bulletin; they have also been posted on mailing lists, blogs and social networks. Please distribute the calls as you see fit. Most importantly, I hope that you will take the time to nominate excellent researchers and papers for these awards. Awards and prizes are a way to recognize the achievement of some of our many outstanding colleagues and they put our favourite research fields in the spotlight. Last, but by no means least, awards provide examples and inspiration for the younger generations of researchers who are the future of our field as a whole. Writing a nomination takes some of our precious time, but it is worth it.<br /><br />At the time of writing, the EATCS is cooperating with the newly formed ACM SIGLOG, the EACSL and the Kurt Gödel Society on a new award, which we hope to be in a position to announce in the not-too-distant future. I am also happy to announce that the <a href="http://computationalcomplexity.org/" target="_blank">Computational Complexity Conference</a> will be held in cooperation with the EATCS from 2015.<br /><br />On Thursday, 2 October, I attended a talk given at my university by <a href="http://en.wikipedia.org/wiki/Donald_Sadoway" target="_blank">Donald Sadoway</a>, John F. Elliott Professor of Materials Chemistry at the Massachusetts Institute of Technology. His talk was inspirational and stressed the importance of research carried out at universities the world over. University research is even more fundamental today than it ever was because, according to Sadoway, universities are the places where truly innovative research takes place. In his view, corporate research laboratories do not embark in fundamental research today as they did in the past.<br /><br />While listening to Sadoway's talk, I could not help but think about the sudden closure of Microsoft Research Silicon Valley. As you all know, Microsoft Research Silicon Valley had achieved a very high reputation within the theoretical-computer-science community because of the scientific standing of its stellar staff, the high impact of the work done at the laboratory, the mentoring role its members played within our research community (with many outstanding<br />young researchers spending important formative periods at the laboratory) and its stimulating research environment with frequent visits by high-profile scientists.<br /><br />As the blog posts from TCS researchers and the associated comments clearly<br />indicate, losing Microsoft Research Silicon Valley has left our community with a sense of loss and sadness, also because of the timing and the abrupt nature of its closing. <br /><br />With a laboratory like Microsoft Research Silicon Valley, Microsoft had gained a substantial amount of credence within the theoretical-computer-science community and had attracted some of the best talent in our field worldwide. Many outstanding young researchers had considered a position at Microsoft Research Silicon Valley and Microsoft's other research labs as their first choice, even above tenure-track or tenured positions at prestigious academic institutions. All this is now probably bound to change, which would be a loss for both Microsoft and our research community.<br /><br />For what it is worth, I hope that Microsoft Research will continue to support research in theoretical computer science. Advances in the theory of computing will benefit the company in the long run and further investments by Microsoft in TCS will be beneficial for our field of study.<br /><br />I thank you for reading this letter, and look forward to hearing suggestions and opinions from the members of the EATCS (and the community at large). You are the heart and soul of our association! http://processalgebra.blogspot.com/2014/10/letter-from-president-of-eatcs-for.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-5507841570625179657Wed, 17 Sep 2014 10:05:00 +00002014-09-17T14:31:32.706ZCall for nominations: Presburger Award 2015<div style="text-align: left;"><i>Here is the call for nominations for one of the EATCS awards that is closest to my heart. Do put pen to paper and nominate your favourite young TCS researcher! He/She might join a truly impressive list of previous award recipients. </i><b><br /></b></div><center><b> </b></center><center><b>Presburger Award for Young Scientists 2015</b><br /><b></b><br /><b> Call for Nominations</b><br /><b></b><br /><b> Deadline: December 31st, 2014</b><br /><br /></center>Starting in 2010, the European Association for Theoretical Computer Science (EATCS) established the Presburger Award. The Award is conferred annually at the International Colloquium on Automata, Languages and Programming (ICALP) to a young scientist (in exceptional cases to several young scientists) for outstanding contributions in theoretical computer science, documented by a published paper or a series of published papers. The Award is named after Mojzesz Presburger who accomplished his path-breaking work on decidability of the theory of addition (which today is called Presburger arithmetic) as a student in 1929.<br /><br />Nominations for the Presburger Award can be submitted by any member or group of members of the theoretical computer science community except the nominee and his/her advisors for the master thesis and the doctoral dissertation. Nominated scientists have to be at most 35 years at the time of the deadline of nomination (i.e., for the Presburger Award of 2015 the date of birth should be in 1979 or later). The Presburger Award Committee of 2015 consists of Zoltan Esik (Szeged), Claire Mathieu (Paris), and Peter Widmayer (Zürich, chair).<br /><br />Nominations, consisting of a two page justification and (links to) the respective papers, as well as additional supporting letters, should be sent by e-mail to:<br /><br /> Peter Widmayer<br /> <a href="mailto:widmayer@inf.ethz.ch" target="_blank">widmayer@inf.ethz.ch</a><br /><br />The subject line of every nomination should start with Presburger Award 2015, and the message must be received before December 31st, 2014.<br /><br />The award includes an amount of 1000 Euro and an invitation to ICALP 2015 for a lecture.<br /><br />Previous Winners:<br /><ul><li>Mikołaj Bojanczyk, 2010</li><li>Patricia Bouyer-Decitre, 2011</li><li>Venkatesan Guruswami and Mihai Patrascu, 2012</li><li>Erik Demaine, 2013</li><li>David Woodruff, 2014</li></ul>Official website: <a href="http://www.eatcs.org/index.php/presburger" target="_blank">http://www.eatcs.org/index.<wbr></wbr>php/presburger</a>http://processalgebra.blogspot.com/2014/09/call-for-nominations-presburger-award.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-1700327409486803707Thu, 11 Sep 2014 22:18:00 +00002014-09-11T22:18:54.822ZCall for Nominations: EATCS Distinguished Dissertation Award 2014The <a href="http://eatcs.org/" target="_blank">EATCS</a> has established the <a href="http://eatcs.org/index.php/component/content/article/1-news/1949--eatcs-distinguished-dissertation-award-2014" target="_blank">EATCS Distinguished Dissertation Award</a> to promote and recognize outstanding dissertations in the field of Theoretical Computer Science.<br /><br />Any PhD dissertation in the field of Theoretical Computer Science that has been successfully defended in 2014 is eligible.<br /><br />Three dissertations will be selected by the committee for year 2014. The dissertations will be evaluated on the basis of originality and potential impact on their respective fields and on Theoretical Computer Science.<br /><br />Each of the selected dissertations will receive a prize of 1000 Euro. The award receiving dissertations will be published on the EATCS web site, where all the EATCS Distinguished Dissertations will be collected.<br /><br />The dissertation must be submitted by the author as an attachment to an email message sent to the address <a href="mailto:giuper@gmail.com">giuper@gmail.com</a> with subject <i>EATCS Distinguished Dissertation Award 2014</i> by 31 December 2014. The body of the message must specify:<br /><br /><ul><li>Name and email address of the candidate;</li><li>Title of the dissertation;</li><li>Department that has awarded the PhD and denomination of the PhD program;</li><li>Name and email address of the thesis supervisor;</li><li>Date of the successful defence of the thesis.</li></ul>A five page abstract of the dissertation and a letter by the thesis supervisor certifying that the thesis has been successfully defended must also be included. In addition, the author must include an endorsement letter from the thesis supervisor and can include one more additional endorsement letters.<br /><br />The dissertations will be selected by the following committee:<br /><ul><li>Javier Esparza</li><li>Fedor Fomin</li><li>Luke Ong</li><li>Giuseppe Persiano</li></ul>The award committee will solicit the opinion of members of the research community as appropriate.<br /><br />Theses supervised by members of the selection committee are not eligible.<br /><br />The EATCS is committed to equal opportunities, and welcomes submissions of outstanding theses from all authors.http://processalgebra.blogspot.com/2014/09/call-for-nominations-eatcs.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-8897743790347390700Mon, 08 Sep 2014 09:18:00 +00002014-09-08T09:18:03.197ZReport of TRENDS 2014 (Guest post by Ilaria Castellani and MohammadReza Mousavi)<i><a href="http://www-sop.inria.fr/members/Ilaria.Castellani/Home.html" target="_blank">Ilaria Castellani</a> and <a href="http://ceres.hh.se/mediawiki/Mohammad_Mousavi" target="_blank">MohammadReza Mousavi </a>have kindly written this guest post reporting on TRENDS 2014, a satellite event of <a href="http://concur2014.org/" target="_blank">CONCUR 2014</a> organized by IFIP WG1.8 on Concurrency Theory. Enjoy it!</i><br /><br /><a href="http://ceres.hh.se/mediawiki/index.php/TRENDS_2014" target="_blank">TRENDS 2014 </a>is the third edition of the series of workshops organized by the IFIP Working Group 1.8 on Concurrency Theory. TRENDS traditionally comprises invited speeches by both promising young researchers and leading senior researchers to demonstrate the emerging trends in concurrency theory research. The workshop is followed by the business meeting of the working group, which is open to the public. This year's TRENDS was attended by 20 participants throughout the workshop and featured 4 excellent talks by the following first class speakers: <br /><ol><li> <b>Alexandra Silva</b> gave an introduction to using co-algebras as a generic way of exploiting efficient algorithms in automata theory for minimization and equivalence checking of labelled transition systems (or different variants thereof) with respect to various notions of behavioural equivalence. In particular, she showed how <a href="http://en.wikipedia.org/wiki/DFA_minimization#Brzozowski.27s_algorithm" target="_blank">Brzozowski's algorithm</a> for minimization of finite automata can be used to minimize LTS's efficiently and also how Hopcroft and Karp's algorithm for checking language equivalence can be used to check equivalence of LTS's with respect to different notions of behavioural equivalence. She also presented some ideas about the application of learning algorithms for automata in the domain of concurrency theory. She concluded her talk by the following motto: <i>Co-algebra is not only about semantics, but also about algorithms. </i>Alexandra's slides are <a href="http://ceres.hh.se/mediawiki/images/3/3c/Alexandra_silva_trends_2014.pdf" target="_blank">here</a>. <i><br /></i></li><li> <b>Simon Gay </b> gave an overview of the history of session types and in particular remembered the legacy of the late Kohei Honda as the founding father of this field. He then pointed subsequent important developments in the field, such as the introduction of behavioural sub-typing by himself and the link to linear logic and the very interesting recent interpretation of the Curry-Howard isomorphism in the concurrency theory setting by Luís Caires, Frank Pfenning and associates. He also gave an overview of the future challenges in this field. </li><li> <b>Michele Bugliesi</b>, who has recently been appointed as the Rector of the University of Venice, pinpointed security vulnerabilities in the current practice of authentication. Then, he presented the solutions devised by him and his associates through client-side protection of authentication cookies. The devised techniques were formally shown to guarantee security (provide authentication and integrity) on a formalization of the Firefox browser. The proof techniques use a noninterference-like notion, which exemplifies yet another application of concurrency theory. </li><li> <b>Stéphanie Delaune</b> gave a presentation on the formal modelling and analysis of cryptographic protocols. She used a privacy issue in the old French electronic passport as a motivating example and showed how process algebraic formalisms, such as the applied pi-calculus, can be used in modelling the protocols used in such an e-passport (at an abstract level) and how behavioural equivalences (equipped with additional term equivalences on terms) can be used to verify these protocols. She pointed out several existing tools for this purpose, also developed within her group at ENS Cachan, and presented the challenges in her ongoing research.</li></ol>http://processalgebra.blogspot.com/2014/09/report-of-trends-2014-guest-post-by.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-4194676764449810022Fri, 29 Aug 2014 16:01:00 +00002014-09-08T10:38:36.975ZTwo recent events in Reykjavik: Crossroads of Art and Science and the 10th ICE-TCS Theory DayThe autumn semester 2014 started on Monday, 18 August, for us at the <a href="http://en.ru.is/CS/" target="_blank">School of Computer Science at Reykjavik University</a> (SCS). As usual at this time of the year, teaching-related matters took centre stage and occupied most faculty members, especially since we had just welcomed our third intake of well over 300 new computer science students. However, many of us at the <a href="http://www.icetcs.ru.is/">Icelandic Centre of Excellence in Theoretical Computer Science (ICE-TCS)</a> will remember the first week of the new academic year for two events showcasing the artistic and scientific work of <a href="http://erikdemaine.org/" target="_blank">Erik Demaine</a>, who visited ICE-TCS and the <a href="http://en.ru.is/CS/">School of Computer Science at Reykjavik University</a> in the period 20-27 August.<br /><br />The first event, <a href="http://icetcs.ru.is/crossroads-art-science/" target="_blank">Crossroads of Art and Science</a>, took place on Thursday, 21 August 2014, from 5pm till 7pm GMT, and was organized by ICE-TCS, SCS and <a href="http://www.visindafelag.is/">Vísindafélag Íslendinga</a> (the Icelandic Academy of Sciences). It was attended by about 220 people, including a good number of our undergraduate students, and featured a keynote address by Erik entitled <a href="http://icetcs.ru.is/crossroads-art-science/Erik.txt"><i>Folding Paper: Visual Art Meets Mathematics. </i></a><br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-MzG5c0aI6Uk/VA2GycABPkI/AAAAAAAAQ4Q/9XUrR32Ph60/s1600/ErikCrossroads.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-MzG5c0aI6Uk/VA2GycABPkI/AAAAAAAAQ4Q/9XUrR32Ph60/s1600/ErikCrossroads.jpg" height="320" width="237" /></a></div><br /><br />Art and science are often viewed as very different, and somewhat antithetic, human endeavours, so much so that some artists happily profess ignorance of the basic methods and results of science and some scientists sneer at art. In 1959, this prompted British scientist and novelist <a href="http://en.wikipedia.org/wiki/C._P._Snow" target="_blank">C. P. Snow</a> to express his view that "the intellectual life of the whole of western society" was split into two separate cultures---namely the sciences and the humanities---and that this was a major hindrance to solving the world's problems.<br /><br />However, we can all mention key figures from the Renaissance and earlier times who were both artists and scientists. Is the breed of the Renaissance man a thing from a long gone past? The aim of <a href="http://icetcs.ru.is/crossroads-art-science/" target="_blank">Crossroads of Art and Science</a> was to provide resounding evidence that the distinction between art and science in modern society is fictitious. We did so by showcasing three figures of polymaths whose work, be it artistic or scientific, benefits from the interplay of art and science.<br /><br /><a href="http://erikdemaine.org/" target="_blank">Erik Demaine</a> needs no introduction to the readers of this piece. He helped start the field of Computational Origami, but he is also an artist, some of whose work has been exhibited at the MoMA, amongst other venues. He uses art to explore the feasibility of some of his mathematical ideas and mathematics to suggest artistic ideas, leading, for instance, to paper or glass sculptures. To quote Erik himself: <br /><blockquote>"One of our growing realizations over the years is that mathematics itself is an art form, and I think that's what attracted both of us to this area in the first place. [I]t has the same kind of creativity, the same kinds of aesthetics, that you get in art: You want a clean problem to solve, and you want an elegant solution to that problem. Both art and mathematics are about having the right ideas [and] executing those ideas in some convincing way, so in that sense they're indistinguishable." (See <a href="http://www.brainpickings.org/index.php/2011/04/06/erik-demaine-computational-origami/">here</a> for the video of that presentation.) </blockquote>In case you have not done so already, do look at the inspirational video Erik produced when he received the <a href="http://www.eatcs.org/index.php/component/content/article/1-news/1512-presburger-award-2013" target="_blank">Presburger Award 2013</a>.<br /><br /><iframe allowfullscreen="" frameborder="0" height="315" src="//www.youtube.com/embed/ROYIVVZ5gvE" width="560"></iframe> <br /><br />Crossroads of Art and Science also featured two Icelandic speakers. <br /><ul><li><a href="http://annahrund.carbonmade.com/">Anna Hrund Másdóttir</a> is an artist and a mathematics teacher who teaches mathematics to support her art practice and whose teaching benefits from her artistic work. </li><li><a href="https://www.linkedin.com/pub/kjartan-emilsson/0/b/534">Kjartan Emilsson</a>, a mathematical physicist by training, uses artistic methods of working and thinking in his work as Principal Game Designer and Studio Managing Director at CCP in Shanghai, where he directs the innovation and implementation of core virtual world game designs for CCP Games. </li></ul>The thesis underlying Crossroads of Art and Science was that art and science are not antithetic, and that their cooperation can lead to powerful ways for solving scientific problems and to creating new art forms. As <a href="http://en.wikipedia.org/wiki/Nicholas_of_Cusa" target="_blank">Nicholasof Cusa</a> put it in his philosophy, and as Anna Hrund wrote in the title of <a href="http://icetcs.ru.is/crossroads-art-science/Anna.txt" target="_blank">her presentation</a>, we are in the presence of a "coincidence of opposites". We like to think that the people attending the event went home agreeing with that message.<br /><br />If you understand Icelandic, you might enjoying listening to an excellent <a href="http://ruv.is/sarpurinn/sjonmal/26082014" target="_blank">radio interview with Magnús M. Halldórsson</a> where he discusses the event and its theme with the host of the show. (The interview starts at around minute 15:40 and lasts for about 14 minutes.)<br /><br />The second keynote address delivered by Erik Demaine was part of the <a href="http://icetcs.ru.is/theory-day2014.html" target="_blank">10th ICE-TCS Theory Day</a> and was entitled <a href="http://icetcs.ru.is/TD2014/ErikTD.txt"><i>Replicators, Transformers, and Robot Swarms: Science Fiction through Geometric Algorithms.</i></a>. Erik's talk wasvery well attended and the audience included a good number of undergraduate students. During the talk, Erik presented some of his work that draws inspiration from science fiction and presented some answers to the following questions:<br /><ol><li>How can we build reconfigurable robots like Transformers or Terminator 2? </li><li>How can we orchestrate the motion of a large swarm of robots? </li><li>How can we build Star Trek-style replicators that duplicate or mass-produce a given shape at the nano scale? </li></ol>While addressing the first question, Erik gave us a whirlwind tour of his work on the <a href="http://erikdemaine.org/papers/Crystalline_CGTA/" target="_blank">equivalence of models for modular robots</a>, <a href="http://erikdemaine.org/papers/Moteins_TRO/" target="_blank">hinged dissections</a> (see <a href="http://en.wikipedia.org/wiki/Hinged_dissection" target="_blank">this Wikipedia page</a> for a brief introduction) and <a href="http://people.csail.mit.edu/nbenbern/Robotica.pdf" target="_blank">robotic paper</a>. He also mentioned some of the work done in the context of the <a href="http://milli.cba.mit.edu/" target="_blank">Millibiology project</a> at MIT. Of course, the recently unveiled origami robot featured in this part of Erik's presentation, as well as some of its early incarnations.<br /><br /><iframe allowfullscreen="" frameborder="0" height="315" src="//www.youtube.com/embed/CihMimZc3Ac" width="420"></iframe> <br /><br />In his discussion of problems related to robot swarms, Erik mentioned the <a href="http://erikdemaine.org/papers/BoundaryDetection_IROS2009/" target="_blank">distributed boundary detection algorithm</a> he developed with <a href="http://people.csail.mit.edu/jamesm/">James McLurkin</a>, which is suitable for use on multi-robot systems with dynamic network topologies. The game of <a href="http://www.thinkfun.com/tilt" target="_blank">Tilt</a> also featured in this part of Erik's talk, together with a <a href="http://erikdemaine.org/papers/Tilt_ALGOSENSORS2013/" target="_blank">sketch of the proof of its NP-hardness</a>.<br /><br /><br /><iframe allowfullscreen="" frameborder="0" height="315" src="//www.youtube.com/embed/mFGevho4OLY" width="560"></iframe> <br /><br />Finally, we were given a glimpse of some of Erik's fascinating work related to replicators. Two highlights were <a href="http://erikdemaine.org/papers/StagedAssembly_DNA2007/" target="_blank"><i>staged self-assembly</i> of Wang tiles</a> and <a href="http://erikdemaine.org/papers/Replication_SODA2010/" target="_blank">shape replication in the Wang tile self-assembly model</a>. Amongst other things, Erik showed the audience how to make infinitely many copies of any shape without holes in a single stage!<br /><br />Last, but by no means least, the Theory Day 2014 included two presentations by members of ICE-TCS. <a href="http://www.ru.is/faculty/marjan/">Marjan Sirjani</a> discussed some work done by her research group in Reykjavik and Tehran on analysis of network-on-chips using probabilistic timed actors. This work uses the language <a href="http://www.rebeca-lang.org/wiki/pmwiki.php" target="_blank">Rebeca</a> and its tool set. <a href="http://www.liafa.univ-paris-diderot.fr/%7Ekonrad/">Christian Konrad</a> closed the programme by presenting work on <a href="http://www.liafa.univ-paris-diderot.fr/%7Ekonrad/publications/ckyyz14.pdf"><i>Robust Set Reconciliation</i></a>, which was selected for presentation at SIGMOD 2014.<br /><br />At the end of the scientific programme, the attendees mingled while being treated to chocolate and sparkling wine.<br /><br />As you can see, the fun continued after dinner with an impromptu origami masterclass where people attempted to fold a <a href="http://erikdemaine.org/curved/history/" target="_blank">hyperbolic paraboloid</a> (Albers 1927). The instructions are <a href="https://www.youtube.com/watch?v=4g1OcLHp6yI" target="_blank">here</a>. <br /><br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-7LkgMwK204I/U_ixXDsHw1I/AAAAAAAAQ0M/HpG84zS7GaA/s1600/2014-08-22%2B22.30.37.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-7LkgMwK204I/U_ixXDsHw1I/AAAAAAAAQ0M/HpG84zS7GaA/s1600/2014-08-22%2B22.30.37.jpg" height="240" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-lIpwEbaSGh4/U_ixMe2DzMI/AAAAAAAAQzc/l2FIt3whusY/s1600/2014-08-22%2B22.38.41.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-lIpwEbaSGh4/U_ixMe2DzMI/AAAAAAAAQzc/l2FIt3whusY/s1600/2014-08-22%2B22.38.41.jpg" height="240" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"></div><br /><br /><br />We held the first Theory Day in 2005, the day after the opening of ICE-TCS, and we have been having one such event every year since then.The list of foreign guests we have had so far for the Theory Day reads as follows:<br /><br /><ul><li>2005: Ryan Hayward (Alberta), Kim G. Larsen (Aalborg), Mogens Nielsen (Aarhus)</li><li>2006: Wan Fokkink (VU Amsterdam), Jan Kratochvil (Prague), Moshe Vardi (Rice)</li><li>2007: Thomas Erlebach (Leicester), Tommi Sottinen (Helsinki)</li><li>2008: None, but we had all the ICALP invited <span class="il">speakers in July.</span> </li><li>2009: Zoltan Esik (Szeged), Paul van Tilburg (Eindhoven)</li><li>2010: David de Frutos Escrig and Carlos Gregorio-Rodriguez (both at the Universidad Complutense de Madrid).</li><li>2011: None</li><li>2012: None</li><li>2013: Pierluigi Crescenzi (Firenze), Pierre Fraigniaud (Paris Diderot) and Stephan Holzer (ETH)</li><li>2014: Erik Demaine (MIT)</li></ul>We will see what the future will bring and look forward to celebrating the tenth birthday of ICE-TCS next year. Whatever we do, it will be hard to top the impact and national visibility of last week's events.<br /><br />http://processalgebra.blogspot.com/2014/08/two-recent-events-in-reykjavik.htmlnoreply@blogger.com (Luca Aceto)1tag:blogger.com,1999:blog-27705661.post-7121051006193277360Sun, 13 Jul 2014 07:53:00 +00002014-07-13T07:53:35.575ZDay 4 and Recap of ICALP 2014 (guest post by Andrew Winslow)<i>Here is the last guest post by <a href="http://www.eecs.tufts.edu/%7Eawinslow/" target="_blank">Andrew Winslow </a> from ICALP 2014. Enjoy it! Thanks to Andrew for his conference reports. </i><br /><br />This [Friday, 11 July 2014] is the last day of ICALP! <br /><h3><a href="http://link.springer.com/chapter/10.1007/978-3-662-43948-7_72">George Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos and Paul Spirakis. Determining Majority in Networks with Local Interactions and very Small Local Memory</a></h3>This talk focused on a problem in distributed computing on a graph with stateful nodes. Given a graph with nodes colored red and blue, a <i>population protocol</i> is a set of rules that define how the colors of a pair of endpoints of an edge can be transformed. For instance, a population protocol might include a rule to turn the colors of a pair of red nodes sharing to both be blue. One is also allowed to add additional colors not found in inputs, and the total number of colors that appear in the input and population protocol is the number of <i>states</i> of the protocol. <br />A population protocol for the <i>majority problem</i> transforms the colors of all (or all but a (1-ε) fraction) of the nodes into the color appearing most frequently in the input graph. In may be possible at any point during the execution of the protocol that more than one rule can be applied to the endpoints of more than one edge, and it is assumed that either the rules are chosen randomly (a <i>randomized scheduler</i>) or advesarially subject to some basic requirements, like that any rule that can be applied is applied after a finite amount of time (a <i>fair scheduler</i>). One can also ask about the amount of time (i.e. the number of rule applications) needed for a majority to be reached.<br /><br />It was previously known that a 3-state protocol for majority exists in the case that both the graph is a clique and the ratio of the occurrence counts of most common color over least common color is ω(sqrt(n)log(n))[1]. In this work, Mertzios, Nikoletseas, Christoforos, and Spirakis constructed a four-state protocol that correct computes majority with probability 1 on any graph and with any difference between the number of occurrences of the two colors, assuming a fair scheduler. They also prove that the 3-state protocol described in [1] is strictly worse, failing to converge to the correct majority with high probability for an infinite family of graphs (graphs consisting of a clique at the end of a chain), even with a probabilistic scheduler.<br /><br />[1] D. Angluin, J. Aspnes, and D. Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Computing, 21(2): 87-102, 2008. <br /><h3><a href="http://link.springer.com/chapter/10.1007/978-3-662-43948-7_21">Karl Bringmann, Fabian Kuhn, Konstantinos Panagiotou, Ueli Peter and Henning Thomas. Internal DLA: Efficient Simulation of a Physical Growth Model.</a></h3>Karl gave the talk. This work is about improving the speed of sampling the results of the following process, called <i>internal diffuse limited aggregation</i> or <i>IDLA</i>: <br /><ol><li>Place a particle at origin in the square lattice. </li><li>Take a random walk with this particle until a lattice location not containing another particle is found. </li><li>Place this particle at the empty location. </li></ol>As one might expect, the resulting shape of the particle locations is usually roundish. The roundness can be captured by considering the ratio of the radii of the smallest containing and largest contained circles for the shape, centered at the origin. It is known that the expected difference in the ratios of these circles is O(log(n)), i.e. that the shape is usually quite round. <br />The IDLA process comes from statistical physics, and natural problems in this area related to understanding the distribution of shapes generated by this process. The naive approach to randomly sample the result of the IDLA process takes O(n^2) time, since the expected radius is Theta(n^0.5), a randomly walk from the origin takes Theta(n) expected time to reach an empty location (usually on the boundary), and n particles must be simulated. <br />Bringmann, Kuhn, Panagiotou, Peter, and Thomas improve this to O(nlog^2(n)) expected time and O(n^0.5*log(n)) expected space with high probability. The idea of the algorithm is to efficiently carry out the random walk by making large <i>jumps</i>, carrying out a significant portion of the walk in O(1) expected time. An upper bound on the number of jumps can then be obtained by computing the time expected to leave the region containing previous points (with radius O(sqrt(n)*log(n))). <br /><h3>Recap</h3>This was my first time attending ICALP, and overall had a great experience. The conference was well-organized and the work presented was consistently very high quality and also had a great diversity to it; every session had a fairly distinct theme. One of the more unique aspects of the conference are the three topical tracks, and the mixing and interaction between "Track-A people" and "Track-B people" (and don't forget Track-C people...) led to some great discussions. http://processalgebra.blogspot.com/2014/07/day-4-and-recap-of-icalp-2014-guest.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-8478509124949143196Fri, 11 Jul 2014 10:05:00 +00002014-07-11T10:05:08.277ZJuly 9, 2014 - July 10, 2014 ICALP (guest post by Clément Canonne)<div class="flushleft"><i>Here is the second guest post from ICALP 2014 kindly written by <a href="http://www.cs.columbia.edu/%7Eccanonne/" target="_blank">Clément Canonne</a>. Enjoy it! (This post is also available in <a href="http://www.ru.is/%7Eluca/ICALP2014/Canonne2.pdf" target="_blank">PDF</a>. Any typo or typesetting issue with the HTML version is my responsibility.)</i><br /> </div><h4 class="likesubsectionHead"><a href="https://www.blogger.com/null" id="x1-1000" name="x1-1000"></a>Fast Algorithms for Constructing Maximum Entropy Summary Trees (Howard Karloff)</h4>This talk <a href="http://dx.doi.org/10.1007/978-3-662-43948-7_28">[1]</a> revolved around a question. A simple question, really. <em>“How to draw a rooted tree?”</em> Not <em>any</em>tree, though: a big one. A huge, gigantic n-node tree T, with n » ⌊2<sup>22.891112</sup>⌋ [2], on a tiny sheet of paper (or a screen, for that matter). Most of the time, the approach is either to<br /> <ul class="itemize1"><li class="itemize">draw the whole thing, get a binocular and hope something can be seen at all;</li><li class="itemize">go for interaction, and draw/zoom on parts of the graph on-the-fly.</li></ul>Here, none of this: T is T, magnificent n-node weighted tree; and we are given a parameter k ≥ n, to be though of as k « n; the task is to draw a k-node tree T<sup>′</sup>, the “best summary” of T. (At this point – <a href="http://www2.research.att.com/%7Ekshirley/summarytrees/summarytrees_gauss.pdf">a demo</a>! From the Mathematical Genealogy Project: the tree being made of the academic descendants of a obscure mathematician, someone named Gauss. That’s a hell of a tree.)<br /> The key of their approach is <em>not</em> to draw only k carefully chosen nodes of T, and dismiss the others; but instead to allow T<sup>′</sup> to combine subsets of T’s nodes into a big, meta-node named “others” (†).<br /> Sure. But what is a “good summary” anyway? Quite naturally, the authors went for entropy – a tree is <em>good</em> if, assigning weights to nodes in the straightforward fashion (for v ∈ T<sup>′</sup>, ω<sub>v</sub> ∝ the total weight of original nodes of T in the subtree of T<sup>′</sup> rooted at v), the entropy<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-T2CJihKylMo/U7-2XsS8nAI/AAAAAAAAQW4/Uus6VJxumJY/s1600/icalp-0707-0710-hkarloff-rmdoliveira0x.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-T2CJihKylMo/U7-2XsS8nAI/AAAAAAAAQW4/Uus6VJxumJY/s1600/icalp-0707-0710-hkarloff-rmdoliveira0x.png" /></a></div><br />is big. That is, if T<sup>′</sup> is as balanced as possible, or phrased differently remains very <em>informative</em>.<br /><br /><span class="paragraphHead"><a href="https://www.blogger.com/null" id="x1-2000" name="x1-2000"></a>So, what’s the problem?</span> The problem is exactly (†), when it comes to computing such an optimal k-node summary tree. Indeed, if we allow an algorithm to combine an arbitrary subset of a node v into a metanode others<sub>v</sub> (and we do!), there is the slight problem of having exponentially many possibilities – and that could turn out pretty bad. An intuitive idea [3] would be to sort v’s children by non-decreasing weights, and combine together a <em>prefix</em> (the first, say, ℓ of them) – they shouldn’t be too important anyway. Sadly, it does not work – there are counter examples, even for n = 7 and k = 4.<br /><br /> In a previous work <a href="http://www.research.att.com/techdocs/TD_100908.pdf">[4]</a>, <a href="http://www.research.att.com/people/Shirley_Kenneth_E/index.html">Kenneth Shirley</a> and <a href="http://www.research.att.com/archive/people/Karloff_Howard_J/index.html">Howard Karloff</a> managed to give a <em>pseudo</em>polynomial algorithm (polynomial in the total weight), and a polynomial-time (additive) approximation one. This works came for the kill, removing the “pseudo” to give<br /> <ul class="itemize1"><li class="itemize">a O(k<sup>2</sup>n + nlog n)-time algorithm for computing an optimal k-node summary tree;</li><li class="itemize">a (better) O(n + poly(k,1∕ε))-time approximation algorithm</li></ul>as well as a faster (albeit non-provably optimal) greedy algorithm. The crux of the approach? Prefixes don’t work, alright. But <em>extended prefixes</em> do! Instead of (after sorting a node v’s children) merging the nodes {1,…,ℓ}, it is sufficient to merge the {1,…,ℓ,ℓ<sup>′</sup>} for some ℓ<sup>′</sup> ≥ ℓ + 1 (yes, it is surprising to me too).<br /> And <em>voilà</em>! Polynomial time.<br /> <h4 class="likesubsectionHead"><a href="https://www.blogger.com/null" id="x1-3000" name="x1-3000"></a>Testing Equivalence of Polynomials under Shifts (Rafael Mendes de Oliveira)</h4>And now, some testing <a href="http://www.cs.princeton.edu/%7Ezdvir/papers/DOS13.pdf">[5]</a>! <a href="http://www.cs.princeton.edu/%7Ermo/">Rafael</a> has a device: a blackbox computing a n-variate polynomial P ∈ F[X<sub>1</sub>,…,X<sub>n</sub>] (for some fixed field F). And another one – computing Q ∈ F[X<sub>1</sub>,…,X<sub>n</sub>]. On inputs x ∈ F<sup>n</sup>, these two devices allow him to compute P(x), Q(x) in constant time.<br /><br class="newline" />Rafael also has two coauthors, <a href="http://www.cs.princeton.edu/%7Ezdvir/">Zeev Dvir</a> and <a href="http://www.cs.technion.ac.il/%7Eshpilka/">Amir Shpilka</a>, and a question:<br /> <div class="newtheorem"><span class="head"><a href="https://www.blogger.com/null" id="x1-3001r1" name="x1-3001r1"></a> <strong>Question</strong> (Shift Equivalence Testing (SET)).</span> Given a bound on their degree, decide if P and Q are <em>morally</em> the same polynomial. That is, if there is a shift vector a such that P(⋅ + a) = Q(⋅) (and if so, please, find one.)<br /> </div>This is arguably a natural generalization of the infamous Polynomial Identity Testing (PIT) problem, where the goal is to decide whether P is the all-zero polynomial or not. PIT does not have any known efficient deterministic algorithm, but a very simple polynomial-time randomized one; and the task of improving this state of affairs has ramifications in many areas.<br /> So SET must be difficult, since it not only generalizes the question, but also asks for an explicit witness – this vector a. After giving some background on what is known about related questions (is P “shift-equivalent” to a polynomial that can be represented with very few non-zero coefficients, for instance), Rafael gave the main result of their paper:<br /> <div class="newtheorem"><span class="head"><a href="https://www.blogger.com/null" id="x1-3002r1" name="x1-3002r1"></a> <strong>Theorem.</strong></span> There is an efficient (randomized) algorithm for SET. Furthermore, the only randomized part comes from solving instances of PIT.<br /> </div>In other words, in spite of what it seems, SET is not much harder than PIT; and any improvement on the use of randomness for PIT directly translates to the corresponding improvement for SET!<br /> Roughly speaking, the idea of the proof is to try to find a “one step at a time”, by successively coming up with candidates a<sub>d</sub>, a<sub>d-1</sub>, …, a<sub>1</sub>. How? Find a<sub>d</sub> that matches the degree-d part of P(⋅ + a) and Q(⋅) – this is just a linear system to solve, along with a call to a randomized subroutine for PIT. Then find a<sub>d-1</sub> that matches both the degree-d and degree-(d - 1) parts of P(⋅ + a) and Q(⋅) – this no longer linear, alas. But, and that’s the trick, one can plug the known value of a<sub>d</sub> in the quadratic system to make it collapse to a linear system, which has the same solutions as the quadratic one!<br /> And so on, and so forth: after computing a<sub>k+1</sub>, one just has to solve a linear system to get a<sub>k</sub>, using the nice properties of a<sub>k+1</sub> (simplifications “trickles down”), before calling PIT to make sure the result is correct so far. And at the end of the day, either a<sub>1</sub> is a good shift-vector, or there is none – and a final call the PIT subroutine lets us know which of the two cases hold.<br /> Hop.<br /> <ul><li class="itemize">[1] <em>Fast Algorithms for Constructing Maximum Entropy Summary Trees</em>, R. Cole and H. Karloff. ICALP, 2014.</li><li class="itemize">[2] This is a prime number. Check it out.</li><li class="itemize">[3] Rule of thumb: when I write “intuitive”, it is a trap.</li><li class="itemize">[4] <em>Maximum Entropy Summary Trees</em>, K. Shirley and H. Karloff, Computer Graphics Forum. 2013.</li><li class="itemize">[5] <em>Testing Equivalence of Polynomials under Shifts</em>, Z. Dvir, R.M de Oliveira, and A. Shpilka. ICALP, 2014.</li></ul>http://processalgebra.blogspot.com/2014/07/july-9-2014-july-10-2014-icalp-guest.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-2386707031459231620Thu, 10 Jul 2014 20:08:00 +00002014-07-10T20:08:29.907ZDay 3 of ICALP 2014 (guest post by Andrew Winslow)<i>Here is the third guest post by <a href="http://www.eecs.tufts.edu/%7Eawinslow/" target="_blank">Andrew Winslow </a> from ICALP 2014. Enjoy it! </i><br /><h3>Invited Talk: Sanjeev Arora</h3><a href="http://www.cs.princeton.edu/%7Earora/" target="_blank">Sanjeev</a> gave a survey of recent work by himself and others in working to develop provable bounds on the performance of many problems across unsupervised learning. The talk itself was entitled "Overcoming Intractability for Unsupervised Learning", where the "unsupervised" refers (loosely) to being given a pile of raw data and asked to extra some relevant statistical data, e.g. given a collection of newspaper articles, what topics do they cover. The foothold for these problems is assuming that the data comes from some (unknown) distribution, and many fo the problems relate to learning something about the distribution.<br /><br />Almost all of the problems covered are NP-hard, and the first part of the talk was an explanation of how this is overcome. In Sanjeev's words, "NP-hardness is not the right way to think about this". He explained that the starting point is determining if the set of interesting/realistic/natural instances lie in a tractable subset by looking for realistic assumptions that lead to tractable instances. <br />As an example, he described the topic modelling problem, where one is given a corpus of text (e.g. all New York Times articles) and the goal is to describe each article as a linear combination of topics, where the topics are <i>not</i> given in advance (i.e. unsupervised learning). A geometric view of this problem is being given a set of points in a convex polytope (articles) and being asked to find the vertices of the polytope (topics). The problem is NP-hard in general, but can be made tractable by assuming that the data is separable: the vertices are included in the set of points given. Then a polynomial time algorithm have be obtained: for each point, test if it's contained on the convex hull, if not, it can be removed, and otherwise it must be a vertex.<br /><br />He also spoke about making process on other machine learning techniques, including dictionary learning (given complex objects built from a small, simple dictionary, compute the dictionary) and approaches like deep learning (many-level neutral networks). Dictionary learning and deep learning are both thought to take place in the human visual cortex, giving good evidence that their worst-case intractability is not a barrier to their effective use. For the case of deep learning, Sanjeev pointed out that learning the network is effectively trying to learn a <a href="http://en.wikipedia.org/wiki/TC0" target="_blank">TC^0</a> (ouch!) and yet they have been used successfully by machine learning people to achieve high accuracy rates on large corpora. <br /><h3><a href="http://link.springer.com/chapter/10.1007/978-3-662-43948-7_4" target="_blank">Amir Abboud, Virginia Vassilevska Williams and Oren Weimann. Consequences of Faster Alignment of Sequences.</a></h3>Amir gave this talk on conditional lower bounds on local matching a pair of strings: given a function defining a score for every pair of symbols, find a pair substrings from the input string that maximizes the score. Like other string problems, including longest common subsequence, the best known algorithm for local alignment takes quadratic time and has resisted improvements in the exponent to, say, O(n^1.99). <br />Amir was quick to point out local alignment is hugely important in genomic sequence analysis (heuristics like <a href="http://en.wikipedia.org/wiki/BLAST" target="_blank">BLAST</a> are hugely popular) and that quadratic is too slow in these cases, since n can be several billion. Abboud, Williams, and Weimann prove that a O(n^{2-ε})-time algorithm for local alignment implies the following results: <br /><ul><li>3SUM solved in O(n^{2-δ}) time for some δ, refuting the weak form of the 3SUM conjecture. </li><li>CNF-SAT solvable in O((2-δ)^n) time, refuting the strong exponential time hypothesis. </li><li>Max-4-Clique solvable in O(n^{4-δ}) time for some δ, resolving a long-standing opening problem of improving the best-known algorithm for Max-4-Clique. </li></ul>They also prove similar results for other problems, including edit distance with gap penalties, and longest commen subsequence with wildcards (input strings are allowed to have wildcard characters that match any character). The proofs follow the usual approach of using a O(n^{2-ε})-time local alignment algorithm to produce faster algorithms for the other problems and those that Amir showed were very clean. <br /><h3><a href="http://link.springer.com/chapter/10.1007/978-3-662-43948-7_10" target="_blank">Amihood Amir, Timothy M. Chan, Moshe Lewenstein and Noa Lewenstein. On Hardness of Jumbled Indexing.</a></h3>This work has a similar flavor to the Abboud, Williams, Weimann paper, using the 3SUM conjecture to develop lower bounds for string problems. <i>Unlike</i> that paper, this work gives lower bounds for data structures answering queries. The main problem considered is of jumbled, a.k.a. histogram indexing: given a string T with alphabet of size k, preprocess T to answer queries of the form "what substrings of T have character occurrence counts ", i.e. what substrings have the given histogram. For many pattern matching problems on strings, suffix trees/arrays are used to achieve linear-time queries. <br />For histogram indexing, naive approaches yield either O(1) preprocessing and O(n) query time (scanning the string using a window whose size is the sum of the entries in the histogram) or O(kn^2) preprocessing time and O(1) query time (precompute the histograms of all substrings and look up the answer). The contribution of Amir, Chan, Lewenstein, and Lewenstein is to prove that, assuming the 3SUM conjecture, these results are the best possible. <br />For a fixed alphabet of size k at least 3, they prove that achieving O(n^{2-2/k}) preprocessing and O(n^{1-1/k}) query time simultaneously is 3SUM-hard. For alphabets of non-constant size, they prove that achieving O(n^{2-ε}) preprocessing and O(n^{1-δ}) query time is 3SUM-hard. He also mentioned that unpublished work with Timothy Chan achieves a positive result in the form of a data structure that achieves O(n^{2 - 2/k + O(1)}) preprocessing and O(n^{1 - 1/k + O(1)}) query time simultaneously for fixed alphabets. <br /><a href="http://u.cs.biu.ac.il/%7Emoshe/" target="_blank">Moshe</a> did a good job of mixing the problems, motivation, and technical details in a way that kept the talk interesting. Related to the reductions in this work, which use a reduction from convolution 3SUM (testing whether there exist two indices i, j, of the input array such that A[i] + A[j] = A[i+j]), he also recommended that people read Patrascu's <a href="http://www.ccs.neu.edu/home/viola/classes/papers/PatrascuTowards.pdf" target="_blank">paper</a> that proves this special form of 3SUM is 3SUM-hard. <br /><h3><a href="http://link.springer.com/chapter/10.1007/978-3-662-43948-7_53" target="_blank">John Iacono and Özgür Özkan. Why Some Heaps Support Constant-Amortized-Time Decrease-Key Operations, and Others Do Not</a></h3><a href="http://john.poly.edu/" target="_blank">John</a>'s hand-drawn slides caught the <a href="https://twitter.com/njlarsson/statuses/487240180848676865" target="_blank">attention</a> of some people from the very beginning, and combined with his deadpan delivery and promise to "keep it light" left the audience quiet chuckling through the talk. The talk started with a chat about heaps. All good heaps have O(log(n))-time insert and extract-min operations. Decrease-key is also an operation of heaps; some heaps are better at it. There are three families of heaps with three different running times for decrease-key: <br /><ul><li>Fibonacci and "improvements" that achieve O(1) time. </li><li>Pairing heaps that achieve O(2^{2^{sqrt{loglog(n)}}}) time. </li><li>Elmasry/sort heaps that achieve O(loglog(n)) time. </li></ul>All decrease-key operations of these trees pair small trees into bigger trees. What distingushes them is how they do this: <br /><ul><li>Pairing heaps: repeatedly pair trees recursively. Repeat until one tree remains. </li><li>Elmasry/sort heaps: break roots into blocks of size log(n), chain all roots of a block together. </li><li>For Fibonacci heaps: pair heaps whose roots have the same number of children. </li></ul>Note that the Fibonacci pair based on tree size, <i>not</i> key value, and use an augmentation of loglog(n) bits in each root. Seems like you augmented bits = fast? Fredman considered this in 1999, proving O(1) decrease-key implies Omega(loglog(n)) bits for some classes of heaps, namely pairing heaps. But lower bound requires assumption that every time a pair of roots have their values compared, their heaps are combined. <br />This contribution of Iacono and Özkan is a new lower bound without such the requirement that trees are combined when compared, but with a new restriction: must pay pointer model costs. This result yields lower bound of Omega(loglog(n)) for pairing and sort heaps, but says nothing about Fibonacci heaps because they cheat: they do not pay pointer model costs. A pointer model version would build a tree above the array, which would have height loglog(n) and give decrease-key a similar running time. The actual proof is adversarial, and considers a whole family of distinct Fibonacci heaps that must grow larger than the total number of possible heaps, a contradiction. http://processalgebra.blogspot.com/2014/07/day-3-of-icalp-2014-guest-post-by.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-2843701412868630710Thu, 10 Jul 2014 06:36:00 +00002014-07-10T06:36:52.248ZICALP Day 2 (guest post by Andrew Winslow)<i><a href="http://www.eecs.tufts.edu/%7Eawinslow/" target="_blank">Andrew Winslow </a>was one of the colleagues who kindly answered my call for guest bloggers from ICALP 2014. Here is guest post on the second conference day. Enjoy it! </i><br /><br /> <h3>Invited Talk: Victor Kuncak</h3><a href="http://lara.epfl.ch/%7Ekuncak/">Victor</a> gave a talk entitled "Verifying and Synthesizing Software with Recursive Functions" about work with his students, including <a href="http://www.mpi-sws.org/%7Episkac/">Ruzica Piskac</a>, Phillipe Suter, <a href="http://people.epfl.ch/eva.darulova">Eva Darulova</a>, <a href="http://www.croustillant.ch/">Ettienne Kneuss</a>, and <a href="http://people.epfl.ch/andrej.spielmann">Andrej Spielmann</a>. The work focused on a number of problems in the area of turning a specification into a program that meets it. He did a great job of breaking out four types of problems they're working on: <br /> <table border="1"> <tbody><tr align="center"><td> </td><td> Run-time </td><td> Compile-time</td></tr><tr align="center"><td> Have specification C and program P</td><td> Assertion checking <br /> (Check P meets C) </td><td> Prove correctness <br /> (Prove P always meets C) </td></tr><tr align="center"><td> Have specification C </td><td> Constraint programming <br /> (Carry out execution according to C) </td><td> Program synthesis <br /> (Create P meeting C) </td></tr></tbody></table>Their work is done in Scala and implemented in the <a href="http://leon.epfl.ch/">Leon</a> system. Out of the four types of problems, Victor indicated that the first two (first row of the table) are easier. Of course, easier doesn't mean easy, and he briefly covered a few of the ideas (induction, arithmetic/algebraic reasoning, SAT solvers, integer linear programs) used to achieve good empirical performance -- a few seconds to prove correctness programs of 100 lines of code or more, and counterexamples in the case of incorrect code. <br /> Constraint programming was next, and he gave the example of programming red-black tress via constraints: using as constraints the <a href="http://en.wikipedia.org/wiki/Red%C3%A2%E2%82%AC%E2%80%9Cblack_tree#Properties">five properties</a> a red-black tree must have. Insertion, for instance, would be encoded as a combination of the five properties, plus the fact that the new tree must have the elements of the old tree plus the inserted item. Although the performance was not great, he stressed that the applications of constraint programming are more along the lines of prototyping new data structures, test case generation, etc. One cool trick was using the fact that a solution is a counterexample of the negation of the constraints...reducing the problem to one in program verification. <br /> Finally, he covered most extreme problem: writing code based on a specification. Here he had some really nice examples, generating code for converting dates and times, simple data structures like sorted lists, etc. in just a few seconds. Many ideas were used, but I was especially impressed by his mention of their work on floating point representations, synthesizing programs that avoided rounding errors. <br /><h3><a href="http://link.springer.com/chapter/10.1007/978-3-662-43948-7_18">Andreas Björklund and Thore Husfeldt, Shortest Two Disjoint Paths in Polynomial Time</a></h3><a href="http://cs.lth.se/english/contact/andreas-bjorklund">Andreas</a> gave the talk for this Best Paper award winner in Track A. The problem considered is a very simple one: given an undirected graph and two pairs of vertices (s1, t1) and (s2, t2), find a pair of disjoint paths whose total length is minimized. Several problems near to this one are NP-hard (e.g. minimizing the maximum of the two path lengths), so placing the problem into P is the major thrust of the paper -- the algorithms given run in O(n^11) and O(n^22) time for vertex- and edge-disjoint paths, respectively. <br /> The approach of the algorithm is almost entirely matrix-based, focusing on solving a cycle cover problem on the input graph with self-loops added to each vertex...except that doesn't quite work. Andreas did a great job of leading us on a journey where obstacle after obstacle to the approach was eliminated. Many of the issues relate to the complexity of computing permanent...indeed one of the major technical contributions is proving that computing the permanent of a matrix over a certain type of ring is in P. In the end, the necessary permanent computation is replaced with a polynomial number of determinant computations, giving the large (but polynomial) running time. <br /> In perhaps the most natural course of events, someone asked after the talk whether the technique might work for the shortest three disjoint paths. So natural was the question that a followup slide for the question was already prepared. The conclusion was "probably not", but Andreas posed a first problem to try in this direction: given an undireced graph, compute the parity of the number of cycle covers having c cycles, with c divisible by 4. <br /><h3><a href="http://link.springer.com/chapter/10.1007/978-3-662-43948-7_63">Mitsuru Kusumoto and Yuichi Yoshida, Testing Forest-Isomorphism in the Adjacency List Model</a></h3>Mitsuru started by introducing the notion of <i>property testing</i> on graphs: computing whether the graph has a given property, answering correctly at least 2/3rds of the time while using only a small number of queries on the graph. In this setting, even the representation of a graph as an adjacency matrix or list matters, as checking whether a given edge is present takes too long with an adjacent list repesentation. <br /> Kusumoto and Yoshida considered the problem of testing whether two forests are isomorphic. It was known that in general graphs this problem requires Omega(sqrt(n)) queries to the graphs, and only O(1) if the graphs have bounded degree. For forests, they achieve an algorithm that uses only O(polylog(n)) queries and prove Omega(sqrt(log(n)) are needed. The algorithm works by first performing a special type of partitioning of the input graph, then testing whether each subgraph is isomorphic. The partitioning is done in a way that ensures that if the two input graphs are significantly far away from being isomorphic, then some pair of their subgraphs in their partitions are too. <br /><h3><a href="http://link.springer.com/chapter/10.1007/978-3-662-43951-7_33">Rom Aschner, Matthew J. Katz, Bounded-Angle Spanning Tree: Modeling Networks with Angular Constraints</a></h3><a href="http://www.cs.bgu.ac.il/%7Eromas/">Rom</a> gave a nicely visual talk about a problem in wireless network design in the plane. The input is a set of points, and the output is a (Euclidean) minimum spanning tree (MST) with an additional constraint: the smallest angle spanning all of the edges is at most some fixed constant b (a b-MST). Another way to think about this constraint is that the largest angle between any pair of adjacent incoming edges must be at least 2*π - b. <br /> For b < π / 3, a b-MST may not even exist: three points at the vertices of an equilateral triangle require at least one of the points to have two incoming edges with interior angle π / 3. For b >= 8 π / 5, the b-MST is simply the minimum spanning tree, as the upper degree bound of 5 on every node in an MST ensures the smallest angle spanning all of the edges is at least 2 * π - 2 π / 5 = 8 π / 5. Finally, for b < 1/2, there exists a simple family of examples (n-1 points placed collinearly ε distance apart and a final point distance 1 from the shared line) that causes the b-MST to have total weight ε * (n - 1) + 1 and b-MST to have total weight 1 * (n - 1) = n - 1. So the non-trivial b are those in the interval [1/2, 8/5*pi). <br /> For these, Aschner and Katz prove both NP-hardness and approximation results. They prove that finding the b-MST for b = π and b = 2 π / 3 are both NP-hard, using a reduction from Hamiltonian path in square and hexagonal grid graphs, respectively. They also achieve constant-factor approximation algorithms for b = π, 2 π / 3, π / 2. The approximation algorithms use a common sequence of steps: <br /><ol><li>Compute the MST. </li><li>Turn the MST into a Hamiltonian cycle via a tour around the boundary of the MST. </li><li>Decompose the points into consecutive groups along the cycle. </li><li>For each group, compute a set of edges connecting the points and minimizing total edge length. </li><li>Connect adjacent groups using the shortest edge possible. </li></ol>Step 4 requires a careful selection of group sizes, as larger groups give greater potential for shorter collections of edges, but for large enough b, actually connecting the points may not be possible. The resulting approximation ratios are 16 and lower, and can further be reduced by a neat pigeonhole argument regarding shofting the groupings along the tour. <h3>Canal Tour and Conference Dinner</h3>The day concluded with a tour through the canals of Copenhagen and dinner at the Odd Fellow Palace. The <a href="http://www.eatcs.org/index.php/component/content/article/1-news/1908-goedel-prize-2014-">2014 Gödel Prize</a> was awarded to <a href="http://researcher.watson.ibm.com/researcher/view.php?person=us-fagin">Ronald Fagin</a>, <a href="http://il.linkedin.com/pub/amnon-lotem/1/226/3a3">Amnon Lotem</a>, and <a href="http://www.wisdom.weizmann.ac.il/%7Enaor/">Moni Naor</a>. Moni gave a great historical and technical talk on the <a href="http://researcher.watson.ibm.com/researcher/files/us-fagin/jcss03.pdf">work</a> for which they received the award, including the threshold algorithm. Ronald Fagin also spoke briefly about Michael Franklin, the "missing fourth author" of the work, and his role in facilitating the successful collaboration. <br />http://processalgebra.blogspot.com/2014/07/icalp-day-2-guest-post-by-andrew-winslow.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-1835328607225973344Wed, 09 Jul 2014 21:44:00 +00002014-07-10T07:43:08.400ZJuly 8, 2014 — ICALP Review (guest post by Clément Canonne)<i>Here is a first guest post from ICALP 2014 kindly written by <a href="http://www.cs.columbia.edu/~ccanonne/" target="_blank">Clément Canonne</a>. Enjoy it! (This post is also available in <a href="http://www.ru.is/~luca/ICALP2014/Canonne1.pdf" target="_blank">PDF</a>. Any typo or typesetting issue with the HTML version is my responsibility.)</i><br /><h3> </h3><h3>On DNF approximators for monotone Boolean functions (Eric Blais)</h3>In this talk, <a href="http://people.csail.mit.edu/eblais/">Eric Blais</a> presented joint work with <a href="http://www.nada.kth.se/%7Ejohanh/">Johan Håstad</a>, <a href="http://www.cs.columbia.edu/%7Erocco/">Rocco Servedio</a> and <a href="http://www.cs.columbia.edu/%7Eliyang/">Li-Yang Tan</a>, concerned with Boolean functions. More precisely, "the simplest representations of functions": DNF (Disjunctive Normal Form) formulas.<br />For a little bit of background, recall that a Boolean function f : {0,1}<sup>n</sup> →{0,1} defined on the hypercube [2] is a DNF if it can be written as<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-6kys58dzkY8/U72yGuoSW-I/AAAAAAAAQWI/RCIr_h_vmoI/s1600/icalp-0706-ericblais-ondnfapproximators0x.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-6kys58dzkY8/U72yGuoSW-I/AAAAAAAAQWI/RCIr_h_vmoI/s1600/icalp-0706-ericblais-ondnfapproximators0x.png" /></a></div><br /><div class="separator" style="clear: both; text-align: center;"></div><center class="math-display"></center>that is as an OR of AND’s. One can also see such functions as being eactly those taking value 1 on an "union of subcubes" (if One prefers. I will not argue with One).<br /><br />A nice property of DNF formulas is that they are arguably amongst the simplest of all representations of Boolean functions; while formulas of depth ≥ 3 are a nightmare, DNFs have been extensively studied, and by now "Everything is known about them". Well, <i>almost</i> everything.<br /><br />Indeed, amidst other facts, we have that<br /><br /><div class="theorem"><span class="head"><a href="https://www.blogger.com/null" id="x1-2r1" name="x1-2r1"></a> <b>Theorem 1</b> (Folklore).</span> Every Boolean function can be computed by a DNF of size 2<sup>n-1</sup>.<br /><br /></div><div class="theorem"><span class="head"><a href="https://www.blogger.com/null" id="x1-3r2" name="x1-3r2"></a> <b>Theorem 2</b> (Lupanov ’61).</span> This is tight (PARITY<sub>n</sub> needs that much).<br /><br /></div><div class="theorem"><span class="head"><a href="https://www.blogger.com/null" id="x1-4r3" name="x1-4r3"></a> <b>Theorem 3</b> (Korshunov '81, Kuznetsov '83).</span> A random Boolean function can be computed by DNFs of size Θ(2<sup>n</sup>∕log n) (and requires that much).<br /><br /></div>So... are we done yet? The mere presence of Eric in the auditorium was a clear hint that all was not settled. And as it turns out, if the picture is well understood for <i>exact</i> computation of Boolean functions by DNFs, what about <i>approximate</i> representation of a function? That is, what about the size required to approximate a Boolean function by a DNF, if one allows error ε (as a fraction of the inputs).<br /><br />This leads to the notion of <b>DNF approximator complexity</b>; and here again some results – much more recent results:<br /><br /><div class="theorem"><span class="head"><a href="https://www.blogger.com/null" id="x1-5r4" name="x1-5r4"></a> <b>Theorem 4</b> (Blais–Tan ’13).</span> Every Boolean function can be approximated by a DNF of size O(2<sup>n</sup>∕log n). Furthermore, our all friend PARITY<sub>n</sub> only needs DNF size O(2<sup>(1-2ε)n</sup>).<br /><br /></div>That’s <i>way</i> better than 2<sup>n-1</sup>. So, again – are we done here? And, again... not quite. This brings us to the main point of the paper, namely: what about <i>monotone</i> functions? Can they be computed more efficiently? Approximated more efficiently? (Recall that a Boolean function f is monotone if x ≼ y implies f(x) ≤ f(y), where ≼ is the coordinate-wise partial order on bit-strings.)<br />As a starter: no.<br /><br /><div class="theorem"><span class="head"><a href="https://www.blogger.com/null" id="1/2</sup>sup>x1-6r5" name="x1-6r5"></a> <b>Theorem 5</b> (Folklore</span>) Every monotone Boolean function can be computed by a DNF of size O(2<sup>n</sup>∕n<sup>1/2</sup>) (using subcubes rooted on each min-term); and again, this is tight for PARITY.</div>Furthermore, and quite intuitively, using negations does not buy you anything to compute a monotone function (and why should it, indeed?):<br /><br /><div class="theorem"><span class="head"><a href="https://www.blogger.com/null" id="x1-7r6" name="x1-7r6"></a> <b>Theorem 6</b> (Quine ’54).</span> To compute monotone Boolean functions, monotone DNFs are the best amongst DNFs.</div>Not surprising, I suppose? Well... it’s a whole new game when one (one, again!) asks only for approximations; and that’s the gist of the paper presented here. First of all, drastic savings in the size of the formulas!<br /><br /><div class="theorem"><span class="head"><a href="https://www.blogger.com/null" id="x1-8r7" name="x1-8r7"></a> <b>Theorem 7</b> (Blais–Hastad–Servedio–Tan ’14).</span> Every monotone Boolean function can be approximated by a DNF of size O(2<sup>n</sup>∕2<sup>Ω(n<sup>1/2</sup>)</sup> ).</div>Eric gave a high-level view of the proof: again, it works by considering the subcubes rooted on each min-term, but in two steps:<br /><ul><li>Regularity lemma: the world would be much simpler if all subcubes were rooted on the same level of the hypercube; so first, reduce it to this case (writing f = f<sub>1</sub> + .....+ f<sub>k</sub>, each f<sub>i</sub> has this property)</li><li>then, approximate independently each f<sub>i</sub>, using a probabilistic argument (via random sampling), to prove there exists a good approximator for all f<sub>i</sub>’s, and then stitching them together.</li></ul>And they also show it is tight: this time with the majority function MAJ<sub>n</sub>. The proof goes by a counting argument and concentration of measure on the hypercube (every or almost every input is on the middle "belt" of the hypercube; but each subcube thus has to be rooted there, and each cannot cover too much... so many are needed)<br /><br />So, approximation <i>does</i> buy us a lot. But clearly, using negations shouldn’t, should it? Why would allowing non-monotone DNF’s to approximate monotone functions <i>ever</i>help? (<b>Hint:</b> it does.) (Yep.)<br /><br /><div class="theorem"><span class="head"><a href="https://www.blogger.com/null" id="x1-9r8" name="x1-9r8"></a> <b>Theorem 8</b> (Blais–Hastad–Servedio–Tan ’14).</span> For every n, there exists ε<sub>n</sub> and f : {0,1}<sup>6n</sup> →{0,1} such that<br /><ul><li>f can be ε<sub>n</sub>-approximated by DNFs of size O(n);</li><li>any <i>monotone</i> DNF ε<sub>n</sub>-approximating f must have size Ω(n<sup>2</sup>).</li></ul></div>(Take that, intuition!)<br /><br /><b>The upshot:</b> <i>exact</i> computation and <i>approximate</i> computation have intrinsically <b>very</b> different properties!<br /><br />Eric then concluded with an open question: namely, how to improve/better understand the gap between approximating functions with monotone DNF vs. approximating them with general DNF’s (the currently known gap in the size being quite huge – almost exponential). Additionally, how to get a separation as in the mind-boggling theorem above, but changing the quantifiers – that is, for a constant ε independent of n?<br /><br />Also, can someone fix my intuition? I think it’s broken.<br /><div align="right"><br /></div><ul style="list-style-type: none; margin: 0; padding: 0;"><li>[1] <a href="http://www.cs.columbia.edu/%7Erocco/papers/icalp14.html">http://www.cs.columbia.edu/~rocco/papers/icalp14.html</a></li><li>[2] Not <a href="http://en.wikipedia.org/wiki/Cube_2:_Hypercube">this one</a>.</li></ul>http://processalgebra.blogspot.com/2014/07/july-8-2014-icalp-review-guest-post-by.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-7626788732971949847Wed, 09 Jul 2014 08:51:00 +00002014-07-09T08:51:25.906ZDay 1 of ICALP 2014 (guest post by Andrew Winslow)<br /><i><a href="http://www.eecs.tufts.edu/~awinslow/" target="_blank">Andrew Winslow </a>was one of the colleagues who kindly answered my call for guest bloggers from ICALP 2014. Here is guest post on the first conference day. Enjoy it! </i><h3>Conference Welcome</h3>Local organizing committee chair Thore Husfeldt kicked off ICALP by mentioning a few stats about IT University of Copenhagen (ITU), where the conference is located: <ul><li>Started in 1999(!) </li><li>2000 students. </li><li>10 theory CS faculty (mostly working in "track B" areas in ICALP parlance) </li><li>1 building. </li></ul>He also noted that ITU is separate from two other universities in Copenhagen hosting TCS conferences this month: Copenhagen University (hosting <a href="http://www.diku.dk/sea2014/">SEA</a> last week) and Technical University of Denmark (hosting <a href="http://algolog.compute.dtu.dk/swat2014/">SWAT</a> last week). <h3>Invited Talk: Claire Matthieu</h3>Claire presented work entitled "Homophily and the Emergence of a Glass Ceiling Effect in Social Networks", joint work with Chen Avin, Zvi Lotker, Barbara Keller, David Peleg, and Yvonne-Ann Pignolet. She started the talk by asking why there's only one female Danish scientist (<a href="http://en.wikipedia.org/wiki/Inge_Lehmann">Inge Lehmann</a>) listed on the <a href="http://en.wikipedia.org/wiki/Category:Danish_scientists">Wikipedia page</a> for famous Danish scientists out of about 60 entries -- why so rare? Looking at the <a href="http://www.informatik.uni-trier.de/%7Eley/db/">DBLP</a> database data as a social network with co-authorship edges gives similarly bleak results: the induced subgraphs of men and women in the top 1000 nodes shows a large, well-connected graph and a disconnected, sparse graph, respectively. <br /> Claire and co-authors developed a formal model of growing co-authorship social networks, including assumptions about what a "glass ceiling effect" means for these networks, and proved that three properties are minimal sufficient set of properties to imply the effect. These properties are: <br /><ul><li>Preferential attachment: a "rich get richer" effect where incoming students choose to work an advisor with probability proportional to the number of co-authors the advisor has. </li><li>Minority: an incoming student is female with probability r < 0.5. </li><li>Homophily: students stick with an advisor of the same gender with probability 1, otherwise find a new advisor with probability p < 1. </li></ul>Incoming students are iteratively added to the graph to form growing random graphs, repeatedly chosing new advisors according to homophily and preferential attachment. The glass ceiling effect is defined by looking at all nodes with degree k, where k = k(n) chosen so that the number of such nodes goes to infinity with n, and examining the ratio of women to men in this set. If the expected ratio of female over male nodes goes to 0 as the number of nodes goes to infinity, then the system is said to have a glass ceiling effect for the parameters r, p chosen. They are able to prove that the above three properties imply the class ceiling effect, and removing any one of them does not. The model was also verified experimentally using the DBLP database. <br /> As a final twist, Claire considered modifying the model to account to capture the "men are intrinsically better" hypothesis, giving new male students two advisors rather than one. This was proven <i>not</i> to cause the glass ceiling effect. I was really struck by the meta-ness of the talk and how natural the problem seems. In the formal study of (social) networks, isn't the most natural network of study the one that directly impacts our ability to formally study networks? <br /><h3><a href="http://link.springer.com/chapter/10.1007/978-3-662-43948-7_36">György Dósa and Jiří Sgall. Optimal Analysis of Best Fit Bin Packing.</a></h3>Dösa and Sgall complete the analysis of two classic (online) algorithms for the standard bin packing problem: given a collection of items specified by numbers in [0, 1], assign these items to the fewest number of bins where each bin has an item total of at most 1. The two algorithms, first-fit and best-fit, process the items one-by-one, placing each item permanently into an existing bin if possible, otherwise placing the item into a newly created bin. First-fit and best-fit differ only in the criteria by which they place item into existing bins, using the oldest bin (first-fit) or bin that would have the least remaining room after the item is placed into it (best-fit). It was previously shown that for every instance with optimal solution using OPT bins, first-fit and best-fit use ceil(1.7*OPT) bins and there exist instances where both use 1.7*OPT bins. Dösa and Sgall improved the upper bound to 1.7*OPT bins, dropping the ceiling and completing the analysis of the competitive ratio of these algorithms. Jiří commented that he felt that such classic algorithms deserved a complete analysis and I agree; the talk had an air of finality, having put the 40-year-old gap to rest. <br /><h3><a href="http://link.springer.com/chapter/10.1007/978-3-662-43948-7_39">Hossein Esfandiari, Mohammadtaghi Hajiaghayi, Reza Khani, Vahid Liaghat, Hamid Mahini and Harald Räcke. Online Stochastic Reordering Buffer Scheduling.</a></h3>Vahid Liaghat gave this talk on a scheduling problem where items have types from a fixed universe and enter into a buffer of sized size k. One can then process all items of a type, flushing them from a buffer and causing new items to take their place. The cost of processing a sequence of items is either the number of processing steps used (block operation model) or number of times the type processed changes (standard model). It was known that a O(loglog(k))-competitive algorithm is possible for the adversarial/worst-case. This work studies the sitation where the input is not adversarial, but is randomly sampled from some set. Esfandiari et al. achieve an average-case O(1)-competitive algorithm for both the block operation and standard models for the case where an adversary designs an input that is then randomly permuted. The analysis uses several lemmas regarding the optimal solutions of various buffer sizes as well as threshold algorithms: algorithms that process each type as soon as a specific number of occurrences of a type is exceeded. <br /><h3><a href="http://link.springer.com/chapter/10.1007/978-3-662-43948-7_32">Erik D. Demaine, Yamming Huang, Chung-Shou Liao and Kunihiko Sadakane. Canadians Should Travel Randomly.</a></h3>This paper attracted <a href="https://plus.google.com/+SureshVenkatasubramanian/posts/1VPq3AbuQda">a few comments</a> related to the curious title. The title comes from the "canandian traveler problem" of study, introduced by Papadimitriou and Yannakakis in 1991. The problem is a shortest path problem with partial information : some of the edges of the path are blocked (by intense canadian snowfall) and cannot be traversed, but this is only known after a traveler has visited an endpoint of the blocked edge. The parameterized version of the problem has k blocked edges, and the goal is find an algorithm with good competitive ratio compared to the shortest path that avoids all blocked edges. For deterministic algorithms, tight 2k+1 upper and lower bounds on the ratio are known, while for randomized algorithms, only a lower bound of k+1 (and implied upper bound of 2k+1) were known. <br /> Demaine, Huang, Liao, and Sadakane improve the best-known randomized algorithm in two ways, giving a polynomial-time algorithm that achieves a ratio of (2 - o(1))k + 1, and a pseudo-polynomial-time algorithm (parameterized by k, the number of blocked edges) that achieves a (1 + sqrt(2)/2)k + 1 ratio. The ideas for both algorithms are to repeatedly compute a collection of nearly shortest paths, traverse them each until blocked, and repeating the process with the new information if none of the paths lead to reaching the destination. A careful selection of the number of paths used then yields the bound. The main difference between the two algorithms is exactly what short paths are used; the pseudo-polynomial-time algorithm uses a list of shortest paths, whereas the polynomial-time algorithm only finds paths within a constant factor of the shortest. <br /><h3><a href="http://link.springer.com/chapter/10.1007/978-3-662-43948-7_43">Dmitry Gavinsky and Shachar Lovett. En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations.</a></h3>Dmitry started by reviewing two-party communication problems, where the goal is to compute a combined Boolean function f of inputs x and y held by the two parties while passing the fewest number of bits between the parties. One can consider the matrix defined by the two inputs, with an entry for every (x, y) pair, called the Boolean matrix. The rank of this matrix (and Boolean function f) is the minimum number of rectangles found in some partition of the matrix into rectangular blocks of entries with the same value. It is known that if a c-bit communication protocol is possible, then rank of the matrix is at most 2^c, i.e. the communication complexity (in bits) is bounded from below by log(rank(f)). The log-rank conjecture is that polylog(rank(f)) is an upper bound on the communication complexity of computing f. <br /> Part of this work by Gavinsky and Lovett is to provide a number of equivalent versions of the problem that may provide a way to make progress on the log-rank conjecture. For instance, they show that proving the log-rank conjecture for the randomized communication complexity on low-rank functions implies the log-rank conjecture for the deterministic version, as does proving the conjecture for the information cost of f, the minimum amount of information given by each party the other party in the worst-case. <br /><h3>EATCS General Assembly</h3>The day ended with the EATCS general assembly led by Luca Aceto and appearances by the many people involved in ICALP and EATCS. ICALP 2015 will be in Kyoto, Japan, and some information about travel, accomodations, and Kyoto were presented by Kazuo Iwama, and ICALP 2016 will be in Rome, Italy. Some statistics about ICALP 2014 were given by Elias Koutsoupias -- the number of submissions is up from previous years, acceptance rate is about steady at 30%, and the vast bulk of the submissions were to to Track A. <br /> As one final thought from the day, the organization of the conference so far has been top-notch. Many of the talks are online (including <a href="https://www.youtube.com/watch?v=XyewnrPciqw">Claire Matthieu's</a>), the sessions start and end on time, sound and projection issues are non-existent, and the food/drink is tasty (and rotates every break...). http://processalgebra.blogspot.com/2014/07/day-1-of-icalp-2014-guest-post-by.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-3696694863057547650Mon, 07 Jul 2014 19:00:00 +00002014-07-07T19:00:42.500ZIn Copenhagen for ICALP 2014It is good to be back in lovely Copenhagen and breathe the atmosphere of the Danish capital city.<br /><br />One of the first things I saw when arriving in Kongens Nytorv was a smiling guy showing a sign to cyclists and car drivers that read "Husk; du er smuk" (Remember; you are beautiful).<br /><br />The <a href="http://www.carstendahl.dk/" target="_blank">Carsten Dahl </a>Trio opened the <a href="http://www.jazz.dk/" target="_blank">Copenhagen Jazz Festival </a>events at the legendary <a href="http://www.jazzhusmontmartre.dk/" target="_blank">Jazzhus Montmartre</a> (which can host 150 people) with a lunch concert to launch <a href="https://www.youtube.com/watch?v=wG2pNJvMTNc" target="_blank">their new recording</a>. <br /><br />The ICALP welcome reception was an opportunity to meet colleagues, thank the organizing committee for all the work they have done in preparing the conference and to enjoy the band <a href="http://www.degraed.dk/">De Græd</a>, which created a jazzy and relaxed ambience.<br /><br />The conference kicks off tomorrow at 6:30am GMT with the invited talk <em>Homophily and the Glass Ceiling Effect in Social Networks </em>by <a href="http://www.di.ens.fr/ClaireMathieu.html">Claire Mathieu</a> (ENS Paris). The talk will be <a href="https://www.youtube.com/watch?feature=player_embedded&v=XyewnrPciqw" target="_blank">streamed live</a> as will all the other <a href="http://icalp2014.itu.dk/en/Events-and-Attractions/~/link.aspx?_id=A05D2ACCF114459EB1768AEA678F732A&_z=z" target="_blank">invited talks</a> and most of the other <a href="http://icalp2014.itu.dk/en/Events-and-Attractions/Video" target="_blank">plenary events</a>. <br /><br />Watch this space for some reports on ICALP 2014. http://processalgebra.blogspot.com/2014/07/in-copenhagen-for-icalp-2014.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-1259090727798045664Fri, 04 Jul 2014 10:04:00 +00002014-07-04T10:04:08.797ZMusic composed for the ICALP 2014 Gödel Prize ceremony gets coverage in Nature! The piece of music composed for the ICALP 2014 Gödel Prize ceremony gets coverage in <a href="http://www.nature.com/news/enigmatic-foundations-of-maths-put-to-music-1.15502" target="_blank">Nature</a>! See also the video presenting the composition (in Danish, but with English sub-titles).<br /><br /><div class="separator" style="clear: both; text-align: center;"><object width="320" height="266" class="BLOGGER-youtube-video" classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=6,0,40,0" data-thumbnail-src="https://ytimg.googleusercontent.com/vi/7W_SJ8rUdIQ/0.jpg"><param name="movie" value="https://youtube.googleapis.com/v/7W_SJ8rUdIQ&source=uds" /><param name="bgcolor" value="#FFFFFF" /><param name="allowFullScreen" value="true" /><embed width="320" height="266" src="https://youtube.googleapis.com/v/7W_SJ8rUdIQ&source=uds" type="application/x-shockwave-flash" allowfullscreen="true"></embed></object></div><br /><br />Thanks to Thore Husfeldt for adding this further twist to the award ceremony for the Gödel Prize! I am looking forward to the event very much. <a class="link customisable" data-expanded-url="http://www.nature.com/news/enigmatic-foundations-of-maths-put-to-music-1.15502" data-scribe="element:url" dir="ltr" href="http://t.co/AZAGu3sulJ" rel="nofollow" target="_blank" title="http://www.nature.com/news/enigmatic-foundations-of-maths-put-to-music-1.15502"><span class="tco-ellipsis"></span></a>http://processalgebra.blogspot.com/2014/07/music-composed-for-icalp-2014-godel.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-3314106519634156567Sun, 29 Jun 2014 15:56:00 +00002014-07-01T11:53:06.443ZIssue 113 of the Bulletin of the EATCS is outIssue 113 of the Bulletin of the EATCS is now available <a href="http://www.eatcs.org/beatcs/index.php/beatcs/issue/view/15" target="_blank">on line</a> abd be downloaded as a <a href="http://www.eatcs.org/images/bulletin/beatcs113.pdf" target="_blank">single PDF file</a>. As usual, the bulletin is freely accessible for everyone.<br /><br />In the current issue, you will find very interesting survey articles on, for instance, the <a href="http://www.eatcs.org/beatcs/index.php/beatcs/article/view/266/249" target="_blank">complexity of valued constraint satisfaction</a>, <a href="http://www.eatcs.org/beatcs/index.php/beatcs/article/view/285/267" target="_blank">kernelization</a> and <a href="http://www.eatcs.org/beatcs/index.php/beatcs/article/view/286/268" target="_blank">contextual semantics</a>. I strongly recommend the first installment of the Concurrency Column edited by Nobuko Yoshida on <a href="http://www.eatcs.org/beatcs/index.php/beatcs/article/view/269/251" target="_blank">recreational formal methods</a>. The piece by Frits Vaandrager and Freek Verbeek tells us how to design vacuum cleaning trajectories using Uppaal, SAT solvers and theorem provers.<br /><br />I hope that you will enjoy this issue of the BEATCS. At the <a href="http://icalp2014.itu.dk/en/Events-and-Attractions/~/link.aspx?_id=0C3438C886FF4AE3A817ADED0B5BB675&_z=z" target="_blank">EATCS general assembly</a>, which will be held at ICALP 2014 in Copenhagen, we will discuss the developments of the BEATCS. Your input to the discussion is very valuable. <br /><br /><br />http://processalgebra.blogspot.com/2014/06/issue-113-of-bulletin-of-eatcs-is-out.htmlnoreply@blogger.com (Luca Aceto)3tag:blogger.com,1999:blog-27705661.post-8120934170533719898Sun, 15 Jun 2014 12:52:00 +00002014-06-16T17:27:15.713ZSad news: Berthold Vöcking passed away<a href="http://algo.rwth-aachen.de/~voecking/" target="_blank">Berthold Vöcking</a>, who was a professor for Algorithms and Complexity at RWTH Aachen, passed away on 11th June after a long illness. He was only 47.<br /><br />Berthold was a leading figure in algorithmics research in Europe, was an invited speaker at ICALP 2012 and was one of the authors of the best paper for Track C at this year's ICALP, where we will remember him during the award session.<br /><br />Our thoughts go to his family.<br /><br />Addendum: For some information on Berthold's work, do read <a class="entryheader" href="http://mybiasedcoin.blogspot.com/2014/06/sad-news-berthold-vocking.html">Sad News: Berthold Vöcking</a> by <a class="entryheader" href="http://mybiasedcoin.blogspot.com/" title="My Biased Coin">Michael Mitzenmacher's blog</a>. http://processalgebra.blogspot.com/2014/06/sad-news-berthold-vocking-passed-away.htmlnoreply@blogger.com (Luca Aceto)5tag:blogger.com,1999:blog-27705661.post-1313925714632781272Mon, 09 Jun 2014 10:45:00 +00002014-06-09T10:45:00.950ZAnother computer scientist becomes rector of an Italian universityI just heard that <a href="http://www.dsi.unive.it/~michele/" target="_blank">Michele Bugliesi</a> has been elected as the new rector of the Universita' Ca' Foscari in Venice. (Italian speaking readers may wish to look <a href="http://www.michelebugliesi2014.it/" target="_blank">here</a> for details.) Michele is yet another (theoretical) computer scientist who becomes rector of an Italian university. This is a sign of recognition for our discipline as a whole, as well as for the Italian computer science community.<br /><br />I am sure that Michele will do a great job and I wish him the best of luck in his new, and challenging, role. http://processalgebra.blogspot.com/2014/06/another-computer-scientist-becomes.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-3720815079262448211Wed, 04 Jun 2014 10:31:00 +00002014-06-04T10:31:14.861ZCall for guest posts from ICALP 2014If you are going to ICALP 2014 and you are willing to contribute guests posts on that conference on this blog, drop me a line. It would be good to have reports on the three tracks, on the invited talks and on the award-related events, as well as on the conference as a whole.<br /><br /><br />http://processalgebra.blogspot.com/2014/06/call-for-guest-posts-from-icalp-2014.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-7416815054580557593Tue, 03 Jun 2014 20:41:00 +00002014-06-03T20:41:20.962ZHelga Guðmundsdóttir lands one of Google’s 2014 Anita Borg ScholarshipsMy colleagues and I at the <a href="http://en.ru.is/CS/" target="_blank">School of Computer Science at Reykjavik University</a> are thrilled by the recent news that <a href="https://www.linkedin.com/pub/helga-gudmundsdottir/57/413/410" target="_blank">Helga Guðmundsdóttir</a>, one of our master students and one of the very best BSc students we have ever had, has been selected as one of <a href="https://www.google.com/anitaborg/emea/winners.html" target="_blank">Google’s 2014 Anita Borg Scholarship recipients</a>. Congratulations to Helga for this achievement! <br /><br />Apart from being an outstanding student, who has already done <a href="http://arxiv.org/abs/1401.1723" target="_blank">some research in algorithms for wireless networks</a> and has had successful internships at the Fraunhofer Center for Experimental Software Engineering (University of Maryland) and Cornell University, Helga is also a role model for our female students and fantastic ambassador for computer science. She is one of the founders of <a href="http://www.sky.is/index.php/item/1692-sys-tur" target="_blank">/sys/tur</a>, the association of female computer scientists at Reykjavik University. I was amazed by how active the association is in promoting computer science at all our outreach events. <br /><br />I don't need to look at my crystal ball to forecast a bright future for Helga and that she will go from strength to strength whatever she decides to do. <br /><table summary="Overview for Helga Gudmundsdottir"><tbody><tr id="overview-summary-current"><th scope="row"><br /></th><td><br /></td></tr><tr id="overview-summary-past"><th scope="row"><br /></th><td><br /></td></tr></tbody></table>http://processalgebra.blogspot.com/2014/06/helga-gumundsdottir-lands-one-of.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-5977461907289004903Sat, 31 May 2014 22:18:00 +00002014-05-31T22:18:23.390ZPhD positions in Computer Science at IMT Lucca (Italy)<div align="justify" style="line-height: 100%;"><style type="text/css">p { margin-bottom: 0in; direction: ltr; line-height: 150%; text-align: justify; widows: 2; orphans: 2; }p.western { font-family: "Times New Roman",serif; font-size: 12pt; }p.cjk { font-family: "Times New Roman"; font-size: 12pt; }p.ctl { font-size: 12pt; }a:link { color: rgb(0, 0, 255); }</style><i><span style="font-family: Calibri, serif;"><span style="font-size: x-small;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">As readers of this blog might <a href="http://processalgebra.blogspot.com/2012/06/phd-positions-at-imt-lucca.html" target="_blank">have noticed already</a>, <a href="http://www.imtlucca.it/" target="_blank">IMT Lucca</a> is one of the institutions in Italy that is close to my heart. I am therefore happy to advertise their ongoing call for applications for their PhD positions in Computer Science. Do encourage your students to apply: the terms of employment for PhD students are excellent and so are the facilities. The town of Lucca is lovely and has a very high quality of life. IMT is still relatively small, but it is a very ambitious graduate school. </span></span></span></span></span></i></div><div align="justify" style="line-height: 100%;"><i><span style="font-family: Calibri, serif;"><span style="font-size: x-small;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US"><br /></span></span></span></span></span></i></div><div align="justify" style="line-height: 100%;"><i><span style="font-family: Calibri, serif;"><span style="font-size: x-small;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">If your students or you are interested, IMT will be holding a <a href="http://connect.physicsworld.com/research-and-consultancy/phd-webinar-in-computer-science-and-engineering/2001645.article" target="_blank">(free) interactive webinar</a> on June 11 for any students interested in the program. </span></span></span></span></span></i></div><div align="justify" style="line-height: 100%;"><br /></div><div align="justify" style="line-height: 100%;"><span style="font-family: Calibri, serif;"><span style="font-size: x-small;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">=========================================================</span></span></span></span></span></div><div align="left" style="line-height: 100%;"><span style="font-family: Calibri, serif;"><span style="font-size: x-small;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">PhD positions in Computer Science at IMT Lucca (Italy)</span></span></span></span></span></div><div align="left" style="line-height: 100%;"><span style="font-family: Calibri, serif;"><span style="font-size: x-small;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">- Deadline July 14, 2014 -</span></span></span></span></span></div><div align="left" style="line-height: 100%;"><span style="font-family: Calibri, serif;"><span style="font-size: x-small;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">=========================================================</span></span></span></span></span></div><div align="left" lang="en-US" style="line-height: 100%;"><br /></div><div align="left" style="line-height: 100%;"><span style="font-family: Calibri, serif;"><span style="font-size: x-small;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">The Institute for Advanced Studies IMT Lucca - Italy</span></span></span></span></span></div><div align="left" style="line-height: 100%;"><span style="font-family: Calibri, serif;"><span style="font-size: x-small;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">( announces multiple PhD scholarships (appx. </span></span></span><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">€13,600/year),</span></span></span><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">that also include accommodation and full board.</span></span></span></span></span></div><div align="justify" lang="en-US" style="line-height: 100%;"><br /></div><div align="justify" style="line-height: 100%;"><span style="font-family: Calibri, serif;"><span style="font-size: x-small;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">Deadline for application is July 14th, 2014 at 18:00 Italian time.</span></span></span></span></span></div><div align="justify" lang="en-US" style="line-height: 100%;"><br /></div><div align="justify" style="line-height: 100%;"><span style="font-family: Calibri, serif;"><span style="font-size: x-small;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">IMT Lucca (Italy) is a research university within the Italian public higher education system. IMT's mission is to establish itself as a research center that promotes cutting-edge research in key areas, structuring its PhD program in close connection with research, to attract top students, researchers and scholars through competitive international selections, and to contribute to technological innovation, economic growth and social development.</span></span></span></span></span></div><div align="justify" lang="en-US" style="line-height: 100%;"><br /></div><div align="justify" style="line-height: 100%;"><span style="font-family: Calibri, serif;"><span style="font-size: x-small;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">The three year doctoral program, which is taught entirely in English, is articulated in curricula. The 8 curricula currently offered are field-specific, although in many instances they share a common scientific background. </span></span></span><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">The curriculum in Computer Science is coordinated by Rocco De Nicola and focuses on key aspects of current research in the theory and applications of informatics, such as open-endedness, autonomy, security, concurrency, cost-effectiveness, quality of services, and dependability.</span></span></span></span></span></div><div align="justify" lang="en-US" style="line-height: 100%;"><br /></div><div align="justify" style="line-height: 100%;"><span style="font-family: Calibri, serif;"><span style="font-size: x-small;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">The main goal of the curriculum is to develop models, algorithms, and verification methods for modern distributed systems. The doctoral students enrolled in this curriculum will carry out cutting-edge research on the fundamentals and applications of architectures and languages for modern distributed systems, including global and cloud computing systems, web systems and services, and mobile systems. They will also acquire professional skills in the application of computer technologies to massively distributed systems, working in close collaboration with the SysMA research unit of IMT (<a href="http://sysma.lab.imtlucca.it/">http://sysma.lab.imtlucca.it/</a>). Graduates from the curriculum are qualified to work in universities, public and industrial research centers, and to take on professional roles and high-profile tasks and responsibilities in both private companies and public institutions.</span></span></span></span></span></div><div align="justify" lang="en-US" style="line-height: 100%;"><br /></div><div align="justify" class="western" style="line-height: 100%;"><span style="font-family: MgOpen Cosmetica, serif;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">PhD students, besides receiving a research scholarship, are offered on-campus housing on a newly restored and fully integrated San Francesco Complex in the historical center of the beautiful Tuscan city of Lucca, and daily access to the canteen. Students also get the opportunity to spend research periods abroad during the program, </span></span></span><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">with the possibility of receiving additional financing through the Erasmus+ program.</span></span></span></span></div><div align="justify" lang="en-US" style="line-height: 100%;"><br /></div><div align="justify" style="line-height: 100%;"><span style="font-family: Calibri, serif;"><span style="font-size: x-small;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">Please note that students who are expected to obtain the required degree by October 31, 2014 will also be considered; they must still apply by July 14. Further details, along with online the application form, can be found at:</span></span></span></span></span></div><div align="justify" lang="en-US" style="line-height: 100%;"><br /></div><div align="justify" style="line-height: 100%;"><span style="font-family: Calibri, serif;"><span style="font-size: x-small;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US"><a href="http://phd.imtlucca.it/">http://phd.imtlucca.it</a></span></span></span></span></span></div><div lang="en-US" style="line-height: 100%;"><br /></div><div align="justify" class="western" style="line-height: 100%;"><span style="font-family: MgOpen Cosmetica, serif;"><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">Be sure to sign up for our free interactive webinar (<a href="http://brightrecruits.com/webinars/">http://brightrecruits.com/webinars/</a>) scheduled for June 11</span></span></span><sup><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">th</span></span></span></sup><span style="font-family: Tahoma, serif;"><span style="font-size: x-small;"><span lang="en-US">2014.</span></span></span></span></div><div lang="en-US" style="line-height: 100%;"><br /></div><div align="left" class="western" style="line-height: 100%;"><br /></div>http://processalgebra.blogspot.com/2014/05/phd-positions-in-computer-science-at.htmlnoreply@blogger.com (Luca Aceto)0tag:blogger.com,1999:blog-27705661.post-2166616290369649944Thu, 08 May 2014 11:06:00 +00002014-05-09T10:02:23.691ZBest paper awards at ICALP 2014The EATCS is proud to announce that the program committees of the three tracks of <a href="http://icalp2014.itu.dk/" target="_blank">ICALP 2014</a> have selected the following papers for the best paper awards: <br /><br /><div><div><br /></div><div><b>Track A:</b></div><div>Andreas Björklund and Thore Husfeldt,<span style="white-space: pre-wrap;"> </span><a href="http://thorehusfeldt.files.wordpress.com/2010/08/spdp-e5d5661.pdf" target="_blank"><i>Shortest Two Disjoint Paths in Polynomial Time</i></a></div><div><b>Track B:</b></div><div>Joel Ouaknine and James Worrell. <a href="http://arxiv.org/abs/1309.1914" target="_blank"><i>Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences</i></a></div><div><b>Track C:</b></div><div>Oliver Göbel, Martin Hoefer, Thomas Kesselheim, Thomas Schleiden and Berthold Voecking, <a href="http://arxiv.org/abs/1307.3192" target="_blank"><i>Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods</i></a></div><div><br /></div>The best student paper awards are given to papers that are solely authored by students. This year these awards will go to: </div><div><div><br /></div><div><b>Track A:</b></div><div>Sune K. Jakobsen,<span style="white-space: pre-wrap;"> </span><a href="http://arxiv.org/abs/1402.3125" target="_blank"><i>Information Theoretical Cryptogenography</i></a></div><div><b>Track B:</b></div><div>Michael Wehar, <a href="http://www.acsu.buffalo.edu/~mwehar/documents/mwehar_INE_2_15_14.pdf" target="_blank"><i>Hardness Results for Intersection Non-Emptiness</i></a><b><br /></b></div><div><b>Track C:</b></div><div>Mohsen Ghaffari, <a href="http://arxiv.org/abs/1404.7559" target="_blank"><i>Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set </i></a><i></i><br /><i><br /></i></div></div>Congratulations to the award recipients and many thanks to the <a href="http://icalp2014.itu.dk/en/Conference/Program-Committees" target="_blank">PC chairs and their PCs</a> for their sterling work!<br /><br />It is interesting to see that the best papers for 2014 are all from Europe, whereas two of the three best student papers are from the US. Having worked in Northern Europe for the best part of 20 years, I am happy to see that the best papers for Track A have Scandinavian authors. <br /><br />I hope that you will enjoy reading the award-receiving papers. <br /><br />http://processalgebra.blogspot.com/2014/05/best-paper-awards-at-icalp-2014.htmlnoreply@blogger.com (Luca Aceto)1