Tuesday, September 02, 2014

How hard is changing fields? Ask Sheldon!

In the last season of  The Big Band Theory Sheldon wants to change field from String theory to something else (I don't recall if he settled on what it would be, though Standard Model Physics, Quantum Loop Gravity, Calculation of nuclear matrix elements, were mentioned negatively, and Geology is, according to Sheldon, not a real science.)

Sheldon faced opposition from his department. And since Physics is... hard... changing fields seems hard.
How hard is it to change fields, both intellectually and in terms of your dept?

  1. If you are hired as a string theorist and you are one of the only ones in your dept, your dept may quite reasonably ask you to still teach string theory. I think this is fine.
  2. Math and Physics are far older than CS so to change fields requires learning more background knowledge. In CS it was easier about 20 years ago, but CS has grown so much that I suspect it would be harder now.
  3. There may be a time when you have less papers and grants as you are making the transition. Hence it may be unwise to do this before you get Tenure.
  4. If your dept hired you to do String Theory and you change to Calculation of nuclear Matrix elements should they mind that? I would think that as long as it's still good work they wouldn't. And they should give you enough time to get grants and papers in it. If you change to a field they don't care about, or change to a field not in the area they might not like that. If Sheldon went into Computational Complexity then would his dept (physics) be justified in not liking that?  If he solved P vs NP then all would be forgiven.
  5. Perhaps the further away you change from your field the better your work has to be before your dept doesn't mind. This could be modelled by a formula. Maybe Sheldon will change to computational dept dynamics and derive it for us.
  6. The obvious thing to say is Depts should allow their professors to wander free as a bird and not erect arbitrary walls since the best work comes from people not being constrained. I would like to think this is true but I wonder--- how many people have changed fields and ended up doing great work? good work? totally failed?

Thursday, August 28, 2014

Sixteen Years in the Making

Every paper has a story but Sunny Daniel's Arxiv paper from yesterday deserves a blog post.

We begin in 1982 when Ravi Kannan proved that Σ2 (the problems computable in NP with an NP oracle) cannot have n2 size circuits. Kannan's result hold for nk-size circuits but for this story we'll keep it simple.

Kannan had an ingeniously simple proof. By diagonalization you can create a language L in Σthat does not have n2-size circuits. Now there are two cases:
  1. SAT doesn't have n2-size circuits. Since SAT is in Σ2 we are done.
  2. SAT has n2-size circuits. Then by Karp-Lipton Σ4 = Σ2 so L is in Σ2 and we are done.
Kannan's proof is non-constructive and doesn't give an explicit Σ2 language that we can show doesn't have n2-size circuits. Either SAT or L but one can't be sure which one.

In 1998, Sunny Daniels, a PhD student at Rutgers, took Eric Allender's complexity course. Eric offered up a constructive example of Kannan as an open problem. Sunny came up with a solution. He wrote up a draft in LaTeX but for personal reasons dropped out of academics and never published the paper.

In 2003, Jin-Yi Cai and Osamu Watanabe, not aware of Daniels' paper, came up with their own independent construction and presented their paper at the COCOON conference in Montana. Word got back to Sunny but he thought he had lost the LaTeX file and didn't want to retypeset the whole proof.

Sunny had Iomega Zip Drive cartridges from his Rutgers days. Recently he found someone who had a Zip Drive reader and managed to recover the files. In there he discovered the original LaTeX, cleaned the paper up, and sixteen years after his proof put the paper on ArXiv. Even if you don't care about the math, read the introduction for the complete version of this story.

Kannan's proof actually shows Σ2∩Π2 does not have n2-size circuits and this was later improved to S2P. Whether we have any constructive language in Σ2∩Π2 or S2P without n2-size circuits still remains open. 

Monday, August 25, 2014

A Deadly Side of Complexity

Better algorithms can lead to better medicine and save lives. Just today Tim Gowers discusses Emmanuel Candès' ICM Plenary Lecture, which among other things describes how Candès' work on compressed sensing leads to shorter MRI scans for children, greatly reducing the risk of oxygen deprivation. Prove P = NP with a practical algorithm, and you'll conquer that worst of our diseases. Sounds great until you realize what we can't do.

I was talking to a cancer researcher recently and he points out that many of their challenges are indeed algorithmic. But he also brings up the contrapositive. Since we don't have great algorithms now, we don't know how to make sense of DNA sequences and in particular don't know how to map genetic markers to an appropriate cancer treatment. He works with cancer patients, knowing he can't give them the best possible treatment, not because of lack of data, but due to lack of ways to analyze that data. People die because we don't have the ability to break through the complexity of these algorithmic challenges.

Thursday, August 21, 2014

Turing's Oracle

My daughter had a summer project to read and summarize some popular science articles. Having heard me talk about Alan Turing more than a few times, she picked a cover story from a recent New Scientist. The cover copy says "Turing's Oracle: Will the universe let us build the ultimate thinking machine" sounds like an AI story but in fact more of an attack on the Church-Turing thesis. The story is behind a paywall but here is an excerpt:
He called it the "oracle". But in his PhD thesis of 1938, Alan Turing specified no further what shape it might take...Turing has shown with his universal machine that any regular computer would have inescapable limitations. With the oracle, he showed how you might smash through them. 
This is a fundamental misinterpretation of Turing's oracle model. Here is what Turing said in his paper Systems of Logic Based on Ordinals, Section 4.
Let us suppose we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. We shall not go any further into the nature of the oracle apart from saying it cannot be a machine. (emphasis mine)
The rest of the section defines the oracle model and basically argues that for any oracle O, the halting problem relative to O is not computable relative to O. Turing is arguing here that there is no single hardest problem, there is always something harder.

If you take O to be the usual halting problem then a Turing machine equipped with O can solve the halting problem, just by querying the oracle. But that doesn't mean that you have some machine that solves the halting problem for, as Turing has so eloquently argued in Section 9 of his On Computable Numbers, no machine can compute such an O. Turing created the oracle model, not because he thought it would lead to a process that would solve the halting problem, but because it allowed him to show there are problems even more difficult.

Turing's oracle model, like so much of his work, has played a major role in both computability and computational complexity theory. But one shouldn't twist this model to think the oracle could lead to machines that solve non-computable problems and it is sacrilege to suggest that Turing himself would think that.

Monday, August 18, 2014

Complexity versus Algorithms: The FOCS Challenge

In recent years, I've heard complaints from my complexity colleagues that FOCS and STOC are mostly algorithms and from the algorithm buddies that STOC and FOCS are mostly complexity. What exactly counts as a complexity or algorithms paper has become quite blurred in recent years. So let's try an experiment. Below is a poll I've created using titles from the upcoming FOCS conference. Which of these papers do you consider complexity? Does complexity in the title make them a complexity paper? 

If you are interested, you can find the manuscripts for most of these papers on the FOCS accepted papers list.

survey tools

Disclaimer: This is a completely non-scientific poll solely for the interest of the readers of this blog. The results will have no effect on future conference papers.

Thursday, August 14, 2014

Favorite Theorems: Limited Independence

When can limited randomness act as well as true random bits?
Polylogarithmic independence fools AC0 circuits by Mark Braverman (JACM 2010)
To explain this result consider choosing uniformly from among the following four strings:
000 110 101 011
If we look at any two of the bits, say the first and third, all four possibilities 00 10 11 01 occur. The sequence is thus 2-wise independent. We can get 2-wise independence using only two random bits to choose one of the four strings. In general one can get k-wise independent in n-bit strings using O(k2 log n) random bits.

Braverman shows that any polylogarithmic independent distribution fools polynomial-size constant-depth circuits (AC0), or more precisely for a size s depth d circuit C, for k=(log (m/ε))O(d2), the probability that C will output 1 with uniformly-random inputs will differ at most ε from the probability C outputs 1 from inputs chosen from a k-wise random distribution. Braverman's result followed after Bazzi and Razborov proved a similar result for depth-2 circuits (CNF formulas).

Another nice result along these lines: Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio and Emanuele Viola show that Bounded Independence Fools Halfspaces. A half-space is just a weighted threshold function (is the sum of wixi at most some given θ). Diakonikolas et al. show that one can fool halfspaces with k=O(ε-2log2(1/ε)), in particular for constant ε, k is a constant independent of the number of variables.

Tuesday, August 12, 2014

Subhash Khot wins Nevanlinna

At the opening ceremonies of the International Congress of Mathematicians in 2014, Subhash Khot was awarded the Rolf Nevanlinna Prize, given every four years to an under-40 researcher for outstanding contributions in Mathematical Aspects of Information Sciences. Subhash's citation reads
Subhash Khot is awarded the Nevanlinna Prize for his prescient definition of the “Unique Games” problem, and leading the effort to understand its complexity and its pivotal role in the study of efficient approximation of optimization problems; his work has led to breakthroughs in algorithmic design and approximation hardness, and to new exciting interactions between computational complexity, analysis and geometry.
Khot's work has indeed generated a large research agenda over the last decade. I highlighted his work in March's favorite theorems post.

In other big news, we have our first female Fields Medalist Maryam Mirzakhani for contributions to the dynamics and geometry of Riemann surfaces and their moduli spaces. Still no female winners among the nine Nevanlinna winners. Artur Avila, Manjul Bhargava and Martin Hairer also received Fields medalists. Stanley Osher won the Gauss Prize, Phillip Griffiths the Chern Medal and Adrián Paenza the Leelavati Prize.

Pictures and press releases and citations of all the prize winners.

Monday, August 11, 2014

Questions that arose teaching High School students crypto

I taught a 3-week, 3-hours-a-day course to High School student titled

Computer Science: A Hands Off Approach.

Given that time constraints and the fact that some already know (say) Java and some don't know any language, this seemed like a good choice.

I decided to teach mostly pre-RSA crypto with the following theme: Alice and Bob want to pass secret messages. How do they do it? I cover Shift, affine, general sub, Vigenere, Matrix, 1-time pad, Diffie-Helman (a highpoint of the course since Alice and Bob don't have to meet in a dark alley). In also did secret sharing with polynomials, error correcting codes (elementary), Huffman codes, and some applications of mod arithmetic.

While teaching this course some points of interest came up. I suspect most are know and I appreciate polite comments telling me so.

  1. A student suggested this cipher:   code a,b,c,...,z into a 100-letter alapahbet and map each letter to a set of symbols that is the size of the freq. For example, if e occurs 9% of the time then map e to 9 letters. Then use those letters at random. This would seem to foil freq analysis? Does it?  Has it been used? What are the downsides.
  2. Many students suggested using Vigenere but instead of having every xth letter be done by a different shift, have it be affine or general. Of course this can be cracked the same way Vig is cracked. But it does raise an interesting point: Which ciphers are used and not used can be the based on when things were discovered. Martians may very well have used some kind of Vig where every xth letter is a different gen sub cipher.
  3. Wikipedia and other sources say that the Vig cipher was unbroken for 300 years. A student pointed out that it might have been broken but the one who broke it didn't say. Jon Katz (crypto prof at UMCP) can't believe it wasn't broken immediately, but of course hindsight is 20-20.
  4. (I have commented on this before) A matrix cipher with a 10x10 matrix seems uncrackable using plaintext only.  I have made this question rigorous here.
  5. I made the comment that 1-time pads are not used much (is this even true? Might depend on the definition of ``must'') because getting a perfect source of randomness is hard. During WW II they also would be hard to use because its hard to carry around a billion bits. But now that would not be a problem. Again--if history had been different we may use 1-time pads, or quasi-random ones today!
  6. I told the students about arithmetic mod n. One of the students really really didn't like that (say) in mod 7 we have 1/3 = 5. He REALLY wants 1/3 to be between 0 and 1. I suspect he didn't care much for discrete logs either. This was a GOOD student- so his objection was not that it was hard.
  7. For some of the students their first exposure to matrices was matrix codes over mod 26. I hope they can recover from that.
  8. Most of the students know what logs were, but weren't that comfortable with them. And here I go and teach them discrete logs! I hope they can recover from that.
  9. I showed the students that there were quadratic equations over mod 12 with more than 2 roots and challenged them to see how many roots they could come for other mods. One of my students ran massive computer tests and found stuff and in the end had a result that didn't need all of his computations:  x^2 \equiv 0 mod n^2 has n roots. And I later had on a HW x^a \equiv 0 mod n^a. I am sure none of this is new, but its new to him when he discovered it and of course new to the class when I taught it.
  10. I taught the class the Baby-Step/Giant-Step Discrete Log algorithm which has sqrt(p) prepocessing an sqrt(p) running time. Its not used because it also takes sqrt(p) space; however, it was good to show them that Discrete Log can be done in sqrt(p) time, much better than p time--- hence Alice and Bob need to pick their parameters larger than they may have thought when doing Diffie-Helman. That night I easily worked out that it can be modified to do p^{2/3} preprocessing (and space) but just p^{1/3} time. HW was p^a prep, p^{1-a} time. One of the students inquired if this algorithm has a name. I then looked over the web but couldn't find it anywhere so I told them to call it  The Gasarch Variant of Baby-Step, Giant-Step. I also quickly told them to NOT be impressed--- and this helped me make a point I had made often, that CS is a NEW field, so NEW that one can present new or newish results to HS students. I also made the point that I am sure this variant is KNOWN to anyone who would care, but (1) they may not care since it takes even more space if x is larger than 0.5  and more time if x is less than 1/2  and (2) not everything is no the web. That last point freaked them out more than the quadratic equation mod 12 that had more than two roots.
UPSHOT- teaching HS students CS can bring up some issues that you had not thought of. Or at least that I had not thought of.