Refine your search:

From Computational Complexity
#### Inverting Onto Functions

Here's an open question that goes back to a 2003 paper that I wrote with Steve Fenner, John Rogers and Ashish Naik. The conference paper goes back to 1996.
In...

From Computational Complexity
#### Remembering George H. W. Bush

Today is the national day of mourning for George Herbert Walker Bush, one of the best presidents for science and computing. He created PCAST, the President's...

From Computational Complexity
#### LOGCFL Venkat Style

H. Venkateswaran, a much loved professor in the School of Computer Science at Georgia Tech and a fellow computational complexity theorist, is retiring at the end...

From Computational Complexity
#### Simons and Amazon

I'm spending this week at the Simons Institute in smokey Berkeley, California. This fall Simons has a program in Lower Bounds in Computational Complexity. Scroll...

From Computational Complexity
#### The Data Transformation of Universities

With all the news about elections, caravans, shootings and attorney generals, maybe you missed the various stories about real transformations at our top universities...

From Computational Complexity
#### P = NP Need Not Give a SAT Algorithm

In Bill's post earlier this week, he asks if there is a fixed algorithm such that if P = NP, this algorithm will correctly compute satisfiability on all inputs....

From Computational Complexity
#### Good Results Made Meaningless

Sometimes you see a beautiful theorem A that you love to talk about. Then another beautiful theorem B comes around, making the first one meaningless since B trivially...

From Computational Complexity
#### A New Cold War?

Imagine the following not-so-unrealistic scenario: The US-China trade war deepens leading to a cold war. The US blocks all Chinese citizens from graduate school...

From Computational Complexity
#### 2018 Fall Jobs Post

As we do every year at this time, we help you find that perfect academic job. So who's hiring in CS this year? Perhaps we should instead follow the advice of John...

From Computational Complexity
#### Muffin Math

Lance: It's Friday afternoon and the Dagstuhl workshop has ended. We have some time before we need take off so how about one final typecast.
Bill: Always a good...

From Computational Complexity
#### Still Typecasting from Dagstuhl

Lance: Bill, in our typecast earlier this week I said you were older than me. But 68? You don't look day over 66.
Bill: Neither do you. But seriously, why do you...

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...