STOC 2014: 46th Annual Symposium on the Theory of Computing

How To Get Around New York

First and most importantly, DO NOT RENT A CAR. Should you rent a car, you will regret it. Not only is traffic very bad in New York, parking is ridiculously expensive, as are parking tickets. New York is the worst city, by far, in which I've lived regarding driving. The viable options for transportation are walking, public transit, and cabs. (If by any chance you drive to New York, say, because you're carpooling, I recommend parking far from the hotel and leaving your car in the garage for the duration of the conference. The parking lot I use is on West End Ave. between 62nd and 63rd. and charges about $19 per day, which is very cheap for Manhattan.)

New York is the safest big city in the US. Do not worry about crime. On the other hand, don't forget your wallet on a subway car, either. (But you actually might get it back if you do. The New York Daily News sent a blind woman into ten cabs to take a $3 ride, and to offer the driver a $20 bill and say, "Here. Take this $5 bill and keep the change." How many told her she'd erred? The answer is at the bottom.)

While you can always take a cab---cabs are not only numerous but not expensive---taking the train (New Yorkers refer to the subway as "the train") is what most locals do. The fare is $2.50 a ride, but $2.75 if you only buy one ride; however, if you spend $10 or more, you get a 5% bonus. Any transfer betweeen trains is free, as is one transfer from a train to a bus or vice versa. You can also buy a weekly pass for $30. If you choose to pay cash on a bus, you'd better have exact change in coins, since bills are not accepted. Hence you're better off buying a Metrocard, which can be purchased in subway stations (of course), newspaper stands (e.g., at the airport), and, supposedly, from ATMs, though I've never done so.

The subway is great. Not only does it go everywhere and run frequently, it runs 24 hours a day. (In fact, there are only a few heavy-rail subway systems in the world that run 24 hours a day. I can name three or four, depending on the definition of "subway," and they are all in the US. Surely there are some abroad?) It's one of the best things about New York. Don't let it intimidate you. If you have questions, ask a clerk in a booth or a random passenger. People here are, contrary to popular opinion, actually nice and helpful. Make sure you pick up an invaluable free subway map from a subway booth clerk. Visit www.mta.info for maps, etc. See tripplanner.mta.info for mapquest-style personalized travel directions: you put in your origin and destination, and it tells you how to get there via public transit. By the way, when you put in an address, such as "130 west 85th Street", you must enter it as follows: "130 W 85 St". Note the "W" and the "St" and the complete lack of punctuation.

Restaurants

How about restaurants? New York has one or two good restaurants, so finding one won't be a problem. I've included below a highly indiosyncratic list of my favorite restaurants in New York. While I can't guarantee you'll like them, I can guarantee that I like them. Do check Zagat's or some other restaurant guide if you don't trust my opinion.

Catering mostly to tourists, the restaurants in the Times Square area generally stink. Avoid restaurants between about 40th St. and 52th St., and between 6th Ave. and 8th Ave. (inclusive), unless you have a specific recommendation. I've given you a few recommendations below.

Though I am unfamiliar with the region of 9th Ave. near 34th St., the general rule is that restaurants are better on 9th Ave., a block from the hotel, than on 8th Ave.

I suggest you check out any restaurant on my list on the web before you go, to make sure that it hasn't closed recently and that it is open at the time when you want to go. By the way, in many cases I've given subway directions to the restaurants. In all cases, taking a cab would be reasonable as well, unless the restaurant is so close that one could walk.

Here are my recommendations in the vicinity of the hotel listed in random order. You will need to walk some distance or take a cab to get to some of them.

1. Kum Gang San: Korean at 49 West 32nd St., an easy walk from the hotel. It's cheap and good albeit crowded. If you like Korean food, don't miss this opportunity to visit Manhattan's little Koreatown. My 3-year-old daughter loves this place, where she pleads, "more kimchi, please."
   
   
2. Marseille, good French at 630 9th Ave. (around 44th St.).
   
   
3. Tagine: Moroccan on 9th Ave., near 40th St., 212-564-7292. Excellent Moroccan, though my wife and I haven't been there for years.
   
   
4. Pongsri, 244 West 48th St., between Broadway and 8th Ave. Decent Thai in the heart of Times Square, better than most restaurants in the vicinity.
   
   
5. Uncle Nick's: Good, inexpensive Greek food. They have a few locations, including two near each other on Ninth Ave. near 50th or 51st Sts. I've only gone to the one farther south. 212-245-7992.
   
   
6. Russian Vodka Room: Excellent Russian food (and flavored vodkas), recommended by Maxim Sviridenko and also enjoyed by Kostya Makarychev. While I do enjoy the vodkas, for me the draw is the unusual Russian food---specifically, don't miss the fish. Sometimes I eschew the entrees here and order multiple appetizers. The Russian Vodka Room is one of the best places to eat in the Times Square area. It's at 265 W. 52nd St., 212-307-5835.
   
   
7. Junior's: A Jewish-style deli in the heart of Times Square, Junior's has the best cheesecake in the world. My wedding cake was their best cake: a Junior's devil's food chocolate cheesecake. On 45th St. between Broadway and Eighth Ave.

