Friday, April 12, 2019

New conference: ACM-SIAM Algorithmic Principles of Computer Systems (APoCS20)

ACM-SIAM Algorithmic Principles of Computer Systems (APoCS20)

January 8, 2020
Hilton Salt Lake City Center, Salt Lake City, Utah, USA
Colocated with SODA, SOSA, and Alenex

The First ACM-SIAM APoCS is sponsored by SIAM SIAG/ACDA and ACM SIGACT.

Important Dates:

August 9: Abstract Submission and Paper Registration Deadline
August 16: Full Paper Deadline
October 4: Decision Announcement

Program Chair:

Bruce Maggs, Duke University and Akamai Technologies

Submissions:

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:

Databases
Compilers
Emerging Architectures
Energy Efficient Computing
High-performance Computing
Management of Massive Data
Networks, including Mobile, Ad-Hoc and Sensor Networks
Operating Systems
Parallel and Distributed Systems
Storage Systems


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. 

Steering Committee:

Michael Bender
Guy Blelloch
Jennifer Chayes
Martin Farach-Colton (Chair)
Charles Leiserson
Don Porter
Jennifer Rexford
Margo Seltzer

Wednesday, March 27, 2019

Meaningful votes

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 Norway plus (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.

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”.

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.

I checked the paper Thirteen Reasons Why the Vickrey-Clarke-Groves Process Is Not Practical 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.

The effort we put into studying voting systems is justified by the following Milton Friedman quote:
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.

Monday, March 18, 2019

The will of the people

At one point in Iain Banks’ novel The Wasp Factory, the main character (a troubled teenager called Frank) makes the following observation:
Often I’ve thought of myself as a state; a country or, at the very least, a city.
He then compares his moods and thought processes to political moods that countries go through:
…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.
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.

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 Condorcet cycle.

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.

Tuesday, November 06, 2018

What do you know that deserves more publicity?

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.

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 much attention, and other unspecified stories are getting overlooked in consequence. The challenge is to make a positive 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.

With hindsight, I would point to the topic of fairness in AI, which has received some mass-media coverage (example) 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.

Tuesday, April 17, 2018

STOC child care

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 here).

In a challenge to my long-standing view of academic life as a hybrid of Herman Hesse’s The Glass Bead Game 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 British Colloquium on Theoretical Computer Science, although I don’t recall it being subsidised.)

On a related note, I was separately circulated an email advertising a TCS women event 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.

Thursday, April 12, 2018

SAGT and WINE 2018

New web sites for conferences later this year in Algorithmic Game Theory:
Note that the paper submission deadline for SAGT is getting close.

Wednesday, March 21, 2018

thinking algebraically or geometrically

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.