Refine your search:

From Computational Complexity
#### Lance and Bill go to Dagstuhl: The Riemann Edition

Lance: Welcome to our typecast directly from Dagstuhl in Southwestern Germany for the 2018 edition of the seminar on Algebraic Methods in Computation Complexity...

From Computational Complexity
#### Why wasn't email built securely?

Recently I talked with Ehsan Hoque, one of the authors of the ACM Future of Computing Academy report that suggested "Peer reviewers should require that papers and...

From Computational Complexity
#### P = NP and Cancer

Often when the question comes to what happens if P = NP, one typically hears the response that it kills public-key cryptography. And it does. But that gives the...

From Computational Complexity
#### Are Conferences Discriminatory?

Glencora Borradaile wrote a blog post in June about how conferences discriminate.
Let me spell it out. In order to really succeed in most areas of computer science...

From Computational Complexity
#### What is Data Science?

The Simons Institute at Berkeley has two semester long programs this fall, Lower Bounds on Computational Complexity and Foundations of Data Science. The beginning...

From Computational Complexity
#### Katherine Johnson (1918-)

Katherine Johnson is celebrating her 100th birthday today. This is the first centenary post we've done for a living person.
The movie Hidden Figures made her story...

From Computational Complexity
#### The Zero-One Law for Random Oracles

A couple of years ago, Rossman, Servedio and Tan showed that the polynomial-time hierarchy is infinite relative to a random oracle. That is if you choose each string...

From Computational Complexity
#### While I Was Away

After the Oxford Workshop I enjoyed a two-week family vacation in Spain, where there was no rain in the plain, just very hot up to 106℉. The old Spanish citiesMeanwhile...

From Computational Complexity
#### Complexity in Oxford

Oxford, England is in the middle of a heat wave and it handles high temperatures about as well as Atlanta handles snow. But that can't stop the complexity and a...

From Computational Complexity
#### CRA Snowbird 2018

Marios Papaefthymiou (UC Irvine), Michael Franklin (U. Chicago), Larry Birnbaum (Northwestern) and me.
This week I attended the 2018 Computing Research Association...

From Computational Complexity
#### The Mystical Bond Between Man and Machine

You just can't watch a movie these days without being inundated with trailers. First came Axl, a movie about a boys love for a military robotic dog.
"It's...

From Computational Complexity
#### Happy 90th Juris!

Juris Hartmanis turns 90 today. Hartmanis with Richard Stearns received the 1993 Turing Award for their seminar work On the Computational Complexity of Algorithms...

From Computational Complexity
#### STOC 50 Part II

On Wednesday, STOC had a great complexity session and the best complexity paper of the conference, Cody Murray and Ryan Williams extending Ryan’s celebrated result...

From Computational Complexity
#### STOC 50 Part I

This week I'm in Los Angeles attending the 50th Symposium on the Theory of Computing. Most attendees weren't even born before the first STOC. Many of them weren't...

From Computational Complexity
#### Hoteling

Thanks to Grigory Yaroslavtsev for taking over the Theory Jobs Spreadsheet. Details on Grigory's blog. Check out who is going where next year.
My office...

From Computational Complexity
#### BQP not in the Polynomial-Time Hierarchy in Relativized Worlds

The quantum complexity world is a rocking with the paper released yesterday by Ran Raz and Avishay Tal, Oracle Separation of BQP and PH, resolving a question open...

From Computational Complexity
#### Seventh Grade Math Contest

I stumbled upon an old blog post on the Lesswrong weblog that quotes several famous mathematicians on the connections, or lack thereof, between mathematics competitions...

From Computational Complexity
#### Kolmogorov Complexity and Causation

I got an interesting email question.
Suppose I give you a set of points S of the form (x,y). He suggested ideally they would be pairs of a real numbers. Supposing...

From Computational Complexity
#### The Complexity of the Firm

In 1937, a year after Turing had his seminal paper, Ronald Coase published a paper The Nature of the Firm to give a framework to why we have companies and how large...

From Computational Complexity
#### Richard Feynman (1918-1988)

When I took cryptography from Manuel Blum, he handed out copies of the chapter "Safecracker Meets Safecracker" from Richard Feynman's book Surely You're Joking...