Algorithms in the Field: The PI Meeting

Algorithms in the Field is a program of Algorithms + Other CS researchers working jointly "in the field" of problems. Here is a history of development of this program. Recently I attended the PI meeting for this NSF program:

• Nearly all the talks were interesting, genuinely targeting the middle ground. They didnt go into the rabbit holes of describing the minute technical improvements in approximation ratios or the 6 different data sets they had to cull to compare 4 different algorithms. Each speaker made an effort to cover the field area (special hardware like memristors, SDNs, wireless receivers etc) and also provide an overview of the algorithmic challenges. This was refreshing. 
• There were some very interesting examples of the joint research: Ashish Goel spoke about societal decision making and examples such as budget decisions, viewed as collaborative convex programs; Piotr Indyk, ever-wise with his choices, spoke about the wireless transmitter/receiver setting for most part of his talk, really communicating the nature of the "field" before quickly connecting it to sparse Fourier estimation problems; Vyas Sekar spoke about formulating SDN routing policies using path constraints and posed some open problems, which Bobby Kleinberg who went just after, proceeded to solve at least partially, with his work. This shows (a) Algorithms in the Field research can happen in real time and (b) Dont speak before Bobby and pose open problems. 

ps: Sucheta Soundarajan and Martin Farach-Colton organized the meeting and did an excellent call to include graduate students/postdocs in the invite, graduate students/postdocs being the glue between professors and conduits for communication. 

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.

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)?
  

Algorithms in The Field (Update)

Some updates:

• Algorithms in The Field continues to be in focus. The new call from the Algorithmic Foundations division of NSF has it.
• Thanks to Tanya for the tip, there is a center emphasizing "field academics" with an interesting graphic.

People ask me about algorithms in the field, and I say, "it is getting theory and applied researchers working together so early that you can not tell what came first, friends or facebook". :)

On Compression

Compression is a research area with many branches. I will focus on lossless compression; lossy compression has a huge history with its recent renaissance thanks to compressed sensing, not-too-recent resurgence due to wavelets for image and video standards, and other constant hums.

In lossless compression, there was the early pioneering work of Lempel-Ziv (LZ) in 70's. Since then there have been various extensions: Ziv worked on extending the"context" into various forms of universality; LZ method got applied to objects other than strings, from file versions to tables, graphs, web, grammars, etc; heuristics were developed using different chunking techniques or suitable dictionaries; and so on. But the general consensus when you spoke to people is that at the highest level, compression involved replacing copies of an object with references to a single copy, and you can perhaps eke out some small constant factor tradeoffs, but no further.

Are there major breakthroughs in compression? Doubtless one breakthrough has been the Burrows-Wheeler (BW) approach. The first time I saw it was in mid 90's and it was very unusual, almost magical. I couldnt tell how far this method will go. Now, not only is this a commonly used compression scheme based on BW (bzip), but we have clear theoretical analysis of its compression ratio which is asymptotically better than LZ, and interestingly, it has been used for indexing and made available in far more applications than LZ or simply compression. That is a good story of Algorithms in the Field.

I am working on next steps following the last year's workshop on Algorithms in the Field (8F), and to determine if there are other brewing new ideas in compression.

Algorithms in the Field (8F)

NSF announces a new funding program for Algorithms in the Field. Deadline is Feb 9, 2015.  One of the metrics in Algorithms community is the ultimate use of our algorithms, ``use" being broadly interpreted, and this often needs us to go more than halfway to meet other communities. This program is an opportunity to codify the process some. When one does meet the other communities, almost always it leads to new theories and algorithms, and more than pays for the journey. I hope you will respond.

Here is more info on the workshop we organized 2 years ago. The videos of the talks are here.

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?

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

Algorithmicist in the Field: Google+ Weekly

Labor day weekend is a good landmark, interns are gone and stalled projects in research labs will restart; students are back at universities and new semester will begin; summer will end and fall will burst out; it is time for last hikes and new beginnings, etc.

