renting a place in the bay area

at a grad student social today, i met a new grad student, andre, from iceland. he actually was working in upstate new york for the past few years, and now he's here at berkeley doing systems research. when deciding where to live, andre realized that he wouldn't have time to visit berkeley. so he did all his house-finding online and over the phone. now he's not too happy with his place, or rather his area.

he lives about 30 minutes away from campus in a dodgy area, and actually feels more comfortable in his office than at home. this is a shame -- i think it's really a failure of the department and the graduate division in general that this happened. sure, andre could have asked around more and tried to get more help. but i know of countless people that this has happened to in the bay area. there's got to be somewhere we can collect the wisdom and help out new students so they can make better decisions, even from far away.

sudoku

if you haven't heard of sudoku yet, then you're at a big loss! it's such a fun game. the idea is that you're given a 9x9 grid like below. In each row, column, and square you must place the numbers 1 through 9. so that each number appears only once per row, column and square. It can be surpirsingly difficult! see the wikipedia here



at the theory lunch today, the speaker talked about sudoku from a theory perspective. here's the idea behind a zero knowledge proof. suppose alice wants to show bob that she has the solution to a given sudoku puzzle (there is only 1 solution) without revealing the solution itself. the act of doing this is called giving a zero-knowledge proof, because alice has given no knowledge about the actual solution BUT has shown that there is a solution, and she knows it. i won't go into the details on this one, but ask me if you're interested. (for you techies, sudoku is an NP-hard problem).

if you want to play now, go here

[tech] the theory lunch and zero knowledge proofs

every wednesday at noon the theory group gives a theory lunch, where faculty and students from computer science and other departments get together, eat lunch, talk about life and what they're working on, and listen to one speaker give an informal talk on some problem they are working on.

today we had indian food. and quite good indian food! the saag paneer was first-rate, and there was a really good fish curry. i've never thought of fish curry as particular indian, but this fish curry was excellent.

anyway, the talk given today was about cryptographic protocols and zero-knowledge proofs. info about the speaker, Moni Naor.

i honestly don't know a lot about cryptography or these protocols, but i learned quite a bit nonetheless. the first protocol was motivated by polling (see the paper for more detail here). imagine that alice wants to take an exit poll after a vote. however, many voters don't like to reveal how they voted. but suppose alice does this. let's call the two candidates D and R. alice makes a scratch card with 4 entries like so:

DR
RD

initially all these letters are covered, and the position of each D and R in a row is randomly chosen. so another potential card is:

RD
DR

or

DR
DR

but NOT:
DD
RR

namely, each row must contain the two different candidates.

Alice hands this scratch card to Bob, who just voted. Now Bob must follow these instructions: he randomly chooses to reveal 1 entry from each row. So suppose this is what bob does:

Initial Card:
o o
o o

Bob scratches:
D o
o R

Bob gets one more scratch. Bob's vote is indicated by the single revealed entry in the row that still contains one hidden entry. So in this situation, suppose Bob is a D man. Since he knows that the row with only one revealed entry will be the row that indicates his vote, he scratches the second line:

D o
D R

and hands his scratch card back to Alice. Alice tallies Bob's vote as D.

Ok so now here's the trick: suppose Bob's initial scratches reveal this:

R o
R o

In this case, whether Bob wanted it or not, when he hands his scratch card back to Alice, he'll vote will be tallied as an R vote.

Now notice this: in 3/4 of Bob's scratchings, he'll be able to indicate the candidate he truly voted for. This is because if he scratches out a D and an R first, then he can choose D. If he first scratches out R and R, then he must choose R. But if he scratches out D and D, then he is forced to choose D, his real vote. So 75% of the time, Alice will get the correct vote, and in ALL CASES, Alice will NOT KNOW Bob's true vote (she could guess 75% of the time correctly, but in an individual case she really has no idea).

this is my "office".. does it look clean from here? maybe.. but now look closer at the other photos 

it's typical of the shelves in this room to contain both food and unused hardware 

look closely above the notebook and to it's left. those marks on the table: hardened grime and dirty. this is my workspace! it's going to take quite the cleaning supplies! 

see all this stuff? no one actually seems to have claim to this area of the room, despite it been filled with junk! 

the whiteboard in our office -- NOTE: this is AFTER cleaning it. the black dots you see in the middle are giant holes in the board. 

[tech] graphical models

