tag:blogger.com,1999:blog-329020562024-03-19T00:10:09.435-07:00Paul Goldbergtheoretical computer science, economics, and academic life in general. Writing in personal capacity, not representing my employer or other colleaguesPaul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.comBlogger298125tag:blogger.com,1999:blog-32902056.post-33462456434171845902020-04-26T07:43:00.000-07:002020-04-26T07:43:37.499-07:00Surge pricing, anyone?<div dir="ltr" style="text-align: left;" trbidi="on">
One social contribution that I tentatively attribute to Uber is popularisation of the concept of surge pricing. That is, we try to call an Uber and all-too-frequently get told that we have to pay a premium at this particular point in time, due to high demand. On the other hand, recent shortages of toilet paper, paracetamol, and certain foods were not accompanied by any kind of surge pricing, and the limits imposed on how much stuff you can buy, were not so effective in keeping these goods available. At this point, things have improved, although I have not been able to buy flour recently: the shortage of flour in the supermarkets I visit seems to be chronic.<br />
<br />
Now I appreciate the objection to charging to charging a premium to allcomers, rich and poor alike, in the context of vital food and medicine. (Although, limits on purchases can also be criticised as being unfair to a single purchaser buying for a large family, or a key worker who is short of time and doesn't want to search excessively for a desired item.) In trying to advocate surge pricing, let me turn instead to possible examples less controversial, such as hairdressers and garden centres. When these establishments are allowed to reopen, it seems reasonable that they should charge a premium (temporarily). Not only do they need the money, but it would help to control a flood of customers all causing long queues and infecting each other at close quarters. To be honest, I’m not optimistic that this will happen, since they will still worry about accusations of price-gouging, plus there’s the question of how big a premium is appropriate.<br />
<br />
<a href="https://www.economist.com/britain/2020/04/25/the-impossibility-of-measuring-inflation-in-a-pandemic">An article in the Economist</a> highlights a related problem, which is the difficulty of measuring the rate of inflation, at a time when various goods and services (whose prices get used to measure inflation) are unavailable. Coming back to flour, it may be felt that some of it (not all!) should be sold at market price, meaning one that some people will pay, but where it stays on the shelves for a few days, at least. There is a moral case against selling goods too cheaply, which is that it becomes an attempt to hide a problem — a successful attempt, if inflation cannot be measured.<br />
<br />
Finally, the problem discussed here touches on a defect at the heart of traditional economic theory, which is the <a href="https://en.wikipedia.org/wiki/Arrow%E2%80%93Debreu_model">celebrated existence</a> of “correct” prices, unaccompanied by a means of arriving at those prices. The Algorithmic Game Theory community has quite rightly worried about price discovery and its computational obstacles. But the obstacles are also social, and status quo bias plays a big part.</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-37568022562038505352020-04-21T08:54:00.002-07:002020-04-21T08:54:54.072-07:00Short-term prospects for UK universities<div dir="ltr" style="text-align: left;" trbidi="on">
A round-up of gloomy reading material I have been taking in.<br />
<br />
<a href="https://www.theguardian.com/education/2020/apr/10/uk-universities-fear-huge-budget-holes-as-chinese-students-stay-home">UK universities fear huge budget holes as Chinese students stay home</a> has worrying figures about the dependence of UK universities on students from China in particular. Note the discussion about Aberdeen University towards the end of the article. <i>had hoped to earn £50m from overseas students this year, 20% of its overall income, but that “is now likely to fall substantially, because of the restrictions and uncertainty created by coronavirus”</i><br />
<br />
<a href="https://wonkhe.com/blogs/how-can-universities-climb-out-of-the-coming-financial-abyss/">How can universities climb out of the coming financial abyss?</a> considers prospects of universities closing or merging, or obtaining bridging loans from banks or government, possibly with strings attached (such as closure of certain courses seen as not very valuable). It is suggested that some prospective UK students may decide to defer going to university, although for the ones that do, <i>“those students may have an edge in the graduate jobs in three or four years’ time, though it’s not clear how many students, if any, will be making that wholly rational calculation.”</i><br />
<br />
<a href="https://www.timeshighereducation.com/news/universities-uk-state-bailout-required-save-institutions">Universities UK: state bailout required to save institutions</a>. Some comments added by readers made the point that senior administrative salaries ought to be cut, in the context of requesting a government bailout.<br />
<br />
<a href="https://www.ft.com/content/0ae1c300-7fee-11ea-82f6-150830b3b99a">Coronavirus: universities face a harsh lesson</a> discusses universities in the UK, USA, and Australia, with emphasis on the likely loss of income from overseas students, especially from China. The ‘overexposure to the Chinese market’ story seems to be widespread.<br />
<br />
<a href="https://www.kcl.ac.uk/news/what-will-higher-education-look-like-after-coronavirus">What will higher education look like after coronavirus?</a><br />
<i>The Office for Students will need to design and put in place a multi-billion pound stabilisation fund to prevent the collapse of scores of vulnerable English universities. Access to this fund should be subject to strict non-negotiable conditions, including the phased closure of poor-quality and low-value courses under teach-out arrangements to ensure that students can complete their studies.</i> (This seems easy to say; harder to say what’s meant by a poor-quality and low-value course. I don’t think some smirking reference to Gender Studies does the job.) More optimistic about the long-term; argues that demand for higher education will increase in developing countries. The article has an unfortunate digression into an argument that universities that attract plenty of students, should continue to expand at the expense of ones that don’t.<br />
<br /></div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-89056534430342524502020-01-06T04:21:00.000-08:002020-01-06T04:21:29.662-08:00On leaving the EU<div dir="ltr" style="text-align: left;" trbidi="on">
For someone based in the UK who works in any kind of international market, it looks reasonable to consider how his business strategy should be affected by leaving the EU. In the case of CS theory research, this perhaps runs counter to an idealised view in which all research is global, and should not be affected by squalid political considerations. The interest inherent in any specific problem or result ought to be independent of where it was studied. On a related note, it may be felt that it’s the research topic that chooses the researcher, not the researcher who chooses the topic. On the other hand, even in CS theory, ones political environment and associated social networks may have a stronger effect than we would like to acknowledge.<br />
<br />
When I was a graduate student, Algorithms and Computational Complexity was relatively under-represented in the UK, compared with today. The UK theory community was dominated by so-called “Euro-theory”, which at the time did not seem to exhibit obvious points of contact with algorithms research. People like me had to look west for assurance that our research was of wider interest than what was apparent in our own backyard. To further justify that west-looking approach, it was clear that the USA was, in terms of research, the undisputed world leader. Then as now, it collected the lion’s share of Nobel prizes. It had industrial research labs producing leading CS theory research, such as IBM, AT&T, and NEC, while Europe had nothing similar. For me, this sowed the seeds of a defiantly Atlanticist attitude to CS theory research — appropriate for Brexit Britain, perhaps? — that the best way to pursue high-quality research was via links with colleagues in the USA.<br />
<br />
Fast-forward to about five years ago, and my attitude had softened. The UK’s algorithms-and-complexity community steadily grew, and is much larger than it was in the early 90’s. Travel within Europe is relatively quick and cheap, with no visa issues. The European research community became a bit of a comfort-zone, while the USA’s research ethic seemed comparatively intense and high-pressure. The perennial question of “Where’s my next STOC/FOCS paper going to come from?” has always seemed less urgent in Europe.<br />
<br />
The EU has attempted to unify Europe’s academic research activity, which is supported by diverse governments, and gives rise to diverse complaints among European colleagues. I am reminded of the “<a href="https://en.wikipedia.org/wiki/Anna_Karenina_principle">unhappy families</a>” quote from <i>Anna Karenina</i>. In an attempt to give it a bit of unity, there’s some EU funding for research, concerning which we have this criticism from <a href="https://www.nobelprize.org/uploads/2018/06/geim_lecture.pdf">Andre Geim’s Nobel prize speech</a>: “I can offer no nice words for the EU Framework programmes which, except for the European Research Council, can be praised only by Europhobes for discrediting the whole idea of an effectively working Europe.” For my part, I recently tried to get a grant from the European Research Council but they turned me down. If I were a rational agent, I should at this point be one of Geim’s Europhobes; of course in reality things are not quite so simple. But at this point I reckon the US research funding system looks like the least worst. <a href="http://occamstypewriter.org/athenedonald/2019/12/16/post-election-christmas-reading-list/">A recent article</a> at Athene Donald’s blog discusses the post-EU era and the idea of a DARPA-like research agency for the UK.<br />
<br />
So, leaving the EU looks like an opportune point to dust off the above-mentioned “Atlanticist attitude”. These days China is also becoming more important. But I hope that Europe will not give up on us, but will compete strenuously with them for our attention.</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com4tag:blogger.com,1999:blog-32902056.post-2773172877505327982019-12-12T01:20:00.000-08:002019-12-12T01:20:10.318-08:00A competitive foraging/gathering game<div dir="ltr" style="text-align: left;" trbidi="on">
Here’s an interesting-looking game that occurred to me recently; let me know if you have seen an analysis of it or something similar. Suppose that two or more competing agents can move around in an environment in which there are a number of valuable items, and agents want to gather more items than their opponents. (One thinks of the arena in the vicinity of the Cornucopia in <i>The Hunger Games</i>, although a better story may be a collection of robots who can each obtain credit for performing tasks that have arisen in various locations.) How hard is it to figure out what each agent should do, and how many items she can collect? The analysis looks challenging. What follows is a few observations. A and B denote players.<br />
<br />
It looks like a player faces an NP-hard problem, since one can present player A with a Travelling Salesman Problem of collecting n items in his vicinity before player B (initially located some distance away) has time to reach the area and collect some of these items.<br />
<br />
One question that is not about computational difficulty is: can such a game ever have a standoff in which players stop moving, and one or more items remains uncollected? The answer seems to be yes, subject to certain modelling assumptions.<br />
<br />
Suppose that the items are located at the vertices of a graph, and players may traverse the edges. If the graph is allowed to be directed, a standoff is easy to construct, see diagram below. All edges take 1 time unit to traverse. Suppose both players A and B start at the central vertex, and there are items of equal value 1 on each of the other vertices. If player A moves towards the top vertex, player B will move towards the bottom left vertex just downstream (according to the edge direction), and will be able to collect 2 out of the 3 items, exploiting the directedness of the edges. Hence it looks like both players will be reluctant to leave the central vertex. (Especially if we assume that the aim is to get more items than the opponent, as opposed to maximising the number of items collected.)<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgf7dZ1cMMvnIwOfVqwtXlNH4-Up3yTjOZY_WgBNpfGrY_T58qRCgX0R57VhiAR0AGoArSajy4hqpeiAu54hz3FoTimgNr7goByRdKhB8dABl2wo-K3QRC1WTUCzeslWBvlE4pE/s1600/fg1.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="389" data-original-width="511" height="243" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgf7dZ1cMMvnIwOfVqwtXlNH4-Up3yTjOZY_WgBNpfGrY_T58qRCgX0R57VhiAR0AGoArSajy4hqpeiAu54hz3FoTimgNr7goByRdKhB8dABl2wo-K3QRC1WTUCzeslWBvlE4pE/s320/fg1.jpeg" width="320" /></a></div>
Can we do something similar for undirected graphs? The following example is inspired by a secure protocol for bilateral trade of physical goods, which I used once or twice as a young child. The parties to the transaction place the items on the ground a few metres apart, and walk towards each other, passing at the halfway point. Assuming they want the exchange to go ahead, they continue towards their preferred item, noting that neither trader can grab both items, subject to the reasonable assumption that neither can run 3 times as fast as the other.<br />
<br />
The figure below shows an undirected graph where player A is very close to an item worth 1.5 (we can assume he grabs it immediately) while player B is distance 1 from the remaining two items of value 1. Player A is distance 1.5 from each of these 2 remaining items. <br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipXlJCzHnQsG1HQWfKDVK9q0AJ9_je2kc30dV9BgtZu7TGmfeyR9FNCQX2zTV-xk04ws4X5182X_hJhxF_44kMBPKx6UVp3Dk-l5KvKuuB3Y7JnqJaEoJNl3VioDMwMFzyxESy/s1600/fg2.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="427" data-original-width="433" height="314" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipXlJCzHnQsG1HQWfKDVK9q0AJ9_je2kc30dV9BgtZu7TGmfeyR9FNCQX2zTV-xk04ws4X5182X_hJhxF_44kMBPKx6UVp3Dk-l5KvKuuB3Y7JnqJaEoJNl3VioDMwMFzyxESy/s320/fg2.jpeg" width="320" /></a></div>
Assuming that the aim of the game is to get the lion’s share of the items, A needs one more item, and B needs both remaining items. If A moves towards the top item, then B can move towards that same item, get there first and then go back for the bottom item. If players can move freely (and reverse directions) on edges, B can stop A from getting both, by staying slightly closer to whichever item A is closest to. However, if B goes ahead and collects (say) the top item, then A can go for the bottom one, as soon as B is close to the top one. Result: an impasse, especially if you assume that such an impasse means the game is tied and the overall prize is split.<br />
<br />
Notice that you do not get this deadlock if players can move freely in the plane: in that version, A can move directly towards B, and if B approaches (say) the top item then A should approach the bottom one. So A wins with no impasse. It would be interesting to know whether an impasse can result in this setting of free movement in the plane.</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-27577594571418347902019-06-04T03:46:00.000-07:002019-06-04T06:05:01.905-07:00plans for WINE conferences<div dir="ltr" style="text-align: left;" trbidi="on">
Update on the annual Conference on Web and Internet Economics (I am on the steering committee).<br />
<br />
<a href="http://wine2019.cs.columbia.edu/">WINE 2019</a> (the 15th) will be at Columbia University, December 10-12. We could not avoid the clash with NeurIPS, due to Columbia’s exam schedule. Submission deadline is July 15th.<br />
<br />
The plan is for WINE 2020 to take place at Peking University, following the tradition to rotate between Europe, USA, and Asia.<br />
<br />
WINE 2021 is under discussion; one idea it to hold it in Addis Ababa, Ethiopia, which is not as novel as it may seem at first sight, it would be following ICLR 2020 (see <a href="https://venturebeat.com/2018/11/19/major-ai-conference-is-moving-to-africa-in-2020-due-to-visa-issues/">this link</a> (noting the visa issues) and others). The rationale is that Africa has a burgeoning AI community including people who are interested in algorithmic game theory, and for them, Ethiopia is an easy destination (administratively, in particular). WINE 2018 (at Oxford, UK) had (I think) 5 African participants, and about 10 more would have liked to come but were denied visas. These participants brought home to me the point that there is this developing AI community in Africa. At WINE 2018, Eric Sodomka (from Facebook) gave a well-received presentation on the idea of holding a future WINE in Africa. Are there other places in Africa we should be thinking of? I welcome feedback and comments!<br />
<br /></div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-83195172457189504722019-05-30T07:41:00.000-07:002019-05-30T07:41:46.793-07:00Augar review<div dir="ltr" style="text-align: left;" trbidi="on">
This note considers the Augar review from the perspective of a prospective student, as opposed to a typical university (<a href="https://wonkhe.com/blogs/government-to-take-back-control-as-universities-get-their-most-thoughtful-kicking-to-date/">Wonkhe</a> does not fill me with enthusiasm on that aspect).<br />
<br />
<a href="https://www.moneysavingexpert.com/news/2019/05/editorial-comment--the-augar-report-heralds-the-end-of-student--/">Moneysavingexpert</a> gives a fairly helpful list of the main points; see the bold-face subtitles. It goes wrong in one place with “Student loans should be renamed a ‘student contribution system’ … Student loans are a misnomer. So it’s with relief that the Augar report notes our call to change the name…” However, when an expense incurs interest and an obligation on an individual to repay it, there’s no getting away from the fact that it’s a loan (and incurs a debt), and in a minor victory for plain English, the article goes on to use the word loan, and not ‘student contribution system’.<br />
<br />
An earlier BBC article <a href="https://www.bbc.co.uk/news/education-46866346">Rich students save by paying fees up front</a> notes that under the current regime, 10% of students pay tuition fees upfront (or at least, their parents do). I agree with the criticism of the current regime, as quoted as in the article. When I first read that Augar proposes the fees to be reduced, but you’re on the hook for debt repayment for an additional 10 years (as noted in the moneysavingexpert article: “The loan will wipe after 40, not 30, years – substantially increasing the total repayment for many”) it looked to me like that added up to an even stronger incentive to pay upfront. But wait... there’s also a proposed cap of loan plus 20% (adjusted for inflation) that you have to repay, that makes the set-up more benign. It means that with a partial repayment, you’re chipping away at something that cannot grow without limit. That mitigates a deeply disagreeable feature of the present system, namely the uncertainty and lack of control on how much someone will repay.<br />
<br />
My guess: affluent parents will continue to pay the fees upfront, even if the cost to the family for not doing so is at most an additional 20%. It’s basically an attractive mechanism for bequeathing money. There’s also the issue of how such a bequest changes the behaviour the student after they graduate (an aspect of up-front payment that has not received much attention) — arguably if a graduate doesn’t face a tax bill when his income exceeds some amount, he’s more likely to pursue a well-paid job.<br />
<br /></div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-75734205232199902822019-04-12T01:27:00.000-07:002019-04-12T01:27:32.478-07:00New conference: ACM-SIAM Algorithmic Principles of Computer Systems (APoCS20)<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
ACM-SIAM Algorithmic Principles of Computer Systems (APoCS20)</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
<a class="" href="https://www.siam.org/Conferences/CM/Main/apocs20">https://www.siam.org/Conferences/CM/Main/apocs20</a></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px; min-height: 14px;">
<br class="" /></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
January 8, 2020</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Hilton Salt Lake City Center, Salt Lake City, Utah, USA</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Colocated with SODA, SOSA, and Alenex</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px; min-height: 14px;">
<br class="" /></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
The First ACM-SIAM APoCS is sponsored by SIAM SIAG/ACDA and ACM SIGACT.</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px; min-height: 14px;">
<br class="" /></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
<b class="">Important Dates:</b></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px; min-height: 14px;">
<br class="" /></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
<span class="Apple-tab-span" style="white-space: pre;"></span>August 9: Abstract Submission and Paper Registration Deadline</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
<span class="Apple-tab-span" style="white-space: pre;"></span>August 16: Full Paper Deadline</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
<span class="Apple-tab-span" style="white-space: pre;"></span>October 4: Decision Announcement</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px; min-height: 14px;">
<br class="" /></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
<b class="">Program Chair:</b></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px; min-height: 14px;">
<br class="" /></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Bruce Maggs, Duke University and Akamai Technologies</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px; min-height: 14px;">
<br class="" /></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
<b class="">Submissions:</b></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px; min-height: 14px;">
<br class="" /></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Contributed papers are sought in all areas of algorithms and architectures that offer insight into the performance and design of computer systems. Topics of interest include, but are not limited to algorithms and data structures for:</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px; min-height: 14px;">
<br class="" /></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Databases</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Compilers</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Emerging Architectures</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Energy Efficient Computing</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
High-performance Computing</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Management of Massive Data</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Networks, including Mobile, Ad-Hoc and Sensor Networks</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Operating Systems</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Parallel and Distributed Systems</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Storage Systems</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px; min-height: 14px;">
<br class="" /></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px; min-height: 14px;">
<br class="" /></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
A submission must report original research that has not previously or is not concurrently being published. Manuscripts must not exceed twelve (12) single-spaced double-column pages, in addition the bibliography and any pages containing only figures. Submission must be self-contained, and any extra details may be submitted in a clearly marked appendix. </div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px; min-height: 14px;">
<br class="" /></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
<b class="">Steering Committee:</b></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px; min-height: 14px;">
<br class="" /></div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Michael Bender</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Guy Blelloch</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Jennifer Chayes</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Martin Farach-Colton (Chair)</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Charles Leiserson</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Don Porter</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Jennifer Rexford</div>
<div class="" style="font-family: "Helvetica Neue"; font-stretch: normal; line-height: normal; margin: 0px;">
Margo Seltzer</div>
</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-79574441682390398512019-03-27T04:11:00.000-07:002019-03-27T04:11:31.006-07:00Meaningful votes<div dir="ltr" style="text-align: left;" trbidi="on">
In the unlikely event that we get a second referendum on Brexit, here’s how it ought to be done: Arrange all the alternatives in a line in order of “hardness” of Brexit. In may be felt that Remain should not be an option, in which case we have <a href="https://en.wikipedia.org/wiki/Norway_plus">Norway plus</a> (a.k.a. Common Market 2.0) at one end, and no-deal at the other. Every voter chooses their favourite option from the list. The winning option is chosen to be the one for which at least half the voters prefer a harder Brexit, and at least half favour a softer Brexit. The claim that this system is truthful, is based on the presumed single-peaked-ness of preferences: every voter has a favourite option, and their support for the others goes down, the further away you get from the favoured option.<br />
<br />
Of course, the only thing less likely than a second referendum is the adoption of an eminently sensible approach such as the one above, and the interesting question is, why it would not be used. One objection I can think of, goes as follows: suppose there are 3 alternatives offered, say Norway plus, Theresa May’s deal, and no-deal. Suppose that 20 million voters support Norway plus, another 20 million support no-deal, and one voter supports May’s deal. In that case, May’s deal wins, and someone would complain it’s (a lot) less popular than one of the others (probably the one the complainant supported). In reality, this result should have everyone — on both sides — celebrating the fact that whatever outcome they liked least has just been narrowly averted. A better objection is that some people would prefer a principled in-or-out result, and either extreme is preferable to some sort of fudge. (I admit, I recently heard that view sincerely expressed.) So, for them the vote is not truthful, but there are not many people like that, and they are free to vote (strategically) for whatever extreme they prefer. A third objection, implicit in most objections to electoral reform, states that voters are too stupid to understand anything other than plurality, or “first past the post”.<br />
<br />
If the above system were used in Parliament, May’s deal would probably win, unless MPs were allowed to vote anonymously, in which case Norway Plus would probably win. <br />
<br />
I checked the paper <a href="https://rangevoting.org/rothkopf_article.pdf">Thirteen Reasons Why the Vickrey-Clarke-Groves Process Is Not Practical</a> since the point about voting is analogous to the observation that no-one uses VCG. The 13 reasons are mostly not applicable, or only weakly applicable, to the above election. It is true that there are other weak equilibria besides truth-telling, but it seems unlikely that someone would vote against his preference simply because he’s unlikely to swing the outcome.<br />
<br />
The effort we put into studying voting systems is justified by the following Milton Friedman quote:<br />
<blockquote>
Only a crisis - actual or perceived - produces real change. When that crisis occurs, the actions that are taken depend on the ideas that are lying around. That, I believe, is our basic function: to develop alternatives to existing policies, to keep them alive and available until the politically impossible becomes the politically inevitable.</blockquote>
</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-42217006411776100722019-03-18T10:19:00.000-07:002019-03-18T10:19:00.698-07:00The will of the people<div dir="ltr" style="text-align: left;" trbidi="on">
At one point in Iain Banks’ novel <i><a href="https://en.wikipedia.org/wiki/The_Wasp_Factory">The Wasp Factory</a></i>, the main character (a troubled teenager called Frank) makes the following observation: <br />
<blockquote>
Often I’ve thought of myself as a state; a country or, at the very least, a city.</blockquote>
He then compares his moods and thought processes to political moods that countries go through: <br />
<blockquote>
…For example, there has always been a part of me which has felt guilty about killing Blyth, Paul and Esmerelda. … But I liken it to an opposition party in a parliament, or a critical press; acting as a conscience and a brake, but not in power and unlikely to assume it.</blockquote>
Frank is modelling a single self-contained agent (himself) as the embodiment of many separate agents. It is common in literature for someone to have a struggle between, say, the admirable and the less admirable parts of his nature, but the above is the best example I can recall of this kind of modelling.<br />
<br />
Usually we do the opposite, trying to represent many agents as a single one. In the context of Brexit, that approach has been stretched to breaking-point. The phrase “the will of the people” attempts to conflate the electorate (a multitude of agents) into a self-contained purposive entity. Is Brexit the will of the people? Yes, in the same sense that getting a hung parliament is the will of the people. The people seem to want to make life difficult for themselves. UK politicians and commentators have discussed negotiating Brexit with the European Union as if the EU is a self-contained purposive agent. This has led to the unfortunate idea that the EU may want to punish the UK for leaving, in order to discourage other states from leaving. It views the EU as a single entity motivated by the desire to survive and grow, and assumes that it will take actions that run counter to the goodwill of EU leaders. Likewise, we have recently heard a great deal about how Parliament has said what it doesn’t want, but not what it wants. If Parliament is modelled as a single agent, then it ought to want something, but as soon as we acknowledge that it’s not a single agent, there is no particular reason to suppose that there is something that it wants. Given, say, three alternatives, there could perfectly well be a <a href="https://en.wikipedia.org/wiki/Condorcet_paradox">Condorcet cycle</a>.<br />
<br />
Returning to Frank, it may be useful to model an individual as a multitude of internal agents. In economics, it could be a new an interesting way to model individual irrationality, which is a perennial challenge that has been taken up in a rather patchy way, and deserves more attention. Finally it may even constitute a way to model emotions: in Frank’s case it is guilt that is represented this way.</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-63904548101112136832018-11-06T15:36:00.000-08:002018-11-06T15:36:26.303-08:00What do you know that deserves more publicity?<div dir="ltr" style="text-align: left;" trbidi="on">
I was talking with a journalist yesterday - not an interview, just an informal conversation - and he asked me the question: What stories in Computer Science are not getting enough attention? And my immediate reaction was: great question! although I suppose for journalists, asking great questions is what they’re supposed to do. And, unaccustomed to being pestered by members of the fourth estate, I did not have a slick and ready answer, but feel like I should have done. It’s reasonable enough to expect a university professor may have insider information on some topic that s/he reckons should be more publicised. Maybe CS theory is not such a rich source of such professors as most other fields.<br />
<br />
In coming up with an answer, I would impose the following rules. One’s own research should be off-limits, due to personal bias. Also, you should not argue that some area of CS (presumably AI/big data) is getting too <i>much</i> attention, and other unspecified stories are getting overlooked in consequence. The challenge is to make a <i>positive</i> claim in favour of some specific research sub-field. I thought briefly of exposing the manifold failings of the research funding system, but decided that the story should be CS-specific, not one that many researchers could have come up with.<br />
<br />
With hindsight, I would point to the topic of fairness in AI, which has received some mass-media coverage (<a href="https://www.theguardian.com/commentisfree/2018/oct/14/the-guardian-view-on-artificial-intelligence-human-learning">example</a>) but most people outside of CS/AI still don’t know that it is increasingly viewed as important. It has attracted a fair (?) amount of interest from the TCS community, i.e. among computer scientists who have good taste. Crucially, it is easy to motivate to someone who is a complete outsider. (I have been taking an interest but it’s not currently my own research field, just a related one.) To conclude, I mentioned above that CS theory is maybe not such a rich source of topics that deserve more publicity, but let me know if there are any I should have thought of.</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com8tag:blogger.com,1999:blog-32902056.post-40031221456126138762018-04-17T03:44:00.000-07:002018-04-17T03:44:06.653-07:00STOC child care<div dir="ltr" style="text-align: left;" trbidi="on">
I received a request to call attention to the following, but will refrain from sharing it with the Theory of Computing blog aggregator since others have already done so (for example <a href="https://windowsontheory.org/2018/04/16/childcare-at-stoc-2018-theoryfest/">here</a>).<br />
<br />
In a challenge to my long-standing view of academic life as a hybrid of Herman Hesse’s <i><a href="https://en.wikipedia.org/wiki/The_Glass_Bead_Game">The Glass Bead Game</a></i> and Paul Erdős’ itinerant-scholar lifestyle, STOC 2018 will be the first STOC to provide subsidised, pooled childcare. (OK, this is not completely new. Dagstuhl has had this facility for some years, and the earliest example I can recall is the year 2000 <a href="http://www.bctcs.ac.uk/index.php/past-meetings/">British Colloquium on Theoretical Computer Science</a>, although I don’t recall it being subsidised.)<br />
<br />
On a related note, I was separately circulated an email advertising a <a href="https://tcswomen.wordpress.com/">TCS women event</a> at STOC. Features include a panel of senior female researchers, a women’s lunch, and a research rump session. They have also secured funding to sponsor travel scholarships for women to attend STOC (see the web site); the organizers would like to see increase in women participation from outside of USA.</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-25413029566422275062018-04-12T04:18:00.001-07:002018-04-12T04:18:57.580-07:00SAGT and WINE 2018<div dir="ltr" style="text-align: left;" trbidi="on">
New web sites for conferences later this year in Algorithmic Game Theory:<br />
<ul>
<li><a href="http://aims.sjtu.edu.cn/SAGT_2018/index.html">11th International Symposium on Algorithmic Game Theory (SAGT)</a><br />
Beijing, China, from the 11th to the 13th of September 2018.</li>
<li><a href="http://www.cs.ox.ac.uk/conferences/wine2018/index.html">14th Conference on Web and Internet Economics (WINE)</a><br />
Oxford, UK, 11th to 15th December, 2018.</li>
</ul>
Note that the paper submission deadline for SAGT is getting close.</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com1tag:blogger.com,1999:blog-32902056.post-16491326304093662172018-03-21T16:00:00.000-07:002018-03-21T16:00:59.495-07:00thinking algebraically or geometrically<div dir="ltr" style="text-align: left;" trbidi="on">
I was recently talking with an historian who mentioned to me that when Stephen Hawking lost the use of his hands (so could no longer write on a whiteboard), he had to switch from thinking algebraically to thinking geometrically. The historian asked me about this distinction, and I attempted to explain these alternative modes of mathematical thinking. We discovered an analogy that is so cute that I have to write it up: the historian, who specialises in shipping in the Mediterranean, often visualises the scenery, and life on board the ships, but does not end up illustrating his books with his imagined scenes. Visualising the past environment presumably helps to understand the narrative of what was going on at the time, and of course, that corresponds to the geometrical thinking.</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-2918138296066857132017-10-18T08:10:00.000-07:002017-10-18T08:10:04.604-07:002018 Alan Turing Institute Doctoral Studentships<div dir="ltr" style="text-align: left;" trbidi="on">
Doctoral research in data science: studentships to begin in autumn 2018. The application deadline is midday on 30 November 2017.<br />
<br />
<a href="https://www.turing.ac.uk/opportunities/studentships/">Here is a link to the full advertisement</a>, with details about what the studentships offer.<br />
<br />
I’m on the 2018 Turing supervisor list and received an email suggesting to circulate the advert.</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-53458666470025160232017-09-25T09:00:00.000-07:002017-09-25T09:00:15.241-07:00JOB: Associate Professorship of Algorithms and Complexity Theory, Oxford<div dir="ltr" style="text-align: left;" trbidi="on">
Associate Professorship of Algorithms and Complexity Theory with Tutorial Fellowship at Hertford College<br />
<br />
UNIVERSITY of OXFORD<br />
<br />
<a class="moz-txt-link-freetext" href="http://www.cs.ox.ac.uk/news/1383-full.html">http://www.cs.ox.ac.uk/news/1383-full.html</a><br />
<br />
Applications are invited for the post of Associate Professor (or Professor) of Algorithms and Complexity Theory to be held in the Department of Computer Science with effect from 1 October 2018. The successful candidate will also be appointed as Fellow and Tutor in Computer Science at Hertford College; Tutors being responsible for the organisation and teaching of their subject within the College.<br />
<br />
The salary for this position is offered on a scale from £46,336 per annum, plus substantial additional benefits, including single accommodation at college, if available, or a living-out allowance of £9,437 pa. An allowance of £2,700 pa would be payable upon award of Full Professor title.<br />
<br />
The Department of Computer Science is a vibrant and growing academic department, which has a research profile across the entire spectrum of contemporary computing. The Associate Professor will be expected to engage in independent and original research in the field of Algorithms and Complexity Theory, to secure funding and engage in the management of research projects and disseminate research of the highest international standard through publications, conferences and seminars. They will also will contribute to teaching on the Department’s highly successful undergraduate and graduate programmes. Oxford has a strong tradition in Algorithms and Complexity Theory, with multiple active faculty members in the Computer Science, Information Engineering, and Statistics departments.<br />
<br />
The Associate Professor will be a member of both the University and the college community. They will be part of a lively and intellectually stimulating research community with access to the excellent research facilities which Oxford offers. They will have a role to play in the running of the College as a member of the Governing Body and a trustee of the College as a charity.<br />
<br />
The successful candidate will hold a doctorate in Computer Science, or a related subject, will have the ability to teach across a range of Computer Science subjects, and will also have a proven research record of high quality at international level in the area of Algorithms and Complexity Theory, and experience of research collaborations at both national and international level.<br />
<br />
The closing date for applications is 12.00 noon on 5 January 2018. Interviews will be held on 13 February 2018 – please allow a full day for these.<br />
<br />
<a class="moz-txt-link-freetext" href="http://www.cs.ox.ac.uk/news/1383-full.html">http://www.cs.ox.ac.uk/news/1383-full.html</a></div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-10225580202337613522017-07-12T02:33:00.000-07:002017-07-12T02:33:49.103-07:00WINE 2017 : Conference on Web and Internet Economics<div dir="ltr" style="text-align: left;" trbidi="on">
A reminder about the 13th WINE conference:<br />
<br />
<a href="http://lcm.csa.iisc.ernet.in/wine2017/">Link to conference web site</a><br />
<a href="http://lcm.csa.iisc.ernet.in/wine2017/papers.html"> Link to Call for Papers</a> (deadline is 2nd August 2017)<br />
<br />
Over the past decade, research in theoretical computer science, artificial intelligence, and microeconomics has joined forces to tackle problems involving incentives and computation. These problems are of particular importance in application areas like the Web and the Internet that involve large and diverse populations. The Conference on Web and Internet Economics (WINE) is an interdisciplinary forum for the exchange of ideas and results on incentives and computation arising from these various fields. WINE 2017 builds on the success of the Conference on Web and Internet Economics (named Workshop on Internet & Network Economics until 2013), which was held annually from 2005 to 2016. <br />
<br />
The program will feature invited talks, tutorials, paper presentations, and a poster session. All paper submissions will be peer-reviewed and evaluated on the basis of the quality of their contribution, originality, soundness, and significance. Industrial applications and position papers presenting novel ideas, issues, challenges and directions are also welcome. Submissions are invited in, but not limited to, the following topics: <br />
<br />
Algorithmic Game Theory <br />
Algorithmic Mechanism Design <br />
Auction Algorithms and Analysis <br />
Computational Advertising <br />
Computational Aspects of Equilibria <br />
Computational Social Choice <br />
Convergence and Learning in Games <br />
Coalitions, Coordination and Collective Action <br />
Economic Aspects of Security and Privacy <br />
Economic Aspects of Distributed Computing <br />
Network Games <br />
Price Differentiation and Price Dynamics <br />
Social Networks <br />
<br />
More details are at the conference web site.</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-54569670615415463462017-06-28T03:56:00.000-07:002017-06-28T03:56:48.650-07:00new idea for TEF<div dir="ltr" style="text-align: left;" trbidi="on">
The <a href="http://www.hefce.ac.uk/lt/tef/">Teaching Excellence Framework</a> (TEF) attempts to measure teaching quality by looking at a collection of metrics obtained from universities, and universities recently received (provisional) gold/silver/bronze ratings. Metrics include NSS scores, dropout rates, and employment destinations. An <a href="https://www.timeshighereducation.com/news/tef-what-makes-gold-university">article</a> in the Times Higher on “what makes a gold university”, notes that TEF scores correlate poorly with REF scores but well with NSS scores. An <a href="https://www.theguardian.com/education/2017/jun/22/many-top-uk-universities-miss-out-on-top-award-in-controversial-new-test">article</a> in the Guardian noted “critics argue that none of the indicators directly measure teaching quality”. Here, I suggest as a new metric, the salaries of people doing the teaching.<br />
<br />
I thought of this metric from reading the <a href="https://www.theguardian.com/education/2017/jun/22/many-top-uk-universities-miss-out-on-top-award-in-controversial-new-test">Guardian article</a>, which quotes Universities minister Jo Johnson as saying that TEF is supposed to give teaching the same status as research. Salary is a good measure of status. As a measure of quality, the general principle (of judging the value of something in terms of what you put in rather than what you get out) is widespread elsewhere: institutions measure research in terms of research funding received, and similarly, buildings, other infrastructure projects, and company bosses are commonly described in terms of their cost (treating cost as a proxy for value, or quality).<br />
<br />
Specifically, I recommend using the median salary of members of staff involved with teaching. (Note, I suggest the median, not the mean.) Concerning what it should mean to be involved with teaching, there are various options, since the median is fairly robust to tampering with the data. One option is to just let every member of staff assess the extent of his/her own level of teaching as a fraction of their work.<br />
<br />
Overall, the effect of this metric would be to encourage universities to save money on central administration and other expenses. Talking of which, <a href="https://www.theguardian.com/science/2017/jun/27/profitable-business-scientific-publishing-bad-for-science">this Guardian article</a> on the high profit margins in academic publishing is well worth reading. It does a good job of explaining the historic background to the problem, and the bad incentives that cause so much to be spent on academic journals.</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-61937492716573058662017-06-09T05:33:00.000-07:002017-06-09T05:33:45.957-07:00Brexit and Rubinstein’s bargaining model<div dir="ltr" style="text-align: left;" trbidi="on">
A Google search for Brexit and game theory finds a number of web pages that discuss models of the negotiation process, constructing payoff matrices in which the parties to the negotiation choose to cooperate (or not) over issues such as free movement of people; these models aim to predict the outcome of the negotiations. The models are rather simplistic, but are probably more realistic than the <a href="https://www.theguardian.com/politics/2016/oct/16/brexit-debate-iwould-give-game-away-to-brussels-priti-patel">efforts</a> by certain members of government to treat Brexit as a game of poker.<br />
<br />
Rubinstein’s classic paper <i>Perfect Equilibrium in a Bargaining Model</i> (<a href="https://en.wikipedia.org/wiki/Rubinstein_bargaining_model">wikipedia page</a>) models a negotiation between 2 players who have to share a pie; there is no limit on the number of rounds, but there’s a cost of delaying, which in one version consists of a player’s <i>discounting factor</i>, which is the rate at which the value of (a share of) the pie goes to zero, each time a round of bargaining takes place without agreement. It could possibly be taken to represent a situation following the March 2019 deadline, supposing that no agreement has been reached, and both sides suffer ongoing economic costs while an agreement is being constructed. The “pie” would consist of the collection of (many) issues that have to be resolved in favour of one side or the other.<br />
<br />
Suppose player 1 (the UK) has a discounting factor δ<sub>1</sub> and player 2 (the EU) has discounting factor δ<sub>2</sub>. (δ<sub><i>i</i></sub> denotes the fraction of value of remaining after a round, not the fraction lost.) According to the model, the UK’s share of the pie should be (1-δ<sub>2</sub>)/(1-δ<sub>1</sub>δ<sub>2</sub>). It just remains for us to decide the values of these discounting factors, and we’re in good shape to figure out what share of the pie the UK should accept before the deadline expires.<br />
<br />
According to <a href="https://www.weforum.org/agenda/2017/04/brexit-european-union-negotiations/">this page</a>, Britain depends on the EU for half of its exports, while Britain accounts for only one-sixth of Europe’s. If we give the UK a discounting factor of 1/2 and the EU a discounting factor of 5/6, we get that the UK should receive 2/7 of the pie — so, not the lion’s share. Still, those discounting factors may look harsh; there’s more to life than exports to our geographical neighbours. Let’s average them with 1, and use δ<sub>1</sub>=3/4 and δ<sub>2</sub>=11/12. In that case, the UK’s share of the pie unfortunately goes down to 4/15, and I don’t think it gets any better when you adjust them further! To conclude, the UK should cave in on most of the issues that need to be resolved in a Brexit settlement. As the above-mentioned web page notes (based on a different model): The EU has an incentive to offer a bad deal, and the UK has an incentive to take it.</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-85331701918109120422017-04-28T09:52:00.000-07:002017-04-28T09:52:36.216-07:00SAGT 2017 deadline extended to 5th May<div dir="ltr" style="text-align: left;" trbidi="on">
The PC chairs asked me to advertise that the submission deadline for the <a href="http://cs.gssi.infn.it/sagt2017/">2017 symposium on Algorithmic Game Theory</a> is now the 5th of May.</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-59949467840588461382016-10-05T01:59:00.000-07:002016-10-05T01:59:10.074-07:00EATCS Fellows 2017 - Call for Nominations<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
The official call for nominations is <a href="https://eatcs.org/index.php/component/content/article/1-news/2354-eatcs-fellows-2017-call-for-nominations">at this URL</a> at the European Association for Theoretical Computer Science (EATCS), below is a copy:<br />
<center>
<b>Deadline: December 31, 2016</b></center>
<ul>
<li>VERY IMPORTANT: all nominees and nominators must be EATCS Members</li>
<li>Proposals for Fellow consideration in 2017 should be submitted by DECEMBER 31st, 2016 by email to the EATCS Secretary (secretary "at" eatcs "dot" org). The subject line of the email should read "EATCS Fellow Nomination - <surname of candidate>".</li>
</ul>
The EATCS Fellows Program is established by the Association to recognize outstanding EATCS Members for their scientific achievements in the field of Theoretical Computer Science. The Fellow status is conferred by the EATCS Fellows- Selection Committee upon a person having a track record of intellectual and organizational leadership within the EATCS community. Fellows are expected to be "model citizens" of the TCS community, helping to develop the standing of TCS beyond the frontiers of the community.<br />
<br />
In order to be considered by the EATCS Fellows-Selection Committee, candidates must be nominated by at least four EATCS Members. Please verify your membership at <a href="http://www.eatcs.org/">www.eatcs.org</a>.<br />
<br />
The EATCS Fellows-Selection Committee consists of<br />
<ul>
<li>Rocco De Nicola (IMT Lucca, Italy)</li>
<li>Paul Goldberg (Oxford, UK, chair)</li>
<li>Anca Muscholl (Bordeaux, France)</li>
<li>Dorothea Wagner (Karlsruhe, Germany) </li>
<li>Roger Wattenhofer (ETH Zurich, Switzerland)</li>
</ul>
<br />
<b>INSTRUCTIONS:</b> A nomination should consist of details on the items below. It can be co-signed by several EATCS members. At least two nomination letters per candidate are recommended. If you are supporting the nomination from within the candidate’s field of expertise, it is expected that you will be specific about the individual’s technical contributions.<br />
<br />
To be considered, nominations for 2016 must be received by <b>December 31, 2016</b>.<br />
<br />
1. Name of candidate, Candidate’s current affiliation and position, Candidate’s email address, postal address and phone number, 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 contributions that qualify the candidate for the rank of EATCS Fellow according to the following two categories:<br />
<br />
A) Technical achievements<br />
<br />
B) Outstanding service to the TCS community. Please limit your comments to at most three pages.<br />
<br />
4. Nominator(s): Name(s) Affiliation(s), email and postal address(es), phone number(s)<br />
<br />
Please note: all nominees and nominators must be EATCS Members<br />
<br /></div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-3931360466383878672016-08-27T05:56:00.000-07:002016-08-27T05:56:25.695-07:00Graduate wage premium<div dir="ltr" style="text-align: left;" trbidi="on">
I liked the Guardian article <a href="https://www.theguardian.com/commentisfree/2016/aug/20/value-for-money-not-only-measure-of-university">‘Value for money’ can’t be the only measure of university</a>, one reason being that it calls attention to Michael Oakshott’s 1950 essay <a href="https://www.cse.cuhk.edu.hk/irwin.king/_media/teaching/gen1113/scn_20090202113046_001.pdf"><i>The Idea of a University</i></a>, which I now reckon should be read by every university student, or prospective student. No so much due to it being likely that they would buy into “the gift of an interval” as just that it presents a radically alternative viewpoint on the question of why people go to university; alternative, that is, to the current conventional wisdom that it’s about buying a ticket to a higher-paid job.<br />
<br />
Graduates still benefit from a “wage premium”, despite increases in the proportion of people who go to university (<a href="https://www.ft.com/content/305e85d4-6489-11e6-a08a-c7ac04ef00aa">article in FT</a>, <a href="https://www.theguardian.com/education/2016/aug/18/gap-between-graduate-and-non-graduate-wages-shows-signs-of-waning">article in Guardian</a>). This was found to be the case in a new report from the Institute for Fiscal Studies (link to <a href="https://www.ifs.org.uk/publications/8426"> press release</a>) arguing that the continued wage premium is due to structural changes in organisations, or maybe due to increased demand (for graduates) increasing to meet the increased supply. The Guardian article notes that the IFS reckon that further increases in university take-up may reduce the graduate premium. I came up with the following observation (which doesn’t seem to have been suggested in the comments attached to the articles linked-to above). Suppose 99% of us went to university, then it seems likely that a “healthy” graduate premium would continue to exist. (The remaining 1% would be at risk of being seen to be missing some capability that nearly everyone has, and one would expect their average pay to be lower.) The point of that observation is to challenge the idea that we should care about the graduate premium.</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-80600531368942950482016-06-28T01:25:00.000-07:002016-06-28T01:25:31.321-07:00Note on the EU referendum, ex post<div dir="ltr" style="text-align: left;" trbidi="on">
The EU referendum has been interpreted as showing a nation divided by age (older people more likely to have voted Brexit), or possibly affluence, or alternatively geography (as in: Scotland and London more likely to have voted Remain). But plenty of older people voted Remain, likewise there was no clear consensus either way in any geographical region. Maybe we’re actually a nation divided by social networks: people seem to have voted the same way that “everyone” they knew voted. We all exist in social micro-environments, and in the case of academia, they are further subdivided into what might be called nano-environments. I may be biased towards the social-networks story, having dabbled in the associated theoretical problems that have been considered in the Computer Science theory literature. Perhaps the UK’s social network has not one, but two, giant components. If so, that has implications for social mobility. It may be felt that one of them is more effective than the other, when it comes to creating career opportunities for its members.</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-67610493687615006802016-06-19T00:22:00.000-07:002016-06-19T01:17:19.760-07:00Notes on the EU referendum<div dir="ltr" style="text-align: left;" trbidi="on">
The June 2016 issue of the <i>Oxfordshire Observer</i>, a newsletter from the local Liberal Democrats, had the headline “Remain for prosperity”, and from the article: “Thousands of jobs in the county have been created or supported by EU funding. Oxfordshire receives millions of pounds of investment in innovation and research from the EU.” This helps to explain why most members of the academic community, myself included, intend to to vote to remain in the EU. I worry that the article is Oxford-centric and that all this “investment” is at the expense of other places. Now that council leaders of the main northern English cities have also come out in favour of remaining in the EU, that concern is alleviated.<br />
<br />
Concerning Europe’s research funding, I have some sympathy with remarks made in <a href="https://www.nobelprize.org/nobel_prizes/physics/laureates/2010/geim_lecture.pdf">Andre Geim’s Nobel Prize lecture</a>, <i>Random Walk to Graphene</i>, which (as suggested by the title) is worth reading in full as a heartening reminder of the hit-and-miss nature of scientific advances. On pages 77 and 92, EPSRC’s responsive mode comes in for high praise while the EU Frameworks programme “can only be praised by Europhobes”.<br />
<br />
EU membership is convenient when it comes to offering jobs and student places to other EU nationals. A downside is that we maybe don’t do enough in UK academia to nurture home-grown talent. According to <a href="https://hesa.ac.uk/PR228">these HESA figures</a>, about 35-40% of UK-based academics and researchers in science and engineering are not UK nationals. It’s entertaining to imagine what would happen in the UK academic community (at least, some parts of it) if we were suddenly disallowed to appoint foreign candidates to academic posts. It might help the <a href="https://www.ucu.org.uk/article/8230/Union-blasts-blatant-double-standards-in-university-pay">UCU’s claim</a> that “Universities need to answer some hard questions about how they will continue to attract and retain the best talent when pay is being held down…”<br />
<br />
Another argument for remaining in the EU is that the job market mobility may, over time, exert pressure to reverse the UK’s debt-based approach to student funding. That is, if it’s easy for someone to get a degree here and then go elsewhere to live and work, then the debt (repayable via UK taxes) doesn’t get repaid, and an incentive is in place for productive people to study in the UK but to move elsewhere.<br />
<br />
For balance, <a href="https://www.theguardian.com/money/blog/2016/jun/18/eu-vote-brexit-working-people-rents-wages">here</a> is the best article I have seen so far in support of voting to leave.<br />
<br />
I wrote the above before finding <a href="https://gowers.wordpress.com/2016/06/02/6172/">this blog post</a> of Tim Gowers in support of remaining, in which he compares leaving the EU to defecting in the Prisoner's Dilemma. It surely deserves a mention/link. <br />
<br /></div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-79079031576409940002016-02-04T12:32:00.002-08:002016-02-04T12:32:55.883-08:00Bristol Algorithms Days<div dir="ltr" style="text-align: left;" trbidi="on">
A quick note of thanks to the organisers of <a href="https://www.cs.bris.ac.uk/Research/Algorithms/events/BAD16/">Bristol Algorithms Days</a>, a 2-day workshop (just ended) featuring talks on ongoing work on algorithms and proof techniques for analysing their properties. The event attracted quite a few colleagues from the UK and a surprising number of visitors from further afield. I got a useful introduction to some important lines of research that I’d been vaguely aware of, ones that deserve to be somewhat familiar to those of us in the algorithms community. A notable one is SETH-hardness, and 3SUM-hardness, and their usefulness for providing evidence that various polynomial-time algorithms cannot be improved on (e.g. the quadratic time taken by dynamic programming for problems like longest common subsequence, and computation of Frechet distance as well as other geometrical problems) (talk by Karl Bringmann). Another topic (talk by Iordanis Kerenidis): quantum algorithms that give exponential speedup for certain linear operations, and the applicability of these to machine learning; apparently there’s interest at Google and Microsoft in the potential applicability of such algorithms to their data. A talk by Alina Ene on computational learning problems that can be modelled as constrained submodular maximisation problems was interesting to me, having gotten somewhat familiar with submodular functions in economic-theory contexts. That list is non-exhaustive…</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com0tag:blogger.com,1999:blog-32902056.post-88012966232899231262016-01-28T11:43:00.000-08:002016-01-28T11:43:12.094-08:00go-playing AI<div dir="ltr" style="text-align: left;" trbidi="on">
Back when I was a student I was a fairly enthusiastic <a href="https://en.wikipedia.org/wiki/Go_game">Go</a> player, and always liked the fact that it seemed to be resistant to efforts to make a strong go-playing computer program. (At any rate, it resisted my own effort to write a strong Go-playing program.) Having followed the progress of go-playing programs, of course I was interested in the success of the Google DeepMind program (articles in the <a href="http://www.bbc.com/news/technology-35420579">BBC</a> and <a href="http://www.theguardian.com/media-network/2016/jan/28/google-ai-go-grandmaster-real-winner-deepmind">Guardian</a>) against Fan Hui, Europe’s top Go player. As noted in Neil Lawrence’s Guardian article, the DeepMind program doesn’t achieve the data efficiency of human players, so there is still work to do. And for those of us who like to imagine that Go is really supposed to be hard to program, there is a glimmer of hope: Previous Go-playing programs perform better against a human opponent during the first few games, and then the human opponent learns their weaknesses. Could Fan Hui eventually start winning, with a bit more practice?</div>
Paul Goldberghttp://www.blogger.com/profile/10952445127830395305noreply@blogger.com2