Here are my favorite Manhattan restaurants, without regard to location, listed in no particular order, except that my favorite is first.

1. Craftbar (900 Broadway, I believe between 19th and 20th Sts.): my favorite restaurant in New York, the place to which my wife and I go to celebrate special occasions. Entrees are about $25. You can't go wrong at Craftbar. Dinner for two with one glass of wine, one appetizer, and one dessert will run about $120 total for two.
   
   
2. Turkuaz, the Turkish restaurant where my wife and I had our wedding reception. In fact, the top photo from their takeout menu is a photo from our wedding reception. (See if you can spot my wife.) 2637 Broadway, on the southwest corner of 100th St. and Broadway, 212-665-9541. Excellent Turkish food with entrees at $18-$30. Take the 2 or 3 train uptown, from 34th and 7th Ave., to 96th St. and walk four blocks north. (If you like playing table tennis, take your raquet and play at Wang Chen's table tennis club, 250 W. 100th St., a few doors from Turkuaz, after or before dinner. It costs $8 per hour. See, I said the list was going to be idiosyncratic.)
   
   
3. Limon: very small Turkish restuarant---five small tables total---at 238 E. 24th St., 212-213-3343. Fantastic small Turkish restaurant which, fortunately, has no liquor license. There's a wine store across the street. Do make a reservation since the place is so small. You could walk there, but it would be a long walk. Spring for a cab for this one.
   
   
4. Pomodoro: My wife's and my favorite Italian restaurant, on Columbus Ave. between 70th and 71st. There are several Pomodoro restaurants, so make sure you go to the one on Columbus between 70th and 71st. Pomodoro never fails to satisfy. Whenever I go to a different Italian restaurant, I end up thinking, "On no, why didn't I just go to Pomodoro?" Take the C train, which stops at the hotel, to 72nd St., and walk one block west and one block south.
   
   
5. Grano: Italian in Greenwich Village, 21 Greenwich Ave., at the corner with 10th St. A counterexample to what I just said about Italian restaurants, Grano is as good as Pomodoro. Lighter cuisine in a more mellow, less crowded atmosphere. 212-645-2121. Take the A, C, or E train south to West 4th St., exit at the north end of the station, and walk a few blocks.
   
   
6. Meskerem: Ethiopian at 124 MacDougal St. in Greenwich Village, 212-777-8111. Good Ethiopian in the heart of the Village. Make sure you wander around the Village afterward. Take the A, C, or E train south to West 4th Street and walk a few blocks. (My wife and I actually prefer Massawa at Broadway and 121st, 212-663-0505, for Ethiopian food, but it's much farther from the New Yorker and in a much less interesting neighborhood.)
   
   
7. Epices du Traitteur: Tunisian at 103 W. 70th St., just west of Columbus. Very good Tunisian. Take the C train to West 72nd St., walk two blocks south and one block west.
   
   
8. Viet-Nam Banh Mi So 1: Little Vietnamese storefront, no seats, with fantastic Vietnamese sandwiches which cost next to nothing. Probably open only for lunch. 369 Broome St., between Mott and Elizabeth Sts., 212-219-8341.
   
   
9. Eleven Madison Park, at, well, 11 Madison Park (on Madison around 24th St.). This used to be our favorite restaurant in New York till they upped their prices and shrank their portions. Watch out: I think they only offer $80-and-up meals now. 212-889-0905.
   
   
10. Vatan: My favorite Indian restaurant, at 29th St. and 3rd Ave., where I proposed to my wife. It's a Gujerati, all-you-can-eat, vegetarian banquet. Don't let the all-you-can-eat part turn you off: it's excellent. Definitely make a reservation: they get busy.
    
    
11. Land Thai (as in ``Thai Land''): My favorite Thai restaurant in New York. When they say spicy, they mean it. Unless you like spicy food, avoid this place. 450 Amsterdam (between 81st and 82nd St.), 212-501-8121. Call first to see how crowded they are, since the restaurant is small. Take the C train uptown to 81st St. and walk one block west.
    
    
12. La Paella: Excellent paella, tapas, etc. in the Village. Small and noisy, it's one of my favorite restaurants. It's at 214 E. 9th St., 212-598-4321. Take the N or R train from 34th and 6th Ave. to 8th St. and walk a few blocks east.
    
    
13. Nobu Next Door: the more casual cousin of the famous Nobu. Both serve creative, Japanese fusion dishes, and neither is cheap. But if you like creative Japanese food, don't miss it. 105 Hudson St., at Franklin. Take the 1 train from 34th and 7th Ave. to Franklin and walk one block west. You order several small dishes here. My notes remind me thus: ``Definitely order the arctic char and halibut collar. Mussels were excellent. Oysters and monkfish pate' were excellent but the portions were too small.'' A few years ago, my wife and I had five small dishes total, one glass of wine total, and one dessert total, for $115 plus tip (for two).
    
    
14. Soomsoom: the best falafel I've had in New York, as good as the best I've ever had in Israel, and believe me, I've been to a lot of falafel places. They have pickled eggplant, turnips, and even lemon. Don't miss the amba. The biggest drawbacks to this place? It's closed Friday evenings and Saturdays, and it gets too crowded. It's only $6.38 for falafel. Soomsoom is on West 72nd St., a few doors east of Broadway, on the south side of the street. Take the 2 or 3 train from 34th and 7th Ave. to West 72nd St. and you'll be right there.
    
    
15. Spiga: fancy Italian on the Upper West Side (84th St.).
    
    
16. Bombay Palace: 30 W. 52nd St. Good Indian a short cab ride from the hotel.

By the way, at www.heraldsquarehotel.com/cheapeats.htm, you'll find an old list of 100 restaurants where one could once get a meal for under $10. I personally can vouch for none of them, however. Definitely call the restaurants first to make sure they still exist. (Thanks to Flip Korn for the list.)

Here are a few additional restaurants recommended by friends. I've been to none of these myself. You must check on the web to see if they still exist before you go.

1. Spice, a chain of Thai restaurants.
   
   
2. Kellari: Greek restaurant at 19 W. 44th St. recommended by a Greek friend of mine.
   
   
3. Alfanoose: Middle Eastern, 8 Maiden Lane

Four restaurants recommended by Martin Farach-Colton:

1. Sakagura: Japanese at 211 W. 43rd, in the Times Square district.
   
   
2. Takeshi: Japanese/Korean restaurant on Hudson St.
   
   
3. Txikito: Basque cuisine on 9th Ave. between 24th and 25th, not far from the hotel.
   
   
4. Nougatine: 1 Central Park West (at 60th St.).

Fun Things To Do In New York

Here are some popular touristy things to do in New York:

• The Circle Lines tour: a tour boat showing off Manhattan.
  
  
• Staten Island Ferry: the poor man's tour boat. It starts at the foot of Manhattan and runs to Staten Island. You'll get nice views of downtown and of the Statue of Liberty during the 30-minute, one-way trip. Best of all, it's free. Take the 1 train to South Ferry, its southern terminus.
  
  
• Empire State Building: Especially spectacular at night, if you've never been to the top, you must go.
  
  
• Ground Zero: Not terribly impressive in my opinion, but a lot of people like to go.
  
  
• Brooklyn Bridge: Take a walk across the bridge and enjoy the spectacular view of downtown. Take the 2 or 3 train to the Park Place stop.
  
  
• Times Square: The heart of Midtown. Extremely impressive, impressively crowded, and an easy walk from the hotel. See it once and then leave quickly.
  
  
• Metropolitan Museum of Art: One of the world's best art museums, the Met has everything. Suggested admission is $20, but the secret fact is that you can pay whatever you want. Take the C train to 81st St. and Central Park West and then either walk the half mile across Central Park or transfer to the M79 bus.
  
  
• American Museum of Natural History: Dinosaurs and more, even a planetarium and IMAX. Take the C train uptown to the 81st St. station---there's a museum entrance directly from the subway. The admission fee is a suggestion.
  
  
• Museum of Modern Art: Primarily for modern art cognoscenti, MOMA does have some famous Van Goghs (e.g., Starry Night) and, I believe, Picassos.
  
  
• Broadway: I have a love-hate relationship with Broadway. Most productions I've seen there have been mediocre. Broadways caters to the lowest denominator.
  
  That said, the best Broadway shows are fantastic. I recommend ``Chicago'' and ``A Lion King,'' both of which are musicals. See playbill.com for discounts. Yes, you have to be a member, but anyone can join for free. For a playbill.com discount, I believe you simply need the code on the printout, not the printout itself, but I can't promise.
  
  Do not go to the TKTS booth for discounted tickets unless you have a preferred show in mind. Too many Broadway shows, especially discounted ones at TKTS, stink.
  
  
• Strawberry Fields: The memorial to John Lennon in Central Park. In fact, Central Park in general is not to be missed. If you never seen it, just wander around the park. For Strawberry Fields, take the C train to 72nd St.

Answer to the "Are Cab Drivers Honest?" Quiz

Nine.