## Monday, May 18, 2015

### Theory Jobs 2015

In the fall we list theory jobs, in the spring we see who got them. Like last year, I created a fully editable Google Spreadsheet to crowd source who is going where. Ground rules:
• I set up separate sheets for faculty, industry and postdoc/visitors.
• People should be connected to theoretical computer science, broadly defined.
• Only add jobs that you are absolutely sure have been offered and accepted. This is not the place for speculation and rumors.
• You are welcome to add yourself, or people your department has hired.
This document will continue to grow as more jobs settle. So check it often.

Edit

1. "... or people your department has hired."

Oh my god, this is totally against data protection.
- What if the person beeing added does not want that? (The reason does not matter)

People please think! Don't choose convenience over security!!!

2. Interesting to note that with a very few exceptions, everyone who got a position this year (as well as last year) are not in computational complexity.

My impression is that most hiring were done in machine learning ("and theory"), or economics ("and theory"), etc. Correct me if I'm wrong please.

1. Don't think you are right re: econ!

2. You are not right. Just at a glance I see the names of Daniel Rossman, Andrew Drucker, Li-Yang Tang, Raghu Meka, and Anindya De who have done much of their work in Complexity Theory.

3. @CSprof,
Almost everyone you mentioned are from last year's hiring (except Rossman and Meka).
So this leaves us with two-three complexity scientists from about 30 people hired this year (listed above).
I think that indeed most people hired this year are from machine learning, and other more fashionable current derivatives of TCS (differential privacy, etc.), and not core theory.

4. Only Katrina Ligett is a differential privacy person on this list. (Jeremiah Blocki has two differential privacy papers, and Boaz has one, but for neither of them is this a central aspect of their work.)

There are plenty of algorithms people on this list who work on "core theory": Andoni, Kapralov, Peng, Sidford, Schwartz, Li, Bhaskara, Raichel for example. (I do not mean to be an exhaustive list especially for such an ill defined notion.) Suggesting that "core theory" is restricted to complexity theory is ridiculous.

5. And still, I stand by my claim that out of about thirty five recruited people, no more than 3-2 are in complexity theory (excluding senior people movements within academia).

(Note also that the original comment was written before all these people from algorithms have appeared on the list).

3. Yes, this is totally against privacy and data protection.
You should always ask permission before adding someones name. Only people who are willing to display their personal info, should be added.

4. Why do I think that above comment is written by Richard Stallman?

5. The whole point of the web and current technological progress is to hinder privacy. There is no more privacy when everything is recorder online somewhere.

In this sense, indeed, advance in technology is not necessarily a good thing. On the contrary, some may say.

6. Rossman is solidly a complexity theorist. I actually don't see too much AGT on that list. But plenty of crypto and algorithms.

1. Yes, Benjamin Rossman is doing logic and complexity.

7. hi, it would be cool if you blogged on the response to your new book Golden Ticket. hows it going? what do you think, was it worth writing? here is some near "fighting words" by a hardcore insider in the field good intro to turing/ complexity theory

8. Its nice to see Drexel making a big move to build a theory group!

9. Does Samsung have a sustainable basic research group? Can the people joining there let us know what impressed them?

10. Any news/gossip about the movement of more senior academics (e.g. tenured faculty)?

11. Dear Professor,

I have found a new complexity class that I called equivalent-P" and I have showed it has a close relation with the P versus NP Problem. I have been making a paper that explain my ideas, and in the meantime, I decided to share them as a preprint in the web.

Here, I show you the abstract of the paper (so you can capture the idea):

The P versus NP problem is one of the most important and unsolved problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? This incognita was first mentioned in a letter written by Kurt Gödel to John von Neumann in 1956. However, the precise statement of the P versus NP problem was introduced in 1971 by Stephen Cook in a seminal paper. We consider a new complexity class, called equivalent-P, which has a close relation with this problem. The class equivalent-P has those languages that contain ordered pairs of instances, where each one belongs to a specific problem in P, such that the two instances share a same solution, that is, the same certificate. We demonstrate that equivalent-P = NP and equivalent-P = P. In this way, we find the solution of P versus NP problem, that is, P = NP."

In this preprint, I shall show that there is an NP-complete problem in equivalent-P and a P-complete problem in equivalent-P. Moreover, I shall show the complexity class equivalent-P is closed under reductions. Since P and NP are also closed under reductions, then we can conclude that P = NP.