sounds like a sexy name, doesn't it? well it's a sexy subject: the combination of probability theory and graph theory (you wish you were taking the class, don't you!).

in all seriousness, this class looks like it's going to be about really interesting tools for modelling complex systems. probability theory and statistics are all the rage now in computer science, and so i'm glad i have a pretty good background in those areas.

a way of thinking about this subject is to consider a graph where the nodes are random variables, and the edges between those nodes represent some sort of dependency between the random variables. probably the simplest example of such a model is a markov chain. you remember these: the outcome of step i+1 was only dependent on what occurred at step i. here's a drawing:

Xi -----> Xi+1 -------> Xi+2

notice this is a simple graph, with the Xs as nodes. the directed edge between Xi and Xi+1 indicates the relationship between the two random variables. Now imagine more complicated graphs, and imagine hidden nodes whose behavior we don't understand but must be inferred. fascinating!

[tech] systems and databases -- oh my!

my 2nd course was the berkeley take on graduate intro to systems -- a combination of databases and operating systems. there are two professors, call them DB and OS, who heckle each other when one is speaking. the course looks to be very interesting: we talk about the detailed decisions that go into making systems, and what are the tradeoffs of each decision. we read lots of papers. we get to yell at the profs too. i'm a bit worried because i don't remember any systems stuff and have never taken a databases course and there's an "entrace" exam on thursday, but i think i can brush up.

the foundation series

today in two separate places i saw people reading asimov's foundation series. i hated the first trilogy in this series, which is all i read. the writing seemed so trite. but maybe it wasn't about the writing, but the idea. anyway i thought the idea was stupid too. here's my admittedly biased take on the idea: in the future, there's a society with some sort of scientist/mathematician who has worked out how to predict the happenings of the universe, far in advance of them happening. i forget the name of this group, but it's a stupid name. they move away from their home world to some other planet and establish a civilization. the books are about different generations of these people, and in each book a character goes to this high-tech oracle, created by the original scientist/mathematician, and this oracle tells them everything that happened before, and gives them a hint of what's going to happen next.

in my mind this is stupid. are people comforted by this idea that the universe might be understandable enough that it can be predicted ahead of time? i personally find this very depressing. in that scenario, i'm just a cog in a wheel acting out some scenario which might be important, but must go in such-and-such way because the future, predicted, is predicated on the outcome being such-and-such.

not to mention that the characters are boring, the writing is simple, and the dialog is sooo stilted.

[tech] theory funding

at lunch i learned that there isn't as much funding going around in the computer science theory community as there was many years ago. in a way, i'm more surprised that there was funding before. theory sort of works in a funny way: the stuff you come up with probably isn't immediately applicable, but many times, down the line, someone from the "real world" finds a good use for it. but problem driving funding, with definite goals and timelines, seems counter to how theory operates.

so if i join professor X who's funding by practical grant Y, i better expect to help solve something practical while doing my pure theory on the side. this doesn't really bother me, as i want to work on a practical problem that theory can help. just not sure what that will be...

[tech] random algorithms, pleasant ideas

my first class today was random computation. essentially it's about adding random bits as an input to the turing machine model, and seeing what we can do. i've had some background in random algorithms before, and so i feel pretty prepared. in addition, it was really pleasing to be faced with a Problem, an Input, and a Solution. Life doesn't work that way, but the nice world of random algorithms does.

We talked about a bunch of problems in random algorithms, but the most interesting problem, that i don't expect to solve given that so many people haven't, is the problem of determining whether, for every randomized algorithm, is there a deterministic algorithm that does just as well in run-time and solves basically the same problem. essentially the question is whether the random bits actually add anything to the model, making it more powerful.

[tech] and "normal" posts

i've decided that i'm going to label more technically oriented posts [tech] in the title so that readers can decide on whether they want to read more. a number of readers, i think, aren't technically savvy or don't care, and i don't want to bore them :)

first day at school: day's end

i thought i'd end the day on a high note by meeting my theory colleagues at the theory seminar. the talk was given by a grad student from princeton (i'd actually met him more than a year ago when i visited princeton. nice guy, pretty good lecturer). after the talk they had wine and cheese, which was quite nice. anyway, i was minding my own business, talking with grad students, when someone comes up to me and says hi. i introduce myself and then he looks at someone else and that person says to him "ah! you owe me $100!" then he replies "well not yet. talk to me in a few months."

i ask him who he is - -Satish Rao. the professor who emailed me months back and asked if i would be coming to berkeley, given that i work at mega-bucks company google. i told him i would. it seems he was betting against me! anyway i guess he still thinks that there's a chance i might skip out. i don't think i will, and if i don't maybe he should have to pay less out given that i'm doing a bit of work for google on the side.

in any case, it felt like a very unwelcome "welcome" from my temporary advisor. oh well, given my first day, why should i have expected anything else?

first day at school: midday

went to lunch with some theory students. they were quite nice, and showed me some of the interesting and affordable restaurants near the cs building. i learned about colloqiums and seminars and events and mailing lists that i should connect with. day improving.

after lunch i went to a class on internet architecture. i honestly wasn't sure what this class was going to be about -- i was thinking everything from hardware up to what's below the application layer in the network stack. turns out it's about redesigning the internet's transport layer to make it address the demands of modern applications and the realities of today's internet: quality of service issues, ddos attacks, etc.. the professor really wants us to understand the complicated problems that go into redesigning the internet, and hopefully make some proposals that show we're educated about the difficulties in this area. lots of participation, lots of debates, lots of talking.. seems fun, but i feel very unqualified.

first day at school: daybreak

didn't start too well, and ended poorly too! but that's life.

i got to school and grabbed the keys to my office. i wasn't expecting much given that i'm a first-year grad student, but my office hit new low standards. tomorrow i'll get pictures, but here's my description. The room is long and thin, and in the interior part of the floor it's on, so that it has no window out to nature. instead, it has a window out to the hall. on each of the long walls, there is a long desk, with makeshift shelves above the desk. at the opposite end of the room, there's a white-board. sounds fine? well, now let's look at the desks. covered in dirt and dust, and old books. then there are old wine bottles, hafl-finished bottles of juice, and other assorted junk. there are very few square-inches that aren't encrusted in dirt and dust.

the white-board looks like it might be functional, but the text on the board seems etched into the board itself. it's going to take some strong cleaning solution to get that board white again.

now the people: when i get in, lorenzo, a fellow 1st year grad student, is sitting, looking very cold in a heavy sweater. i think i see him shiver. why? the AC is blasting in the room, and it's clearly many degrees cooler in the stuffy room than in the open, comfortable corridor. lorenzo manages to get the maintenance team to come in and take a look at the AC in the room, and they adjust something, but now it just seems colder.

the room could not be much worse. i will do something about this, and will keep you posted :)

a place for my ideas and thoughts

i've been listening to more and more podcasts now, and they have induced me to create a place for my thoughts about them and other things. i hope to fill this space with those thoughts, as well as provide links to the various things that i'm encountering throughout my days.

that's me: