hackNY Fall 2010

From Chris Wiggins. FYI:

Dear Colleague:

I'm emailing to ask your help getting the word out to students, both undergraduate and graduate, about the Fall 2010 hackNY student hackathon, to take place 1pm-1pm October 9-10 at NYU's Courant Institute, and described here: http://hackny.org/a/f2010_hackathon/

This is a chance for students to find out about NYC's growing tech startup ecosystem via presentations by startups of their APIs and datasets, on which students will base their mashups, creations, visualizations, and other `hacks' over a 24-hour period. At the end students' demos will be judged for prizes and glory.

A brief video which captures the spirit of our spring hackathon was made by the Yahoo Developer Network, one of our sponsors for the hackathons, and can be found here: http://bit.ly/hackNYspring2010vid

The hackathon is also a chance for us to get to know students who might be interested in applying for the 2011 class of hackNY Fellows, a summer internship program including housing at NYU, matched positions at tech startups for which their skills are needed, and a series of pedagogical lectures from CEOs, CTOs, and investors. More information about the Fellows' program can be found in a recent Wall Street Journal article here:http://bit.ly/wsjstartups

Please do feel free to forward this email to students who might be interested in attending, as well as to your faculty colleagues. Students should register in advance here: http://hackny.org/a/f2010_hackathon/students/Please don't hesitate to be in touch if you have any questions.

best regards,

Chris
------

Faculty Position at Harvard

Harvard seeks to hire:

We welcome outstanding applicants in all areas of computer science. We are particularly interested in areas related to machine learning, probabilistic modeling, and artificial intelligence. In terms of applications, areas of interest include computational science, engineering, or the social sciences. We encourage applications from candidates whose research examines computational issues raised by very large data sets or massively parallel processing.

Simons Science Series: Michael Kearns

Simons Foundation runs an invite-only talk Series on Science, including the new one on the block, i.e., Computer Science. Michael Kearns spoke on Sept 22 about his experiments with the behavior of economic agents (students) working on tasks (solving graph problems). I have heard parts of the talk before, but Michael is a superlative speaker, great in answering questions, and included new material.

He started the talk with saying his background was in theoretical computer science, and if you blurred your eyes a bit, you will see the vestiges of his background in the talk. He motivated network science: empirically, we observe many structures (small diameter, clustering) of networks in practice, why do each of these structures arise in the first place, but also, why do these coexist? He spoke about following games:

• Coloring. Each agent sees their node and neighbors, and given a palette of chromatic number of colors to use, Michael showed the video of play by play as players try to color the network. On simple graphs, they seem to converge on legal coloring in many cases.
  
• Consensus. Same setup as before. Agents have to agree on a color (detail: each agent has private random remapping of colors, so they cant just agree on a color a priori). Michael used this task to make the point that structure in networks by itself is not as discriminating as structure in conjuction with the task because coloring and consensus problems have different implications for the same structure. Q from audience: are there irrational, spoiler, outlier players who eg, pick a color and not change? A: Yes.
  
• Voting. Minority have greater incentive for R than B, can they impose their will on others and make all nodes go R? Baruch Schieber anecdote: Wireless providers incentivize a select few, who manage to implicitly convince others in their network to stay and not churn.
• Final example: Network Creation. Now agents can buy edges, but it reduces their payoffs. This video is harder to intuit, the results were hot-off-the-experimental-bench, and still needed more interpretation.
  

The overall talk was polished and held the attention of the \approx 60 people in the audience on fifth avenue, from Courant Inst, Columbia U, to IBM Research and elsewhere in NY. The talk went well over an hour, almost to the time when Michael had to run, catch a train. Some of us lingered and talked to David Eisenbud, Jim Simons and others. I think the foundation has done a great job of picking speakers (see the scan of the program), and am looking forward.

ps: Michael did not use the word "graph" anytime during the talk. :)

WINE 2010

