Refine your search:

From Computational Complexity
#### Physics of Everday Life

Based on Scott's review, I read through Stephen Pinker's Enlightenment Now. I can't top Scott's exposition of the book, but it is pretty incredible how far humanity...

From Computational Complexity
#### Cuckoo Cycles

Guest Blog by John Tromp (Thanks for the opportunity, Lance)
In the past few months, cycle finding has become one of the most widely run
graph theory problems....

From Computational Complexity
#### Scooped

At Dagstuhl I got a few ideas for future posts but then...
We had some discussions about STOC allowing program committee members to submit papers that I planned...

From Computational Complexity
#### Back at Dagstuhl

Participants and Their Research Interests
This week I'm in Germany for the Dagstuhl workshop on Computational Complexity of Discrete Problems well timedtypecast...

From Computational Complexity
#### Captain Einstein

If the president of the United States uses "complexity" in a tweet, I can't leave it alone.
Airplanes are becoming far too complex to fly. Pilots are no longer...

From Computational Complexity
#### QED

Via Scott, John Horgan wrote a blog post following on his 1993 Scientific American article The Death of Proof. The article talked about computer-generated proofs...

From Computational Complexity
#### Flying Pigs Unsafe at Any Speed

Take a moment and imagine a flying pig. Do you see a pig with tiny wings lazily guiding along. But pigs are not particularly slow animals as anyone has seen a pig...

From Computational Complexity
#### Extra! Extra! Read all about it!

Last weekend I saw the documentary Joseph Pulitzer: Voice of the People. Pulitzer, as you probably know from the prize named after him, was a major newspaper publisher...

From Computational Complexity
#### The iPhonification of Everything

So you've got an iPhone XS in Space Grey. Congrats, so do 20 million other people. Maybe you have different cases but otherwise the hardware in all these phones...

From Computational Complexity
#### An Immerman-Szelepcsényi Story

As a grad student in the late 80's I had the opportunity to witness many great and often surprising theorems in computational complexity. Let me tell you aboutnondeterministic...

From Computational Complexity
#### Phish Before Turkey

The Chronicle of Higher Education recently published a story Phishing Scheme Targets Professors’ Desire to Please Their Deans — All for $500 in Gift Cards. TheFrom...

From Computational Complexity
#### Machine Learning and Wind Turbines

My daughter Molly spent six weeks on an environmental program in China last summer. When she got back she had to do a report on machine learning and wind turbines...

From Computational Complexity
#### The Cost of Privacy

Billboard at 2019 CES
Computer scientists tend to obsess about privacy and we've had a privacy/security debate for decades now. But now machine learning has...

From Computational Complexity
#### Search versus Decision

Shockingly I've never done a post on search versus decision, one of the more interesting dualities in complexity. In short: Decision: Is there a needle in the haystack...

From Computational Complexity
#### Complexity Year in Review 2018

Result of the year goes to
Oracle Separation of BQP and PH by Ran Raz and Avishay Tal
which we wrote about in June. This work solves one of the original openQuanta...

From Computational Complexity
#### Ker-I Ko (1950-2018)

A few weeks ago as Bill and I prepared for our upcoming year in review post, we noted that we hadn't lost any theoretical computer scientists this year, at least...

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