Computational Complexity

Richard Guy is a mathematician. He co-authored the classic book Winning Ways for your Mathematical Plays with Elywn Berlekamp and John Conw...

By now you've probably heard the rumors of Google achieving quantum supremacy. I don't have inside information outside of Scott'...

Sitting around with three faculty we had the following conversation ALICE: When I applied to grad school in 1980 they saw a strong math ma...

I am teaching cryptography this semester for the second time (I taught it in Fall 2019) and will soon tell the students about the paper from...

Recall: A is a tally set if A ⊆ 1 * . A is a sparse set if there is a polynomial p such that the number of strings of length n is ≤ ...

You may have noticed, or not, that I haven't posted or tweeted much in the last month. I've had a busy time moving back to Chicago a...

In my last post I noted that if I am asked (since I am a CS prof) Can you fix my iphone is No, I work on the math side of CS Some r...

When I meet non-math people and tell them I am a computer science professor I get a range of responses. Here are some and my responses. ...

In Samuel Wagstaff's excellent book The Joy of Factoring (see here for a review) there is a discussion towards the end about why factor...

BILL: Darling, guess who is soon going to be on the Bank of England 50 pound note? DARLING: Alan Turing. BILL: How did you deduce that? ...

I've always felt a strong advisor/advisee relationship is the single most important factor in a successful PhD career. At its best, the ...

(This is a joint post with David Marcus. You'll see why later.) In a prior I posed two infinite hat problems. Today I post the solut...

(I will post the solution to the problem in the last blog later in the week---probably Thursday. Meanwhile, enjoy these thoughts from Samir...

This is a joint post with David Marcus. You will see how he is involved in my next post. Two infinite hat problems based on one scenario....

Hao Huang's proof of the sensitivity conjecture that I posted on last week relied on a 1992  result of Gotsman and Linial . Let's ...

(Joint Post with David Marcus who was a classmate of mine at SUNY Stony Brook [now called Stony Brook University]. I was class of 1980, he w...

The blogosphere is blowing up  over Hao Huang's just posted proof of the sensitivity conjecture, what was one of the more frustrati...

My father was a High School English teacher who did not know much math. As I was going off to college, intending to major in math, he gave ...

Georgia Tech FCRC Participants I'm heading home from the 2019 ACM Federated Computing Research Conference  in Phoenix, a collection ...

(title of this blog is due to Henry Baker who posted an article about this elsewhere) Amoeba finds approx solution to TSP in linear time: ...