Larkin near Ellis. This is another place I had been meaning to write about for a long time (more than a year now). This is probably the best Vietnamese food I’ve had, and a steal for the price. It’s in the Tenderloin, which is not the nicest of neighborhoods, but it’s a good place for an early dinner before going for more adventures (or rehearsals). If you’re a pho fan, you’ll find their broth to be richer than most places, and the tai (rare flank) is really fresh until you push it under the broth to cook it. There’s a 7-course beef feast that I’ve never tried but I hear it’s delicious. I’ve also tried the construct-your-own spring roll with shrimp molded over sugar cane and grilled (you have to try it). On the curry side I had a lemongrass dish that was good but just wasn’t as exciting as the other things. The restaurant itself is a little spare but in an elegant clean designed way. And did I mention it’s cheap?
Category Archives: Uncategorized
slow club
Mariposa at Hampshire, one block west of Potrero. I meant to write about this place before, but it slipped my mind. Slow Club is one of those hip restaurants in that area between Potrero Hill and the Mission. We had to wait for a table so we decided to sample the drinks at the bar. I had a Junipero martini. I’d never had Junipero before, despite it being a local gin, and it was quite good, although I think I prefer Hendricks if I’m going to pay ridiculous amounts for gin. Overall though, I’d skip the bar next time and maybe get a glass of wine with the meal.
Slow Club is the kind of place that has good food that even your picky (but non-vegetarian) friends might eat. There’s always a pasta, a lamb, a chicken, a fish, and the burger. As I mentioned, the vegetarian pickings are slim. Prices range from $10-$20 for an entree, but I definitely recommend splitting an appetizer, such as the grilled flatbread. It’s a kind of lavash-like pizza thing and it’s ridiculously tasty. The menu changes daily and is posted online.
We had the flatbread and I had linguini with a veal ragout. The pasta tasted fresh and light, much like the Phoenix Pastificio in Berkeley. The sauce was delicious, and not too fatty in spite of the veal. I think I tasted fennel in there, which I will have to try the next time I make meat sauce. I also got to try my friends’ dishes, a leg of lamb that was too tender to be believed, and a citrus-rosemary crusted chicken. It’s the second time I’ve tasted the orange-rosemary combination and I’m sold on it now.
I’m definitely going to go there again, maybe on an off-night. As long as you can ignore the endless parade of hipsters and the loudness of the room and concentrate on the good eats, you’ll be golden.
6 degrees
1403 Solano (in Albany). This is a new vaguely European small-plates restaurant near the Albany/Berkeley border. I went there with my research group after reading about it on Chowhound. The menu is still a little in flux and the wheels of the operation haven’t yet been oiled, but I’m pretty confident that they could work out the kinks by the end of February when they officially open. At the moment, however, the restaurant leaves a lot to be desired.
I ordered the Roman Manhattan, which was Maker’s and Cinzano and was a bit watery. This might have been due to the 10 minutes they spent making it — it had that left-in-the-shaker-to-melt taste to it. For a restaurant that was so empty, it was a little disappointing.
There were a lot of things missing from the menu — the venison was absent to lack of availability, and the Holland crepes were also out, which was surprising since as far as I could tell they are like Dutch quesadillas. The menu also had some pretty glaring typos; not something you expect in such a high-end place. It was especially bad if you knew French. It was hard to tell what was vegetarian and what was not. Lots of the things had ham or something hidden in them.
We ended up getting the pommes frites, saffron rice croquettes with pancetta, breaded olives stuffed with ricotta, ham, marjoram, “amalfi grilled vegetables,” crostini with various spreads, mussels cooked in white wine and garlic, and the vegetarian grill, which was an entree with lots of veggies and some vegetarian croquettes. The bread that came initially was clearly not that fresh, which was a real downer, especially since the Acme bakery is so close by. Of the dishes we ordered, the saffron rice was a clear winner — lightly fried and the saffron was clear but not overpowering. The wine from the mussels was overpowered by the intense brine flavor and the garlic was mostly absent. The vegetarian grill had some sauce on it that was a little sour but absolutely delicious. The olives kept losing their breading but the ricotta was surprisingly good as a stuffing. I didn’t really get to try the crostini so I can’t comment.
Dessert was cheese and fruit and a creme brulée. The latter didn’t have a crunchy enough top — certain movie characters would have been sorely disappointed. On a different day I would have chosen something more chocolate-oriented — there were some other tasty options on there that may have been more exciting.
All in all it seemed like the whole place was getting into the rhythm of things, and I think they have a lot going for them. I’ll definitely try it out again sometime.
Afterwards, we went bowling, and I managed to bowl a 151, which is shockingly good for me. I attribute the score to the white Russians.
paper a day : the Gale-Ryser theorem
By request, today’s paper is kind of about the mathematics of paint-by-numbers puzzles. Merry Christmas, Erin.
A Simple Proof of the Gale-Ryser Theorem
Manfred Krause
The American Mathematical Monthly, Vol. 103, No. 4. (Apr., 1996), pp. 335-337.
The Gale-Ryser Theorem is one of those beautiful little gems in combinatorics. The problem is rather simple to state. Suppose you have a k by n matrix A of zeros and ones. Let r be the vector of sums along each row and c be the vector of sums along each column. The question is this : given an r and a c, when does there exist a matrix A with those row and column sums?
First off, note that r and c satisfy
since the total number of ones has to be constant. We need a few more concepts to understand the result. A partition of N is a set of positive integers r1 ≥ r2 ≥ … ≥ rk whose sum is N. It turns out that it’s sufficient to only consider r and c that are partitions (hint : start swapping rows and columns).
Given two partitions r and c of N, we say r is dominated by c if
where the summands become 0 if we exhaust the partition. As it turns out, dominance provides a partial order on the set of partitions that is particularly useful in combinatorics. The whole theory of majorization is based around the dominance order.
The last concept we need is a Ferrers board and the conjugate partition. Given a partition r of N, imagine a matrix of 0’s and 1’s that has rj 1’s in row j. This is the Ferrers matrix of the partition. The conjugate partition of r, denoted by r*, is the partition whose Ferrers matrix is the transpose of the Ferrers matrix for r.
The Gale-Ryser theorem says that a matrix A exists with row and column sums r and c if and only if r is dominated by c*.
To prove that we need the dominance relation, suppose that r is not dominated by c*. Then look for gaps in A — that is, rows in which you get a 0 and then a 1. Induction on the number of gaps proves it. If there are no gaps we have a Ferrers matrix, so we’re done. If there is a gap, you can swap two entries in a column to reduce the number of gaps.
The novelty in the paper is a new proof of the “only if” half of the statement. It’s basically an algorithm that provably constructs a matrix satisfying the row and column sums given. Clearly this matrix is not unique in general. You start with the Ferrers matrix A0 for c and do a series of swaps until the row sums equal r. Let Aj be the matrix after j swaps. The algorithm guarantees the following:
So it will eventually converge to a valid matrix.
The application to paint-by-numbers should be pretty clear. A PBN is just a 0-1 matrix of pixels. If the image in the PBN is convex, then the puzzle is kind of trivial, but you can use the theorem to decide if it's solvable. An interesting extension to work out would be a theorem or fast algorithm for deciding if a general PBN is solvable or not. If I had the time to think about this, I would. Maybe it's something to do on a rainy afternoon after my deadlines have passed.
edibles folded into main blog
My old edibles blog has been folded into the main blog — once I figure out how to get link bar working properly they should appear there. Maybe that will encourage me to write more food commentary.
Update: WordPress lets you make static pages external to the blog itself but using the same stylesheet. The Edibles section is now available from the top navbar as well as the sidebar.
gee, that name is familiar…
Geeta Dayal has an article in the NY Times! Soon, she will take over the world…
Koetter-Vardy algorithm in MATLAB redux
Pursuant to my previous post, some raw (and possibly now not as functional) code for the Koetter-Vardy and Guruswami-Sudan algorithms is now posted off of my work page. It’s horrendously slow, but I’m sure others can make it better.
Update: I’ve moved and the code is gone, archived elsewhere. I don’t plan to post it again — it’s just a class project, so people should try to do it on their own for educational purposes.
Bissap Baobab
(Mission and 19th) This Senegalese restaurant is always busy, like it’s neighbors Cha Cha Cha and Charanga, so be prepared to wait. Senegalese cuisine is like that of other West African countries — starches, stews, and grilling things. There’s a DJ on weekends and some pretty tasty cocktails with ginger, hibiscus, and other “exotic ingredients.”
We started with fried plantains with a tamarind dipping sauce. Actually, according to our Senegalese companion, plantains are not native to Senegal, but to Cameroon and Cote d’Ivoire, so that dish was not particularly authentic. We managed to ignore that on the basis of its tastiness. For the main course I had the Yapou Khar, which is a lamb stew with tomatoes and onions over rice. The lamb was tender, but I found the stew a little too watery — I wish they had cooked it a little longer or reduced the liquid more. The centerpiece dish is Thiebou Djen (or Djolof rice for those who know Ghanaian food). This is a spicy fish stew over red rice, and is hearty and tasty.
Bissap has managed to get less and less spicy every time I’ve gone there, and the prices seem to have gone up, so it’s harder for me to recommend it against some of the other places in the area. However, if you have a hankering for these flavors it’s still your best bet.
Fattoush
(Church at Clipper) I’m not sure how they managed to get fattoush.com, but more power to them. This restaurant is a bit out of the way, so I wouldn’t recommend it as a pre-movie meal (unless you trust the J-Church MUNI line to come like clockwork), but it’s the only really good pseudo-Lebanese food I’ve had in the city. The ambiance is nice, although some ongoing renovations make the patio area unusable at the moment.
We split an order of hummus to begin with. It was tangy and flavorful, a moister version than you sometimes get at restaurants, but not at all runny. For the entree, I split the Mansaf and M’sakhan with Liz, both of which were covered with a yogurt sauce. The Mansaf was lamb chunks and rice with a slightly sour/tart (“aged”) yogurt, topped with almonds. A whole plate might have been too much for me, since I found the sauce a bit too aggressive for the lamb, which could have been spiced more heavily. The M’sakhan’s yogurt sauce had saffron and was quite a bit sweeter — a nice complement to the Mansaf. They take chicken and caramelized onions and wrap it in a lavash, grill it, and cover it with the sauce. The spicing in this dish came through much better, in my view.
The dishes are large and dense here, so come hungry! Going “family style” might be a better option for those who get full quickly.
Guruswami-Sudan algorithm in MATLAB
Read the updates at the end! Comments are disabled because people don’t actually read the post. This is sad to me, since it really shows that the majority of people commenting on this post are really just trolling for a free pass at an implementation, think that I or someone else will send it to them or port it into C for them, and are so lazy that they can’t scroll through the post themselves.
For part of my class project in coding theory this semester I’ve implemented the Guruswami-Sudan decoding algorithm for Reed-Solomon codes. Reed-Solomon codes are used widely in practice for error-control coding. For example, CDs use a Reed-Solomon code to provide resilience to errors introduced by scratches or machine error. The math behind RS codes is somewhat complicated, but the idea is as follows. Suppose you have some k symbols of data that you want to encode into n symbols. The redundancy (and hence error correction capability) can be thought of as the difference (n – k). This is the “fat” we add into the data to make it resistant to errors.
RS codes take these k symbols and think of them as the coefficients of a polynomial
f(X) = f_0 + f_1 x + f_2 x^2 + … + f_{k-1} x^{k-1}
The encoder and decoder agree to fix n points {a_1, a_2, … a_n}. The encoding map consists of evaluating f(X) at these n points and sending the evaluations:
codeword = (f(a_1), f(a_2), … f(a_n))
The key is in decoding — if the decoder gets any k symbols correctly, it should be able to interpolate a unique polynomial f through them perfectly (this is from linear algebra). Thus in the CD example, if the CD player can’t read some of the symbols, it can only tell the decoder those symbols that it did read. As long as k of those symbols were received the decoder can recover the polynomial and hence the data sequence.
Now of course the math is a little more complicated than that, but not by too much. RS codes are actually defined as polynomials over the ring F[x] where F is the finite field with 2^m elements, and the encoding is the evaluation of a degree k-1 polynomial on all the nonzero elements of the field.
The Guruswami-Sudan algorithm algorithm works in two steps — it interpolates a certain bivariate polynomial Q[x,y] in a F[x,y], and then factors it into factors of the form (y – f_i(x)). The y-roots {f_i(x)} can be thought of as “candidate polynomials” for the data sequences. The algorithm works in polynomial time and outputs a small list of candidates which is guaranteed to contain the transmitted codeword under certain conditions on how bad the errors are. The real key is that the list will often contain the true codeword even if more errors occurred than the code was designed for.
My implementation is based on a very nice tutorial paper by Robert McEliece, who is a really fantastic writer. It uses the Koetter algorithm for interpolation and the Roth-Ruckenstein algorithm to factor the resulting polynomial. This posting is mostly so that Google will possibly pop up this page if people are looking for MATLAB implementations of this algorithm and don’t want to waste sleepless nights like I did trying to force it to work. Caveat emptor, as they always say.
UPDATE : I’ve moved several times since this post was written and in the meantime taken down the code since implementing this is a common course project. It was tricky but not too hard, and I’ve decided the learning benefits of implementing it yourself outweigh the (now negligible) time savings for projects involving follow-on work.
An Ergodic Walk 