NYU Visit
Last night, arrived in NYC by bus, met my friend Benjamin Chan for Indian food around 9pm. Decamped to his place at "the House" on Roosevelt Island. Slept on his too-short couch, which worked, barely. (My feet went on the coffee table.)
Went over my slides one more time, then had a leisurely breakfast with Ben (made-to-order omelettes!). Showered and put on my khakis and blazer. 5 min meditation, and I was off on the F Train to NYU's Warren Weaver building on 55th where my talk was scheduled for 11am. There 45 minutes early, I convinced the security guard to let me in prior to my host's arrival, and set myself up in the seminar room.
Professor Chris Musco, my host, arrived 15 minutes before 11 and we had a good conversation. He'd seen on my website I'd been at Jane Street--apparently he runs a high school math competition every year, and the finals are held at the Jane Street offices.
I'd been nervous all of yesterday about the talk, partially because I have some kind of mental block for rehearsing talks. I am currently simply incapable of giving a talk to the mirror exactly how I'd give it to the audience, without stopping and trying to improve things. This is a fascinating issue and one I'm actively looking to fix. But in any case, my fears were ill-placed. My work on the slides and reviewing all the details of the algorithm and related work paid off, and I gave the best rendition of the talk yet. Watching Bill Kuszmaul give his Cornell job talk had inspired me to give the talk a bit more emotional/historical richness. And having the extra slides explaining Fiat-Naor meant that I got more detailed questions and was able to show off my deep understanding of the problem a bit. (Also, one thing I should include in the next version of the paper; probably log(N)-wise independent hash functions should suffice to run the non-adaptive algorithm.)
After the talk, lunch was enjoined; fresh bagel sandwiches! I talked with Chris and another professor Richard Cole a little bit, and then sat down with a roast beef sandwich. Talked a while with a young woman Nikki Sigurdson who had just finished her PhD and now was working at a crypto company called ChainCode. Apparently it's actually a non-profit R&D thingy anonymously backed by retired financiers? Very confusing, slightly sus. But she was bullish about doing cryptography-related stuff in industry. She said a big part of her job was just explaining cryptography concepts to her coworkers. After that, I joined some of Chris's PhD students, who were talking about some numerical linear algebra stuff. Got coffee with Chris and his students, then walked to another NYU building 15 mins away. Went up to the 6th floor and played some ping pong!
Then we went to a talk by a professor from CMU, Anupam Gupta. It was a job-talk style talk about online algorithms. Very cool result for online set-cover and a problem I hadn't heard of before (online convex optimization) but could easily believe would have lots of optimizations. I found myself, now properly in academic character, asking questions without thinking about it.
Ensconced myself on the 5th floor and, after answering some urgent emails from Becky about adding people to the visit days Slack, started reading everything I could about Oded Regev--my academic grandfather, the legend who invented the modern foundations of lattice-based crypto and then decided to work in fundamental biology. After 30 minutes of reading about his new model for RNA splicing decisions, went to meet with him! We met in a temp office on the 7th floor, which was itself pretty cool--some kind of VR lab. He actually seemed impressed with my progress on the function inversion problem, which took a while to sink in. I protested that the result was technically simple and in hindsight, not too hard to see. But he insisted that nobody had seen it before, and it was a substantial improvement. That meant a lot, coming from Oded--a man whose taste for what to work on (according to Noah and others that knew him) was exceeded only by his meticulous technical ability. He seemed intrigued by the fact that no improvement to the 30-year-old impossibility result was known for the (intuitively) very weak class of non-adaptive algorithms, something which I'd emphasized in the talk. I got to inform him that indeed, no lower bound was known against an even weaker class of algorithms, and proving such a bound would entail new circuit impossibility results. Then I showed him our attempt to prove the bound by showing a lower bound on the number of colors needed to color a graph related to the function-inversion problem. We talked about possible approaches, including one I'd briefly considered, using a lower bound on the "fractional chromatic number" That one was kinda fun because Oded and I got confused about how the fractional chromatic number related to the usual chromatic number. I knew they were only off by a log(n) factor, but he was sure they couldn't be, because that would give an efficient algorithm for estimating the chromatic number to within that factor. The resolution--which I emailed Oded about later--is that the fractional chromatic number, even though it is given by a linear program, which usually can be computed efficiently, is given by a linear program with exponentially many variables. So in fact it cannot be computed efficiently (at least, we think).
Running out of time, so short finish to this one! Walked with Oded back to his home in the NYU apartments. He asked me some questions about ultimate since his sons were nearly teenage and looking for some fun sports. BTW, another cool family. This is []Oded's brother!](https://www.flytrex.com/)
Then I had a great dinner with my friend Akshay from undergrad. He went in straightaway and asked me lots of questions about research and cryptography. I made him promise that I could ask HIM questions at some point. Biggest sticking point was the point of worst-case to average-case reductions--I think it requires a decent amount of background knowledge to appreciate. He's engaged to my friend Amrutha, they met early at UW. She just quit Facebook to found a startup, which is cool because Akshay was big into startups--we met at an entrepreneurship club.
Back to the House, answered an email from Oded, did some other random reading, and crashed.