Congrats to Noam!

I’m sure that Noam is too modest to mention the great news on his own blog, so I’ll have to do it: Noam was just awarded the Knuth Prize for his many fundamental contributions to computational complexity, pseudorandomness, and algorithmic game theory.  The Knuth Prize is awarded for “outstanding contributions to the foundations of computer science by individuals for their overall impact in the field over an extended period.”


The 2017 Innovations in Theoretical Computer Science (ITCS) conference, will be held in Berkeley on January 9-11, 2017.  the Call for Papers is online.  Submission deadline is September 15th.  At the request of the program chair, Christos Papadimitriou, I am mirroring his take on the conference (which previously also appeared here).


ITCS:  A hidden treasure of TCS

by Christos Papadimitriou

Conferences, for me, are a bit like demonstrations: they were fun in the 1970s.  There was the Hershey STOC, of course, and that great FOCS in Providence, plus a memorable database theory gathering in Calabria.  Ah, children, you should have been there…

So, even though I was a loyal supporter of the ITCS idea from the beginning – the “I”, you recall, stands for innovation –, I managed to miss essentially all of them – except for those that left me no excuse.  For example, this year the program committee was unreasonably kind to my submissions, and so this January I was in Boston to attend.

I want to tell you about ITCS 2016, because it was a gas.

First, I saw all the talks.  I cannot recall this ever happening to me before.  I reconnected with fields of old, learned a ton, and got a few cool new ideas.

In fact, I believe that there was no talk with fewer than 60 people in the audience – and that’s about 70% of the attendees.  In most talks it was closer to 90%.  When was the last conference where you saw that?

And what is the secret of this enhanced audience attention?  One explanation is that smaller conference means small auditorium.  Listening to the talk no longer feels like watching a concert in a stadium, or an event on TV, it’s more like a story related by a friend.  Another gimmick that works well is that, at ITCS, session chairs start the session with a 10-minute “rant,” providing context and their own view of the papers in the session.

Our field got a fresh breath of cohesion at ITCS 2016: cryptographers listened to game theorists in the presence of folks who do data structures for a living, or circuit complexity – for a moment there, the seventies were back.

Ah, those papers, their cleverness and diversity and freshness!  Here is a sample of a few with a brief comment for each (take a look at the conference website for the papers and the presentations).

  • What is keeping quantum computers from conquering all of NP? It is the problem with destructive measurements, right?  Think again, say Aaronson, Bouland and Fitzsimons.  In their paper (pdf, slides) they consider several deviations from current restrictions, including non-destructive measurements, and the space ‘just above’ BQP turns out to be a fascinating and complex place.
  • Roei Tell (pdf, slides) asks another unexpected question: when is an object far from being far from having a property? On the way to an answer he discovers a rich and productive duality theory of property testing, as well as a very precise and sophisticated framework in which to explore it.
  • If you want to represent the permanent of a matrix as the determinant of another matrix of linear forms in the entries, how large must this second matrix be? – an old question by Les Valiant. The innovation by Landsberg and Ressayre (pdf, slides) is that they make fantastic progress in this important problem through geometric complexity: If certain natural symmetries are to be satisfied, the answer is exponential!

(A parenthesis:  The last two papers make the following important point clear: Innovation in ITCS isnot meant to be the antithesis of mathematical sophistication.  Deep math and methodological innovation are key ingredients of the ITCS culture.)

  • When shall we find an explicit function requiring more than 3n gates? In their brave exploration of new territory for circuit complexity, Golovnev and Kulikov (pdf, slides) find one possible answer: “as soon as we have explicit dispersers for quadratic varieties.”
  • The student paper award went to Aviad Rubinstein for his work (pdf) on auctioning multiple items – the hardest nut in algorithmic mechanism design. He gives a PTAS for optimizing over a large – and widely used – class of “partitioning” heuristics.

Even though there were no lively discussions at the lobby during the sessions – too many folks attending, see? – the interaction was intense and enjoyable during the extra long breaks and the social events.

Plus we had the Graduating Bits night, when the youngest among us get 5 minutes to tell.  I would have traveled to Cambridge just for that!

All said, ITCS 2016 was a gem of a meeting.  If you skipped it, you really missed a good one.