The list of accepted papers to the 6th Workshop on Internet & Network Economics (WINE 10) is now online (in xls form, 32 regular accepts). Amin Saberi who is PCing the conference has put together a fantastic set of plenary speakers: Daron Acemoglu, Jennifer Chayes, Michael Kearns, Jon Kleinberg, Nimrod Megiddo and Rakesh Vohra. Each of them is worth traveling to hear, any two of them as plenary speakers will make a great conference, the constellation of six of them makes it stellar. See you in Stanford, Dec 13--17.

Institute for the Theory of Computing

As Lance and others blogged, Simons Foundation has called for proposals for a new Institute for the Theory of Computing. This is great and we should be grateful to the foundation.

What got my attention:

Modes of Operation: To help attract the best-established researchers and the strongest postdocs, the Institute must provide excellent working conditions for collaboration among its residents, excellent scientific leadership to determine the planned activities, and an excellent director with strong administrative support to manage it. To have full impact on the field, the Institute must host a frequently changing group of computer scientists as well as mathematicians and scientists from other fields. Suitable models may be found in the Kavli Institute for Theoretical Physics in Santa Barbara and in the mathematics institutes such as the Mathematical Sciences Research Institute in Berkeley or the Institute for Mathematics and its Applications in Minnesota. The Institute plan may call for a small core of long-term members, perhaps with a structure similar to that of the Kavli Institute for Theoretical Physics in Santa Barbara; or the plan may call for a membership that changes entirely every year, perhaps with a structure similar to that of the Mathematical Sciences Research Institute in Berkeley.

Question: are these efficient models for 2010's and beyond? DIMACS, IMA, MSRI and many other institutes were set up several decades ago, and operate in a mode quite similar to each other (when funding allows). Now my new premises are:

• it is difficult to get senior researchers to travel far for sabbatical at various academic Institutes, and
  
• given the Internet, we can very effectively video conference, network and collaborate at far distances.
  

Given these two premises, shouldn't new institutes go where researchers are (instead of other way around) and be a totally distributed center across geographic US regions? There could be a lightweight, but intellectually strong center running say very high profile series of talks, brainstorming meetings, a periodic physical meeting of all distributed centers, etc., providing leadership; any group of researchers across the country can propose and run a special activity of 2 or 3 years (say when some of them are on sabbatical). We need to balance the obvious benefits of being in one place for collaboration and the convenience of being away for collaboration. :)

Disclaimer: In the spirit of the fast Internet world, I am rushing out this post before debating pros and cons, eg., didn't discount for the angst of leaving a tried model for the unknown.

MapReduce Prefix Sums

Input is a set of items (i, v_i), for 1=1, ..., n, distributed in arbitrary order among m machines with memory M each. Output should be (i, s_i=\sum_{j\leq i} v_j), for all i, again distributed in arbitrary order on the machines. This is the prefix sums problem for massive, unordered, distributed (MUD) data. We need to solve this using MapReduce. I can design an algorithm that will take 3 phases of Map+Reduce with suitable assumptions about n vs M, maybe even 2. Can someone show this can not be done in one phase of Map+Reduce?

To Endow Theory

Two questions:

• how much does it take to make theory conferences free?, and
  
• how do we get there?
  

Let me focus only on the first question. It will be great to support or subsidize

• travel, meals, and stay for all academic participants -- students, postdocs, faculty -- and
  
• conference operational cost including auditoriums, A/V, publication, website and publicity, etc.

for major conferences, say 3 per year: 300 attendees @ $1000 each, and additional expenses of $100k, $400k per conference and $1.2M per year? At the standard calculation that $x investment will give 3% per year in spending money after preserving capital adjusted for inflation, x=40M. Like all numbers, these can be tweaked of course (fewer/more conf, persons or level of support, adjusting for inflation per year in required budget, etc), which only leaves the second question open.

Mac Time

Should I switch from the functional black box of my Windows laptop to the gleaming toy of a Mac? I am probably 20 years behind in facing this question. Everywhere around me, I see people willing to live with single threaded Mac OSes, slow browsers, flash-less world, walled garden, whatever, to own and display Mac products. Here is the onion's take on this cult.

New Apple Friend Bar Gives Customers Someone To Talk At About Mac Products