Navigation

Program Committee




APPROX

Nikhil Bansal
Ziv Bar-Yossef
Artur Czumaj
Michel Goemans
Sudipto Guha
Magnus M. Halldorsson
Dorit Hochbaum
Elias Koutsoupias
Robert Krauthgamer
Ravi Kumar
Lap Chi Lau
Seffi Naor (chair)
Tim Roughgarden
Bruce Shepherd
Tami Tamir

RANDOM

Irit Dinur (chair)
Vitaly Feldman
Parikshit Gopalan
Danny Gutfreund
Prahladh Harsha
Avinatan Hassidim
Russel Impagliazzo
Mark Jerrum
Tali Kaufman
Subhash Khot
J. Radhakrishnan
Dana Randall
Michael Saks
Adi Shraibman
Emanuele Viola

Program Chairs


APPROX
Seffi Naor,
Technion
email:
naor@cs.technion.ac.il

RANDOM
Irit Dinur,
Weizmann Institute
email:
irit.dinur@weizmann.ac.il

Workshop Chairs


Klaus Jansen,
U. of Kiel
e-mail: kj@informatik.uni-kiel.de

José Rolim,
U. of Geneva
e-mail: rolim@cui.unige.ch

Local Chairs


Neha Dave,
UC Berkeley
e-mail: nehad@eecs.berkeley.edu
Important dates
Submission deadline
April 12, 2009

Notification to authors
June 1, 2009

Camera ready
June 15, 2009

Conference
August 21-23, 2009
Call for papers

Restaurants / Cafeterias


Other links

sfstation.com has  information on things to do in San Francisco and in the Bay area
here is another list of restaurants in Berkeley, written with less editorial restraint
bart.gov has  information on how to use the Bart (subway system connecting Berkeley with San Francisco and other places)
511.org provides  traffic information.
Google maps or Yahoo maps can be used to find your way around campus and beyond


Coffee Shops

See Andrej Bogdanov's list

In addition:

  • Canvas, also listed below under "After Dinner". Free wireless internet access, near Golden Gate park. 1200 9th Avenue (@ Lincoln)

Restaurants

Prices are according to Zagat's guide. Expect to pay more for a full meal with wine.

Restaurants in Berkeley

Convenient For Lunch

There is a food court of sorts on Hearst street, going down half a block from Soda Hall. There is a Thai, a Vietnamese, a Korean, a Chinese, Japanese, and a hamburger place. Luca likes the spicy chicken from the Korean place and the daily specials from the Thai place. Note that the Thai place is somewhat downstairs with respect to the others.

There are several places around the corner from Soda: on Euclid between Hearst and Ridge, including:

  • Nefelihas elaborate, and good, sandwiches (for example the Alpino has prosciutto, walnuts, fontina, pears and arugola) and one or two daily specials. The coffee is very good
  • Hummingbird has sandwiches made to order and middle eastern fare (falafel, hummus, . . .)

Far from Soda, but still walking distance:

  • Cheese Board makes one type of pizza per day, always different, and that's all they sell. It's run by a collective. It's a Berkeley institution. 1504 Shattuck (@ Vine)
  • Gregoire unbelievably good sandwiches made by a noted local French chef. Desserts and potato puffs are also worth noting. 2109 Cedar (@Shattuck)
  • Phoenix fresh pasta, open only for lunch. 1788 Shattuck Ave (@Delaware)

Walking Distance from Soda Hall (Dinner)

  • Liason very popular French restaurant close to Soda Hall. 1849 Shattuck (@ Hearst). $32
  • Venus Californian cuisine, suggested by James. 2327 Shattuck (@Durant) $21
  • Cha Am Thai nice Thai restaurant. 1543 Shattuck (@ Hearst). $18.
  • Cha Ya a vegan Japanese restaurants popular with the theory group.1686 Shattuck (@Virginia). No Zagat's rating, moderate price, around $25
  • Cesar excellent place for drinks and small plates, the kitchen is open until 11pm, which is considered very late by Berkeley standards. Next door from Chez Panisse. 1515 Shattuck (@ Vine)
  • Chez Panisse Cafe the temple of the new California cuisine, no description would give it justice. Zagat's price estimate is very optimistic. Reserve at least two weeks in advance, but for a 10pm seating same-day reservations are typically possible. 1517 Shattuck Ave (@ Vine) $43
  • Chez Panisse for the serious worshipper, the Chez Panisse restaurant, downstairs from the cafe, offers just one prix-fix menu, that is changed every day. 1517 Shattuck Ave (@ Vine) $69