But there is no reason to miss ITCS 2017, let me tell you a few things about it:

  • It will be in Berkeley, January 9 -11 2017, the week before the Barcelona SODA.
  • It will take place at the Simons Institute just a few days before the boot camps on Pseudorandomness and Learning.
  • I volunteered to be program chair, and the steering committee has decided to try a few innovations in the submission process:
  • Submission deadline is mid-September, so you have a few more weeks to collect your most innovative thoughts. Notification before the STOC deadline.
  • Authors will post a copy of their paper, and will submit to the committee a statement about it, say 1000 words max. Think of it as your chance to write a favorable referee report for your own paper!  Telling the committee why you think it is interesting and innovative.  If you feel this is self-evident, just tell us that.
  • The committee members will be the judges of the overall worth and innovative nature of the paper. Sub-reviewers are optional, and their opinion is not communicated to the rest of the committee.
  • The committee may invite speakers to present specific recent interesting work. Submitted papers especially liked by the committee may be elevated to “invited.”
  • Plus Graduating Bits, chair rants, social program, not to mention the Simons Institute auditorium and Berkeley in January.

You should come!

The following announcement is posted on behalf of Arpita Ghosh and Matt Lease, co-chairs of the HCOMP 2016 conference. Arpita writes, “I’m enthusiastic about bringing work from the EC community to the application domain of human computation, very broadly defined.”
Call for Papers
Deadline for full papers: June 7, 2016
The theme for HCOMP 2016 is Interaction:
  • between people and technology that is foundational to human computation
  • between theoretical foundations, experimental work, and engineering
  • between the computational, scientific, and social applications of crowdsourcing
  • between diverse disciplines and perspectives, within our community and beyond
HCOMP strongly believes in inviting, fostering, and promoting broad, interdisciplinary research on crowdsourcing and human computation. Submissions may present principles, studies, and/or applications of systems that rely on programmatic interaction with crowds, or where human perception, knowledge, reasoning, or physical activity and coordination contributes to the operation of computational systems, applications, or services. More generally, we invite submissions from the broad spectrum of related fields and application areas including (but not limited to):
  • human-centered crowd studies: e.g., human-computer interaction, social computing, design, cognitive and behavioral sciences (psychology and sociology), management science, economics, policy, ethics, etc.
  • applications and algorithms: e.g., computer vision, cultural heritage, databases, digital humanities, information retrieval, machine learning, natural language (and speech) processing, optimization, programming languages, systems, etc.
  • crowdsourcing areas: e.g., citizen science, collective action, collective knowledge, crowdsourcing contests, crowd creativity, crowd funding, crowd ideation, crowd sensing, distributed work, freelancer economy, open innovation, microtasks, prediction markets, wisdom of crowds, etc.

Our Senior Program Committee (SPC) will oversee the review process and ensure that each submission receives a constructive and rigorous review.

To ensure relevance, submissions are encouraged to include research questions and contributions of broad interest to crowdsourcing and human computation, as well as discuss relevant open problems and prior work in the field. When evaluation is conducted entirely within a specific domain, authors are encouraged to discuss how findings might generalize to other communities and application areas using crowdsourcing and human computation.

All papers must be anonymized (include no information identifying the authors or their institutions) for double-blind peer-review and formatted according to the conference’s style guidelines. An Author Kit is available for getting started with LaTeX or Word.

Accepted papers will be published in the HCOMP conference proceedings and included in the Conference’s Digital Archive. HCOMP is a young but quickly growing conference, with a historical acceptance rate of 30% for full papers.

Full Papers
Full papers of up to 10 pages (including references) may be submitted. Full papers must represent original work, not previously published or under simultaneous peer-review for any other peer-reviewed, archival conference or journal.

Important Dates:

  • May 31, 2016: Abstracts (for Full Papers) due
  • June 7, 2016: Full Papers due
  • July 11, 2016: Reviews released to authors
  • July 14, 2016: [Optional] author feedback due
  • August 4, 2016: Notification of acceptance decisions
  • August 20, 2016: Camera-ready papers due

The following announcement is posted on behalf of Nicole Immorlica, Hamid Nazerzadeh, and Sergei Vassilvitskii, who are organizing the 12th Annual Ad Auctions Workshop. Note that the submission deadline is this Friday.

12th Annual Ad Auctions Workshop

July 25, 2016 in Conjunction with EC. 


The 12th Ad Auctions Workshop, will be held on July 25, 2016, in conjunction with the 17th ACM Conference on Electronic Commerce (EC’16) in Maastricht, Netherlands. The workshop will bring together researchers and practitioners from academia and industry to discuss the latest developments in online advertisement auctions and exchanges.


