Computational Complexity

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

Tuesday, June 28, 2022

A Gadget for 3-Colorings

›
Following up on Bill's post earlier this week on counting the number of 3-colorings, Steven Noble emailed us with some updated informa...
Sunday, June 26, 2022

Counting the Number of 3-colorings of a graph is Sharp-P complete. This should be better known.

›
(ADDED LATER- Lance and I were emailed more information on the topic of this post, and that was made into a post by Lance which is  here .) ...
1 comment:
Sunday, June 19, 2022

Guest post by Prahalad Rajkumar: advice for grad students

›
I suspect that Lance and/or I have had blogs giving advice to grad students. I won't point to any particular posts since that's a ha...
Sunday, June 12, 2022

I am surprised that the Shortest Vector Problem is not known to be NP-hard, but perhaps I am wrong

›
A lattice L in R^n is a discrete subgroup of R^n.  Let p IN [1,infinty) The p-norm of a vector x=(x_1,...,x_n) IN R^n is                   ...
5 comments:
Saturday, June 04, 2022

Does the Social Media Law in Texas affect theory bloggers?

›
A new law in Texas states that any social media sites that has at least 50 million subscribers a month cannot ban anyone (its more nuanced t...
7 comments:
Monday, May 30, 2022

Discussions I wish we were having

›
1) Democrats think the best way to avoid school shootings (and other problems with guns) is to have regulations on Guns. They have proposed ...
4 comments:
Sunday, May 22, 2022

In the 1960's students protested the Vietnam war!/In 1830 students protested... Math?

›
 I was at SUNY Stonybrook for college 1976-1980.  I remember one student protest about a change to the calendar that (I think) would have us...
1 comment:
Sunday, May 15, 2022

Is Kamala Harris our first female PREZ? No. Do I have a theorem named after me. No. But in both cases...

›
On Nov 19, 2021 Joe Biden got a colonoscopy and hence the 25th amendment was used to make Kamala Harris the president temporarily (this sour...
2 comments:
›
Home
View web version
Powered by Blogger.