NSF W8F: Questionnaire

NSF Workshop on Algorithms In The Field (8F) is about having (theory/algorithms) and (other CS areas) researchers collaborate on key challenges. For the purpose here, (theory/algorithms) researchers publish in stoc/focs/soda/socg/spaa/....; (other CS areas) researchers publish in sigmod/sigcomm/icml/kdd/sdm,www,....

This blog post is a call, you probably have well formed opinions on this topic, help us by filling this questionnaire and mailing it to nsfw8f@gmail.com. Your help is much appreciated, and will be acknowledged in the workshop report.

--------------------------- CUT HERE --------------------------------------------------

• Your areas of research/expertise
• Any pointers to any excellent examples of online surveys, tutorials, talk slides, monographs that demonstrate some of the outstanding challenges in your areas of interest.
• List any papers/DBLP entries that you would like to highlight as an example of (theory/algorithms) + (other areas of CS) researchers working together to get a nice result.
• What area/topic in algorithms/theory you or your students or researchers in your area wish they knew? (I have had various researchers say they wish their students knew linear algebraic algorithms better, or randomized algorithms, or optimization or whatever).
• How should we train (theory/algorithms) + (other areas of CS) students, researchers to work with each other.
• In your experience, did you face any obstacles/bottlenecks in such collaborations?

-------------------------------------------------------------------------------------

New Univ in New York?

Mayor Bloomberg has put his energy in the past on big projects, some more successfully than others, and this time, the City has been seeking responses to its proposal to start a new Univ for Applied Sciences (yes, CS counts). More info in NYT article.

NAS Kavli Frontiers Meeting

NAS/NAE Frontiers meetings are truly exciting, drawing very creative people from various sciences, and putting together a few select talks that never fail to generate unbridled questions or suggestions from the audience. I was at the NAE Frontier's meeting in 2002 (held over from fateful Sept 2001, my flight from Dulles to LA on Sept 12 cancelled). I was glad to be back at the NAS Kavli Frontiers meeting at Irvine a few days ago.

One session was on The Creative Brain on how brain controls behavior, in particular, creativity. Beversdorf introduced the session and discussed relationship between creativity and neurological conditions as well as possible brain mechanisms. Dr. Ganesan (real Dr kind) discussed relationship between creativity and pathological conditions including psychosis, schizophrenia and insanity, and presented evidence of a link via chemistry, biology and evolution. (I remember a gem about schizophrenia being defined on basis of language, need to follow up). Beeman gave an engaging talk (using puzzles!) about processes and neural activity leading to insights, and their modulation by mood and attention. See connection between Aha moments, problem solving skills and cognitive activity. Audience had questions about parallels with other animals. I liked this session because there is a lot of pop theories about creativity and drugs, or tortured artists, or genius, but here were serious scientists doing the hard job of trying to really understand the underlying connections. Brain and its dynamics is one complicated system! But we humans really need to understand it. I wondered what will be a challenge in the spirit of the Human Genome project or the Manhattan project in this area: map the 100B neuron graph or pick one Brain area and understand its function? There were many other sessions of similarly high quality of discourse: freshwater supplies of the world, causes of extinction in very large and short scales, biomimetic materials, organic drug synthesis, genetics, quantum, and so on. Fantastic collection.

There were more attendees than speakers, so there was a poster session to bring out latent exciting research. My favorite poster was by a population biologist that presented research on migration patterns in ants. Apparently this takes place with a leader who repeatedly schleps between the old and new location, recruiting one ant after another for the tandem walk.

My talk was in a session on Algorithms and Big Data sets --- one of the two CS sessions --- with Asu Ozdaglar (spoke about social networks and strategies, gave an interesting example of herding behavior) and Ramesh Hariharan (spoke about genomics with minimalist slides, presented an interesting probabilistic string problem and variations on Burrows-Wheeler indexing, and made a nice case for faster algorithms using smaller memory since both these resources actually cost dollars in the cloud computing era). I spoke about CM sketch and streaming and enjoyed myself. Scientists are interesting. After my talk, one of them told me, "We should do a psychoanalysis of you", and another said, " We should sequence your genome". :)

One of the great things about Frontier meetings is the discussions over meals. I found out about this project to mark the spots where we bury nuclear waste using some universal language so we leave clues that will be understood say 1000's of years from now so archeaologists don't end up digging these sites when their institutional knowledge vanishes (we know how this expt worked out for Pyramids). And there was a discussion about tectonic plates moving in CA region and I wondered if we will develop the technology to get down there and grease the plates so they slide smoothly and more harmlessly. Scientists at that table liked at me like what is this Engineer doing here.

Finally, organizational issues. There was a powerful presentation from Indo-US Science and Technology Forum (IUSSTF) on bilateral collaborations between India and US. NAS and Kavli Foundation seem to be doing an excellent job of Frontiers meetings. A couple of suggestions:

