Algorithm Conferences

I have had a browse of some theoretical computer science conferences. A list of the conferences was given here.

The FOCS 2011 conference is scheduled for October so no list of submitted abstracts was available today. The list of abstracts for the 2009 conferences was unavailable (broken link). From the '11 homepage, they highlight papers in many aspects of theoretical computer science from algorithms and data structures, complexity, networks, crypto, etc.

STOC 2011 ended about a week ago and consists of papers similar in topic to FOCS. There are many papers on graph problems, and on approximation algorithms for problems. A paper on data streams was in the fast estimation of moments (Kane, Nelson, Porat & Woodruff). Problems based on graphs seem to dominate the list of papers here, specifically multicut [pdf].

SODA (sponsored by SIAM) has many pure maths (combinatorics, algebra, number theory, graphs, metric spaces, etc) papers as well as computer science. Their last conference was in January 2011. The about page highlights their goal to link mathematics with other sciences. The  papers again have graph problems, but also many are on approximations or solutions to mathematical problems.

ALGO 2011 is scheduled for September and is a collection of conferences. WABI seem to have a lot of genetic/biological papers (given also by their name!). IPEC (2010) had a lot on complexity. ESA didn't have a list of papers for this year, but in 2010 did a joint conference with WABI. The ESA topic list includes topics as detailed in FOCS/STOC.

Briefly, SPAA deals with parallelism in algorithms, IPCO with graphs, sets, etc; and COLT with machine learning.


In conclusion, approximation algorithms are prolific throughout all conferences, but there is also seems to be a  lot of current interest in graph problems.

Streaming Algorithm Lecture Notes

I begin with a brief read of some lecture notes about Streaming Algorithms. The links to the documents are also added for completeness. I have only read the first couple of chapters of these to get an idea into thought processes and styles in this field.

Lecture Notes by Muthu Muthukrishna
http://www.cs.mcgill.ca/~denis/notes09.pdf

Talks initially about some streaming algorithms; estimating the minimum frequency item in a stream. Hash functions seem prevalent in this field so will need some work, and also some probability in the analysis of bounds. Will need to do a bit of work on these two aspects (particularly hashing) if I continue down this path.
Then talks about counting elements in a stream, again using hashing. Very good.

Lecture Notes from Dartmouth
http://www.cs.dartmouth.edu/~ac/Teach/CS85-Fall09/Notes/lecnotes.pdf

Gives a more precise model of computation for streaming algorithms.

Lecture from Stanford
http://theory.stanford.edu/~rajeev/cs361.html#read-massive

Starts with naive approach, and discusses memory issues when you stream data. The lecture notes above explain this all a bit better really, but I read it so the link is here.

Lectures (and paper) from Wisconsin
http://pages.cs.wisc.edu/~shuchi/courses/787-F07/

First of these lectures (17) just recaps briefly on model including frequency moments, and then moves to counting distinct elements (continued in Lecture 18). Median of means to take result after many trials.
Paper is the book below.

Book by S. Muthukrishnan
http://scholar.google.co.uk/scholar?hl=en&q=Data+Streams%3A+Algorithms+and+Applications&btnG=Search&as_sdt=0%2C5&as_ylo=&as_vis=1

Applications and motivations for the thoughts.

The beginnings

Here the project begins. I have a supervisor, so step one is complete. Now to pick the project focus over the next few weeks.

Initially I need to find and read lecture notes on Streaming Algorithms and also look at some of the Algorithms conferences found here: http://www.cs.tau.ac.il/~iftgam/eventlist.htm