Further From Soda Hall (Dinner)

  • Vik's Chaat Corner exceptionally good South-Indian place, with all the hard-to-find "breakfast" items like idlis and dosas, plus very very good chaat. A cross between a car repair shop and a fast-food joint, the decor is not Vik's strong point. 726 Allston (@ 4th) $10
  • Breads of India excellent Indian restaurant, with a short menu that is changed daily. They do not accept reservations and the wait can be long. 2448 Sacramento St. (@ Dwight) $18
  • Kirala very good sushi place. No reservations, and occasional long waits. 2100 Ward St. (@ Shattuck) $33
  • Rivoli a place to go when you can't get a reservation at Chez Panisse, it has excellent food but, according to Luca (others disagree), it does not achieve greatness. 1539 Solano Ave. (@ Neilson) $42
  • Oliveto is another back-up for Chez Panisse, and it's highly recommended by most of the Berkeley theory group. 5655 College Ave (@Shafter, in Oakland) $47
  • O Chamé a very good Japanese place. 1830 Fourth (@Hearst) $30
  • Ajanta a good Indian restaurant, suggested by Neha. 1888 Solano (@Alameda) $24
  • Fonda tapas place, recommended by Alistair. 1501 Solano Ave (@Curtis, in Albany) $31
  • À Côté French tapas, recommended by Alistair. 5478 College Ave (@Taft, in Oakland) $34
  • Pearl  seafood place, recommended by Alistair  5634 College Ave (@ Keith, in Oakland)
  • Trattoria La Siciliana good Italian restaurant, with notable seafood dishes. 2993 College Ave (@Ashby Ave) $26
  • Holy Land Isreali restaurant praised for falafels and hummus. It has a branch in Berkeley and one in Oakland. Both keep a kosher kitchen, but only the branch in Oakland is certified by a rabbi. Berkeley: 2965 College, Oakland: 677 Rand. No Zagat's rating, cheap (around $10).
  • Picante mexican restaurant, suggested by James. 1328 Sixth St (@ Camelia) $14

Restaurants in San Francisco

In the Mission

The following places are easiliy reachable from the 16th st or 24th st stops of the Bart
  • Delfina Luca's favorite reasonably priced restaurant in San Francisco, it has exceptional appetizers and pastas, somewhat less satisfying entrees, and very good desserts. It is good to reserve at least one week in advance. Delfina's pizzeria has just opened next door. 3621 18th St. (@ Dolores) $41
  • Limòn officially a Peruvian restaurant, it has a very good selection of ``nuevo latino'' dishes. 524 Valencia St. (@ 16th St.) $33
  • Andalu one of the places that started the tapa trend in San Francisco, when they say "small plate" on the menu they mean small. Be prepared to order a lot of dishes, or to move to the nearby Pakwan for a real dinner afterwards. 3198 16th (@ Guerrero) $31
  • Pakwan Luca's favorite cheap Indian place in San Francisco (others prefer Shalimar). 3182 16th (@ Guerrero) $13
  • Charanga a very good Cuban tapa place, the seafood dishes are quite recommendable. 2351 Mission St (@ 19th) $24
  • Watercress a French-Asian fusion restaurant, its $20 three-course prix fix is an unbeatable deal. Luca always orders either the shrimps (that come with mashed potatoes!) or the fried wontons (with goat cheese stuffing) for appetizer. This is one place where you will pay less than Zagat's estimate. 1152 Valencia St (@22nd) $31
  • Poncho Villa: taqueria in the Mission, Samantha calls it "one of the best places for burritos, soft and hard tacos, homemade chips, salsas, and it's also cheap." 3071 16th St (@Valencia)

In the Tenderloin / Union Square

These places are easily reachable from the Civic Center or Powell stops of the Bart, and are convenient if you go to the shops or theaters around Union Square.

Note: this area feels scary at night but it is not really unsafe. At night, it is better to use the Powell stop than the Civic center stop, and it is better to stay on Geary and O'Farrell, rather than Turk, Eddie or Ellis.

  • Osha Thai an outstanding, cheap Thai place in the Tenderloin that is open until 2am. Luca always orders the spicy string beans. 696 Geary (@ Leavenworth) $15
  • Shalimar some people say this is the best cheap Indian place in San Francisco. 532 Jones (@ Geary) $14