We solicit contributions of two types: (1) research contributions, and (2) position statements. Research contributions should report new (unpublished) research results or ongoing research.  The workshop’s proceedings can be considered non-archival, meaning contributors are free to publish their results later in archival journals or conferences.  Position statements are short descriptions of the authors’ view of how ad auction research or practice will or should evolve.  Position statements should be no more than five pages long. Panel discussion proposals and invited speaker suggestions are also welcome.

Submissions should be uploaded to the submission server by 9pm EST, May 20, 2016.  Author notification is June 17, 2016.

On behalf of the organizers:

The Workshop on Economic Aspects of Cloud Computing
(with the Conference on Economics and Computation)
July 24, 2016, Maastricht, the Netherlands

From the CFP: “The digitization of the world’s businesses, and the movement of this digitization into the cloud is akin to an industrial revolution. Cloud computing will be to businesses what mobile computing has been to consumers. This raises a whole slew of questions in economics, most of which are deeply entangled with computer science topics. The focus of this workshop is on the economic aspects of cloud computing. The goal of the workshop is to be the premier platform to raise the most important research questions, to announce the latest results, to exchange ideas, to learn and to get feedback on the state of the art research in this area. The topics of interest for this workshop include but not limited to the following.

  • Moving to the cloud: How are current businesses impacted by moving to a cloud enabled world?
  • New Markets: What new markets emerge? What new economic models are enabled?
  • Cloud Pricing: What are the different pricing or auction mechanisms to sell cloud computing resources, and the pros and cons of each?
  • Cloud provisioning: The economies of scale in provisioning and running large data centers.
  • Fair Allocation: How to allocate cloud resources in a fair manner in a shared multi-tenant system?”

The workshop is organized by Nikhil Devanur, Eric Friedman, Preston McAfee, Noam Nisan, Eva Tardos, and Adam Wierman.  All submissions should be submitted through the EasyChair no later than May 17, 2016.

On behalf of the organizers:

The Second Workshop on Algorithmic Game Theory and Data Science
(with the Conference on Economics and Computation)
July 24, 2016, Maastricht, the Netherlands

From the CFP: “Computer systems have become the primary mediator of social and economic interactions, enabling transactions at ever-increasing scale. Mechanism design when done on a large scale needs to be a data-driven enterprise. It seeks to optimize some objective with respect to a huge underlying population that the mechanism designer does not have direct access to. Instead, the mechanism designer typically will have access to sampled behavior from that population (e.g. bid histories, or purchase decisions). This means that, on the one hand, mechanism designers will need to bring to bear data-driven methodology from statistical learning theory, econometrics, and revealed preference theory. On the other hand, strategic settings pose new challenges in data science, and approaches for learning and inference need to be adapted to account for strategization. The goal of this workshop is to frame the agenda for research at the interface of algorithms, game theory, and data science.”

The workshop is organized by Richard Cole (NYU), Brad Larsen (Stanford U), Kevin Leyton-Brown (UBC), Balasubramanian Sivan (Google Research), and Vasilis Syrgkanis (Microsoft Research).  All submissions should be sent electronically to AGTDataScienceWorkshop16@gmail.com on or before May 20, 2016.

We are delighted to announce that the Handbook of Computational Social Choice has now been published with Cambridge University Press.

handbook_cscDescription: The rapidly growing field of computational social choice, at the intersection of computer science and economics, deals with the computational aspects of collective decision making. This handbook, written by thirty-six prominent members of the computational social choice community, covers the field comprehensively. Chapters devoted to each of the field’s major themes offer detailed introductions. Topics include voting theory (such as the computational complexity of winner determination and manipulation in elections), fair allocation (such as algorithms for dividing divisible and indivisible goods), coalition formation (such as matching and hedonic games), and many more. Graduate students, researchers, and professionals in computer science, economics, mathematics, political science, and philosophy will benefit from this accessible and self-contained book.

A PDF of the book is freely available on the Cambridge University Press website. Click on the Resources tab, then on “Resources” under “General Resources”, and you will find a link called “Online Version”. The password is cam1CSC.

Alternatively, the book can be purchased through Cambridge University Press, Amazon, and other retailers.

We hope that the book will become a valuable resource for the computational social choice community, and the CS-econ community at large.

Best regards,
Felix Brandt, Vince Conitzer, Ulle Endriss, Jerome Lang, and Ariel Procaccia (the editors)