I will be on video hangout on Google+ every week, Wednesdays 9 AM -- 10 AM EDT (NY Time). Anyone can join me on the hangout. The idea is, we can talk algorithms in theory, systems, field or otherwise; we can talk problems, solutions, patents, techniques or angst about the state of the world; we can look ahead and seek directions or look behind and summarize; we can talk courses, careers, conferences or about the cult of research; we can be students, professors, researchers, and be in any part of the world.

What you need to do, if you want to join me in my hangout:

• Have a google+ account. If you dont have one, get an invite or email me at muthubyshance@gmail.com.
  
• Go to Google+, add me (muthubyshance) to your circle and join my hangout anytime during the period specified above. If you cant find me or have problems, email me at muthubyshance@gmail.com. You will also get updates from me on google+ if I am in one of your circles.
  

This is obviously an experiment, but for some time, I wanted a channel to have real time conversation about our issues in addition to the existing channels of the single speaker on the pulpit mode (blogs/lectures) or the post and seek mode (of cstheory.stackexchange.com) or hunt and find the proper subset of people mode (of live conferences).

ps: This will start on Wed, Sept 7.

CFP: MLOAD 10

NIPS 2010 Workshop on Machine Learning in Online ADvertising (MLOAD), December 10, 2010, Whistler, B.C. Canada
http://research.microsoft.com/~mload-2010

IMPORTANT DATES: Submission deadline: Oct. 23, 2010 Notification of Acceptance: Nov. 11, 2010 Camera ready: Nov. 22, 2010 Workshop Date: Dec. 10, 2010.

Overview: Online advertising, a form of advertising that utilizes the Internet and World Wide Web to deliver marketing messages and attract customers, has seen exponential growth since its inception over 15 years ago, resulting in a $65 billion market worldwide in 2008; it has been pivotal to the success of the World Wide Web. This success has arisen largely from the transformation of the advertising industry from a low-tech, human intensive, “Mad Men” (ref. HBO TV Series) way of doing work (that were common place for much of the 20th century and the early days of online advertising) to highly optimized, mathematical, machine learning-centric processes (some of which have been adapted from Wall Street) that form the backbone of many current online advertising systems.

The dramatic growth of online advertising poses great challenges to the machine learning research community and calls for new technologies to be developed. Online advertising is a complex problem, especially from machine learning point of view. It contains multiple parties (i.e., advertisers, users, publishers, and ad platforms such as ad exchanges), which interact with each other harmoniously but exhibit a conflict of interest when it comes to risk and revenue objectives. It is highly dynamic in terms of the rapid change of user information needs, non-stationary bids of advertisers, and the frequent modifications of ads campaigns. It is very large scale, with billions of keywords, tens of millions of ads, billions of users, millions of advertisers where events such as clicks and actions can be extremely rare. In addition, the field lies at intersection of machine learning, economics, optimization, distributed systems and information science all very advanced and complex fields in their own right. For such a complex problem, conventional machine learning technologies and evaluation methodologies are not be sufficient, and the development of new algorithms and theories is sorely needed.

The goal of this workshop is to overview the state of the art in online advertising, and to discuss future directions and challenges in research and development, from a machine learning point of view. We expect the workshop to help develop a community of researchers who are interested in this area, and yield future collaboration and exchanges.

Algorithms in the Field (8F)

I updated the Algorithms in the Field (8F) site with links to videos, reports, slides, followup meetings etc. This vision continues to be compelling for me and many others. 

Compressed Sensing

There is some excitement about what is called Compressed Sensing (CS) in signal processing, harmonic analysis and applied math.

