On Sunday we had the Symposium on Theoretical Computer Science on the Occasion of Michael Sipser's 60th birthday to celebrate what Mike has brought to research (seminal work on the complexity of randomness and circuits), service (ten years leading the MIT math department before recently becoming Dean of Science) and education (his great textbook and the corresponding popular course he still teaches).
We had an incredible turnout for the symposium and banquet that followed. I counted five Turing Award Winners (Mike's advisor Manuel Blum, Leslie Valiant, Shafi Goldwasser, Silvio Micali and Ron Rivest), five of the nine Nevanlinna Prize winners (Mike's student Daniel Spielman, Avi Wigderson, Valiant, Peter Shor and Madhu Sudan) and nine Gödel Prize winners.
Manuel Blum talked about his work with Jeremiah Blocki, Anupam Datta, and Santosh Vempala about a human computable hash function to create different passwords for every website. I've seen Manuel and Santosh produce passwords from arbitrary words and I'm impressed.
Johan Håstad recounted the early days of circuit complexity. Avi also talked about lower bounds. Shafi talked on her great paper with Mike showing public and private coin interactive proofs have the same power and a recent application of that result by Moni Naor et al showing how a defendant can convince the police his DNA doesn't match without revealing his DNA.
A number of Mike's PhD students also gave talks. Dan Spielman gave a framework for designing quantum algorithms without knowing much quantum.
The banquet included several stories, thanks and toasts. Nearly all of Mike's students participated in some way, a great collection of men and women I'm proud to be part of: David Barrington, Ravi Boppana, Jonathan Buss, Andrew Chou, Aditi Dhagat, Lance Fortnow, David Gillman, Michelangelo Grigni, Christos Kapoutsis, Marcos Kiwi, Mary (Bruzzese) O'Connor, Sofya Raskhodnikova, Zack Remscrim (current), Alexander Russell, Leonard Schulman, Daniel Spielman, Ravi Sundaram, Andrew Sutherland and Yiqun Yin .
Wish the talks were recorded and uploaded on youtube.
ReplyDeleteWhat's the framework for designing quantum algorithms without knowing quantum?
ReplyDelete2nd the wish for youtubed video talks.
ReplyDeletesipsers circuit model is one of the great innovations of theoretical CS.
suspect it is the closest to a P vs NP proof & more.
see also outline for a NP vs P/poly proof based on monotone circuits, hypergraphs, factoring, and slice functions
Anon 8:56 -- It's called "adiabatic quantum computing" -- Dan's abstract was:
ReplyDeleteThe adiabatic approach to quantum computing was introduced in a provocative paper of Farhi, Goldstone, Gutmann and Sipser. While it is known to be equivalent in computational power to the model of quantum circuits, it seems much easier to design algorithms using the adiabatic approach. The designer knows exactly what the adiabatic algorithm will compute. The hard part is figuring out how long it will take. This is very different from the design of algorithms in the quantum circuit model, in which the number of computation steps is determined, but it can be very difficult to figure out what a given circuit actually computes.
We will demonstrate the elegance of the adiabatic quantum computing by presenting a simple adiabatic algorithm for solving large systems of linear equations. A quantum circuit for solving this problem was originally described by Harrow, Hassidim and Lloyd.
This is joint work with Nicholas Read.
Academia in the US perpetuates strange forms of sycophancy. One involves junior faculty frequently biting their tongue in the presence of senior colleagues for fear of jeopardizing their tenure case. Another is the celebration in honor of an advisor reaching a landmark age. These celebrations are often independent of the merits of the person as an advisor or as a researcher. And many times they turn into exercises in self-aggrandizement where the advisees exult in their membership in an exclusive elite.
ReplyDeleteIt is a long custom and not restricted to US. You can see similar events in Europe. It is honoring and respecting people who contributed to the field. It is kind children gathering together to honor their parents.
ReplyDeleteThat said, it is a bit unusual that so many people in this area are academic relatives. It makes one wonder if the effect of networking is too much in the field.
I have never met Michael Sipser and know him only through his work. IMHO he is deserving of even more accolades than have been showered upon him. Having said that I do acknowledge that there are instances in academics where junior colleagues wrongly praise senior people.
ReplyDelete