Far from the Bart

  • Helmand the same menu and the same very good Afghan food of Helmand in Cambridge, MA, but with friendly service. Being surrounded by strip joints, its location could be better, but, on the good side, parking is not difficult. 430 Broadway (@ Kearny) $29
  • Old Mandarin this Muslim restaurant manages to prepare Chinese food without pork and is probably ok for non-strict Kosher eaters. It is better to go with a Chinese speaker, but in any case, by pointing to the other tables if necessary, do get the thing with the big boiling pot where you cook your own lamb. 3132 Vicente (No Zagat rating)
  • Burma Super Star it is very difficult to park, they do not take reservation, and the wait is always very long, but what does it matter when the food is so good? Write your cell phone number in the waiting list, and then go to the coffee shop across the street. Eventually, they will call you when a table is ready. 309 Clement St. No Zagat rating, quite cheap.

For those who cashed in before the bubble burst

Expect to pay more, much more, than Zagat's estimate in these places. For Aqua in particular, the bill can easily be almost twice the estimated amount. For the other places, expect about 40-50% more than the estimate.
  • Gary Danko generally considered the best place in San Francisco. Alistair and Umesh beg to differ. 800 N. Point (@ Hyde) $88
  • Masa Gary Danko's rival, Luca thought that Masa was great but not worth the hype and the bill. 648 Bush (@ Powell) $93
  • Acquerello considered the best Italian restaurant in San Francisco, Luca was blown away by the appetizer and the pasta during his only visit. 1722 Sacramento (@ Polk) $60
  • Aqua extremely good Asian-fusion seafood place. 252 California St. (@ Battery) $65
  • Fleur de Lys the place where Luca had his best dinner ever. The second visit was not as good. 777 Sutter (@ Jones) $87

After Dinner

In Berkeley

  • Cesar also listed above as a restaurant, it's a great place to go even just for a drink.
  • Jupiter the standard place for drinks close to campus for the crowd that does not need a fake ID. 2181 Shattuck
  • Blake's the place close to campus for the crowd that does need a fake ID. 2367 Telegraph
  • The Albatross Andrej calls it "a very nice pub with good beers, games to play, and live music from time to time" 1822 San Pablo

In Oakland

  • Cato's Ale House is a "family-friendly" drinking place. Snacks are available until late. 3891 Piedmont Ave, Oakland
  • Yoshi's a well known jazz place in Oakland. They also serve an undeservedly expensive dinner. 510 Embarcadero West

In San Francisco

Remember to go to sfstation.com for many more suggestions of things to do in San Francisco and in the Bar Area.

  • 111 Minna Art gallery by day, bar with a small dance floor at night. The crowd is pretentious but interesting (think an average place in New York, but with less black turtlenecks and more adventurous piercings ). 111 Minna.
  • Canvas, to top 111 Minna, Canvas is an art gallery that is a coffee shop by day, with free wireless internet access, and bar at night. Wonderful ambience. No dancing. 1200 9th Avenue (@ Lincoln)
  • Toronado  is praised by Andrej for its "amazing selection of beers on tap, including Chimay and Hoegaarden." 547 Haight 
  • The Elbo Room: Samantha describes it as "a relaxed bar with a club upstairs that regularly features live bands." 647 Valencia (@17th)
  • El Rio bar with outdoor patio/dance floor, variety of music (world, salsa, hip-hop, house), the type of music depends on the day/night.  (Mixed gay-straight crowd)  3158 Mission St (@ Cesar Chavez)
  • Martuni's a piano bar with a curious mix of show tunes and jazz music. (Mixed gay-straight crowd) 4 Valencia.
  • The Lexington the main (and only?) lesbian bar in San Francisco. Small and low-lit, it plays mostly  hip-hop and Latin music. 3464 19th St (@Valencia)
  • Bar on Castro unimaginatively named, this small place gets extremely crowded on weekends and is more pleasant on weekdays. Luca thinks it has the  best ambience and the best music in the Castro. A theory graduate student thinks "it is too yuppie sometimes." It does not have a dance floor, but the whole place becomes a dance floor on weekends. No cover charge. (Predominantly gay crowd) 456 Castro (@18th).
  • Popscene only on Thursdays. Brit-pop and indie music. Probably the most fun party in San Francisco. 330 Ritch.
  • Trannyshack only on Tuesdays at the Stud, they have a high concept (and always different) drag show at midnight: think of a drag interpretation of Pink Floyd's the Wall, or a drag take on punk rock. Offensive, imaginative, and highly recommended. Dancing before and after the show. 399 9th (@Harrison)