David Donoho came up with this question that since signals were going to be approximated anyway (using few coefficients in some suitable basis), can one just make a small number of measurements rather than measuring at every point? He showed how to do it. Did this have a precursor? Indeed it did, in a kingdom by the sea (gratuitous reference to Nabokov). Not an exact precursor, but some related results were known in learning theory, streaming algorithms, etc. Donoho's twist is interesting and has generated a lot of research the past few years. Check out the CS site for the early papers by Candes, Tao (yes, field medalist Terence Tao), Romberg, Ruselson, Vershynin et al, and the other papers since.

I was lucky to get to a meeting with Ingrid Daubechies, Ron DeVore, Anna Gilbert and Martin Strauss (thanks to a NSF FRG) where we tried to figure out CS and its relationship to other problems. In particular, I am indebted to Ron for gamely explaining elements of the CS conditions in Donoho's paper and the proofs, on the white board.

Recently, I went to the Allerton conference (my first, it IS in the middle of nowhere, but it was a reassuringly warm math conf) to speak about algorithmic issues in compressed sensing. I eked out some research time to write down a few results I have been mulling over, and some new research directions in compressed sensing (in particular, what I call functional compressed sensing; the distributed, continous version of compressed sensing and its intriguing connection to the classical Slepian-Wolf). Check out a copy of the paper here. I hope to refine this over time, so comments are welcome.

NSF W8F: Last heave

Thanks to efforts of many, and mainly thanks to those who accepted our invitation to come out and brainstorm (without giving a talk, and with minimal information on what the workshop will be. my sincere thanks to them and this is an IOU, collect when you need it), we are near the beginning of the NSF Workshop on Algorithms In The Field (W8F). The webpage has been updated with the list of attendees, schedule, abstracts, breakout meeting rooms, etc.

We have a limited number of talks. These will frame individual issues, large themes, and set us for our discussions. Check out the abstracts, some truly exciting talks on the menu, from FOCS to Education, right things to cheap wins!

We have a fantastic set of attendees. Now all that remains is to bring an open mind, discuss and find exciting ideas, directions, collaborations. Weather is rainy and promises to be that way M-W. We will be away from grading, teaching and admin (in case of academics) and bosses, quarters, or deliverables (in other cases), so let us have fun, solve some problems, or at least pose them.

NSF Workshop on Algorithms In The Field (8F) Contd

The workshop 8F is in the final lap of preparations. The schedule is up, breakout groups have been announced, etc. Time for some humor. Urban dictionary tells me: 8F is hexadecimal term for 143 which is known as the numeric term for "I Love You". I postulate that every word is within four degrees of separation from love, or sex. Let us say this is the 8F postulate.

CFP for HCOMP 2016, deadline soon

The deadline for AAAI Conference on Human Computation (HCOMP) 2016 is nearly here.  It is an application domain where the depth and reasoning of theory CS folks might find unexpectedly rich outlet. You will see our folks deeply involved in organizing the conference including Arpita G, Sid S, Santosh V,  Jenn W. V, and others. 

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

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.

......

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.

Full CFP is here. May 31, 2016: Abstracts (for Full Papers) due. June 7, 2016: Full Papers due. 

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

DIMACS seeks an Associate Director

DIMACS continues to thrive, with its current Director Rebecca Wright, finding, following and leading the flow of Theoretical Computer Science as it meanders through ever new application areas and burrows to new foundations. DIMACS is looking for an Associate Director.

Short Blurb: 

The DIMACS Center at Rutgers University (dimacs.rutgers.edu) is seeking an Associate Director. DIMACS facilitates research, education, and outreach in discrete mathematics, computer science theory, algorithms, mathematical and statistical methods, and their applications..  The Associate Director is expected to play a leadership role in planning, developing, and running DIMACS activities and programs, including setting new directions.  A PhD in computer science, mathematics, operations research, statistics, or a related field is preferred. Applicants with a doctorate will be considered for Associate Director with a non-tenure-track calendar-year research faculty appointment at Rutgers. Highly qualified applicants without a doctorate will be considered for a staff appointment as Assistant Director. For more details, visit dimacs.rutgers.edu/AssociateDirector.