• Have a blogger at each of these meetings to disseminate informal description of these talks to the larger audience.
• Kavli Foundation seems to be supporting research in Sciences with awards. Start an award for CS. Start an award for CS. Start an award for CS.
  

Finally, Raissa D' Souza and Edward Patte co-chaired the meeting and did the hard job of organizing it . As I discovered, Raissa -- a broad thinker and researcher --- and I are less than 2 hops away via multiple paths related to work!

On the left, chemical formula I havent seen in a while. Below, the tandem ants.

ps: It was fun to meet physicist Jocelyn Monroe who was looking for a billion hours of computing for free. Here it is.

Simons Science Series Talk: Jon Kleinberg

Before taxes were due, Jon Kleinberg spoke at the Simons Science Series on Social Networks. Quite simply, Jon is the Carl Sagan of the Computer Science Universe. He switched between

• science (Quoted Pauli that one could not even think of a wrong model; Martian's question, Is there life on Earth?),
  
• technologies (karate clubs, wiki, epinions, flickr, emails, and of course facebook and gmail),
  
• theories (structural social theories of balance, peer factors in social evaluations: people have negative opinion of peoplewhose level of achievement is similar to theirs),
  
• theoretical CS (random graph modeling of dynamics, convergence analysis of local phenomena, rank 1 matrix encoded in data, random walk that returns to origin),
  
• some truly fun experiments with data ( use flicker photo locations and abstract out a world map of population centers -- you can find the line outside a sushi restaurant if you used facebook data!; what is the prob that you answer a mail within X min?), and
  
• great oneliners (on social networks, everyone gets a line; incredible richness of graphs; in 2000 at IBM we wondered if only we had a website where people will register and tell us where they live, and how long will it take for that to happen; we prefer facebook to enemybook; software knows you better than you do; we live in networks)
  

to enthrall the entire audience, and inspire them to step out of the talk, and start asking questions about the native social world online and around them, and use whatever tools --- percolation, statistics, graphs --- they have handy and start digging.

Some morsels from the feast: gmail could tell you when you are tired and not being productive; same place and same time flicker upload is sufficient correlation to associate the different uploaders tightly -- like they are a family or belong to the same conference; is there a balance theory like enemy-of-a-friend-is an-enemy for asymmetric networks?; how long will controversial topics exposed via say twitter hashtags survive?; etc.

Also, he made wiki -- at least the wiki administration that "grants tenure" to those with > = 10k edits after a vote on their portfolio -- sound cool. Finally, it is also cool to see Jon interact with many communities smoothly, go from talking about ergodicity to "like spin systems but spins here are on edges; gauge theory in physics, problem of removing frustrations".

NSF Workshop on Algorithms In The Field: Request Ideas

NSF Workshop on Algorithms In The Field (W8F) will assemble CSists from networking, databases, social networks, data mining, machine learning, graphics/vision/geometry/robotics and those from algorithms and theoretical computer science. It is a wider collection than you'd find in most meetings yet small enough to discuss or even debate.

Many of you are native experts in 8F. Many of you have first hand experience of being algorithms researchers and working with others on a common challenge or vice versa. Also, many of you have thought about frustrations and triumphs, in collaborations that involve algorithms/theory researchers.

This is a call for help. Please email any issues you think we should explore; any questions you would like any particular community to address or any pair of communities to debate, or for a panel to ponder; any ideas for how to organize this workshop, etc. Here are some potential examples (disclaimer: this list is limited by my background and lack of imagination):

• [Technical] Is recommendation only a machine learning problem? What problem would be most interesting to database/networking/machine learning/ folks if we could do a smoothed analysis? Is there a networking analysis for which streaming algorithm is the bottleneck? What problems in database engine is a bottleneck for which databases will be willing to live with approximation? Is there a uber version of nearest neighbors of interest to vision/machine learning/data mining? Is there a structural theory of social behavior that can be captured by graph theory? Can we prove via reductions that problems in these areas are related to each other (at a deeper level than by formulating common data structure/graph/scheduling problems)? Is there an applied area where scheduling is the bottleneck? Are there key problems in massive data analysis that needs efficient MapReduce algorithms? If algorithmic complexity was not the bottleneck, what will be main problems in vision, data mining, machine learning systems?
  
• [Organization] If there is an annual conf on 8F, what advice will you provide? Besides developing metrics, what questions about 8F can we that will be helpful to the Kanellakis awards committee. Propose new grand challenges in 8F that requires algorithms folks and others to work together to accomplish.
  
• [Education] How should we train students in 8F? What algorithms area do researchers in databases, networking, machine learning, vision, graphics etc. wish they (or their students) knew better? What format will be a summer school take that aims at teaching algorithms/theory students about the various fields? What will be a "field trip" in CS (akin to say in Biology)?
  

Google Technical Events Blog

Google has presence in many technical events, from academic conferences to hackathons, developer conferences and others, and their presence is of interest to the global technical and academic community. For example, this should be of interest to graduate students looking for travel support, meeting Engineers and Researchers from Google, or pursuing jobs, etc. There is a nice blog that shows both upcoming events as well as commentary on events with Google presence. Enjoy!! (I learned about the mobility data contest from this blog).

More CS Humor

One of my students in the algorithms class recently used "overbound" and "underbound" for O and \Omega. Apt, isnt it?

In the past, people's last names used to be their profession, Baker, Fisher, Kempe, etc. Soon we will have John Programmer?

Natl Acad of Sc Talk on Streams: Suggestions?

I will be giving a talk on challenges in data stream processing at the NAS Kavli Frontiers of Science meeting in a couple of weeks in Irvine, CA. These meetings tend to bring in very bright researchers from many different areas in Science and Engg. They say,

"The success of this symposium largely rests on your ability to speak effectively to an interdisciplinary audience. Your task is to introduce top young scientists from many fields to the excitement of your field in general and your own research in particular. Your presentation should not be a review of your field; rather you should (1) clearly delineate the problem that you are trying to solve, (2) place that problem and your research in the larger context of your field and other fields, and (3) explain its significance. In general, your talk should be geared to ignite the interest of scientists outside your field, to communicate why the topic of the session is an exciting “frontier” and to provide the specifics necessary to set the stage for the general discussion after your talk or at the end of your session."

There is a long discussion following these talks. If you think of an interesting way to present data streams research (or passionately believe in some outstanding challenge, or think we should explore connections to some areas in Science, or have a new/old result that you think should be of special interest in this discussion) please send me ideas/suggestions, I can use a new angle.

Headline Humor

Just saw a headline: The ACM Awards emphasize music (this is CS humor.)

Some general newspaper headline/classifieds humor here.

NSF Workshop on Algorithms In The Field (May 16--18)

Algorithms research can take many forms from fundamental algorithms theory, to applied algorithms or even algorithms engineering. There is yet another (perhaps distinct) type of algorithms research, one in which researchers from different communities --- including algorithms and systems --- work together “in the field”, developing the system and theory jointly --- constantly informing each other and inventing in their respective areas --- without needing to make independent research threads meet ex post.

Thanks to NSF folks' initiative, there will be a workshop to explore this theme. Researchers from networking, databases, data mining, statistics, machine learning, social networks, parallel systems, graphics, robotics, massive data and others will participate in the workshop together with algorithms/theory researchers. This will be held at DIMACS, May 16--18. More details here.

Chances are many of you have ideas how Algorithms In The Field (8F, acronymize that!) is done, what topics should be covered, how this workshop should be structured, etc. Please email any suggestions. Your input will be much appreciated, if this workshop succeeds, our communities will benefit. Also, if students/postdocs/visitors in the neighborhood want to be at the workshop, please email.

Theory of Computation as a Lens on the Sciences: Berkeley Conference

Theory of Computation as a Lens on the Sciences
University of California, Berkeley, May 7-8, 2011

The conference will explore the theme that many processes in the physical, biological, engineering and social sciences involve information processing at a fundamental level and can be studied through computational models. A conference held in Berkeley in May, 2002 helped crystallize this theme as a promising direction of research, and this second conference will highlight the impact of the computational lens on areas such as quantum information science, statistical physics, social networks, economics and game theory, genetics, molecular biology, evolutionary biology, cognitive science, mathematics, statistics and machine learning. Featured Speakers:

• Professor Leslie Valiant, Harvard University, Evolution as a Form of Learning
• Professor Ehud Kalai, Northwestern University, Robustness and Complexity in Games
• Professor Christos Papadimitriou, UC Berkeley, Algorithms, Games, and the Internet
• Professor Michael Kearns, Univ of Pennsylvania, Social Networks, Strategic Behavior and Computation
• Professor Mark Newman, University of Michigan, Structure and Dynamics of Networks in the Real World
• Professor Michael Jordan, UC Berkeley, On Joint Inference of Phylogeny and Alignment
• Professor David Haussler, UC Santa Cruz, Cancer Genomics
• Professor Andrea Montanari, Stanford, Statistical Mechanics through the Lens of Computation
• Professor Daniel Fisher, Stanford, Modeling Evolutionary Dynamics: Problems and Prospects
• Dr. Jonathan Oppenheim, University of Cambridge, Computer Science as a Lens on Quantum Theory
• Professor Umesh Vazirani, UC Berkeley, How does Quantum Mechanics Scale?
• Professor Lior Pachter, UC Berkeley, A Computational Approach to Discovery in Biology
• Professor Tandy Warnow, UT, Austin, Ultra-Large Phylogenetic Estimation
• Professor Sebastien Roch, UCLA, Large Phylogenies from Short Sequences: Recent Theoretical Insights

Please register for this conference here. There is no charge for registration. If you have questions, please contact Heather Levien, tel: 15106423497.