This is my response to a recent email from a student, who shall of course remain anonymous. I've added a few links and comments.
While doing some web browsing on quantum algorithms, I stumbled upon your page. I noticed that you boast that you have the lowest undergraduate GPA of any professor you have ever met. I am an undergraduate computer science student who dreams of one day obtaining a PhD, but my GPA is less than impressive. If you have a moment, I would love to know how you were able to convince graduate admissions and more importantly, yourself, that you were up to the task of getting a PhD.
Hard work, arrogance, and pure dumb luck.
I always wanted to go to grad school, but I was a LAZY undergrad. I spent more time hacking on independent programming projects than on homework or studying for exams. Anything I found boring, I spent no time on whatsoever. Usually, by the time final exams rolled around, I was too far behind to catch up. (I'd love to claim that I spent all that time partying, but I was also a geek.) I aced the programming classes (which landed me some student TA jobs), and I did lots of independent study projects, but I bombed everything else. It wasn't that I couldn't understand the material or do the work (at least, if I'd kept up); I just didn't care.
Hey, it worked in high school. I got into college, despite almost failing English and history, because I was years ahead at math.
My senior year in college, a couple of other computer science majors started their own software company. They hired one of my friends; he suggested they hire me (since I was good at programming). That was where I finally learned to work. School was great, because if I didn't get something done by the deadline, I didn't have to do it anymore! Sure, there's a bad grade, but whatever. At the startup, if I didn't get something done by the deadline, I still had to do it -- unless I wanted to pay back all the money they'd given me -- only now my boss and co-workers were pissed off. After a few months of this, it finally sunk in that it would be easier just to do the work. I still have to remind myself of this sometimes.
The first time I applied to grad school, I didn't get in ANYWHERE, despite high GRE scores. I got some rec letters through my undergrad TA jobs, but they all said "he's smart but lazy", which is the kiss of death.
The startup was bought by a bigger company in Silicon Valley (which is now part of Apple, or dead, depending on who you ask). By this point I'd learned to work, but I discovered (or remembered) that I was more interested in doing things RIGHT than doing them NOW, which is bad news in the software industry; this wasn't the place for me. On the other hand, I got a reputation for being able to answer hard math-y questions, and I found myself working through automata theory textbooks for fun while I waited for my program to compile. So I decided to apply again, this time saying I wanted to do software engineering (since I'd been a software engineer for four years) and getting letters from my managers (who said I could work hard) in addition to my old profs (who still remembered me as smart but lazy). I retook the GREs and did well.
This time, I got into a couple of schools. When I arrived at UC Irvine, the director of graduate admissions, a software engineer, told me he had burned some political capital to get me admitted despite my crappy GPA, that he had a lot riding on my success, that he'd gambled on me because of my work experience, and that I'd better not let him down. (That was the last time I ever talked to him. A month later, I realized I didn't want to do software engineering.)
I think one big reason I got in despite my grades was good timing. I started at Irvine in 1990, at the height of the PC software boom/bubble. It was basically a smaller version of the .com boom/bubble ten years later. Most good CS students were getting high-paying programming jobs, or even starting their own companies, right out of college. So fewer people were applying to graduate school, but undergrad demand was up, so more faculty were being hired, so there was more room for grad students. The bar for admissions must have been lower.
Five years later (as I was finishing my PhD), the software bubble burst, and the pendulum swung the other way -- it was hard to find programming jobs, undergrad enrollment dropped, faculty hiring went down, more people applied to grad school. The bar for grad admissions (and faculty jobs) went back up.
The same thing happened later with the .com bust, only this time I saw it from within the grad admission committee. At UIUC, we get many more, and much better, domestic grad school applications now than in previous years. (International applicants are more complicated. Yay 9/11.) Good grades are a MINIMUM requirement for admission now. Most incoming grad students already have some research experience; some of them even have publications. That was not true five years ago.
When grad applications arrive, one of our department secretaries sorts them roughly into three equal piles -- MAYBE, PROBABLY NOT, and NO -- based almost entirely on GPA, weighted by the quality of the school, and GREs. (Penn has a very good program, so this works in your favor.) The committee looks at the MAYBE pile, and if there's still space, maybe the top of the PROBABLY NOT pile. If a student's GPA is under 3.0, it's very likely that no one on the committee will even look at their application. (This is a bit of an oversimplification.)
...UNLESS they're rescued by someone on the faculty. Occasionally, I'll get an email from someone I know at another school asking me to look out for their student's application and pointing out their other strengths: independent study projects, research experience, internships, other employment, etc. If the student looks interesting, I'll pass the note to the committee, asking them to look at the file. That doesn't guarantee that they'll be admitted, of course -- especially if they're in the NO pile -- but if a faculty member really wants to admit someone, it's harder for the committee to say no.
That's how I got into grad school. Someone on the faculty liked my application, despite my bad grades, and they pulled for me.
Free advice is usually worth exactly what you pay for it, but let me offer one concrete suggestion: Talk to faculty in your department who do the things you're most interested in. (Penn's a big department, so you'll have to hunt them down.) If you're good at their subject, tell them you're interested and ask if they can suggest something for you to study further. If you're not so good at their subject, tell them you're interested anyway and ask if they have any suggestions for how to improve. Don't be discouraged if they don't have time; just ask for suggestions for other faculty to talk to. Figure out what you're best at, and do something visible with that!
I hope this helps. Good luck!