Computational Complexity

Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch

Wednesday, March 29, 2023

Alan Turing, The Opera

›
  Last Thursday I attended the world premier of The Life and Death(s) of Alan Turing , a new production from Chicago Opera Theater composed ...
Sunday, March 26, 2023

The SIGACT Book Review column list of books it wants reviewed

›
I am posting this for Nick Tran who is the current SIGACT Book Review Editor (before him it was Fred Green for about 6 years, and before him...
7 comments:
Thursday, March 23, 2023

A Strange Hiring Season

›
In my fall jobs post , I had trouble predicting this season's CS faculty job market but I didn't expect this:  strong supply and str...
1 comment:
Sunday, March 19, 2023

New Upper Bound on R(k). WOW!

›
 R(k) is the least n such that for all 2-colorings of the edges of \(K_n\) there is a monochromatic \(K_k\) (so there are k vertices such th...
4 comments:
Thursday, March 16, 2023

Identities in Computational Complexity

›
Guest post by Josh Grochow On the birdsite, Jay Cummings tweeted : TOP 5 IDENTITIES OF ALL TIME 5. You 4. Can't 3. Rank 2. Identities...
6 comments:
Monday, March 13, 2023

Problems we assume are hard. Are they? ALSO- revised version of Demaine-Gasarch-Hajiaghayi is posted!

›
 (The latest version of  Computational Intractability: A Guide to Algorithmic Lower Bounds by Demaine-Gasarch-Hajiaghayi is posted  here . I...
6 comments:
Monday, March 06, 2023

Peer Review

›
I ran into a partner of a computer scientist at a social event who asked me "Is the publication system in CS screwed up or really screw...
3 comments:
Thursday, March 02, 2023

Goodbye Dilbert

›
Scott Adams, creator of Dilbert, had a racist rant in a video he posted last week. As a result most newspapers that carried the comic strip ...
7 comments:
›
Home
View web version
Powered by Blogger.