[Lowerbounds, Upperbounds]

Algorithms are everywhere.

http://www.cs50.cs.cmu.edu/

This April, from 19 Wed to 22 Sat, will be our department’s celebration of the 50-year anniversary of Computer Science at Carnegie Mellon. Now many of us know that our department is old but probably not that old… so how could that be possible?

Late spring of 2006 will mark the 50th anniversary of computer science research and education at Carnegie Mellon: the University’s first computer, an IBM 650, was delivered to the basement of the business school in July 1956. At that time, Herb Simon recruited Allen Newell and Alan Perlis to help found a center of computer science activity that established Carnegie Mellon as one of the premier institutions for computer science in the world.

I did ask around… very few of us have seen that IBM 650. :P

As noted in the previous post about MillerFest, there are a lot of things going on during that week. Let me show you the full schedule because the short list below will surely miss something.

First, I note that the Language Technology Institute and the Human Computer Interaction Institute will both be celebrating their anniversaries. So there will be a lot of seminars going on. Lots.

There is also another workshop in honor of Ed Clarke. I TA’ed for Ed once and he’s absolutely one of the finest professors to work with. And I can tell you that while Ed did not invent the Internet, he did start the whole field of using model checking in formal verification with his student Allen Emerson back in 1981. You would think that Finite Automata is “easy”. Hmm, I did have that thought before I came to CMU but I started to think again once I met Ed.

There is also the Women@SCS Outreach Roadshow, as well as the always-exciting tour to Entertainment Technology Center. (I learn something new every time I go to ETC. So go to the tour!)

Besides all these, we also have two celebrations for Sharon Burks and Mark Stehlik for their service to the department. To me, Sharon is to our department what the Oracle is to the Matrix. She literally knows everything!

Finally, there is no shortage of luminary speakers for the general CS50 event. To pick two that are more familiar to the Theory community, we have Leslie Valiant and Charles Leiserson. Time to meet my Grandpa.

Oh, and to show you that we are really a CS department, we have a PGP Key Signing Event. :P (I want to give exactly 42 cents to whoever came up with that idea.)

Now you may think that everything happens in the SCS buildings that week. Well, turns out CMU has an annual event called the Spring Carnival, which starts right with CS50. Tons of booths, games, food and rides. All outdoors!

I already ordered extra camera batteries for that weekend. The question is: can I really perform superposition to make myself “present” in all these events, many of which are parallel? Or perhaps the photons may find their way to register their effect on my camera sensor without my being “present” in the room? :P

P.S. To show you how digital photography can make it hard for me to fall asleep at night: with my 2-year-old Nikon D70, each photo will “cost” me about 9MB of storage without counting backup storage. (6MB RAW + 3MB JPG) And if I really upgrade to a Nikon D200, 10+4 MB. Now if you think that harddisk storage is cheap (definitely not as cheap when you do it robustly with RAID and such)… No, I don’t want to think about the time it takes to postprocess the photos. I guess I would keep my D70 for the moment.

(Maverick’s note: There are just about a million events occurring on campus that weekend during CS50. See my next post.)

You’re Invited to Celebrate Gary Miller’s 60th Birthday at MillerFest 2006!

April 19-20, 2006
Carnegie Mellon University, Pittsburgh, PA

We are celebrating Gary Miller’s 60th birthday this spring with a banquet and workshop. The banquet will be held Wednesday evening, April 19th, at the Pittsburgh Athletic Association, with the workshop occurring on Carnegie Mellon’s campus the following day. The workshop will feature presentations related to Professor Miller’s research achievements, including computational number theory, randomized algorithms, parallel algorithms, and scientific computing.

For more information, please see the workshop web site:
http://www.aladdin.cs.cmu.edu/workshops/millerfest/

** REGISTRATION IS REQUIRED **

There is no fee to attend the workshop if you register by Monday, April 3rd. There is small fee to attend the banquet, which promises to be an enjoyable evening featuring reminiscences about the life and career of Professor Miller.

** HOTEL DEADLINE EXTENDED TO APRIL 3RD **

Out-of-town visitors should make their hotel reservations by Monday, April 3rd,* to take advantage of the pre-negotiated workshop rate of \$105 per night (\$119.70 including taxes) at the Holiday Inn near campus. To make your reservations, call the the Holiday Inn (100 Lytton Avenue, Pittsburgh, PA 15213) at 412-682-6200 and be sure to ask for the ALADDIN Workshop rate.

You may also be interested to know that MillerFest is being held in conjunction with CS50, which celebrates fifty years of computer science at Carnegie Mellon. Please see http://www.cs50.cs.cmu.edu/ for a complete schedule of CS50 events.

We look forward to seeing you at MillerFest!

Susan Hrishenko, ALADDIN Center Assistant Director
for MillerFest organizers Guy Blelloch, Alan Frieze, and Shanghua Teng

A relative-error CUR decomposition for matrices and its data applications

Michael W. Mahoney
Yahoo Research

4/18 11am
Wean 8220

Much recent work in the Theoretical Computer Science, Linear Algebra, and Machine Learning has considered matrix decompositions of the following form: given an m-by-n matrix A, decompose it as a product of three matrices, C, U, and R, where C consists of a few (typically a constant number of) columns of A, R consists of a few (typically a constant number of) rows of A, and U is a small carefully constructed matrix that guarantees that the product CUR is “close” to A. Applications of such decompositions include the computation of compressed “sketches” for large matrices in a pass-efficient manner, matrix reconstruction, speeding up kernel-based statistical learning computations, sparsity-preservation in low-rank approximations, and improved interpretability of data analysis methods. In this talk we shall discuss various choices for the matrices C, U, and R that are appropriate in different application domains. The main result will be an algorithm that computes matrices C, U, and R such that the (Frobenius) norm of the error matrix A - CUR is almost minimal. We will also discuss applications of this algorithm (and related heuristics) in the bioinformatics of human genetics, in recommendation system analysis, and in medical imaging.

Speaker: Abraham Flaxman

Time: Monday 10:30-11:30 AM

Place: Wean 5320

Title: Average-case analysis for combinatorial problems

Abstract:

This thesis considers the average case analysis of algorithms, focusing primarially on NP-hard combinatorial optimization problems. It contains a catalog of distributions frequently used in average-case analysis and collection of mathematical tools that have proven useful in studying these distributions. The bulk of the thesis consists of case-studies in average-case analysis of algorithms, where algorithms for 3-SAT, Subset Sum, Strong Connectivity, Stochastic Minimum Spanning Tree, and Uncapacitated Facility Location are analyzed on random instances.