You are currently browsing the category archive for the ‘Uncategorized’ category.
Ely asked me to remind everyone that the deadline for the 26th Annual Symposium on Combinatorial Pattern Matching is fast approaching. You have until 2nd February to match your combinatorial pattern.
- Michael’s looking for a post doc position. Michael has done some really nice work in the field of data stream algorithms including designing the first graph algorithms for the sliding window model; analyzing space-sample trade-offs in stochastic streams; estimating stream periodicity via linear sketches; and improving the best known results for approximate maximum weighted matching (to appear). Prior to this, he worked in descriptive complexity and built a system for automatically finding reductions between problems. Michael gives great lectures and also has a particular strength when it comes to helping and mentoring more junior students. Which brings me to…
- Dan’s applying to grad school. Dan worked with Michael on the above graph algorithms and separately has a really neat result on sketching the earth-mover distance on graph metrics. Of particular note is that he has just been declared:
This award “recognizes undergraduate students in North American colleges and universities who show outstanding research potential in an area of computing research.” Except, in Dan’s case, I’d skip the word “potential”.
- I’m looking for new students! If you’re applying to grad school and are interested in data stream algorithms, or algorithms in general, please consider submitting your application to UMass Amherst. Details are here and our deadline is December 15th. For more details about my research interests see my website. And check-out the UMass Theory Group.
Email me if you’d like to follow-up on any of the above points.
New Blog: Eric Blais, Sourav Chakraborty, and C. Seshadhri have started a new blog on property testing at http://ptreview.sublinear.info/. Also check out Moritz Hardt’s newish blog at http://mrtz.org/blog/.
This Blog: Things have been quieter at the polylogblog over the last few months but this will soon be rectified. This semester, I’m visiting the Simons Institute for the Theory of Computing in Berkeley. The program on Theoretical Foundations of Big Data Analysis has been great so far and the second workshop starts tomorrow: tune in live here for everything you’ve always wanted to know about “Succinct Data Representations and Applications”. However, with so much happening, I’ve been rather derelict in my blogging duties. Fortunately, numerous other bloggers have picked up the slack:
- Moritz Hardt: http://mrtz.org/blog/what-should-a-theory-of-big-data-do/
- Sebastian Bubeck: https://blogs.princeton.edu/imabandit/2013/09/02/first-week-of-activity-at-the-simons-institute/
- Muthu Muthukrishnan: http://mysliceofpizza.blogspot.com/2013/09/simons-big-data-boot-camp.html
- Suresh Venkatasubramanian: http://geomblog.blogspot.com/2013/08/on-theory-of-big-data.html and this, and that.
- Gil Kalai: http://gilkalai.wordpress.com/2013/09/09/simonsucberkeley/
Efficient and effective transmission, storage, and retrieval of information on a large-scale are among the core technical problems in the modern digital revolution. The massive volume of data necessitates the quest for mathematical and algorithmic methods for efficiently describing, summarizing, synthesizing, and, increasingly more critical, deciding when and how to discard data before storing or transmitting it. Such methods have been developed in two areas: coding theory, and sparse approximation (SA) (and its variants called compressive sensing (CS) and streaming algorithms).
Coding theory and computational complexity are both well established fields that enjoy fruitful interactions with one another. On the other hand, while significant progress on the SA/CS problem has been made, much of that progress is concentrated on the feasibility of the problems, including a number of algorithmic innovations that leverage coding theory techniques, but a systematic computational complexity treatment of these problems is sorely lacking. The workshop organizers aim to develop a general computational theory of SA and CS (as well as related areas such as group testing) and its relationship to coding theory. This goal can be achieved only by bringing together researchers from a variety of areas.
The Coding, Complexity and Sparsity workshop (SPARC 13) will be held in Ann Arbor, MI on Aug 5-7.
These will be hour-long lectures designed to give students an introduction to coding theory, complexity theory/pseudo-randomness, and compressive sensing/streaming algorithms. We will have a poster session during the workshop and everyone is welcome to bring a poster but graduate students and postdocs are especially encouraged to give a poster presentation.
This is the third incarnation of the workshop and the previous two workshops were also held in Ann Arbor in August of 2011 and 2012.
- Jin Yi Cai (University of Wisconsin, Madison)
- Shafi Goldwasser (MIT)
- Piotr Indyk (MIT)
- Swastik Kopparty (Rutgers University)
- Dick Lipton (Georgia Tech)
- Andrew McGregor (University of Massachusetts, Amherst)
- Raghu Meka (IAS)
- Jelani Nelson (Harvard)
- Eric Price (MIT)
- Christopher Ré (University of Wisconsin, Madison)
- Shubhangi Saraf (Rutgers University)
- Suresh Venkatasubramanian (University of Utah)
- David Woodruff (IBM)
- Mary Wootters (Michigan)
- Shuheng Zhou (Michigan)
We have some funding for graduate students and postdocs with preference given to those who will be presenting posters. For registration and other details, please look at the workshop webpage.
A guest post from Krzysztof Onak:
A few recent workshops on sublinear algorithms compiled lists of open problems suggested by participants. During the last of them, in July in Dortmund, we realized that it would be great to have a single repository with all those problems. After followup discussions (with Alex Andoni, Piotr Indyk, and Andrew McGregor), we created a wiki page at http://sublinear.info/. Currently, it only contains open problems from the aforementioned workshops, but we invite submissions of inspiring problems from all areas of sublinear algorithms (sublinear time, sublinear space, etc.). Additionally, we want to compile a list of books, surveys, lecture notes, and slides that can be useful for learning about different areas of sublinear algorithms. We hope that this wiki will not serve only spambots, which have already been raiding it for a while, but it will also be a great source of inspiration for the whole community.
After a very successful hiring season last year, the department is now focusing on hiring in theory, NLP, robotics, and vision (that’s four separate searches rather than one extreme interdisciplinary position). So please apply! The official ad is here and note that, unlike previous years, we’re able to hire in theory at either the assistant or associate level. We’ll start reviewing applications December 3.
As promised, here are the slides from the STOC Workshop on Algorithms for Distributed and Streaming Data. The workshop was standing-room only so here’s your chance to review the slides while sitting down. More generally, all the workshops seemed to be a great success and I’m happy to see that the experiment will be repeated at FOCS. Deadline for proposals is 20 June.
- Sergei Vassilvitskii, Google: Distributed and Parallel Models
- Andrew McGregor, UMass Amherst: Data Streams and Linear Sketches
- John Langford, Microsoft Research: Fun Machine Learning Problems on Big Data
- Piotr Indyk, MIT: CS on CS: Computer Science Insights into Compressive Sensing (and vice versa)
- Ashish Goel, Stanford and Twitter: Challenges in Industry and Education
Thanks again to the speakers and everyone who came along.
While on the topic of STOC, I also wanted to mention a STOC workshop on “Algorithms for Distributed and Streaming Data” that will hopefully be of interest. It will take place Saturday afternoon, 19th May in NYU. The schedule can be found here.
So here’s the pitch: At this point it’s readily apparent that big data has become big news (e.g., see here and here). But what does this mean for the STOC/FOCS/SODA community? What are the algorithmic problems we could be solving? What are the appropriate computational models? Are there opportunities for industrial impact? What should we be teaching our undergraduate and graduate students? To address the relevant topics, we’ve lined-up a great set of speakers including Sergei Vassilvitskii, John Langford, Piotr Indyk, and Ashish Goel. Hope to see you there.