Refine your search:

From Computational Complexity
#### William Kruskal's 100th birthday

Today, Oct 10, 2019 is William Kruskal's 100th birthday (he's dead, so no cake. Oh well.) William Kruskal was a great statistician. To honor him we have a guest...

From Computational Complexity
#### What comes first theory or practice? Its Complicated!

Having majored in pure math I had the impression that usually the theory comes first and then someone works out something to work in practice. While this is true...

From Computational Complexity
#### Quantum Supremacy: A Guest Post by Abhinav Deshpande

I am delighted to introduce youto Abhinav Deshpande, who is a graduate student at the University of Maryland, studying Quantum Computing. This will be a guest post...

From Computational Complexity
#### Richard Guy is 102 years old today

Richard Guy is a mathematician. He co-authored the classic book Winning Ways for your Mathematical Plays with Elywn Berlekamp and John Conway.
On Sept 30 (today)...

From Computational Complexity
#### Applicants to Grad School are too good. Here is why this might be a problem.

Sitting around with three faculty we had the following conversation
ALICE: When I applied to grad school in 1980 they saw a strong math major (that is, I had good...

From Computational Complexity
#### this paper from 2015 cracks Diffie-Hellman. What to tell the students?

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 2015:
Imperfect Forward...

From Computational Complexity
#### Random non-partisan thoughts on the Prez Election

This post is non-partisan, but in the interest of full disclosure I disclose that I will almost surely be voting for the Democratic Nominee. And I say almost surely...

From Computational Complexity
#### Are there any natural problems complete for NP INTER TALLY? NP INTER SPARSE?

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 ≤ p(n).
If there existsthis...

From Computational Complexity
#### Can Mathematicians Fix Iphones? Can anyone?

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 readers emailed me (I told...

From Computational Complexity
#### `Are you a math genius?' `Can you fix my Iphone?' `What do you think about Facebook and Privacy?'

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.
1) Are you a math genius...

From Computational Complexity
#### Obstacles to improving Classical Factoring Algorithms

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

From Computational Complexity
#### Turing to be on the Bank of England 50 pound note, giving me an excuse to talk about Turing

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? (She is right, see here...

From Computational Complexity
#### Answer to both Infinite Hats Problems from the last post

(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 solutions. Actually this is a....

From Computational Complexity
#### Guest post by Samir Khuller on attending The TCS Women 2019 meeting

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

From Computational Complexity
#### Two infinite hat problem and a question about what is ``well known''

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. I am also curious if...

From Computational Complexity
#### Fortran is underated!

(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 was class of 1979. We...

From Computational Complexity
#### A proof that 22/7 - pi > 0 and more

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 me the following sage...

From Computational Complexity
#### Are you smarter than a 5th grade amoeba?

(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:here.
Over the yearshere...

From Computational Complexity
#### Why does the Nevalina Prize (now Abacus) got to Algorithms/Complexity people

In my post about the Nevanlinna prize name change (see here) one of my readers raised a different question about the prize:
BEGIN QUOTE
So there's one of...

From Computational Complexity
#### Ray Miller, one of our founders, Passes away at the age of 90

Ray Miller, one of the founders of our field, passed away recently at the age of 90.
He has associations with both GA Tech and The University of Maryland, so both...