Refine your search:

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

From Computational Complexity
#### Broader Impacts Redefined

The ACM Future of Computing Academy suggests that "peer reviewers should require that papers and proposals rigorously consider all reasonable broader impacts, both...

From Computational Complexity
#### Memory is Hot

A good number of the faculty candidates interviewing at Georgia Tech have a common theme: Memory. Memory connected to databases, to programming languages, to...

From Computational Complexity
#### Lance and Bill Gather for Gardner

Every two years in Atlanta, recreational mathematicians gather to honor Martin Gardner, whose Scientific American column Mathematical Games through the 60's and...

From Computational Complexity
#### Almost Famous Quantum Polynomial Time

I have been playing with a new complexity class AFQP, defined in a yet-to-be-published manuscript by Alagna and Fleming. A language L is in AFQP if there is a polynomial...

From Computational Complexity
#### A Reduced Turing Award

A Turing machine has an extremely simple instruction set: Move left, move right, read and write. If you want to do real programming, you need something a bit...

From Computational Complexity
#### Stephen Hawking (1942-2018)

Stephen Hawking passed away earlier this morning in Cambridge, England. As a brilliant theoretical physicist and best-selling author all while dealing withA...

From Computational Complexity
#### Data-Driven Programming

Five years ago I posted about Flash Fill, a then new Microsoft Excel feature that would reformat data based on examples. I just checked the latest version of Excel...

From Computational Complexity
#### Me and My Bolt

On Tuesday I got a knock on my car's window. Rolling it down someone asked if I liked my car as he was thinking of buying one himself. Was I driving the...

From Computational Complexity
#### NP is Hard

You don't get much press by stating conventional beliefs--there is no "round earth society". Nevertheless there are serious researchers out there trying to sayI...

From Computational Complexity
#### Corporate Education

First of all read the #metoo testimonial going around the TCS blogosphere. Our field is not immune.
Last Sunday Frank Bruni wrote an op-ed column Corporations,...

From Computational Complexity
#### For the Love of Algorithms

Wired magazine labelled 2017 as The Year We Fell Out of Love with Algorithms. The article goes on to talk about how algorithms give us filter bubbles, affect elections...

From Computational Complexity
#### Flying Blind

Many computer science conferences have made a number of innovations such as a rebuttal phase, multi-tiered program committees, a hybrid journal/conference model...

From Computational Complexity
#### From Art to Science

Q: Why did the neural net cross the road?
A: Who cares along as it got to the other side.
Whit Diffie and Martin Hellman in their classic 1976 paper talk about...

From Computational Complexity
#### A Sensitive Game

Last month I posted about the sensitivity conjecture and today I would like to talk about an interesting game developed by Gilmer, Koucký and Saks and independently...

From Computational Complexity
#### Donald Knuth Turns Eighty

We've kept this blog going long enough that we start repeating our celebrations. Ten years ago Bill celebrated Don Knuth's 70th Birthday and today Donald Knuthcelebrates...